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

Circuito quantistico per la stima della fase

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$.

Voci correlate

• Algoritmo di fattorizzazione di Shor

Collegamenti esterni

• A. Yu. Kitaev, Quantum measurements and the Abelian Stabilizer Problem, su arxiv.org, 1995.