Procedura di stima della fase

Successivamente, discuteremo la procedura di stima della fase, che è un algoritmo quantistico per risolvere il problema della stima della fase.

Inizieremo con un riscaldamento a bassa precisione, che spiega alcune delle intuizioni di base del metodo. Parleremo poi della trasformata di Fourier quantistica, un'importante operazione quantistica utilizzata nella procedura di stima di fase, e della sua implementazione nei circuiti quantistici. Una volta ottenuta la trasformata di Fourier quantistica, descriveremo la procedura di stima della fase in tutta la sua generalità e ne analizzeremo le prestazioni.

---

Riscaldamento: approssimazione delle fasi con bassa precisione

Inizieremo con un paio di versioni semplici della procedura di stima della fase che forniscono soluzioni di 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.

Utilizzo del contraccolpo di fase

Un approccio semplice al problema della stima della fase, che ci permette di imparare qualcosa sul valore $\theta$ che cerchiamo, si basa sul fenomeno del kick-back di fase. Come vedremo, si tratta essenzialmente di una versione a un solo qubit della procedura generale di stima della fase che verrà discussa più avanti nella lezione.

Come parte dell'input del 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 $U$ controllata, che può essere rappresentato come suggerisce questa figura (con l'operazione $U,$ vista come una porta quantistica, a sinistra, e un'operazione $U$ controllata a destra).

Possiamo creare un circuito quantistico per un'operazione controllata $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 - in questo modo il nostro nuovo qubit di controllo controlla effettivamente ogni singolo gate nel circuito per $U.$ Questo richiede una versione controllata di ogni gate del nostro circuito, ma possiamo sempre costruire circuiti per queste operazioni controllate nel caso in cui non siano incluse nel nostro set di gate.

Si consideri ora il seguente circuito, in cui lo stato di ingresso $\vert\psi\rangle$ di tutti i qubit, tranne quello superiore, è l'autovettore di stato quantistico di $U.$

Le probabilità di esito della 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 la prima porta 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 controllata $U$, che dà come risultato 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$ avente autovalore $\lambda = e^{2\pi i\theta},$ possiamo esprimere alternativamente questo stato 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 si osserva il fenomeno del contraccolpo di fase. Questa volta è leggermente diverso rispetto all'algoritmo di Deutsch e all'algoritmo di Deutsch-Jozsa, perché non stiamo lavorando con un query gate, ma l'idea è simile.

Infine, viene eseguito il secondo gate di Hadamard. Dopo una piccola semplificazione, otteniamo questa espressione per questo 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 misurazione 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à dei due possibili risultati, $0$ e $1,$ in funzione di $\theta.$

Naturalmente, le due probabilità si sommano sempre a $1.$ Si noti che quando $\theta = 0,$ il risultato della misurazione è sempre $0,$ e quando $\theta = 1/2,$ il risultato della misurazione è sempre $1.$ Quindi, sebbene il risultato della misura non riveli esattamente cosa sia $\theta$, ci fornisce alcune informazioni su di esso - e se ci venisse promesso che $\theta = 0$ o $\theta = 1/2,$ potremmo imparare dal circuito quale dei due è corretto senza errori.

Intuitivamente, si può pensare che il risultato della misurazione del circuito sia un'ipotesi per $\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 misurazione può essere visto come un'ipotesi per il bit $a.$ Quando $\theta$ non è né $0$ né $1/2,$ c'è una probabilità non nulla che l'ipotesi sia sbagliata, ma la probabilità di commettere un errore si riduce man mano che ci si avvicina a o probabilità di commettere un errore diventa sempre più piccola man mano che ci si avvicina a $0$ o a $1/2.$

È naturale chiedersi quale sia il ruolo delle due porte di Hadamard in questa procedura:

• Il primo gate di Hadamard imposta il qubit di controllo su una sovrapposizione uniforme di $\vert 0\rangle$ e $\vert 1\rangle,$ in modo che quando si verifica il contraccolpo di fase, questo avviene per lo stato $\vert 1\rangle$ e non per lo stato $\vert 0\rangle$, creando una differenza di fase relativa che influisce sui risultati della misurazione. Se non lo facessimo e il contraccolpo di fase producesse una fase globale, non avrebbe alcun effetto sulle probabilità di ottenere risultati di misura diversi.

• La seconda porta di Hadamard ci permette di imparare qualcosa sul numero $\theta$ attraverso il fenomeno dell' interferenza. Prima del secondo cancello 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 dovessimo misurare questo stato, otterremmo $0$ e $1$ ciascuno con la probabilità $1/2,$ senza sapere nulla di $\theta.$ Eseguendo la seconda porta di Hadamard, tuttavia, facciamo in modo che il numero $\theta$ influisca sulle probabilità di uscita.

Raddoppiare la fase

Il circuito di cui sopra utilizza il fenomeno del contraccolpo di fase per approssimare $\theta$ con una precisione di un singolo bit. In alcune situazioni può essere sufficiente un po' di precisione, ma per il factoring avremo bisogno di molta più precisione. Una domanda naturale è: come possiamo imparare di più su $\theta?$

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

Due copie di un'operazione controllata $U$ sono equivalenti a un'operazione controllata $U^2$. Se $\vert\psi\rangle$ è un autovettore di $U$ avente autovalore $\lambda = e^{2\pi i \theta},$ allora questo stato è anche un autovettore di $U^2,$ questa volta avente 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 per il fatto che il numero $\theta$ è sostituito dal numero $2\theta.$ Ecco un grafico che illustra le probabilità di uscita quando $\theta$ varia da $0$ a $1.$

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

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

allora il raddoppio di $\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$ a $\theta = 0$ mentre ci muoviamo intorno al cerchio unitario, vediamo che il bit $a_1$ non ha alcuna influenza sulle nostre probabilità, e stiamo effettivamente ottenendo un'ipotesi 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 pienamente del risultato della misurazione per sapere quale sia.

Tuttavia, non è immediatamente chiaro come questa stima debba essere riconciliata con quanto appreso dal circuito originale (non raddoppiato) del contraccolpo di fase, per ottenere le informazioni più accurate possibili $\theta.$ Facciamo quindi un passo indietro e valutiamo come procedere.

Stima di fase a due qubit

Invece di considerare le due opzioni descritte sopra separatamente, combiniamole in un unico circuito in questo modo.

Le porte di Hadamard dopo le operazioni controllate sono state rimosse e non ci sono ancora misure qui. Aggiungeremo altri elementi al circuito man mano che valuteremo le nostre opzioni per imparare il più possibile su $\theta.$

Se facciamo funzionare 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 "calciate" nello stato dei due qubit superiori. Analizziamo attentamente il circuito attraverso la figura seguente.

Possiamo scrivere lo stato $\vert\pi_1\rangle$ in questo modo:

$$\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 controllata $U$, l'autovalore $\lambda = e^{2\pi i\theta}$ viene spinto nella fase quando $a_0$ (il qubit superiore) è uguale a $1,$ ma non quando è uguale a $0.$ Quindi, possiamo esprimere lo stato risultante in questo modo:

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

La seconda e la terza porta controllata $U$ fanno qualcosa di simile, ma con $a_1$ invece di $a_0,$ e con $\theta$ sostituito da $2\theta.$ Possiamo esprimere lo stato risultante in questo modo:

$$\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 se rappresentasse un intero $x \in \{0,1,2,3\}$ in notazione binaria, che è $x = 2 a_1 + a_0,$, possiamo esprimere questo stato nel modo seguente.

$$\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 particolare, in cui ci viene promesso che $\theta = \frac{y}{4}$ per un qualche numero intero $y\in\{0,1,2,3\}.$ In altre parole, abbiamo $\theta\in \{0, 1/4, 1/2, 3/4\},$ e possiamo esprimere questo numero esattamente con la notazione binaria a 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 nel modo più efficace le informazioni su $\theta$ in generale.

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: se scegliamo una coppia qualsiasi di essi e calcoliamo il loro prodotto interno, otteniamo $0.$ Ognuno di essi è 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 subito che esiste una misura in grado di discriminarli perfettamente - il che significa che, se ci viene dato uno di essi ma non sappiamo quale, possiamo capire quale sia senza errori.

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

$$\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 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}$$

Si tratta di una matrice speciale, che probabilmente alcuni lettori avranno già incontrato: è la matrice associata alla trasformata discreta di Fourier $4$. Alla luce di questo fatto, chiamiamola con il nome di $\mathrm{QFT}_4$ piuttosto che con il nome di $V.$ Il nome $\mathrm{QFT}$ è l'abbreviazione di trasformata quantistica di Fourier, che è essenzialmente solo la trasformata discreta di Fourier, vista come un'operazione unitaria. A breve discuteremo la trasformata di Fourier quantistica in modo più dettagliato e generico.

$$\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'operazione inversa per trasformare 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 imparare quale valore $y\in\{0,1,2,3\}$ descrive $\theta$ come $\theta = y/4.$ Ecco lo schema di un circuito quantistico che esegue questa operazione.

Per riassumere, se facciamo funzionare questo circuito quando $\theta = y/4$ per $y\in\{0,1,2,3\},$ lo stato immediatamente precedente alle misure sarà $\vert \psi\rangle \vert y\rangle$ (per $y$ codificato come una stringa binaria a due bit), quindi le misure riveleranno il valore $y$ senza errori.

Questo circuito è motivato dal caso particolare che $\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 uscita che il circuito produce per scelte arbitrarie di $\theta.$

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

Preparazione alla generalizzazione a molti qubit

Dato il miglioramento appena ottenuto utilizzando due qubit di controllo anziché uno, insieme all'inverso della trasformata di Fourier quantistica $4$ -dimensionale, è naturale pensare di generalizzarlo ulteriormente, aggiungendo altri qubit di controllo. Facendo ciò, otteniamo la procedura generale di stima della fase. Vedremo a breve come funziona, ma per descriverlo con precisione dovremo discutere la trasformata di Fourier quantistica in modo più generale, per vedere come viene definita per altre dimensioni e per vedere come possiamo implementarla (o la sua inversa) 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 è definita questa operazione 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 sono derivate da un'operazione analoga su vettori $N$ -dimensionali nota come trasformata di Fourier discreta. Questa operazione può essere pensata in diversi modi. Per esempio, possiamo pensare alla trasformata discreta di Fourier in termini puramente astratti e matematici come a una mappatura lineare. Oppure possiamo pensarla in termini computazionali, dove ci viene dato un vettore $N$ -dimensionale di numeri complessi (usando la notazione binaria per codificare le parti reali e immaginarie delle voci, supponiamo) e l'obiettivo è calcolare il vettore $N$ -dimensionale ottenuto applicando la trasformata discreta di Fourier. La nostra attenzione si concentrerà sulla terza via, che consiste nel considerare questa trasformazione come un'operazione unitaria che può essere eseguita su un sistema quantistico.

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

Definizione della trasformata di Fourier quantistica

Per definire la trasformata quantistica di Fourier, definiamo prima un numero complesso $\omega_N,$ per ogni intero positivo $N,$ in questo modo:

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

È il numero sul cerchio complesso unitario che si ottiene partendo da $1$ e muovendosi 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, che è 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, si tratta della matrice associata alla trasformata discreta di Fourier $N$ -dimensionale. Spesso il fattore primo di $1/\sqrt{N}$ non è incluso nella definizione di questa matrice, ma è necessario includerlo per ottenere una matrice unitaria.

Ecco la trasformata quantistica di Fourier, scritta come matrice, per alcuni piccoli valori 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}$$

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

Unitarità

Verifichiamo che $\mathrm{QFT}_N$ è unitario, per qualsiasi scelta di $N.$ Un modo per farlo è dimostrare che le sue colonne formano una base ortonormale. Possiamo definire un vettore corrispondente al numero di colonna $y,$ partendo da $y = 0$ e arrivando a $y = N-1,$ in questo modo:

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

Prendendo il prodotto interno tra due vettori qualsiasi si ottiene 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 utilizzando 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}$$

In particolare, possiamo utilizzare questa formula quando $\alpha = \omega_N^{y-z}.$ Quando $y = z,$ abbiamo $\alpha = 1,$ quindi utilizzando 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.$$

Ciò accade perché $\omega_N^N = e^{2\pi i} = 1,$ così $\omega_N^{N(y-z)} = 1^{y-z} = 1,$ rendendo il numeratore nullo, mentre il denominatore è non nullo perché $\omega_N^{y-z} \neq 1.$ Intuitivamente, stiamo sommando un insieme di punti distribuiti attorno al cerchio unitario che, sommati, si annullano e lasciano $0$.

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

che rivela che $\mathrm{QFT}_N$ è unitario.

Gate a fase controllata

Per implementare la trasformata di Fourier quantistica con un circuito quantistico, dovremo fare uso di porte a fase controllata. Ricordiamo 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 ha importanza quale qubit sia il controllo e quale il bersaglio, perché le due possibilità sono equivalenti. Per rappresentare questa porta nei diagrammi dei circuiti quantistici possiamo utilizzare uno dei seguenti simboli.

Per la terza forma, l'etichetta $\alpha$ viene talvolta collocata anche a lato della linea di controllo o sotto il controllo inferiore, quando è conveniente.

Per eseguire la trasformata quantistica di Fourier quando $N = 2^m$ e $m\geq 2,$ dobbiamo eseguire un'operazione su $m$ qubit la cui azione sugli stati 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 utilizzando porte a fase controllata generalizzando il seguente esempio, per il quale $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 le porte di fase $P_{\alpha}$ che vanno da $\alpha = \pi/2^{m-1}$ sul qubit corrispondente al bit meno significativo di $y$ fino a $\alpha = \frac{\pi}{2}$ sul qubit corrispondente al bit più significativo di $y.$ Queste porte di fase controllate sono tutte in commutazione tra loro e possono essere eseguite in qualsiasi ordine.

Implementazione circuitale del QFT

Ora vedremo come implementare la trasformata quantistica di Fourier con un circuito quando la dimensione $N = 2^m$ è una potenza di $2.$ Esistono infatti diversi modi per implementare la trasformata di Fourier quantistica, ma questo è probabilmente il metodo più semplice che si conosca. Una volta che sappiamo come implementare la trasformata di Fourier quantistica con un circuito quantistico, è semplice implementare la sua inversa: possiamo sostituire ogni porta con la sua inversa (o, equivalentemente, con la trasposta coniugata) e applicare le porte nell'ordine inverso. Ogni circuito quantistico composto da sole porte unitarie può essere invertito in questo modo.

L'implementazione è di natura ricorsiva, quindi è il modo più naturale per descriverla. Il caso base è $m=1,$, nel quale la trasformata quantistica di Fourier è un'operazione di Hadamard.

Per eseguire la trasformata quantistica di Fourier su $m$ qubit quando $m \geq 2,$ possiamo eseguire i seguenti passaggi, le cui azioni verranno descritte per stati 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 usando la notazione binaria e $a$ è un singolo bit.

1. Applicare prima la trasformata di Fourier quantistica $2^{m-1}$ -dimensionale ai qubit in basso/più a sinistra $m-1$ 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.$$

Ciò avviene applicando ricorsivamente il metodo descritto per un qubit in meno, utilizzando l'operazione Hadamard su un singolo qubit come caso base su un singolo qubit come caso base.

2. Usare il qubit superiore/destro come controllo per iniettare la fase $\omega_{2^m}^y$ per ogni stato di 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. Eseguire un cancello di Hadamard sul qubit in alto 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. Permutare l'ordine dei qubit in modo che il bit meno significativo diventi il bit più significativo, con tutti gli altri spostati verso l'alto o verso destra tutti gli altri spostati verso l'alto o verso 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.$$

Per esempio, ecco il circuito che otteniamo per $N = 32 = 2^5.$ In questo schema, ai qubit vengono dati nomi che corrispondono ai vettori base standard $\vert x\rangle \vert a\rangle$ (per l'ingresso) e $\vert b\rangle \vert y\rangle$ (per l'uscita) per maggiore chiarezza.

Analisi

La formula chiave che ci serve per verificare che il circuito appena descritto implementa la trasformata di Fourier quantistica $2^m$ è questa:

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

Questa formula funziona per qualsiasi scelta di numeri interi $a,$ $b,$ $x,$ e $y,$ ma ci servirà solo per $a,b\in\{0,1\}$ e $x,y\in\{0,\ldots,2^{m-1}-1\}.$ Si può verificare 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 sfrutta l'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 base standard $\vert x \rangle \vert a\rangle$ e $\vert b \rangle \vert y \rangle$ come a codifiche binarie di numeri 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 di cui sopra implementa l'operazione richiesta. Se questo metodo per eseguire la trasformata di Fourier quantistica sembra notevole, è perché lo è: è essenzialmente la trasformata di Fourier veloce sotto forma di circuito quantistico.

Infine, contiamo quante porte sono utilizzate nel circuito appena descritto. I gate a fase controllata non fanno parte dell'insieme di gate standard di cui abbiamo parlato nella lezione precedente, ma per cominciare ignoreremo questo fatto e considereremo ciascuno di essi come un singolo gate.

Facciamo in modo che $s_m$ denoti il numero di porte di cui abbiamo bisogno per ogni possibile scelta di $m.$ Se $m=1,$ la trasformata quantistica di Fourier è solo un'operazione di Hadamard, quindi

$$s_1 = 1.$$

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

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

Possiamo ottenere un'espressione in forma chiusa mediante la somma:

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

In realtà non abbiamo bisogno di tante porte di scambio come descritto nel metodo. Se riorganizziamo un po' i gate, possiamo spingere tutti i gate di swap verso destra e ridurre il numero di gate di swap necessari a $\lfloor m/2\rfloor.$ Dal punto di vista asintotico, questo non è un grande miglioramento: otteniamo ancora circuiti con dimensioni $O(m^2)$ per eseguire $\mathrm{QFT}_{2^m}.$

Se vogliamo implementare la trasformata di Fourier quantistica usando solo porte del nostro set di porte standard, dobbiamo costruire o approssimare ciascuna delle porte a fase controllata con porte del nostro set. Il numero necessario dipende dalla precisione richiesta, ma in funzione di $m$ il costo totale rimane quadratico.

È infatti possibile approssimare la trasformata quantistica di Fourier con un numero sub-quadratico di porte, sfruttando il fatto che $P_{\alpha}$ è molto vicino all'operazione di identità quando $\alpha$ è molto piccolo - il che significa che possiamo semplicemente escludere la maggior parte delle porte a fase controllata senza subire una perdita eccessiva in termini di precisione.

---

Procedura generale e analisi

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

Si noti che, per ogni nuovo qubit di controllo aggiunto in cima, raddoppiamo il numero di volte in cui viene eseguita l'operazione unitaria $U$. Questo è indicato nel diagramma dai poteri su $U$ per ciascuna delle operazioni controllate-unitarie.

Il modo più semplice per implementare un'operazione controllata $U^k$ per una certa scelta di $k$ è semplicemente ripetere un'operazione controllata $U$ $k$ volte. Se questa è la metodologia utilizzata, bisogna riconoscere che l'aggiunta dei qubit di controllo contribuisce in modo significativo alla dimensione del circuito: se abbiamo $m$ qubit di controllo, come illustrato nel diagramma, sono necessarie in totale $2^m - 1$ copie dell'operazione controllata $U$. Ciò significa che, con l'aumento di $m$, si sostiene un costo computazionale significativo, ma, come vedremo, si ottiene anche un'approssimazione significativamente più accurata di $\theta.$

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

Analizziamo ora il circuito appena descritto. Lo stato immediatamente precedente alla trasformata quantistica inversa di Fourier si presenta così:

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

Analogamente a quanto fatto nel caso di $m=2$, considereremo prima il caso speciale in cui $\theta = y/2^m$ per $y\in\{0,\ldots,2^m-1\}.$ In questo caso lo stato precedente alla trasformata quantistica inversa di Fourier può essere scritto alternativamente in questo modo:

$$\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 si applica la trasformata quantistica inversa di Fourier, lo stato diventa

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

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

Limitare le probabilità

Per altri valori di $\theta,$, cioè quelli che non assumono la forma $y/2^m$ per un intero $y,$, i risultati delle misure non saranno certi, ma possiamo dimostrare i limiti delle probabilità per i diversi risultati. Consideriamo una scelta arbitraria di $\theta$ che soddisfa le esigenze di tutti $0\leq \theta < 1.$

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

$$\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 misure sui qubit superiori $m$, vediamo che ogni risultato $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 capire meglio queste probabilità, utilizzeremo la stessa formula che abbiamo visto prima, 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 compare nella formula per $p_y$ prendendo $\alpha = e^{2\pi i (\theta - y/2^m)}.$ Ecco cosa otteniamo.

$$\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 che $\theta = y/2^m,$ troviamo che $p_y = 1$ (come già sapevamo considerando questo caso speciale), e nel caso di $\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 imparare di più su queste probabilità pensando a come sono correlate le lunghezze degli archi e le lunghezze delle corde sul cerchio unitario. Ecco una figura che illustra le relazioni di cui abbiamo bisogno 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 è maggiore quando $\delta = \pm 1/2,$ e in questo caso il rapporto è la metà della circonferenza del cerchio divisa per il diametro, ovvero $\pi/2.$ Si ha quindi

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

e così

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

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

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

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

Dimostreremo che $p_y$ deve essere piuttosto grande in questo caso. In base all'ipotesi che stiamo considerando, ne consegue che $\vert 2^m \theta - y \vert \leq 1/2,$ e quindi possiamo utilizzare la seconda osservazione precedente relativa alle 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 utilizzare 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.$$

Utilizzando queste due disuguaglianze su $p_y$ si scopre che

$$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 una probabilità maggiore di $40\%$ nella versione $m=2$ della stima di fase discussa in precedenza. Non è proprio il 40%, è $4/\pi^2,$ e infatti questo vincolo 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}.$$

Questo significa che tra $z/2^m$ e $\theta$ c'è un'approssimazione migliore tra $\theta$ e $y/2^m.$

Questa volta dimostreremo che $p_y$ non può essere troppo grande. Possiamo iniziare con la semplice osservazione che

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

che deriva dal fatto che due punti qualsiasi della circonferenza unitaria possono differire in valore assoluto di un massimo di $2.$

Possiamo anche utilizzare la seconda osservazione sulle lunghezze degli archi e delle corde di cui sopra, questa volta lavorando 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}.$$

Mettendo insieme le due disuguaglianze si ottiene

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

Si noti che questo limite, pur essendo sufficientemente buono per i nostri scopi, è piuttosto grossolano: la probabilità è di solito molto più bassa di $1/4.$

L'aspetto importante di questa analisi è che è probabile che si verifichino approssimazioni molto vicine a $\theta$ - otterremo una migliore approssimazione di $m$ bit con una probabilità superiore a $40\%$ - mentre è meno probabile che si verifichino approssimazioni inferiori a $2^{-m}$, con una probabilità limitata da $25\%.$

Date queste garanzie, è possibile aumentare la nostra fiducia ripetendo più volte la procedura di stima della fase, per raccogliere evidenze statistiche su $\theta.$ È importante notare che lo stato $\vert\psi\rangle$ della collezione inferiore di qubit è invariato dalla procedura di stima della fase, quindi può essere usato per eseguire la procedura tutte le volte che vogliamo. In particolare, ogni volta che eseguiamo il circuito, otteniamo una migliore approssimazione $m$ -bit a $\theta$ con probabilità maggiore di $40\%,$ mentre la probabilità di sbagliare di più di $2^{-m}$ è limitata da $25\%.$ Se eseguiamo il circuito più volte e prendiamo il risultato che appare più comunemente tra quelli eseguiti, è estremamente probabile che il risultato che appare più comunemente non sia quello che si verifica al massimo $25\%$ delle volte. Di conseguenza, è molto probabile che si ottenga un'approssimazione $y/2^m$ che si trova entro $1/2^m$ del valore $\theta.$ In effetti, l'improbabile possibilità di sbagliare di più di $1/2^m$ diminuisce esponenzialmente con il numero di volte in cui 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 chiarezza sono mostrati solo tre risultati). Le probabilità di altri risultati si ottengono spostando ciclicamente la stessa funzione sottostante)