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 e uno stato quantico tale che , l'algoritmo stima il valore di con alta probabilità entro un errore , usando qubit (senza contare quelli usati per codificare lo stato dell'autovettore) e operazioni U controllate.
La stima della fase è usata frequentemente come subroutine in altri algoritmi quantistici, come l'algoritmo di Shor[1] e l'algoritmo quantistico per sistemi di equazioni lineari.
Bisogna trovare l'autovaloredi , che in questo caso è equivalente a stimare la fase , a un livello finito di precisione. Si può scrivere l'autovalore nella forma 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 qubit superiori costituiscono il primo registro, e gli qubit inferiori costituiscono il secondo registro.
Sovrapposizione
Lo stato iniziale del sistema è:
Dopo aver applicato la porta di Hadamard a n bit sul primo registro, lo stato diventa
.
Operazioni unitarie controllate
Sia un operatore unitario con autovettore tale che perciò
.
è una porta U controllata che applica l'operatore sul secondo registro se e solo se il suo bit di controllo corrispondente (del primo registro) è .
Assumendo per semplicità che le porte controllate siano applicate sequenzialmente, dopo aver applicato all' -esimo qubit del primo registro e al secondo registro, lo stato diventa
dove si usa:
Dopo aver applicato tutte le restanti operazioni controllate con come visto in figura, lo stato del primo registro può essere descritto come
dove denota la rappresentazione binaria di , cioè la -esima base computazionale, e lo stato del secondo registro è lasciato invariato in .
Applicare la trasformata di Fourier quantistica inversa
Si può approssimare il valore di arrotondando all'intero più vicino. Ciò significa che dove è l'intero più vicino a e la differenza soddisfa .
Possiamo ora scrivere lo stato del primo e del secondo registro nel modo seguente:
Misura
Effettuando una misura nella base computazionale sul primo registro dà il risultato con probabilità
Per l'approssimazione è precisa, perciò e In questo caso, si può sempre misurare il valore preciso della fase.[2][3] Lo stato del sistema dopo la misura è .[1]
Per siccome l'algoritmo produce il risultato corretto con probabilità . Si dimostra questo come segue:[2][3]
Questo risultato mostra che si misurerà la miglior stima di con alta probabilità. Incrementando il numero di qubit di e ignorando quegli ultimi qubit si può incrementare la probabilità a .[3]
Note
^ab Michael A. Nielsen e Isaac L. Chuang, Quantum computation and quantum information, ristampa, Cambridge, Cambridge Univ. Press, 2001, ISBN978-0521635035.
^ab Guiliano Benenti, Giulio Casati e Giuliano Strini, Principles of quantum computation and information, ristampa, New Jersey, World Scientific, 2004, ISBN978-9812388582.