Procedura di stima della fase

In questa sezione discutiamo la procedura di stima della fase, ovvero un algoritmo quantistico per risolvere il problema della stima della fase.

Inizieremo con un "riscaldamento" a bassa precisione, che illustra l'intuizione di base del metodo. Parleremo poi della trasformata di Fourier quantistica, un'importante operazione quantistica impiegata nella procedura di stima della fase, e della sua implementazione tramite circuiti quantistici. Una volta acquisita la trasformata di Fourier quantistica, descriveremo la procedura di stima della fase nella sua generalità e ne analizzeremo le prestazioni.

Riscaldamento: approssimare le fasi con bassa precisione

Iniziamo con alcune versioni semplificate della procedura di stima della fase, che forniscono soluzioni a bassa precisione al problema della stima della fase. Questo è utile per spiegare l'intuizione alla base della procedura generale che vedremo più avanti nella lezione.

Usare il phase kickback

Un approccio semplice al problema della stima della fase, che ci permette di ricavare qualche informazione sul valore $\theta$ cercato, si basa sul fenomeno del phase kick-back. Come vedremo, si tratta essenzialmente di una versione a singolo qubit della procedura generale di stima della fase discussa più avanti nella lezione.

Come parte dell'input al problema di stima della fase, abbiamo un circuito quantistico unitario per l'operazione $U$. Possiamo usare la descrizione di questo circuito per creare un circuito per un'operazione controlled-$U$, che può essere rappresentata come suggerisce la seguente figura (con l'operazione $U$, vista come gate quantistico, a sinistra e un'operazione controlled-$U$ a destra).

Possiamo creare un circuito quantistico per un'operazione controlled-$U$ aggiungendo prima un qubit di controllo al circuito per $U$, e poi sostituendo ogni gate nel circuito per $U$ con una versione controllata di quel gate — quindi il nostro unico nuovo qubit di controllo controlla effettivamente ogni singolo gate nel circuito per $U$. Questo richiede che disponiamo di una versione controllata di ogni gate nel nostro circuito, ma possiamo sempre costruire circuiti per queste operazioni controllate nel caso in cui non siano incluse nel nostro insieme di gate.

Consideriamo ora il seguente circuito, in cui lo stato di input $\vert\psi\rangle$ di tutti i qubit tranne quello superiore è un autovettore di $U$.

Le probabilità dei risultati di misura per questo circuito dipendono dall'autovalore di $U$ corrispondente all'autovettore $\vert\psi\rangle$. Analizziamo il circuito in dettaglio per determinare esattamente come.

Lo stato iniziale del circuito è

$$\vert\pi_0\rangle = \vert\psi\rangle \vert 0\rangle$$

e il primo gate di Hadamard trasforma questo stato in

$$\vert\pi_1\rangle = \vert\psi\rangle \vert +\rangle = \frac{1}{\sqrt{2}} \vert\psi\rangle \vert 0\rangle + \frac{1}{\sqrt{2}} \vert\psi\rangle \vert 1\rangle.$$

Successivamente viene eseguita l'operazione controlled-$U$, che produce lo stato

$$\vert\pi_2\rangle = \frac{1}{\sqrt{2}} \vert\psi\rangle \vert 0\rangle + \frac{1}{\sqrt{2}} \bigl(U \vert\psi\rangle\bigr) \vert 1\rangle.$$

Utilizzando l'ipotesi che $\vert\psi\rangle$ sia un autovettore di $U$ con autovalore $\lambda = e^{2\pi i\theta}$, possiamo esprimere questo stato in alternativa come segue.

$$\vert\pi_2\rangle = \frac{1}{\sqrt{2}} \vert\psi\rangle \vert 0\rangle + \frac{e^{2\pi i \theta}}{\sqrt{2}} \vert\psi\rangle \vert 1\rangle = \vert\psi\rangle \otimes \left( \frac{1}{\sqrt{2}} \vert 0\rangle + \frac{e^{2\pi i \theta}}{\sqrt{2}} \vert 1\rangle\right)$$

Qui osserviamo il fenomeno del phase kickback. È leggermente diverso rispetto a quanto visto nell'algoritmo di Deutsch e nell'algoritmo di Deutsch-Jozsa perché non stiamo lavorando con un gate di query — ma l'idea è simile.

Infine, viene eseguito il secondo gate di Hadamard. Dopo una semplice semplificazione, otteniamo questa espressione per lo stato.

$$\vert\pi_3\rangle = \vert\psi\rangle \otimes \left( \frac{1+ e^{2\pi i \theta}}{2} \vert 0\rangle + \frac{1 - e^{2\pi i \theta}}{2} \vert 1\rangle\right)$$

La misura produce quindi i risultati $0$ e $1$ con queste probabilità:

$$\begin{aligned} p_0 &= \left\vert \frac{1+ e^{2\pi i \theta}}{2} \right\vert^2 = \cos^2(\pi\theta)\\[1mm] p_1 &= \left\vert \frac{1- e^{2\pi i \theta}}{2} \right\vert^2 = \sin^2(\pi\theta). \end{aligned}$$

Ecco un grafico delle probabilità per i due possibili risultati, $0$ e $1,$ in funzione di $\theta.$

Naturalmente, le due probabilità sommano sempre a $1$. Nota che quando $\theta = 0$, il risultato della misura è sempre $0$, e quando $\theta = 1/2$, il risultato della misura è sempre $1$. Quindi, sebbene il risultato della misura non riveli esattamente qual è $\theta$, ci fornisce alcune informazioni su di esso — e se ci fosse stato promesso che $\theta = 0$ oppure $\theta = 1/2$, potremmo capire dal circuito quale delle due è corretta senza errori.

In modo intuitivo, possiamo pensare al risultato della misura del circuito come a una stima di $\theta$ con "un bit di precisione." In altre parole, se scrivessimo $\theta$ in notazione binaria e lo arrotondassimo a un bit, avremmo un numero come questo:

$$0.a = \begin{cases} 0 & a = 0\\ \frac{1}{2} & a = 1. \end{cases}$$

Il risultato della misura può essere visto come una stima per il bit $a$. Quando $\theta$ non è né $0$ né $1/2$, c'è una probabilità non nulla che la stima sia errata — ma la probabilità di commettere un errore diventa sempre più piccola man mano che ci avviciniamo a $0$ o $1/2$.

È naturale chiedersi quale ruolo svolgano i due gate di Hadamard in questa procedura:

• Il primo gate di Hadamard porta il qubit di controllo in una sovrapposizione uniforme di $\vert 0\rangle$ e $\vert 1\rangle$, in modo che quando si verifica il phase kickback, esso avvenga per lo stato $\vert 1\rangle$ e non per lo stato $\vert 0\rangle$, creando una differenza di fase relativa che influenza i risultati della misura. Se non lo facessimo e il phase kickback producesse una fase globale, non avrebbe alcun effetto sulle probabilità di ottenere diversi risultati di misura.

• Il secondo gate di Hadamard ci permette di apprendere qualcosa sul numero $\theta$ attraverso il fenomeno dell'interferenza. Prima del secondo gate di Hadamard, lo stato del qubit superiore è

  $$\frac{1}{\sqrt{2}} \vert 0\rangle + \frac{e^{2\pi i \theta}}{\sqrt{2}} \vert 1\rangle,$$

  e se misurassimo questo stato, otterremmo $0$ e $1$ ciascuno con probabilità $1/2$, senza dirci nulla su $\theta$. Eseguendo il secondo gate di Hadamard, però, facciamo sì che il numero $\theta$ influenzi le probabilità di output.

Raddoppiare la fase

Il circuito sopra usa il fenomeno del phase kickback per approssimare $\theta$ con un singolo bit di precisione. Un bit di precisione potrebbe essere tutto ciò di cui abbiamo bisogno in alcune situazioni — ma per la fattorizzazione avremo bisogno di molta più precisione. Una domanda naturale è: come possiamo sapere di più su $\theta?$

Una cosa molto semplice che possiamo fare è sostituire l'operazione controlled-$U$ nel nostro circuito con due copie di questa operazione, come in questo circuito:

Due copie di un'operazione controlled-$U$ equivalgono a un'operazione controlled-$U^2$. Se $\vert\psi\rangle$ è un autovettore di $U$ con autovalore $\lambda = e^{2\pi i \theta}$, allora questo stato è anche un autovettore di $U^2$, questa volta con autovalore $\lambda^2 = e^{2\pi i (2\theta)}$.

Quindi, se eseguiamo questa versione del circuito, stiamo effettivamente eseguendo lo stesso calcolo di prima, tranne che il numero $\theta$ è sostituito da $2\theta$. Ecco un grafico che illustra le probabilità di output al variare di $\theta$ da $0$ a $1$.

Farlo può effettivamente fornirci alcune informazioni aggiuntive su $\theta$. Se la rappresentazione binaria di $\theta$ è

$$\theta = 0.a_1 a_2 a_3\cdots$$

allora raddoppiare $\theta$ sposta effettivamente il punto binario di una posizione a destra:

$$2\theta = a_1. a_2 a_3\cdots$$

E poiché stiamo equiparando $\theta = 1$ con $\theta = 0$ mentre ci muoviamo attorno al cerchio unitario, vediamo che il bit $a_1$ non ha influenza sulle nostre probabilità, e stiamo effettivamente ottenendo una stima per il secondo bit dopo il punto binario se arrotondiamo $\theta$ a due bit. Per esempio, se sapessimo in anticipo che $\theta$ è o $0$ o $1/4$, potremmo fidarci completamente del risultato della misura per dirci quale.

Non è immediatamente chiaro, però, come questa stima dovrebbe essere riconciliata con ciò che abbiamo appreso dal circuito originale (non raddoppiato) del phase kickback per fornirci le informazioni più accurate possibili su $\theta$. Quindi facciamo un passo indietro e consideriamo come procedere.

Stima della fase a due qubit

Piuttosto che considerare separatamente le due opzioni descritte sopra, combiniamole in un unico circuito come questo.

I gate di Hadamard dopo le operazioni controllate sono stati rimossi e qui non ci sono ancora misure. Aggiungeremo altro al circuito mentre consideriamo le nostre opzioni per imparare il più possibile su $\theta$.

Se eseguiamo questo circuito quando $\vert\psi\rangle$ è un autovettore di $U$, lo stato dei qubit inferiori rimarrà $\vert\psi\rangle$ per tutto il circuito, e le fasi saranno "kickate" nello stato dei due qubit superiori. Analizziamo attentamente il circuito, attraverso la figura seguente.

Possiamo scrivere lo stato $\vert\pi_1\rangle$ così:

$$\vert\pi_1\rangle = \vert \psi\rangle \otimes \frac{1}{2} \sum_{a_0 = 0}^1 \sum_{a_1 = 0}^1 \vert a_1 a_0 \rangle.$$

Quando viene eseguita la prima operazione controlled-$U$, l'autovalore $\lambda = e^{2\pi i\theta}$ viene trasferito nella fase quando $a_0$ (il qubit superiore) è uguale a $1$, ma non quando è $0$. Quindi possiamo esprimere lo stato risultante come segue:

$$\vert\pi_2\rangle = \vert\psi\rangle \otimes \frac{1}{2} \sum_{a_0=0}^1 \sum_{a_1=0}^1 e^{2 \pi i a_0 \theta} \vert a_1 a_0 \rangle.$$

Il secondo e il terzo gate controlled-$U$ fanno qualcosa di simile, ma per $a_1$ invece che per $a_0$, e con $\theta$ sostituito da $2\theta$. Possiamo esprimere lo stato risultante così:

$$\vert\pi_3\rangle = \vert\psi\rangle\otimes\frac{1}{2}\sum_{a_0 = 0}^1 \sum_{a_1 = 0}^1 e^{2\pi i (2 a_1 + a_0)\theta} \vert a_1 a_0 \rangle.$$

Se pensiamo alla stringa binaria $a_1 a_0$ come a un intero $x \in \{0,1,2,3\}$ in notazione binaria, cioè $x = 2 a_1 + a_0$, possiamo esprimere questo stato in modo alternativo come segue.

$$\vert\pi_3\rangle = \vert \psi\rangle \otimes \frac{1}{2} \sum_{x = 0}^3 e^{2\pi i x \theta} \vert x \rangle$$

Il nostro obiettivo è estrarre da questo stato quante più informazioni possibili su $\theta.$

A questo punto considereremo un caso speciale, in cui ci viene promesso che $\theta = \frac{y}{4}$ per qualche intero $y\in\{0,1,2,3\}$. In altre parole, abbiamo $\theta\in \{0, 1/4, 1/2, 3/4\}$, quindi possiamo esprimere questo numero esattamente in notazione binaria con due bit, come .$00$, .$01$, .$10$ o .$11$. In generale, $\theta$ potrebbe non essere uno di questi quattro valori, ma pensare a questo caso speciale ci aiuterà a capire come estrarre informazioni su $\theta$ nel modo più efficace.

Per prima cosa definiamo un vettore di stato a due qubit per ogni possibile valore $y \in \{0, 1, 2, 3\}$.

$$\vert \phi_y\rangle = \frac{1}{2} \sum_{x = 0}^3 e^{2\pi i x (\frac{y}{4})} \vert x \rangle = \frac{1}{2} \sum_{x = 0}^3 e^{2\pi i \frac{x y}{4}} \vert x \rangle$$

Dopo aver semplificato gli esponenziali, possiamo scrivere questi vettori come segue.

$$\begin{aligned} \vert\phi_0\rangle & = \frac{1}{2} \vert 0 \rangle + \frac{1}{2} \vert 1 \rangle + \frac{1}{2} \vert 2 \rangle + \frac{1}{2} \vert 3 \rangle \\[3mm] \vert\phi_1\rangle & = \frac{1}{2} \vert 0 \rangle + \frac{i}{2} \vert 1 \rangle - \frac{1}{2} \vert 2 \rangle - \frac{i}{2} \vert 3 \rangle \\[3mm] \vert\phi_2\rangle & = \frac{1}{2} \vert 0 \rangle - \frac{1}{2} \vert 1 \rangle + \frac{1}{2} \vert 2 \rangle - \frac{1}{2} \vert 3 \rangle \\[3mm] \vert\phi_3\rangle & = \frac{1}{2} \vert 0 \rangle - \frac{i}{2} \vert 1 \rangle - \frac{1}{2} \vert 2 \rangle + \frac{i}{2} \vert 3 \rangle \end{aligned}$$

Questi vettori sono ortogonali: scegliendo una qualsiasi coppia di essi e calcolando il loro prodotto interno, otteniamo $0$. Ognuno è anche un vettore unitario, quindi $\{\vert\phi_0\rangle, \vert\phi_1\rangle, \vert\phi_2\rangle, \vert\phi_3\rangle\}$ è una base ortonormale. Sappiamo quindi immediatamente che esiste una misura in grado di discriminarli perfettamente — ovvero che, se ci viene dato uno di essi ma non sappiamo quale, possiamo capire quale sia senza errori.

Per eseguire tale discriminazione con un circuito quantistico, possiamo prima definire un'operazione unitaria $V$ che trasforma gli stati della base standard nei quattro stati elencati sopra.

$$\begin{aligned} V \vert 00 \rangle & = \vert\phi_0\rangle \\ V \vert 01 \rangle & = \vert\phi_1\rangle \\ V \vert 10 \rangle & = \vert\phi_2\rangle \\ V \vert 11 \rangle & = \vert\phi_3\rangle \end{aligned}$$

Per scrivere $V$ come matrice $4\times 4$, è sufficiente prendere le colonne di $V$ come gli stati $\vert\phi_0\rangle,\ldots,\vert\phi_3\rangle$.

$$V = \frac{1}{2} \begin{pmatrix} 1 & 1 & 1 & 1\\[1mm] 1 & i & -1 & -i\\[1mm] 1 & -1 & 1 & -1\\[1mm] 1 & -i & -1 & i \end{pmatrix}$$

Questa è una matrice speciale, ed è probabile che alcuni lettori l'abbiano già incontrata: è la matrice associata alla trasformata discreta di Fourier in $4$ dimensioni. Alla luce di questo fatto, chiamiamola $\mathrm{QFT}_4$ invece di $V$. Il nome $\mathrm{QFT}$ è un'abbreviazione di quantum Fourier transform (trasformata di Fourier quantistica) — che è essenzialmente la trasformata discreta di Fourier, vista come operazione unitaria. Discuteremo la trasformata di Fourier quantistica in modo più dettagliato e generale a breve.

$$\mathrm{QFT}_4 = \frac{1}{2} \begin{pmatrix} 1 & 1 & 1 & 1\\[1mm] 1 & i & -1 & -i\\[1mm] 1 & -1 & 1 & -1\\[1mm] 1 & -i & -1 & i \end{pmatrix}$$

Possiamo eseguire l'inverso di questa operazione per andare nell'altra direzione, trasformando gli stati $\vert\phi_0\rangle,\ldots,\vert\phi_3\rangle$ negli stati della base standard $\vert 0\rangle,\ldots,\vert 3\rangle$. Se facciamo questo, possiamo misurare per capire quale valore $y\in\{0,1,2,3\}$ descrive $\theta$ come $\theta = y/4$. Ecco uno schema di un circuito quantistico che fa questo.

In sintesi, se eseguiamo questo circuito quando $\theta = y/4$ per $y\in\{0,1,2,3\}$, lo stato immediatamente prima che avvengano le misure sarà $\vert \psi\rangle \vert y\rangle$ (con $y$ codificato come stringa binaria a due bit), quindi le misure riveleranno il valore $y$ senza errori.

Questo circuito è motivato dal caso speciale $\theta \in \{0,1/4,1/2,3/4\}$ — ma possiamo eseguirlo per qualsiasi scelta di $U$ e $\vert \psi\rangle$, e quindi per qualsiasi valore di $\theta$, che desideriamo. Ecco un grafico delle probabilità di output che il circuito produce per scelte arbitrarie di $\theta$.

Questo è un netto miglioramento rispetto alla variante a singolo qubit descritta in precedenza nella lezione. Non è perfetto — può darci la risposta sbagliata — ma la risposta è fortemente orientata verso valori di $y$ per cui $y/4$ è vicino a $\theta$. In particolare, il risultato più probabile corrisponde sempre al valore di $y/4$ più vicino a $\theta$ (equiparando $\theta = 0$ e $\theta = 1$ come prima), e dal grafico sembra che questo valore più vicino per $x$ appaia sempre con probabilità appena superiore al $40\%$. Quando $\theta$ si trova esattamente a metà tra due tali valori, come $\theta = 0.375$ ad esempio, i due valori di $y$ ugualmente vicini hanno la stessa probabilità.

Prepararsi a generalizzare a molti qubit

Dato il miglioramento appena ottenuto usando due qubit di controllo invece di uno, insieme all'inverso della trasformata di Fourier quantistica a $4$ dimensioni, è naturale considerare di generalizzarlo ulteriormente — aggiungendo altri qubit di controllo. Quando facciamo questo, otteniamo la procedura di stima della fase generale. Vedremo come funziona a breve, ma per descriverla con precisione avremo bisogno di discutere la trasformata di Fourier quantistica in maggiore generalità, per vedere come è definita per altre dimensioni e come possiamo implementarla (o il suo inverso) con un circuito quantistico.

Trasformata di Fourier quantistica

La trasformata di Fourier quantistica è un'operazione unitaria che può essere definita per qualsiasi dimensione intera positiva $N$. In questa sezione vedremo come questa operazione è definita e come può essere implementata con un circuito quantistico su $m$ qubit con costo $O(m^2)$ quando $N = 2^m$.

Le matrici che descrivono la trasformata di Fourier quantistica derivano da un'analoga operazione su vettori $N$-dimensionali nota come trasformata discreta di Fourier. Questa operazione può essere concepita in modi diversi. Ad esempio, possiamo pensare alla trasformata discreta di Fourier in termini puramente astratti e matematici come una mappatura lineare. Oppure possiamo pensarla in termini computazionali, dove ci viene dato un vettore $N$-dimensionale di numeri complessi (utilizzando la notazione binaria per codificare le parti reale e immaginaria delle voci, per ipotesi) e l'obiettivo è calcolare il vettore $N$-dimensionale ottenuto applicando la trasformata discreta di Fourier. Il nostro focus sarà su un terzo modo, ovvero considerare questa trasformazione come un'operazione unitaria che può essere eseguita su un sistema quantistico.

Esiste un algoritmo efficiente per calcolare la trasformata discreta di Fourier su un dato vettore di input noto come trasformata veloce di Fourier. Ha applicazioni nell'elaborazione del segnale e in molte altre aree, ed è considerato da molti uno degli algoritmi più importanti mai scoperti. Come si vedrà, l'implementazione della trasformata di Fourier quantistica quando $N$ è una potenza di 2 che studieremo si basa esattamente sulla stessa struttura sottostante che rende possibile la trasformata veloce di Fourier.

Definizione della trasformata di Fourier quantistica

Per definire la trasformata di Fourier quantistica, definiremo prima un numero complesso $\omega_N$, per ogni intero positivo $N$, come segue:

$$\omega_N = e^{\frac{2\pi i}{N}} = \cos\left(\frac{2\pi}{N}\right) + i \sin\left(\frac{2\pi}{N}\right).$$

Questo è il numero sul cerchio unitario complesso che si ottiene partendo da $1$ e spostandosi in senso antiorario di un angolo di $2\pi/N$ radianti, ovvero una frazione di $1/N$ della circonferenza del cerchio. Ecco alcuni esempi:

$$\begin{gathered} \omega_1 = 1\\[1mm] \omega_2 = -1\\[1mm] \omega_3 = -\frac{1}{2} + \frac{\sqrt{3}}{2} i\\[2mm] \omega_4 = i\\[1mm] \omega_8 = \frac{1+i}{\sqrt{2}}\\[3mm] \omega_{16} = \frac{\sqrt{2 + \sqrt{2}}}{2} + \frac{\sqrt{2 - \sqrt{2}}}{2} i\\[2mm] \omega_{100} \approx 0.998 + 0.063 i \end{gathered}$$

Ora possiamo definire la trasformata di Fourier quantistica $N$-dimensionale, descritta da una matrice $N\times N$ le cui righe e colonne sono associate agli stati della base standard $\vert 0\rangle,\ldots,\vert N-1\rangle$. Avremo bisogno di questa operazione solo quando $N = 2^m$ è una potenza di $2$ per la stima della fase, ma l'operazione può essere definita per qualsiasi intero positivo $N$.

$$\mathrm{QFT}_N = \frac{1}{\sqrt{N}} \sum_{x = 0}^{N-1} \sum_{y = 0}^{N-1} \omega_N^{xy} \vert x \rangle\langle y\vert$$

Come già detto, questa è la matrice associata alla trasformata discreta di Fourier $N$-dimensionale. Spesso il fattore iniziale $1/\sqrt{N}$ non è incluso nella definizione di questa matrice, ma dobbiamo includerlo per ottenere una matrice unitaria.

Ecco la trasformata di Fourier quantistica, scritta come matrice, per alcuni valori piccoli di $N$.

$$\mathrm{QFT}_1 = \begin{pmatrix} 1 \end{pmatrix}$$ $$\mathrm{QFT}_2 = \frac{1}{\sqrt{2}} \begin{pmatrix} 1 & 1\\[1mm] 1 & -1 \end{pmatrix}$$ $$\mathrm{QFT}_3 = \frac{1}{\sqrt{3}} \begin{pmatrix} 1 & 1 & 1\\[2mm] 1 & \frac{-1 + i\sqrt{3}}{2} & \frac{-1 - i\sqrt{3}}{2}\\[2mm] 1 & \frac{-1 - i\sqrt{3}}{2} & \frac{-1 + i\sqrt{3}}{2} \end{pmatrix}$$ $$\mathrm{QFT}_4 = \frac{1}{2} \begin{pmatrix} 1 & 1 & 1 & 1\\[1mm] 1 & i & -1 & -i\\[1mm] 1 & -1 & 1 & -1\\[1mm] 1 & -i & -1 & i \end{pmatrix}$$ $$\mathrm{QFT}_8 = \frac{1}{2\sqrt{2}} \begin{pmatrix} 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1\\[2mm] 1 & \frac{1+i}{\sqrt{2}} & i & \frac{-1+i}{\sqrt{2}} & -1 & \frac{-1-i}{\sqrt{2}} & -i & \frac{1-i}{\sqrt{2}}\\[2mm] 1 & i & -1 & -i & 1 & i & -1 & -i\\[2mm] 1 & \frac{-1+i}{\sqrt{2}} & -i & \frac{1+i}{\sqrt{2}} & -1 & \frac{1-i}{\sqrt{2}} & i & \frac{-1-i}{\sqrt{2}}\\[2mm] 1 & -1 & 1 & -1 & 1 & -1 & 1 & -1\\[2mm] 1 & \frac{-1-i}{\sqrt{2}} & i & \frac{1-i}{\sqrt{2}} & -1 & \frac{1+i}{\sqrt{2}} & -i & \frac{-1+i}{\sqrt{2}}\\[2mm] 1 & -i & -1 & i & 1 & -i & -1 & i\\[2mm] 1 & \frac{1-i}{\sqrt{2}} & -i & \frac{-1-i}{\sqrt{2}} & -1 & \frac{-1+i}{\sqrt{2}} & i & \frac{1+i}{\sqrt{2}}\\[2mm] \end{pmatrix}$$

Nota in particolare che $\mathrm{QFT}_2$ è un altro nome per un'operazione di Hadamard.

Unitarietà

Verifichiamo che $\mathrm{QFT}_N$ sia unitaria, per qualsiasi scelta di $N$. Un modo per farlo è mostrare che le sue colonne formano una base ortonormale. Possiamo definire un vettore corrispondente alla colonna numero $y$, partendo da $y = 0$ fino a $y = N-1$, così:

$$\vert\phi_y\rangle = \frac{1}{\sqrt{N}} \sum_{x = 0}^{N-1} \omega_N^{xy} \vert x \rangle.$$

Calcolare il prodotto interno tra due qualsiasi di questi vettori ci fornisce questa espressione:

$$\langle \phi_z \vert \phi_y \rangle = \frac{1}{N} \sum_{x = 0}^{N-1} \omega_N^{x (y - z)}$$

Possiamo valutare somme come questa usando la seguente formula per la somma dei primi $N$ termini di una serie geometrica.

$$1 + \alpha + \alpha^2 + \cdots + \alpha^{N-1} = \begin{cases} \frac{\alpha^N - 1}{\alpha - 1} & \text{if } \alpha\neq 1\\[2mm] N & \text{if } \alpha=1 \end{cases}$$

Nello specifico, possiamo usare questa formula quando $\alpha = \omega_N^{y-z}$. Quando $y = z$, abbiamo $\alpha = 1$, quindi usando la formula e dividendo per $N$ si ottiene

$$\langle \phi_y \vert \phi_y \rangle = 1.$$

Quando $y\neq z$, abbiamo $\alpha \neq 1$, quindi la formula rivela questo:

$$\langle \phi_z \vert \phi_y \rangle = \frac{1}{N} \frac{\omega_N^{N(y-z)} - 1}{\omega_N^{y-z} - 1} = \frac{1}{N} \frac{1 - 1}{\omega_N^{y-z} - 1} = 0.$$

Questo accade perché $\omega_N^N = e^{2\pi i} = 1$, quindi $\omega_N^{N(y-z)} = 1^{y-z} = 1$, rendendo il numeratore zero, mentre il denominatore è diverso da zero perché $\omega_N^{y-z} \neq 1$. In termini intuitivi, quello che stiamo facendo è sommare una serie di punti distribuiti attorno al cerchio unitario, e questi si cancellano dando $0$ quando sommati.

Abbiamo quindi stabilito che $\{\vert\phi_0\rangle,\ldots,\vert\phi_{N-1}\rangle\}$ è un insieme ortonormale,

$$\langle \phi_z \vert \phi_y \rangle = \begin{cases} 1 & y=z\\ 0 & y\neq z, \end{cases}$$

il che rivela che $\mathrm{QFT}_N$ è unitaria.

Gate a fase controllata

Per implementare la trasformata di Fourier quantistica con un circuito quantistico, avremo bisogno di fare uso di gate a fase controllata. Ricorda che un'operazione di fase è un'operazione unitaria a singolo qubit della forma

$$P_{\alpha} = \begin{pmatrix} 1 & 0\\[1mm] 0 & e^{i\alpha} \end{pmatrix}$$

per qualsiasi numero reale $\alpha$. Una versione controllata di questo gate ha la seguente matrice:

$$CP_{\alpha} = \begin{pmatrix} 1 & 0 & 0 & 0\\[1mm] 0 & 1 & 0 & 0\\[1mm] 0 & 0 & 1 & 0\\[1mm] 0 & 0 & 0 & e^{i\alpha} \end{pmatrix}$$

Per questo gate controllato, non importa quale qubit sia il controllo e quale il target, perché le due possibilità sono equivalenti. Possiamo usare uno qualsiasi dei seguenti simboli per rappresentare questo gate nei diagrammi di circuiti quantistici.

Per la terza forma, l'etichetta $\alpha$ viene talvolta posta di lato alla linea di controllo o sotto il controllo inferiore quando è più conveniente.

Per eseguire la trasformata di Fourier quantistica quando $N = 2^m$ e $m\geq 2$, avremo bisogno di eseguire un'operazione su $m$ qubit la cui azione sugli stati della base standard può essere descritta come

$$\vert y \rangle \vert a \rangle \mapsto \omega_{2^m}^{ay} \vert y \rangle \vert a \rangle,$$

dove $a$ è un bit e $y \in \{0,\ldots,2^{m-1} - 1\}$ è un numero codificato in notazione binaria come una stringa di $m-1$ bit. Questo può essere fatto usando gate a fase controllata generalizzando il seguente esempio, per cui $m=5$.

In generale, per una scelta arbitraria di $m\geq 2$, il qubit superiore corrispondente al bit $a$ può essere visto come il controllo, con i gate di fase $P_{\alpha}$ che vanno da $\alpha = \pi/2^{m-1}$ sul qubit corrispondente al bit meno significativo di $y$ a $\alpha = \frac{\pi}{2}$ sul qubit corrispondente al bit più significativo di $y$. Questi gate a fase controllata commutano tra loro e possono essere eseguiti in qualsiasi ordine.

Implementazione circuitale della QFT

Ora vedremo come possiamo implementare la trasformata di Fourier quantistica con un circuito quando la dimensione $N = 2^m$ è una potenza di $2$. Esistono in realtà più modi per implementare la trasformata di Fourier quantistica, ma questo è probabilmente il metodo più semplice conosciuto. Una volta saputo come implementare la trasformata di Fourier quantistica con un circuito quantistico, è semplice implementare la sua inversa: possiamo sostituire ogni gate con la sua inversa (o, equivalentemente, il trasposto coniugato) e applicare i gate nell'ordine inverso. Ogni circuito quantistico composto solo da gate unitari può essere invertito in questo modo.

L'implementazione è di natura ricorsiva, quindi è così che viene descritta nel modo più naturale. Il caso base è $m=1$, nel qual caso la trasformata di Fourier quantistica è un'operazione di Hadamard.

Per eseguire la trasformata di Fourier quantistica su $m$ qubit quando $m \geq 2$, possiamo eseguire i seguenti passaggi, le cui azioni descriveremo per gli stati della base standard della forma $\vert x \rangle \vert a\rangle$, dove $x\in\{0,\ldots,2^{m-1} - 1\}$ è un intero codificato come $m-1$ bit in notazione binaria e $a$ è un singolo bit.

1. Prima applica la trasformata di Fourier quantistica $2^{m-1}$-dimensionale agli $m-1$ qubit inferiori/più a sinistra per ottenere questo stato:

   $$\Bigl(\mathrm{QFT}_{2^{m-1}} \vert x \rangle\Bigr) \vert a\rangle = \frac{1}{\sqrt{2^{m-1}}} \sum_{y = 0}^{2^{m-1} - 1} \omega_{2^{m-1}}^{xy} \vert y \rangle \vert a \rangle.$$

   Questo viene fatto applicando ricorsivamente il metodo descritto per un qubit in meno, usando l'operazione di Hadamard su un singolo qubit come caso base.

2. Usa il qubit superiore/più a destra come controllo per iniettare la fase $\omega_{2^m}^y$ per ogni stato della base standard $\vert y\rangle$ dei restanti $m-1$ qubit (come descritto sopra) per ottenere questo stato:

   $$\frac{1}{\sqrt{2^{m-1}}} \sum_{y = 0}^{2^{m-1} - 1} \omega_{2^{m-1}}^{xy} \omega_{2^m}^{ay} \vert y \rangle \vert a \rangle.$$

3. Esegui un gate di Hadamard sul qubit superiore/più a destra per ottenere questo stato:

   $$\frac{1}{\sqrt{2^{m}}} \sum_{y = 0}^{2^{m-1} - 1} \sum_{b=0}^1 (-1)^{ab} \omega_{2^{m-1}}^{xy} \omega_{2^m}^{ay} \vert y \rangle \vert b \rangle.$$

4. Permuta l'ordine dei qubit in modo che il bit meno significativo diventi il più significativo, con tutti gli altri spostati in su/a destra:

   $$\frac{1}{\sqrt{2^{m}}} \sum_{y = 0}^{2^{m-1} - 1} \sum_{b=0}^1 (-1)^{ab} \omega_{2^{m-1}}^{xy} \omega_{2^m}^{ay} \vert b \rangle \vert y \rangle.$$

Ad esempio, ecco il circuito che si ottiene per $N = 32 = 2^5$. In questo diagramma, ai qubit vengono assegnati nomi che corrispondono ai vettori della base standard $\vert x\rangle \vert a\rangle$ (per l'input) e $\vert b\rangle \vert y\rangle$ (per l'output) per chiarezza.

Analisi

La formula chiave di cui abbiamo bisogno per verificare che il circuito appena descritto implementi la trasformata di Fourier quantistica $2^m$-dimensionale è questa:

$$(-1)^{ab} \omega_{2^{m-1}}^{xy} \omega_{2^m}^{ay} = \omega_{2^m}^{(2x+ a)(2^{m-1}b + y)}.$$

Questa formula vale per qualsiasi scelta di interi $a,$ $b,$ $x$ e $y,$ ma ne avremo bisogno solo per $a,b\in\{0,1\}$ e $x,y\in\{0,\ldots,2^{m-1}-1\}.$ Può essere verificata espandendo il prodotto nell'esponente sul lato destro,

$$\omega_{2^m}^{(2x+ a)(2^{m-1}b + y)} = \omega_{2^m}^{2^m xb} \omega_{2^m}^{2xy} \omega_{2^m}^{2^{m-1}ab} \omega_{2^m}^{ay} = (-1)^{ab} \omega_{2^{m-1}}^{xy} \omega_{2^m}^{ay},$$

dove la seconda uguaglianza fa uso dell'osservazione che

$$\omega_{2^m}^{2^m xb} = \bigl(\omega_{2^m}^{2^m}\bigr)^{xb} = 1^{xb} = 1.$$

La trasformata di Fourier quantistica $2^m$-dimensionale è definita come segue per ogni $u\in\{0,\ldots,2^m - 1\}$.

$$\mathrm{QFT}_{2^m} \vert u\rangle = \frac{1}{\sqrt{2^m}} \sum_{v = 0}^{2^m - 1} \omega_{2^m}^{uv} \vert v\rangle$$

Se scriviamo $u$ e $v$ come

$$\begin{aligned} u & = 2x + a\\ v & = 2^{m-1}b + y \end{aligned}$$

per $a,b\in\{0,1\}$ e $x,y\in\{0,\ldots,2^{m-1} - 1\}$, otteniamo

$$\begin{aligned} \mathrm{QFT}_{2^m} \vert 2x + a\rangle & = \frac{1}{\sqrt{2^m}} \sum_{y = 0}^{2^{m-1} - 1} \sum_{b=0}^1 \omega_{2^m}^{(2x+ a)(2^{m-1}b + y)} \vert b 2^{m-1} + y\rangle\\[2mm] & = \frac{1}{\sqrt{2^m}} \sum_{y = 0}^{2^{m-1} - 1} \sum_{b=0}^1 (-1)^{ab} \omega_{2^{m-1}}^{xy} \omega_{2^m}^{ay} \vert b 2^{m-1} + y\rangle. \end{aligned}$$

Infine, pensando agli stati della base standard $\vert x \rangle \vert a\rangle$ e $\vert b \rangle \vert y \rangle$ come codifiche binarie di interi nell'intervallo $\{0,\ldots,2^m-1\}$,

$$\begin{aligned} \vert x \rangle \vert a\rangle & = \vert 2x + a \rangle\\ \vert b \rangle \vert y \rangle & = \vert 2^{m-1}b + y\rangle, \end{aligned}$$

vediamo che il circuito sopra implementa l'operazione richiesta. Se questo metodo per eseguire la trasformata di Fourier quantistica sembra notevole, è perché lo è: è essenzialmente la trasformata veloce di Fourier nella forma di un circuito quantistico.

Infine, contiamo quanti gate vengono utilizzati nel circuito appena descritto. I gate a fase controllata non fanno parte del gate set standard di cui abbiamo parlato nella lezione precedente, ma per cominciare ignoreremo questo fatto e conteremo ognuno di essi come un singolo gate.

Indichiamo con $s_m$ il numero di gate di cui abbiamo bisogno per ogni possibile scelta di $m$. Se $m=1$, la trasformata di Fourier quantistica è solo un'operazione di Hadamard, quindi

$$s_1 = 1.$$

Se $m\geq 2$, allora nel circuito sopra abbiamo bisogno di $s_{m-1}$ gate per la trasformata di Fourier quantistica su $m-1$ qubit, più $m-1$ gate a fase controllata, più un gate di Hadamard, più $m-1$ gate di swap, quindi

$$s_m = s_{m-1} + (2m - 1).$$

Possiamo ottenere un'espressione in forma chiusa sommando:

$$s_m = \sum_{k = 1}^m (2k - 1) = m^2.$$

In realtà non abbiamo bisogno di tanti gate di swap quanti ne descrive il metodo. Se riorganizziamo leggermente i gate, possiamo spingere tutti i gate di swap verso destra e ridurre il numero di gate di swap richiesti a $\lfloor m/2\rfloor$. Dal punto di vista asintotico questo non è un miglioramento significativo: otteniamo ancora circuiti di dimensione $O(m^2)$ per eseguire $\mathrm{QFT}_{2^m}$.

Se desideriamo implementare la trasformata di Fourier quantistica usando solo gate del nostro gate set standard, dobbiamo costruire o approssimare ciascuno dei gate a fase controllata con gate del nostro insieme. Il numero richiesto dipende da quanta precisione ci serve, ma come funzione di $m$ il costo totale rimane quadratico.

È in realtà possibile approssimare la trasformata di Fourier quantistica abbastanza bene con un numero sub-quadratico di gate, sfruttando il fatto che $P_{\alpha}$ è molto vicino all'operazione identità quando $\alpha$ è molto piccolo — il che significa che possiamo semplicemente omettere la maggior parte dei gate a fase controllata senza subire troppa perdita in termini di precisione.

Procedura generale e analisi

Esaminiamo ora la procedura di stima della fase in generale. L'idea è estendere la versione a due qubit della stima della fase considerata in precedenza nel modo naturale suggerito dal diagramma seguente.

Nota che, per ogni nuovo qubit di controllo aggiunto in cima, il numero di esecuzioni dell'operazione unitaria $U$ raddoppia. Ciò è indicato nel diagramma dalle potenze su $U$ per ciascuna delle operazioni unitarie controllate.

Il modo più diretto per implementare un'operazione $U^k$ controllata per una certa scelta di $k$ è semplicemente ripetere $k$ volte l'operazione $U$ controllata. Se questa è effettivamente la metodologia utilizzata, occorre riconoscere che l'aggiunta di qubit di controllo contribuisce in modo significativo alle dimensioni del circuito: se disponiamo di $m$ qubit di controllo, come illustrato nel diagramma, sono necessarie in totale $2^m - 1$ copie dell'operazione $U$ controllata. Ciò significa che all'aumentare di $m$ si incorre in un costo computazionale considerevole — ma come vedremo, porta anche a un'approssimazione significativamente più accurata di $\theta$.

È importante notare, tuttavia, che per alcune scelte di $U$ potrebbe essere possibile creare un circuito che implementa l'operazione $U^k$ per grandi valori di $k$ in modo più efficiente rispetto alla semplice ripetizione $k$ volte del circuito per $U$. Vedremo un esempio specifico di questo nel contesto della fattorizzazione di interi più avanti nella lezione, dove viene in soccorso l'algoritmo efficiente per l'esponenziazione modulare discusso nella lezione precedente.

Analizziamo ora il circuito appena descritto. Lo stato immediatamente prima della trasformata di Fourier quantistica inversa ha questo aspetto:

$$\frac{1}{\sqrt{2^m}} \sum_{x = 0}^{2^m - 1} \bigl( U^x \vert\psi\rangle \bigr) \vert x\rangle = \vert\psi\rangle \otimes \frac{1}{\sqrt{2^m}} \sum_{x = 0}^{2^m - 1} e^{2\pi i x\theta} \vert x\rangle.$$

Un caso speciale

In modo analogo a quanto fatto nel caso $m=2$, consideriamo prima il caso speciale in cui $\theta = y/2^m$ per $y\in\{0,\ldots,2^m-1\}$. In questo caso lo stato prima della trasformata di Fourier quantistica inversa può essere scritto in modo alternativo come segue:

$$\vert\psi\rangle \otimes \frac{1}{\sqrt{2^m}} \sum_{x = 0}^{2^m - 1} e^{2\pi i \frac{xy}{2^m}} \vert x\rangle = \vert\psi\rangle \otimes \frac{1}{\sqrt{2^m}} \sum_{x = 0}^{2^m - 1} \omega_{2^m}^{xy} \vert x\rangle = \vert\psi\rangle \otimes \mathrm{QFT}_{2^m} \vert y\rangle.$$

Quindi, quando viene applicata la trasformata di Fourier quantistica inversa, lo stato diventa

$$\vert\psi\rangle \vert y\rangle$$

e le misurazioni rivelano $y$ (codificato in binario).

Limitazione delle probabilità

Per altri valori di $\theta$, ovvero quelli che non assumono la forma $y/2^m$ per un intero $y$, i risultati delle misurazioni non saranno certi, ma possiamo dimostrare dei limiti sulle probabilità per i diversi esiti. D'ora in poi, consideriamo una scelta arbitraria di $\theta$ che soddisfi $0\leq \theta < 1$.

Dopo l'esecuzione della trasformata di Fourier quantistica inversa, lo stato del circuito è il seguente:

$$\vert \psi \rangle \otimes \frac{1}{2^m} \sum_{y=0}^{2^m - 1} \sum_{x=0}^{2^m-1} e^{2\pi i x (\theta - y/2^m)} \vert y\rangle.$$

Quindi, quando vengono eseguite le misurazioni sugli $m$ qubit superiori, osserviamo ogni esito $y$ con probabilità

$$p_y = \left\vert \frac{1}{2^m} \sum_{x=0}^{2^m - 1} e^{2\pi i x (\theta - y/2^m)} \right\vert^2.$$

Per comprendere meglio queste probabilità, utilizzeremo la stessa formula vista in precedenza per la somma della parte iniziale di una serie geometrica.

$$1 + \alpha + \alpha^2 + \cdots + \alpha^{N-1} = \begin{cases} \frac{\alpha^N - 1}{\alpha - 1} & \text{if } \alpha\neq 1\\[2mm] N & \text{if } \alpha=1 \end{cases}$$

Possiamo semplificare la somma che appare nella formula per $p_y$ ponendo $\alpha = e^{2\pi i (\theta - y/2^m)}$. Ecco il risultato ottenuto.

$$\sum_{x=0}^{2^m - 1} e^{2\pi i x (\theta - y/2^m)} = \begin{cases} 2^m & \theta = y/2^m\\[2mm] \frac{e^{2\pi i (2^m \theta - y)} - 1}{e^{2\pi i (\theta - y/2^m)} - 1} & \theta\neq y/2^m \end{cases}$$

Quindi, nel caso in cui $\theta = y/2^m$, troviamo che $p_y = 1$ (come sapevamo già dall'analisi di questo caso speciale), e nel caso in cui $\theta \neq y/2^m$, troviamo che

$$p_y = \frac{1}{2^{2m}} \left\vert \frac{e^{2\pi i (2^m \theta - y)} - 1}{e^{2\pi i (\theta - y/2^m)} - 1}\right\vert^2.$$

Possiamo apprendere ulteriori informazioni su queste probabilità ragionando sulla relazione tra lunghezze degli archi e lunghezze delle corde sul cerchio unitario. Ecco una figura che illustra le relazioni necessarie per qualsiasi numero reale $\delta\in \bigl[ -\frac{1}{2},\frac{1}{2}\bigr]$.

Innanzitutto, la lunghezza della corda (disegnata in blu) non può essere maggiore della lunghezza dell'arco (disegnata in viola):

$$\bigl\vert e^{2\pi i \delta} - 1\bigr\vert \leq 2\pi\vert\delta\vert.$$

Mettendo in relazione queste lunghezze nell'altra direzione, vediamo che il rapporto tra la lunghezza dell'arco e la lunghezza della corda è massimo quando $\delta = \pm 1/2$, e in questo caso il rapporto è la metà della circonferenza del cerchio divisa per il diametro, ossia $\pi/2$. Pertanto, abbiamo

$$\frac{2\pi\vert\delta\vert}{\bigl\vert e^{2\pi i \delta} - 1\bigr\vert} \leq \frac{\pi}{2},$$

e quindi

$$\bigl\vert e^{2\pi i \delta} - 1\bigr\vert \geq 4\vert\delta\vert.$$

Un'analisi basata su queste relazioni rivela i seguenti due fatti.

1. Supponiamo che $\theta$ sia un numero reale e che $y\in \{0,\ldots,2^m-1\}$ soddisfi

   $$\Bigl\vert \theta - \frac{y}{2^m}\Bigr\vert \leq 2^{-(m+1)}.$$

   Ciò significa che $y/2^m$ è o la migliore approssimazione a $m$ bit di $\theta$, oppure si trova esattamente a metà tra $y/2^m$ e $(y-1)/2^m$ o $(y+1)/2^m$, quindi è una delle due migliori approssimazioni di $\theta$.

   Dimostreremo che $p_y$ deve essere piuttosto grande in questo caso. Dall'ipotesi che stiamo considerando segue che $\vert 2^m \theta - y \vert \leq 1/2$, quindi possiamo usare la seconda osservazione sulla relazione tra lunghezze degli archi e delle corde per concludere che

   $$\left\vert e^{2\pi i (2^m \theta - y)} - 1\right\vert \geq 4 \vert 2^m \theta - y \vert = 4 \cdot 2^m \cdot \Bigl\vert \theta - \frac{y}{2^m}\Bigr\vert.$$

   Possiamo anche usare la prima osservazione sulle lunghezze degli archi e delle corde per concludere che

   $$\left\vert e^{2\pi i (\theta - y/2^m)} - 1\right\vert \leq 2\pi \Bigl\vert \theta - \frac{y}{2^m}\Bigr\vert.$$

   Applicando queste due disuguaglianze a $p_y$ si ottiene

   $$p_y \geq \frac{1}{2^{2m}} \frac{16 \cdot 2^{2m}}{4 \pi^2} = \frac{4}{\pi^2} \approx 0.405.$$

   Questo spiega la nostra osservazione che il risultato migliore si verifica con probabilità superiore al $40\%$ nella versione con $m=2$ della stima della fase discussa in precedenza. Non è esattamente il 40%, bensì $4/\pi^2$, e in effetti questo limite vale per ogni scelta di $m$.

2. Supponiamo ora che $y\in \{0,\ldots,2^m-1\}$ soddisfi

   $$2^{-m} \leq \Bigl\vert \theta - \frac{y}{2^m}\Bigr\vert \leq \frac{1}{2}.$$

   Ciò significa che esiste un'approssimazione migliore $z/2^m$ di $\theta$ compresa tra $\theta$ e $y/2^m$.

   Questa volta dimostreremo che $p_y$ non può essere troppo grande. Possiamo partire dalla semplice osservazione che

   $$\left\vert e^{2\pi i (2^m \theta - y)} - 1\right\vert \leq 2,$$

   che deriva dal fatto che due qualsiasi punti sul cerchio unitario possono differire in valore assoluto al massimo di $2$.

   Possiamo anche usare la seconda osservazione sulle lunghezze degli archi e delle corde descritta sopra, lavorando questa volta con il denominatore di $p_y$ anziché con il numeratore, per concludere che

   $$\left\vert e^{2\pi i (\theta - y/2^m)} - 1\right\vert \geq 4\Bigl\vert \theta - \frac{y}{2^m}\Bigr\vert \geq 4 \cdot 2^{-m}.$$

   Combinando le due disuguaglianze si ottiene

   $$p_y \leq \frac{1}{2^{2m}} \frac{4}{16 \cdot 2^{-2m}} = \frac{1}{4}.$$

   Nota che, sebbene questo limite sia sufficiente per i nostri scopi, è piuttosto approssimativo — la probabilità è solitamente molto inferiore a $1/4$.

La conclusione importante di questa analisi è che le approssimazioni molto vicine a $\theta$ hanno alta probabilità di verificarsi — otterremo la migliore approssimazione a $m$ bit con probabilità superiore al $40\%$ — mentre le approssimazioni che si discostano di più di $2^{-m}$ hanno minore probabilità di verificarsi, con probabilità limitata superiormente dal $25\%$.

Date queste garanzie, è possibile aumentare la nostra confidenza ripetendo la procedura di stima della fase più volte, per raccogliere evidenze statistiche su $\theta$. È importante notare che lo stato $\vert\psi\rangle$ della collezione di qubit inferiori rimane invariato dalla procedura di stima della fase, quindi può essere usato per eseguire la procedura tutte le volte che si desidera. In particolare, ogni volta che eseguiamo il circuito, otteniamo la migliore approssimazione a $m$ bit di $\theta$ con probabilità superiore al $40\%$, mentre la probabilità di discostarsi di più di $2^{-m}$ è limitata al $25\%$. Se eseguiamo il circuito più volte e prendiamo l'esito che appare più frequentemente, è quindi estremamente probabile che l'esito più comune non sia uno di quelli che si verifica al massimo il $25\%$ delle volte. Di conseguenza, è molto probabile che otterremo un'approssimazione $y/2^m$ che dista al massimo $1/2^m$ dal valore $\theta$. In effetti, la piccola probabilità di discostarsi di più di $1/2^m$ decresce esponenzialmente nel numero di volte che la procedura viene eseguita.

Ecco due grafici che mostrano le probabilità per tre valori consecutivi di $y$ quando $m = 3$ e $m=4$ come funzioni di $\theta$. (Per maggiore chiarezza vengono mostrati solo tre esiti. Le probabilità per gli altri esiti si ottengono traslando ciclicamente la stessa funzione sottostante.)