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 ${\displaystyle U}$e uno stato quantico ${\displaystyle |\psi \rangle }$tale che ${\displaystyle U|\psi \rangle =e^{2\pi i\theta }|\psi \rangle }$, l'algoritmo stima il valore di ${\displaystyle \theta }$con alta probabilità entro un errore ${\displaystyle \varepsilon }$, usando ${\displaystyle O(\log(1/\varepsilon ))}$qubit (senza contare quelli usati per codificare lo stato dell'autovettore) e ${\displaystyle 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.

Sia U un operatore unitario che agisce su m qubit con un autovettore ${\displaystyle |\psi \rangle ,}$tale che ${\displaystyle U|\psi \rangle =e^{2\pi i\theta }\left|\psi \right\rangle ,0\leq \theta <1}$.

Bisogna trovare l'autovalore ${\displaystyle e^{2\pi i\theta }}$di ${\displaystyle |\psi \rangle }$, che in questo caso è equivalente a stimare la fase ${\displaystyle \theta }$, a un livello finito di precisione. Si può scrivere l'autovalore nella forma ${\displaystyle 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'input consiste di due registri (due parti): gli ${\displaystyle n}$qubit superiori costituiscono il primo registro, e gli ${\displaystyle m}$qubit inferiori costituiscono il secondo registro.

Lo stato iniziale del sistema è:

${\displaystyle |0\rangle ^{\otimes n}|\psi \rangle .}$

Dopo aver applicato la porta di Hadamard a n bit ${\displaystyle H^{\otimes n}}$sul primo registro, lo stato diventa

${\displaystyle {\frac {1}{2^{\frac {n}{2}}}}(|0\rangle +|1\rangle )^{\otimes n}|\psi \rangle }$.

Sia ${\displaystyle U}$un operatore unitario con autovettore ${\displaystyle |\psi \rangle }$tale che ${\displaystyle U|\psi \rangle =e^{2\pi i\theta }|\psi \rangle ,}$perciò

${\displaystyle 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 }$.

${\displaystyle C-U}$è una porta U controllata che applica l'operatore ${\displaystyle U}$sul secondo registro se e solo se il suo bit di controllo corrispondente (del primo registro) è ${\displaystyle |1\rangle }$.

Assumendo per semplicità che le porte controllate siano applicate sequenzialmente, dopo aver applicato ${\displaystyle C-U^{2^{0}}}$all' ${\displaystyle n}$-esimo qubit del primo registro e al secondo registro, lo stato diventa

${\displaystyle {\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}}}$${\displaystyle ={\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:

${\displaystyle |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 ${\displaystyle n-1}$operazioni controllate ${\displaystyle C-U^{2^{j}}}$con ${\displaystyle 1\leq j\leq n-1,}$come visto in figura, lo stato del primo registro può essere descritto come

${\displaystyle {\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 ${\displaystyle |k\rangle }$denota la rappresentazione binaria di ${\displaystyle k}$, cioè la ${\displaystyle k}$-esima base computazionale, e lo stato del secondo registro è lasciato invariato in ${\displaystyle |\psi \rangle }$.

Applicare la trasformata di Fourier quantistica inversa su

${\displaystyle {\frac {1}{2^{\frac {n}{2}}}}\sum _{k=0}^{2^{n}-1}e^{2\pi i\theta k}|k\rangle }$

porta a

${\displaystyle {\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 è

${\displaystyle {\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 ${\displaystyle \theta \in [0,1]}$arrotondando ${\displaystyle 2^{n}\theta }$all'intero più vicino. Ciò significa che ${\displaystyle 2^{n}\theta =a+2^{n}\delta ,}$dove ${\displaystyle a}$è l'intero più vicino a ${\displaystyle 2^{n}\theta ,}$e la differenza ${\displaystyle 2^{n}\delta }$soddisfa ${\displaystyle 0\leqslant |2^{n}\delta |\leqslant {\tfrac {1}{2}}}$.

Possiamo ora scrivere lo stato del primo e del secondo registro nel modo seguente:

${\displaystyle {\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 .}$

Effettuando una misura nella base computazionale sul primo registro dà il risultato ${\displaystyle |a\rangle }$con probabilità

${\displaystyle \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 ${\displaystyle \delta =0}$l'approssimazione è precisa, perciò ${\displaystyle a=2^{n}\theta }$e ${\displaystyle \Pr(a)=1.}$In questo caso, si può sempre misurare il valore preciso della fase. Lo stato del sistema dopo la misura è ${\displaystyle |2^{n}\theta \rangle \otimes |\psi \rangle }$.

Per ${\displaystyle \delta \neq 0}$siccome ${\displaystyle |\delta |\leqslant {\tfrac {1}{2^{n+1}}}}$l'algoritmo produce il risultato corretto con probabilità ${\displaystyle \Pr(a)\geqslant {\frac {4}{\pi ^{2}}}\approx 0.405}$. Si dimostra questo come segue:

${\displaystyle {\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 ${\displaystyle \theta }$con alta probabilità. Incrementando il numero di qubit di ${\displaystyle O(\log(1/\epsilon ))}$e ignorando quegli ultimi qubit si può incrementare la probabilità a ${\displaystyle 1-\epsilon }$.

• Algoritmo di fattorizzazione di Shor

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

Portale Informatica

Portale Matematica

Portale Quantistica