# Algoritmo quantistico di stima della fase

L'algoritmo quantistico di stima della fase (in inglese: quantum phase estimation algorithm), è un algoritmo quantistico per la stima della fase (o di un autovalore) di un autovettore di un operatore unitario. Più precisamente, data una matrice unitaria $U$ e uno stato quantico $|\psi \rangle$ tale che $U|\psi \rangle =e^{2\pi i\theta }|\psi \rangle$, l'algoritmo stima il valore di $\theta$ con alta probabilità entro un errore $\varepsilon$, usando $O(\log(1/\varepsilon ))$ qubit (senza contare quelli usati per codificare lo stato dell'autovettore) e $O(1/\varepsilon )$ operazioni U controllate.
La stima della fase è usata frequentemente come subroutine in altri algoritmi quantistici, come l'algoritmo di Shor e l'algoritmo quantistico per sistemi di equazioni lineari.

## Il problema

Sia U un operatore unitario che agisce su m qubit con un autovettore $|\psi \rangle ,$ tale che $U|\psi \rangle =e^{2\pi i\theta }\left|\psi \right\rangle ,0\leq \theta <1$.
Bisogna trovare l'autovalore $e^{2\pi i\theta }$di $|\psi \rangle$, che in questo caso è equivalente a stimare la fase $\theta$, a un livello finito di precisione. Si può scrivere l'autovalore nella forma $e^{2\pi i\theta }$ perché U è un operatore unitario su uno spazio vettoriale complesso, così gli autovalori devono essere numeri complessi con valore assoluto 1.

## L'algoritmo
### Impostazione

L'input consiste di due registri (due parti): gli $n$ qubit superiori costituiscono il primo registro, e gli $m$ qubit inferiori costituiscono il secondo registro.

### Sovrapposizione

Lo stato iniziale del sistema è:
    $|0\rangle ^{\otimes n}|\psi \rangle .$
Dopo aver applicato la porta di Hadamard a n bit $H^{\otimes n}$ sul primo registro, lo stato diventa
    ${\frac {1}{2^{\frac {n}{2}}}}(|0\rangle +|1\rangle )^{\otimes n}|\psi \rangle$.

### Operazioni unitarie controllate

Sia $U$ un operatore unitario con autovettore $|\psi \rangle$ tale che $U|\psi \rangle =e^{2\pi i\theta }|\psi \rangle ,$ perciò
    $U^{2^{j}}|\psi \rangle =U^{2^{j}-1}U|\psi \rangle =U^{2^{j}-1}e^{2\pi i\theta }|\psi \rangle =\cdots =e^{2\pi i2^{j}\theta }|\psi \rangle$.
$C-U$ è una porta U controllata che applica l'operatore $U$ sul secondo registro se e solo se il suo bit di controllo corrispondente (del primo registro) è $|1\rangle$.
Assumendo per semplicità che le porte controllate siano applicate sequenzialmente, dopo aver applicato $C-U^{2^{0}}$all' $n$-esimo qubit del primo registro e al secondo registro, lo stato diventa
    ${\frac {1}{2^{\frac {1}{2}}}}\underbrace {\left(|0\rangle |\psi \rangle +|1\rangle e^{2\pi i2^{0}\theta }|\psi \rangle \right)} _{\text{n-esimo qubit e secondo registro}}\otimes {\frac {1}{2^{\frac {n-1}{2}}}}\underbrace {\left(|0\rangle +|1\rangle \right)^{\otimes ^{n-1}}} _{{\text{qubit dal primo al }}(n-1){\text{-esimo}}}={\frac {1}{2^{\frac {1}{2}}}}\left(|0\rangle |\psi \rangle +e^{2\pi i2^{0}\theta }|1\rangle |\psi \rangle \right)\otimes {\frac {1}{2^{\frac {n-1}{2}}}}\left(|0\rangle +|1\rangle \right)^{\otimes ^{n-1}}$$={\frac {1}{2^{\frac {1}{2}}}}\left(|0\rangle +e^{2\pi i2^{0}\theta }|1\rangle \right)|\psi \rangle \otimes {\frac {1}{2^{\frac {n-1}{2}}}}\left(|0\rangle +|1\rangle \right)^{\otimes ^{n-1}}={\frac {1}{2^{\frac {n}{2}}}}\underbrace {\left(|0\rangle +e^{2\pi i2^{0}\theta }|1\rangle \right)} _{n{\text{-esimo qubit}}}\otimes \left(|0\rangle +|1\rangle \right)^{\otimes ^{n-1}}|\psi \rangle ,$
dove si usa:
    $|0\rangle |\psi \rangle +|1\rangle \otimes e^{2\pi i2^{j}\theta }|\psi \rangle =(|0\rangle +e^{2\pi i2^{j}\theta }|1\rangle )|\psi \rangle ,\ \forall j.$
Dopo aver applicato tutte le restanti $n-1$ operazioni controllate $C-U^{2^{j}}$ con $1\leq j\leq n-1,$ come visto in figura, lo stato del primo registro può essere descritto come
    ${\frac {1}{2^{\frac {n}{2}}}}\underbrace {\left(|0\rangle +e^{2\pi i2^{n-1}\theta }|1\rangle \right)} _{\text{primo qubit}}\otimes \cdots \otimes \underbrace {\left(|0\rangle +e^{2\pi i2^{1}\theta }|1\rangle \right)} _{(n-1){\text{-esimo qubit}}}\otimes \underbrace {\left(|0\rangle +e^{2\pi i2^{0}\theta }|1\rangle \right)} _{n{\text{-esimo qubit}}}={\frac {1}{2^{\frac {n}{2}}}}\sum _{k=0}^{2^{n}-1}e^{2\pi i\theta k}|k\rangle ,$
dove $|k\rangle$ denota la rappresentazione binaria di $k$, cioè la $k$-esima base computazionale, e lo stato del secondo registro è lasciato invariato in $|\psi \rangle$.

### Applicare la trasformata di Fourier quantistica inversa

Applicare la trasformata di Fourier quantistica inversa su
    ${\frac {1}{2^{\frac {n}{2}}}}\sum _{k=0}^{2^{n}-1}e^{2\pi i\theta k}|k\rangle$
porta a
    ${\frac {1}{2^{\frac {n}{2}}}}\sum _{k=0}^{2^{n}-1}e^{2\pi i\theta k}{\frac {1}{2^{\frac {n}{2}}}}\sum _{x=0}^{2^{n}-1}e^{\frac {-2\pi ikx}{2^{n}}}|x\rangle ={\frac {1}{2^{n}}}\sum _{x=0}^{2^{n}-1}\sum _{k=0}^{2^{n}-1}e^{2\pi i\theta k}e^{\frac {-2\pi ikx}{2^{n}}}|x\rangle ={\frac {1}{2^{n}}}\sum _{x=0}^{2^{n}-1}\sum _{k=0}^{2^{n}-1}e^{-{\frac {2\pi ik}{2^{n}}}\left(x-2^{n}\theta \right)}|x\rangle .$
Lo stato complessivo dei due registri è
    ${\frac {1}{2^{n}}}\sum _{x=0}^{2^{n}-1}\sum _{k=0}^{2^{n}-1}e^{-{\frac {2\pi ik}{2^{n}}}\left(x-2^{n}\theta \right)}|x\rangle \otimes |\psi \rangle .$
Si può approssimare il valore di $\theta \in [0,1]$ arrotondando $2^{n}\theta$ all'intero più vicino. Ciò significa che $2^{n}\theta =a+2^{n}\delta ,$ dove $a$ è l'intero più vicino a $2^{n}\theta ,$ e la differenza $2^{n}\delta$ soddisfa $0\leqslant |2^{n}\delta |\leqslant {\tfrac {1}{2}}$.
Possiamo ora scrivere lo stato del primo e del secondo registro nel modo seguente:
    ${\frac {1}{2^{n}}}\sum _{x=0}^{2^{n}-1}\sum _{k=0}^{2^{n}-1}e^{-{\frac {2\pi ik}{2^{n}}}\left(x-a\right)}e^{2\pi i\delta k}|x\rangle \otimes |\psi \rangle .$

### Misura

Effettuando una misura nella base computazionale sul primo registro dà il risultato $|a\rangle$ con probabilità
    $\Pr(a)=\left|\left\langle a\underbrace {\left|{\frac {1}{2^{n}}}\sum _{x=0}^{2^{n}-1}\sum _{k=0}^{2^{n}-1}e^{{\frac {-2\pi ik}{2^{n}}}(x-a)}e^{2\pi i\delta k}\right|x} _{\text{Stato del primo registro}}\right\rangle \right|^{2}={\frac {1}{2^{2n}}}\left|\sum _{k=0}^{2^{n}-1}e^{2\pi i\delta k}\right|^{2}={\begin{cases}1&\delta =0\\&\\{\frac {1}{2^{2n}}}\left|{\frac {1-{e^{2\pi i2^{n}\delta }}}{1-{e^{2\pi i\delta }}}}\right|^{2}&\delta \neq 0\end{cases}}$
Per $\delta =0$ l'approssimazione è precisa, perciò $a=2^{n}\theta$ e $\Pr(a)=1.$ In questo caso, si può sempre misurare il valore preciso della fase. Lo stato del sistema dopo la misura è $|2^{n}\theta \rangle \otimes |\psi \rangle$.
Per $\delta \neq 0$ siccome $|\delta |\leqslant {\tfrac {1}{2^{n+1}}}$ l'algoritmo produce il risultato corretto con probabilità $\Pr(a)\geqslant {\frac {4}{\pi ^{2}}}\approx 0.405$. Si dimostra questo come segue:
    ${\begin{aligned}\Pr(a)&={\frac {1}{2^{2n}}}\left|{\frac {1-{e^{2\pi i2^{n}\delta }}}{1-{e^{2\pi i\delta }}}}\right|^{2}&&{\text{per }}\delta \neq 0\\[6pt]&={\frac {1}{2^{2n}}}\left|{\frac {2\sin \left(\pi 2^{n}\delta \right)}{2\sin(\pi \delta )}}\right|^{2}&&\left|1-e^{2ix}\right|^{2}=4\left|\sin(x)\right|^{2}\\[6pt]&={\frac {1}{2^{2n}}}{\frac {\left|\sin \left(\pi 2^{n}\delta \right)\right|^{2}}{|\sin(\pi \delta )|^{2}}}\\[6pt]&\geqslant {\frac {1}{2^{2n}}}{\frac {\left|\sin \left(\pi 2^{n}\delta \right)\right|^{2}}{|\pi \delta |^{2}}}&&|\sin(\pi \delta )|\leqslant |\pi \delta |{\text{ per }}|\delta |\leqslant {\frac {1}{2^{n+1}}}\\[6pt]&\geqslant {\frac {1}{2^{2n}}}{\frac {|2\cdot 2^{n}\delta |^{2}}{|\pi \delta |^{2}}}&&|2\cdot 2^{n}\delta |\leqslant |\sin(\pi 2^{n}\delta )|{\text{ per }}|\delta |\leqslant {\frac {1}{2^{n+1}}}\\[6pt]&\geqslant {\frac {4}{\pi ^{2}}}\end{aligned}}$
Questo risultato mostra che si misurerà la miglior stima di $\theta$ con alta probabilità. Incrementando il numero di qubit di $O(\log(1/\epsilon ))$ e ignorando quegli ultimi qubit si può incrementare la probabilità a $1-\epsilon$.