Il problema della stima di fase

Questa sezione della lezione spiega il problema della stima di fase. Inizieremo con una breve discussione del teorema spettrale dell'algebra lineare, per poi passare all'enunciato del problema della stima di fase vero e proprio.

Teorema spettrale

Il teorema spettrale è un risultato importante dell'algebra lineare che afferma che le matrici di un certo tipo, chiamate matrici normali, possono essere espresse in modo semplice e utile. In questa lezione avremo bisogno di questo teorema solo per le matrici unitarie, ma più avanti nella serie lo applicheremo anche alle matrici hermitiane.

Matrici normali

Una matrice quadrata $M$ con elementi nel campo dei numeri complessi è detta matrice normale se commuta con la sua trasposta coniugata: $M M^{\dagger} = M^{\dagger} M.$

Ogni matrice unitaria $U$ è normale perché

$$U U^{\dagger} = \mathbb{I} = U^{\dagger} U.$$

Le matrici hermitiane, cioè le matrici uguali alla propria trasposta coniugata, sono un'altra classe importante di matrici normali. Se $H$ è una matrice hermitiana, allora

$$H H^{\dagger} = H^2 = H^{\dagger} H,$$

quindi $H$ è normale.

Non ogni matrice quadrata è normale. Per esempio, questa matrice non è normale:

$$\begin{pmatrix} 0 & 1\\ 0 & 0 \end{pmatrix}$$

(Questo è un esempio semplice ma ottimo di una matrice che spesso risulta molto utile da considerare.) Non è normale perché

$$\begin{pmatrix} 0 & 1\\ 0 & 0 \end{pmatrix} \begin{pmatrix} 0 & 1\\ 0 & 0 \end{pmatrix}^{\dagger} = \begin{pmatrix} 0 & 1\\ 0 & 0 \end{pmatrix} \begin{pmatrix} 0 & 0\\ 1 & 0 \end{pmatrix} = \begin{pmatrix} 1 & 0\\ 0 & 0 \end{pmatrix}$$

mentre

$$\begin{pmatrix} 0 & 1\\ 0 & 0 \end{pmatrix}^{\dagger} \begin{pmatrix} 0 & 1\\ 0 & 0 \end{pmatrix} = \begin{pmatrix} 0 & 0\\ 1 & 0 \end{pmatrix} \begin{pmatrix} 0 & 1\\ 0 & 0 \end{pmatrix} = \begin{pmatrix} 0 & 0\\ 0 & 1 \end{pmatrix}.$$

Enunciato del teorema

Ecco un enunciato del teorema spettrale.

Teorema

Teorema spettrale: sia $M$ una matrice complessa normale di dimensione $N\times N$. Esiste una base ortonormale di vettori complessi $N$-dimensionali $\bigl\{ \vert\psi_1\rangle,\ldots,\vert\psi_N\rangle \bigr\}$ insieme a numeri complessi $\lambda_1,\ldots,\lambda_N$ tali che

$$M = \lambda_1 \vert \psi_1\rangle\langle \psi_1\vert + \cdots + \lambda_N \vert \psi_N\rangle\langle \psi_N\vert.$$

L'espressione di una matrice nella forma

$$M = \sum_{k = 1}^N \lambda_k \vert \psi_k\rangle\langle \psi_k\vert \tag{1}$$

è comunemente chiamata decomposizione spettrale. Nota che se $M$ è una matrice normale espressa nella forma $(1),$ allora l'equazione

$$M \vert \psi_j \rangle = \lambda_j \vert \psi_j \rangle$$

deve essere vera per ogni $j = 1,\ldots,N.$ Ciò è conseguenza del fatto che $\bigl\{ \vert\psi_1\rangle,\ldots,\vert\psi_N\rangle \bigr\}$ è ortonormale:

$$M \vert \psi_j \rangle = \left(\sum_{k = 1}^N \lambda_k \vert \psi_k\rangle\langle \psi_k\vert\right)\vert \psi_j\rangle = \sum_{k = 1}^N \lambda_k \vert \psi_k\rangle\langle \psi_k\vert\psi_j \rangle = \lambda_j \vert\psi_j \rangle$$

Cioè, ogni numero $\lambda_j$ è un autovalore di $M$ e $\vert\psi_j\rangle$ è un autovettore corrispondente a quell'autovalore.

• Esempio 1. Sia

  $$\mathbb{I} = \begin{pmatrix}1 & 0\\0 & 1\end{pmatrix},$$

  che è normale. Il teorema implica che $\mathbb{I}$ può essere scritto nella forma $(1)$ per qualche scelta di $\lambda_1,$ $\lambda_2,$ $\vert\psi_1\rangle,$ e $\vert\psi_2\rangle.$ Ci sono più scelte che funzionano, tra cui

  $$\lambda_1 = 1, \hspace{5pt} \lambda_2 = 1, \hspace{5pt} \vert\psi_1\rangle = \vert 0\rangle, \hspace{5pt} \vert\psi_2\rangle = \vert 1\rangle.$$

  Nota che il teorema non dice che i numeri complessi $\lambda_1,\ldots,\lambda_N$ siano distinti — lo stesso numero complesso può ripetersi, il che è necessario per questo esempio. Queste scelte funzionano perché

  $$\mathbb{I} = \vert 0\rangle\langle 0\vert + \vert 1\rangle\langle 1\vert.$$

  In effetti, potremmo scegliere $\{\vert\psi_1\rangle,\vert\psi_2\rangle\}$ come qualsiasi base ortonormale e l'equazione sarà vera. Per esempio,

  $$\mathbb{I} = \vert +\rangle\langle +\vert + \vert -\rangle\langle -\vert.$$

• Esempio 2. Considera un'operazione di Hadamard.

  $$H = \frac{1}{\sqrt{2}} \begin{pmatrix} 1 & 1\\[1mm] 1 & -1 \end{pmatrix}$$

  Questa è una matrice unitaria, quindi è normale. Il teorema spettrale implica che $H$ può essere scritto nella forma $(1),$ e in particolare abbiamo

  $$H = \vert\psi_{\pi/8}\rangle \langle \psi_{\pi/8}\vert - \vert\psi_{5\pi/8}\rangle \langle \psi_{5\pi/8}\vert$$

  dove

  $$\vert\psi_{\theta}\rangle = \cos(\theta)\vert 0\rangle + \sin(\theta) \vert 1\rangle.$$

  Più esplicitamente,

  $$\begin{aligned} \vert\psi_{\pi/8}\rangle & = \frac{\sqrt{2 + \sqrt{2}}}{2}\vert 0\rangle + \frac{\sqrt{2 - \sqrt{2}}}{2}\vert 1\rangle, \\[3mm] \vert\psi_{5\pi/8}\rangle & = -\frac{\sqrt{2 - \sqrt{2}}}{2}\vert 0\rangle + \frac{\sqrt{2 + \sqrt{2}}}{2}\vert 1\rangle. \end{aligned}$$

  Possiamo verificare che questa decomposizione è corretta eseguendo i calcoli richiesti:

  $$\vert\psi_{\pi/8}\rangle \langle \psi_{\pi/8}\vert - \vert\psi_{5\pi/8}\rangle \langle \psi_{5\pi/8}\vert = \begin{pmatrix} \frac{2 + \sqrt{2}}{4} & \frac{\sqrt{2}}{4}\\[2mm] \frac{\sqrt{2}}{4} & \frac{2 - \sqrt{2}}{4} \end{pmatrix} - \begin{pmatrix} \frac{2 - \sqrt{2}}{4} & -\frac{\sqrt{2}}{4}\\[2mm] -\frac{\sqrt{2}}{4} & \frac{2 + \sqrt{2}}{4} \end{pmatrix} = H.$$

Come rivela il primo esempio, può esserci una certa libertà nella scelta degli autovettori. Non c'è, invece, alcuna libertà nella scelta degli autovalori, a parte il loro ordinamento: gli stessi $N$ numeri complessi $\lambda_1,\ldots,\lambda_N,$ che possono includere ripetizioni dello stesso numero complesso, compariranno sempre nell'equazione $(1)$ per una data matrice $M.$

Concentriamoci ora sulle matrici unitarie. Supponiamo di avere un numero complesso $\lambda$ e un vettore non nullo $\vert\psi\rangle$ che soddisfano l'equazione

$$U\vert\psi\rangle = \lambda\vert\psi\rangle. \tag{2}$$

Cioè, $\lambda$ è un autovalore di $U$ e $\vert\psi\rangle$ è un autovettore corrispondente a questo autovalore.

Le matrici unitarie preservano la norma euclidea, e da $(2)$ concludiamo quanto segue.

$$\bigl\| \vert\psi\rangle \bigr\| = \bigl\| U \vert\psi\rangle \bigr\| = \bigl\| \lambda \vert\psi\rangle \bigr\| = \vert \lambda \vert \bigl\| \vert\psi\rangle \bigr\|$$

La condizione che $\vert\psi\rangle$ sia non nullo implica che $\bigl\| \vert\psi\rangle \bigr\|\neq 0,$ quindi possiamo semplificarlo da entrambi i lati per ottenere

$$\vert \lambda \vert = 1.$$

Questo rivela che gli autovalori delle matrici unitarie devono sempre avere valore assoluto uguale a uno, quindi giacciono sul cerchio unitario.

$$\mathbb{T} = \{\alpha\in\mathbb{C} : \vert\alpha\vert = 1\}$$

(Il simbolo $\mathbb{T}$ è un nome comune per il cerchio unitario complesso. Anche il nome $S^1$ è comune.)

Enunciato del problema della stima di fase

Nel problema della stima di fase, ci viene dato uno stato quantistico $\vert \psi\rangle$ di $n$ qubit, insieme a un circuito quantistico unitario che agisce su $n$ qubit. Ci viene promesso che $\vert \psi\rangle$ è un autovettore della matrice unitaria $U$ che descrive l'azione del circuito, e il nostro obiettivo è calcolare o approssimare l'autovalore $\lambda$ a cui $\vert \psi\rangle$ corrisponde. Più precisamente, poiché $\lambda$ giace sul cerchio unitario complesso, possiamo scrivere

$$\lambda = e^{2\pi i \theta}$$

per un unico numero reale $\theta$ che soddisfa $0\leq\theta<1.$ L'obiettivo del problema è calcolare o approssimare questo numero reale $\theta.$

Problema della stima di fase

Input: un circuito quantistico unitario per un'operazione $U$ su $n$ qubit insieme a uno stato quantistico $\vert\psi\rangle$ di $n$ qubit
Promessa: $\vert\psi\rangle$ è un autovettore di $U$
Output: un'approssimazione del numero $\theta\in[0,1)$ che soddisfa $U\vert\psi\rangle = e^{2\pi i \theta}\vert\psi\rangle$

Ecco alcune osservazioni su questo enunciato del problema:

1. Il problema della stima di fase differisce dagli altri problemi visti finora nel corso perché l'input include uno stato quantistico. Di solito ci concentriamo su problemi con input e output classici, ma nulla ci impedisce di considerare input come stati quantistici. Dal punto di vista della sua rilevanza pratica, il problema della stima di fase si incontra tipicamente come sottoproblema all'interno di un calcolo più ampio, come vedremo nel contesto della fattorizzazione di interi più avanti nella lezione.

2. L'enunciato del problema della stima di fase qui sopra non specifica cosa costituisca un'approssimazione di $\theta,$ ma possiamo formulare enunciati più precisi a seconda delle nostre esigenze e interessi. Nel contesto della fattorizzazione di interi richiederemo un'approssimazione molto precisa di $\theta,$ ma in altri casi potremmo accontentarci di un'approssimazione molto grossolana. Discuteremo a breve come la precisione richiesta influenzi il costo computazionale di una soluzione.

3. Nota che, passando da $\theta = 0$ verso $\theta = 1$ nel problema della stima di fase, percorriamo tutto il cerchio unitario, partendo da $e^{2\pi i \cdot 0} = 1$ e procedendo in senso antiorario verso $e^{2\pi i \cdot 1} = 1.$ Cioè, quando raggiungiamo $\theta = 1$ siamo tornati al punto di partenza $\theta = 0.$ Quindi, quando consideriamo la precisione delle approssimazioni, i valori di $\theta$ vicini a $1$ devono essere considerati vicini a $0.$ Per esempio, un'approssimazione $\theta = 0.999$ dovrebbe essere considerata a una distanza di $1/1000$ da $\theta = 0.$