Consideriamo il seguente problema. Ovvero abbiamo una matrice unitaria $U$ e un suo autovettore $\ket{u}$. Vogliamo stimare la fase $\varphi$ dell’autovalore associato, ovvero
$$U \ket{u} = e^{2\pi i\varphi} \ket{u}$$
In linea di massima preparare un autostato non è banale, vedremo alla fine una variante dell’algoritmo valida in generale. L’obbiettivo è stimare il valore di $\varphi$ a $n$ bit binari di precisione, ovvero
$$\varphi \approx 0.\varphi_1 \varphi_2 \varphi_3 \ldots \varphi_n = \sum_{k=1}^n \frac{\varphi_k}{2^k}$$
dove $\varphi_k = 0,1$. Per eseguire l’algoritmo a $n$ bit di precisione, avremo bisogno di $n$ qubit aggiuntivi (ancillari) rispetto allo spazio dove è definita $U$.
Come ipotesi supponiamo di saper implementare in maniera efficiente l’operazione $C U^k$, ovvero l’applicazione controllata della $k$-esima potenza di $U$. Ciò vuol dire in pratica che utilizzando un qubit ancillare abbiamo
\begin{align*}
CU^k \ket{0} \ket{v} &= \ket{0} \ket{v}\\
CU^k \ket{1} \ket{v} &= \ket{1} U^k\ket{v}
\end{align*}
ovvero controllando sul qubit ancillare, se è $1$ eseguiamo $U^k$ sul registro principale, altrimenti non facciamo nulla. Qui $\ket{v}$ è uno stato qualsiasi del registro principale. Ora notiamo che una potenza arbitraria $U^x$ dove $x$ è un numero qualsiasi compreso tra $0$ e $2^n$ può essere ottenuta nel modo seguente. Scrivendo $x$ nella sua espansione binaria, abbiamo
$$x = x_0 + x_1 2^1 + x_2 2^2 + \cdots + x_{n-1} 2^{n-1} $$
dove $x_i = 0,1$. Perciò abbiamo
$$U^x = U^{\sum_{i=0}^{n-1} x_i 2^i} = \prod_{i=0}^{n-1} U^{x_i 2^i}$$
Ora l’operatore $U^{x_i 2^i}$ è l’identità se $x_i=0$ e invece è uguale a $U^{2^i}$ se $x_i=1$. Capite adesso la connessione con la porta $CU^k$. Uno stato generico del registro ancillare è della forma
$$\ket{x} \equiv \ket{x_0 x_1 x_2 \cdots x_n}$$
Abbiamo visto questa descrizione molte volte negli articoli passati sull’informatica quantistica. Ciò vuol dire che possiamo applicare $U^x$ al registro principale applicando $CU^{2^i}$ al qubit ancillare $i$. Ovvero definiamo
$$C \widetilde{U} \equiv \prod_{i=0}^{n-1} CU^{2^i} \lvert_i $$
dove la barra verticale indica su quale qubit ancillare controlliamo. Abbiamo quindi
$$C\widetilde{U} \ket{x} \ket{v} =\prod_{i=0}^{n-1} CU^{2^i} \lvert_i \ket{x} \ket{v} = \ket{x} \prod_{i=0}^{n-1} U^{x_i 2^i} \ket{v} = \ket{x} U^x \ket{v}$$
Ora procediamo alla descrizione dell’algoritmo vero e proprio. Come al solito procediamo a creare lo stato dato dalla sovrapposizione di tutte le stringhe binarie nel registro ancillare. Ovvero partendo dallo stato $\ket{0}$ in ognuno dei qubit ancillari e applicando $H^{\otimes n}$ (ovvero $n$ porte di Hadamard) sappiamo che otteremo la sovrapposizione su tutti gli stati base del registro ancillare nella base computazionale:
$$\frac{1}{\sqrt{2^n}} \sum_{x} \ket{x} $$
dove $\ket{x}$ è l’abbreviazione che abbiamo mostrato prima e usiamo $x$ sia come numero sia come etichetta per la sua decomposizione binaria. Ora dato l’autostato $\ket{u}$ di $U$ abbiamo
$$C \widetilde{U} \pqty{\frac{1}{\sqrt{2^n}} \sum_{x} \ket{x}}\ket{u} =\frac{1}{\sqrt{2^n}} \sum_{x} C \widetilde{U} \ket{x} \ket{u} = \frac{1}{\sqrt{2^n}} \sum_{x} \ket{x} U^x\ket{u} =\frac{1}{\sqrt{2^n}} \sum_{x} \ket{x} e^{2\pi i x \varphi}\ket{u}$$
dove abbiamo utilizzato il fatto che $\ket{u}$ è un autovettore di $U$. A questo punto $\ket{u}$ non è più aggrovigliato col resto e possiamo ignorarlo. Il registro ancillare si troverà quindi nello stato
$$\ket{\psi} \equiv \frac{1}{\sqrt{2^n}} \sum_{x} e^{2\pi i x \varphi} \ket{x} $$
Che cos’è questo stato? Molto concretamente è lo stato seguente: avendo applicato la porta $CU^{2^i}$ all’$i$-esimo qubit ancillare, l’$i$-esimo qubit si troverà nello stato
$$\frac{1}{\sqrt{2}}\pqty{\ket{0} + e^{2\pi i 2^{i} \varphi} \ket{1}} $$
e $\ket{\psi}$ è il prodotto tensoriale di tutti questi stati per ogni $i$. Vediamo come ci sia utile questo fatto: se riuscissimo a recuperare l’argomento dell’esponenziale, otterremmo $2^i \varphi$ per $0 \leq i \leq n-1$, che, vedendo la forma iniziale di $i$, è sufficiente per ricostruire $\varphi$ fino all’$n$-esima cifra binaria.
Come abbiamo visto già diverse volte, spostare informazione dall’esponente allo stato (che poi può essere misurato) si può fare utilizzando la trasformata di Fourier quantistica, di cui abbiamo parlato in un precedente articolo. Su uno stato base abbiamo
$$\mathcal{F} \ket{x} = \frac{1}{\sqrt{2^n}}\sum_{x=0}^{2^{n}-1} e^{-2\pi i \frac{xy}{2^n}} \ket{y}$$
dove $y$ è un’altra etichetta dello stesso tipo di $x$, ovvero un numero tra $0$ e $2^{n-1}$. Ora supponiamo che $\varphi$ abbia esattamente $n$ bit di precisione, ovvero esiste un intero $z$ tale che $\varphi = z/2^n$. Allora notiamo che
$$\ket{\psi} \equiv \frac{1}{\sqrt{2^n}} \sum_{x} e^{2\pi i x z /2^n} \ket{x}$$
Confrontando con la formula per la trasformata di Fourier, notiamo che $\ket{\psi}$ è precisamente la trasformata inversa di Fourier applicata allo stato computazionale $\ket{z}$. In questo caso possiamo quindi scrivere
$$\ket{z} = \mathcal{F}^{-1} \ket{\psi}$$
Confrontando con l’espansione iniziale di $\varphi$, abbiamo
$$z = 2^n \varphi = \sum_{k=1}^n \varphi_k 2^{n-k} = \sum_{k=0}^{n-1} \varphi_{n-k} 2^k$$
E quindi lo stato $z$ è dato da
$$\ket{z} = \ket{\varphi_n \varphi_{n-1} \cdots \varphi_2 \varphi_1}$$
Perciò misurando il $k$-esimo qubit ancillare otteniamo con certezza $\varphi_{n-k}$, e quindi abbiamo ricostruito $\varphi$.
Nel caso in cui invece $\varphi$ è solo approssimativamente dato da $n$ bit di precisione, allora effettuando l’algoritmo otterremo un numero $\varphi’$ che non è necessariamente identico a $\varphi$. Tuttavia argomentazioni probabilistiche mostrano che la probabilità di ottenere il numero corretto con $n$ bit è alta. In particolare invece di utilizzare $n$ qubit ancillari, ne potremmo usare $n’ > n$ (dove $n$ è la precisione richiesta). Si può dimostrare quindi che la probabilità di ottenere i primi $n$ bit correttamente è almeno $1-\epsilon$ purché $n’ \gtrsim n + \log(1/\epsilon)$.
L’altro problema di questo algoritmo è che non è detto che abbiamo tra le mani un’autovettore $\ket{u}$ di $U$; in linea di massima un tale stato è difficile da preparare. Tuttavia supponiamo che $U$ ha degli autovettori $\ket{u}$ indicizzati da $u$. Allora un generico stato può essere scritto come
$$\ket{\phi} = \sum_{u} c_u \ket{u}$$
Possiamo applicare l’algoritmo esattamente come prima, e ripetendo i passaggi, prima della misurazione finale avremo lo stato
$$\sum_{u} c_u \ket{z_u} \ket{u_k}$$
dove $z_u$ è lo stato $z$ corrispondente alla fase $\varphi_u$ che corrisponde all’autovalore di $u$. Procediamo quindi come prima misurando il registro ancillare. Otterremo quindi uno $\ket{z_u}$ specifico a caso, con probabilità $\abs{c_u}^2$. Il registro principale collasserà quindi sullo stato $\ket{u}$ corrispondente all’autovalore $z_u$ (o su una sovrapposizione di tali stati, se sono degeneri o approssimativamente tali).