Procedura de estimare a fazei

În continuare, vom discuta despre procedura de estimare a fazei, care este un algoritm cuantic pentru rezolvarea problemei de estimare a fazei.

Vom începe cu o variantă simplificată de precizie redusă, care explică o parte din intuiția de bază a metodei. Vom vorbi apoi despre transformata cuantică Fourier, care este o operație cuantică importantă folosită în procedura de estimare a fazei, precum și despre implementarea sa sub formă de Circuit cuantic. Odată ce avem transformata cuantică Fourier la îndemână, vom descrie procedura de estimare a fazei în toată generalitatea sa și vom analiza performanța acesteia.

Pregătire: aproximarea fazelor cu precizie redusă

Vom începe cu câteva versiuni simple ale procedurii de estimare a fazei care oferă soluții de precizie redusă pentru problema estimării fazei. Acest lucru este util pentru a explica intuiția din spatele procedurii generale pe care o vom vedea puțin mai târziu în lecție.

Folosind phase kickback

O abordare simplă a problemei de estimare a fazei, care ne permite să aflăm ceva despre valoarea $\theta$ pe care o căutăm, se bazează pe fenomenul de phase kick-back. Așa cum vom vedea, aceasta este în esență o versiune cu un singur Qubit a procedurii generale de estimare a fazei care va fi discutată mai târziu în lecție.

Ca parte a datelor de intrare pentru problema de estimare a fazei, avem un Circuit cuantic unitar pentru operația $U.$ Putem folosi descrierea acestui Circuit pentru a crea un Circuit pentru o operație controlată-$U$, care poate fi reprezentată după cum sugerează această figură (cu operația $U,$ privită ca un Gate cuantic, în stânga și o operație controlată-$U$ în dreapta).

Putem crea un Circuit cuantic pentru o operație controlată-$U$ adăugând mai întâi un Qubit de control la Circuitul pentru $U$, și apoi înlocuind fiecare Gate din Circuitul pentru $U$ cu o versiune controlată a acelui Gate — astfel, noul nostru Qubit de control controlează efectiv fiecare Gate individual din Circuitul pentru $U.$ Acest lucru necesită să avem o versiune controlată a fiecărui Gate din Circuit, dar putem construi întotdeauna Circuite pentru aceste operații controlate în cazul în care nu sunt incluse în setul nostru de Gate-uri.

Acum să considerăm următorul Circuit, unde starea de intrare $\vert\psi\rangle$ a tuturor Qubiților cu excepția celui de sus este vectorul stare propriu cuantic al lui $U.$

Probabilitățile rezultatelor măsurătorii pentru acest Circuit depind de valoarea proprie a lui $U$ corespunzătoare vectorului propriu $\vert\psi\rangle.$ Să analizăm Circuitul în detaliu pentru a determina exact cum.

Starea inițială a Circuitului este

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

iar primul Gate Hadamard transformă această stare în

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

Apoi, se efectuează operația controlată-$U$, ceea ce duce la starea

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

Folosind presupunerea că $\vert\psi\rangle$ este un vector propriu al lui $U$ cu valoarea proprie $\lambda = e^{2\pi i\theta},$ putem exprima alternativ această stare astfel.

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

Aici observăm fenomenul de phase kickback. Este ușor diferit de această dată față de algoritmul lui Deutsch și algoritmul Deutsch-Jozsa, deoarece nu lucrăm cu un Gate de interogare — dar ideea este similară.

În final, se efectuează al doilea Gate Hadamard. După o scurtă simplificare, obținem această expresie pentru această stare.

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

Măsurătoarea produce astfel rezultatele $0$ și $1$ cu aceste probabilități:

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

Iată un grafic al probabilităților pentru cele două rezultate posibile, $0$ și $1,$ ca funcții ale lui $\theta.$

Firește, cele două probabilități sumează întotdeauna la $1.$ Observă că atunci când $\theta = 0,$ rezultatul măsurătorii este întotdeauna $0,$ iar când $\theta = 1/2,$ rezultatul măsurătorii este întotdeauna $1.$ Deci, deși rezultatul măsurătorii nu dezvăluie exact ce este $\theta,$ ne oferă totuși ceva informație despre acesta — și dacă am fi promis că fie $\theta = 0$ fie $\theta = 1/2,$ am putea afla din Circuit care este corect fără eroare.

Intuitiv vorbind, putem considera rezultatul măsurătorii Circuitului ca o estimare a lui $\theta$ cu „o precizie de un bit." Cu alte cuvinte, dacă am scrie $\theta$ în notație binară și l-am rotunji la un bit, am obține un număr de forma:

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

Rezultatul măsurătorii poate fi privit ca o estimare a bitului $a.$ Când $\theta$ nu este nici $0$ nici $1/2,$ există o probabilitate nenulă că estimarea va fi greșită — dar probabilitatea de a face o eroare devine din ce în ce mai mică pe măsură ce ne apropiem de $0$ sau $1/2.$

Este firesc să ne întrebăm ce rol joacă cele două Gate-uri Hadamard în această procedură:

• Primul Gate Hadamard setează Qubitul de control la o superpozție uniformă a lui $\vert 0\rangle$ și $\vert 1\rangle,$ astfel încât atunci când se produce phase kickback, acesta se produce pentru starea $\vert 1\rangle$ și nu pentru starea $\vert 0\rangle$, creând o diferență de fază relativă care afectează rezultatele măsurătorii. Dacă nu am face asta și phase kickback ar produce o fază globală, nu ar avea niciun efect asupra probabilităților de a obține diferite rezultate ale măsurătorii.

• Al doilea Gate Hadamard ne permite să aflăm ceva despre numărul $\theta$ prin fenomenul de interferență. Înainte de al doilea Gate Hadamard, starea Qubitului de sus este

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

  și dacă am măsura această stare, am obține $0$ și $1$ fiecare cu probabilitatea $1/2,$ fără a ne spune nimic despre $\theta.$ Efectuând însă al doilea Gate Hadamard, facem ca numărul $\theta$ să afecteze probabilitățile de ieșire.

Dublarea fazei

Circuitul de mai sus folosește fenomenul de phase kickback pentru a aproxima $\theta$ cu o precizie de un singur bit. O precizie de un bit poate fi tot ce avem nevoie în unele situații — dar pentru factorizare vom avea nevoie de mult mai multă precizie decât atât. O întrebare naturală este: cum putem afla mai mult despre $\theta?$

Un lucru foarte simplu pe care îl putem face este să înlocuim operația controlată-$U$ din Circuitul nostru cu două copii ale acestei operații, ca în acest Circuit:

Două copii ale unei operații controlate-$U$ sunt echivalente cu o operație controlată-$U^2$. Dacă $\vert\psi\rangle$ este un vector propriu al lui $U$ cu valoarea proprie $\lambda = e^{2\pi i \theta},$ atunci această stare este și un vector propriu al lui $U^2,$ de această dată cu valoarea proprie $\lambda^2 = e^{2\pi i (2\theta)}.$

Deci, dacă rulăm această versiune a Circuitului, efectuăm efectiv același calcul ca înainte, cu excepția că numărul $\theta$ este înlocuit cu $2\theta.$ Iată un grafic care ilustrează probabilitățile de ieșire pe măsură ce $\theta$ variază de la $0$ la $1.$

Acest lucru ne poate oferi într-adevăr unele informații suplimentare despre $\theta.$ Dacă reprezentarea binară a lui $\theta$ este

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

atunci dublarea lui $\theta$ deplasează efectiv punctul binar cu o poziție spre dreapta:

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

Și deoarece asimilăm $\theta = 1$ cu $\theta = 0$ pe măsură ce ne deplasăm pe cercul unitar, vedem că bitul $a_1$ nu are nicio influență asupra probabilităților noastre, și obținem efectiv o estimare pentru al doilea bit de după punctul binar dacă rotunjim $\theta$ la două biți. De exemplu, dacă am ști dinainte că $\theta$ este fie $0$ fie $1/4,$ atunci am putea să ne bazăm pe deplin pe rezultatul măsurătorii pentru a ști care este.

Nu este imediat clar, totuși, cum ar trebui reconciliată această estimare cu ceea ce am aflat din Circuitul original de phase kickback (nedublat) pentru a obține informații cât mai precise despre $\theta.$ Deci să facem un pas înapoi și să considerăm cum să procedăm.

Estimarea fazei cu două Qubit-uri

În loc să considerăm separat cele două opțiuni descrise mai sus, hai să le combinăm într-un singur Circuit, astfel.

Gate-urile Hadamard de după operațiile controlate au fost eliminate și nu există măsurători aici încă. Vom adăuga mai multe elemente la Circuit pe măsură ce analizăm opțiunile noastre de a afla cât mai multe despre $\theta.$

Dacă rulăm acest Circuit când $\vert\psi\rangle$ este un vector propriu al lui $U,$ starea Qubit-urilor de jos va rămâne $\vert\psi\rangle$ pe tot parcursul Circuitului, iar fazele vor fi „lovite" în starea celor două Qubit-uri de sus. Hai să analizăm Circuit-ul cu atenție, prin intermediul figurii de mai jos.

Putem scrie starea $\vert\pi_1\rangle$ astfel:

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

Când se efectuează prima operație controlată-$U,$ valoarea proprie $\lambda = e^{2\pi i\theta}$ este lovită în fază atunci când $a_0$ (Qubit-ul de sus) este egal cu $1,$ dar nu și când este $0.$ Astfel, putem exprima starea rezultată în felul următor:

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

Al doilea și al treilea Gate controlat-$U$ fac ceva similar, dar pentru $a_1$ în loc de $a_0,$ și cu $\theta$ înlocuit prin $2\theta.$ Putem exprima starea rezultată astfel:

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

Dacă ne gândim la șirul binar $a_1 a_0$ ca reprezentând un număr întreg $x \in \{0,1,2,3\}$ în notație binară, adică $x = 2 a_1 + a_0,$ putem exprima alternativ această stare astfel:

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

Scopul nostru este să extragem cât mai multă informație despre $\theta$ din această stare.

În acest punct vom considera un caz special, în care ni se garantează că $\theta = \frac{y}{4}$ pentru un număr întreg $y\in\{0,1,2,3\}.$ Cu alte cuvinte, avem $\theta\in \{0, 1/4, 1/2, 3/4\},$ deci putem exprima acest număr exact în notație binară cu doi biți, ca .$00,$ .$01,$ .$10,$ sau .$11.$ În general, $\theta$ s-ar putea să nu fie una dintre aceste patru valori, dar gândirea la acest caz special ne va ajuta să ne dăm seama cum să extragem cât mai eficient informații despre $\theta$ în general.

Mai întâi vom defini un vector de stare cu două Qubit-uri pentru fiecare valoare posibilă $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$$

După simplificarea exponențialelor, putem scrie acești vectori astfel:

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

Acești vectori sunt ortogonali: dacă alegem orice pereche dintre ei și calculăm produsul lor interior, obținem $0.$ Fiecare este și un vector unitar, deci $\{\vert\phi_0\rangle, \vert\phi_1\rangle, \vert\phi_2\rangle, \vert\phi_3\rangle\}$ este o bază ortonormată. Știm astfel imediat că există o măsurătoare care îi poate discrimina perfect — adică, dacă ni se dă unul dintre ei fără să știm care, îl putem identifica fără eroare.

Pentru a realiza o astfel de discriminare cu un Circuit cuantic, putem defini mai întâi o operație unitară $V$ care transformă vectorii bazei standard în cele patru stări listate mai sus.

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

Pentru a scrie $V$ ca o matrice $4\times 4,$ este suficient să luăm coloanele lui $V$ ca fiind stările $\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}$$

Aceasta este o matrice specială, și este probabil că unii cititori au mai întâlnit-o: este matricea asociată transformatei Fourier discrete de dimensiune $4.$ Având în vedere acest fapt, hai să o numim $\mathrm{QFT}_4$ în loc de $V.$ Numele $\mathrm{QFT}$ este prescurtarea pentru transformata Fourier cuantică — care este în esență transformata Fourier discretă, privită ca o operație unitară. Vom discuta transformata Fourier cuantică mai în detaliu și în mai mare generalitate în curând.

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

Putem efectua inversul acestei operații pentru a merge în sens invers, transformând stările $\vert\phi_0\rangle,\ldots,\vert\phi_3\rangle$ în vectorii bazei standard $\vert 0\rangle,\ldots,\vert 3\rangle.$ Dacă facem asta, putem măsura pentru a afla care valoare $y\in\{0,1,2,3\}$ descrie $\theta$ ca $\theta = y/4.$ Iată o diagramă a unui Circuit cuantic care face acest lucru.

Pe scurt, dacă rulăm acest Circuit când $\theta = y/4$ pentru $y\in\{0,1,2,3\},$ starea imediat înainte de măsurători va fi $\vert \psi\rangle \vert y\rangle$ (cu $y$ codificat ca un șir binar de doi biți), deci măsurătorile vor dezvălui valoarea $y$ fără eroare.

Acest Circuit este motivat de cazul special în care $\theta \in \{0,1/4,1/2,3/4\}$ — dar îl putem rula pentru orice alegere de $U$ și $\vert \psi\rangle,$ și prin urmare pentru orice valoare a lui $\theta,$ dorim. Iată un grafic al probabilităților de ieșire pe care le produce Circuit-ul pentru alegeri arbitrare ale lui $\theta.$

Aceasta este o îmbunătățire clară față de varianta cu un singur Qubit descrisă mai devreme în lecție. Nu este perfectă — poate da un răspuns greșit — dar răspunsul este puternic înclinat spre valorile lui $y$ pentru care $y/4$ este aproape de $\theta.$ În particular, cel mai probabil rezultat corespunde întotdeauna celei mai apropiate valori a lui $y/4$ față de $\theta$ (asimilând $\theta = 0$ cu $\theta = 1$ ca înainte), iar din grafic se pare că această cea mai apropiată valoare pentru $x$ apare întotdeauna cu o probabilitate puțin peste $40\%.$ Când $\theta$ se află exact la jumătatea distanței dintre două astfel de valori, ca de exemplu $\theta = 0.375,$ cele două valori ale lui $y$ egal de apropiate sunt egal de probabile.

Pregătirea pentru generalizare la mai multe Qubit-uri

Dat fiind progresul pe care tocmai l-am obținut folosind două Qubit-uri de control în loc de unul, în conjuncție cu inversul transformatei Fourier cuantice de dimensiune $4,$ este firesc să ne gândim la generalizarea acestuia — prin adăugarea mai multor Qubit-uri de control. Procedând astfel, obținem procedura generală de estimare a fazei. Vom vedea în curând cum funcționează, dar pentru a o descrie cu precizie va trebui să discutăm transformata Fourier cuantică în mai mare generalitate, pentru a vedea cum este definită pentru alte dimensiuni și cum o putem implementa (sau inversul ei) cu un Circuit cuantic.

Transformata Fourier cuantică

Transformata Fourier cuantică este o operație unitară ce poate fi definită pentru orice dimensiune $N$ număr întreg pozitiv. În această secțiune, vom vedea cum este definită această operație și cum poate fi implementată cu un Circuit cuantic pe $m$ Qubit-uri cu cost $O(m^2)$ atunci când $N = 2^m.$

Matricele care descriu transformata Fourier cuantică sunt derivate dintr-o operație analogă pe vectori de dimensiune $N,$ cunoscută sub numele de transformata Fourier discretă. Această operație poate fi privită din perspective diferite. De exemplu, putem privi transformata Fourier discretă în termeni pur abstracți, matematici, ca o aplicație liniară. Sau o putem privi în termeni computaționali, unde ni se dă un vector de dimensiune $N$ de numere complexe (folosind notația binară pentru a codifica părțile reale și imaginare ale intrărilor, să presupunem) și scopul este să calculăm vectorul de dimensiune $N$ obținut prin aplicarea transformatei Fourier discrete. Atenția noastră se va concentra pe o a treia perspectivă, care privește această transformare ca o operație unitară ce poate fi efectuată pe un sistem cuantic.

Există un algoritm eficient pentru calculul transformatei Fourier discrete pe un vector de intrare dat, cunoscut sub numele de transformata Fourier rapidă. Are aplicații în procesarea semnalelor și în multe alte domenii și este considerat de mulți a fi unul dintre cei mai importanți algoritmi descoperiți vreodată. Se dovedește că implementarea transformatei Fourier cuantice atunci când $N$ este o putere a lui 2, pe care o vom studia, se bazează pe exact aceeași structură de bază care face posibilă transformata Fourier rapidă.

Definiția transformatei cuantice Fourier

Pentru a defini transformata cuantică Fourier, vom defini mai întâi un număr complex $\omega_N,$ pentru fiecare număr întreg pozitiv $N,$ astfel:

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

Acesta este numărul de pe cercul unitate complex pe care îl obținem dacă pornim de la $1$ și ne deplasăm în sens invers acelor de ceasornic cu un unghi de $2\pi/N$ radiani, adică o fracțiune de $1/N$ din circumferința cercului. Iată câteva exemple:

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

Acum putem defini transformata cuantică Fourier de dimensiune $N$, care este descrisă de o matrice $N\times N$ ale cărei linii și coloane sunt asociate cu stările bazei standard $\vert 0\rangle,\ldots,\vert N-1\rangle.$ Vom avea nevoie de această operație doar atunci când $N = 2^m$ este o putere a lui $2$ pentru estimarea fazei, dar operația poate fi definită pentru orice număr întreg pozitiv $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$$

Așa cum s-a menționat deja, aceasta este matricea asociată cu transformata Fourier discretă de dimensiune $N$. De regulă, factorul $1/\sqrt{N}$ nu este inclus în definiția acestei matrice, dar trebuie să îl includem pentru a obține o matrice unitară.

Iată transformata cuantică Fourier, scrisă ca matrice, pentru câteva valori mici ale lui $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}$$

De remarcat, în special, că $\mathrm{QFT}_2$ este un alt nume pentru operația Hadamard.

Unitaritate

Să verificăm că $\mathrm{QFT}_N$ este unitară, pentru orice alegere a lui $N.$ O modalitate de a face acest lucru este să arătăm că coloanele sale formează o bază ortonormală. Putem defini un vector corespunzător coloanei cu numărul $y,$ începând de la $y = 0$ și mergând până la $y = N-1,$ astfel:

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

Calculând produsul intern dintre oricare doi astfel de vectori, obținem expresia:

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

Putem evalua sume de acest tip folosind formula pentru suma primilor $N$ termeni ai unei serii geometrice.

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

Mai exact, putem folosi această formulă când $\alpha = \omega_N^{y-z}.$ Când $y = z,$ avem $\alpha = 1,$ deci aplicând formula și împărțind la $N$ obținem

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

Când $y\neq z,$ avem $\alpha \neq 1,$ deci formula ne arată că:

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

Acest lucru se întâmplă deoarece $\omega_N^N = e^{2\pi i} = 1,$ deci $\omega_N^{N(y-z)} = 1^{y-z} = 1,$ făcând numărătorul zero, în timp ce numitorul este nenul deoarece $\omega_N^{y-z} \neq 1.$ Intuitiv, ceea ce facem este să sumăm o serie de puncte distribuite în jurul cercului unitate, iar ele se anulează reciproc și dau $0$ la sumare.

Am demonstrat astfel că $\{\vert\phi_0\rangle,\ldots,\vert\phi_{N-1}\rangle\}$ este o mulțime ortonormală,

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

ceea ce arată că $\mathrm{QFT}_N$ este unitară.

Porți de fază controlate

Pentru a implementa transformata cuantică Fourier cu un Circuit cuantic, va trebui să folosim porți de fază controlată. Reamintim că o operație de fază este o operație unitară pe un singur Qubit de forma

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

pentru orice număr real $\alpha.$ O versiune controlată a acestei Gate are matricea:

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

Pentru această Gate controlată, nu contează de fapt care Qubit este controlul și care este ținta, deoarece cele două variante sunt echivalente. Putem folosi oricare dintre simbolurile de mai jos pentru a reprezenta această Gate în diagramele de Circuit cuantic.

Pentru a treia formă, eticheta $\alpha$ este uneori plasată și pe latura liniei de control sau sub controlul inferior, atunci când este mai convenabil.

Pentru a realiza transformata cuantică Fourier când $N = 2^m$ și $m\geq 2,$ va trebui să efectuăm o operație pe $m$ Qubiți a cărei acțiune pe stările bazei standard poate fi descrisă ca

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

unde $a$ este un bit și $y \in \{0,\ldots,2^{m-1} - 1\}$ este un număr codificat în notație binară ca un șir de $m-1$ biți. Acest lucru poate fi realizat folosind porți de fază controlată, generalizând exemplul de mai jos, pentru care $m=5.$

În general, pentru o alegere arbitrară a lui $m\geq 2,$ Qubitul de sus corespunzând bitului $a$ poate fi privit drept control, cu porțile de fază $P_{\alpha}$ variind de la $\alpha = \pi/2^{m-1}$ pe Qubitul corespunzând bitului cel mai puțin semnificativ al lui $y$ până la $\alpha = \frac{\pi}{2}$ pe Qubitul corespunzând bitului cel mai semnificativ al lui $y.$ Aceste porți de fază controlată comutează toate între ele și pot fi aplicate în orice ordine.

Implementarea circuitului pentru QFT

Acum vom vedea cum putem implementa transformata Fourier cuantică cu un circuit atunci când dimensiunea $N = 2^m$ este o putere a lui $2.$ Există, de fapt, mai multe moduri de a implementa transformata Fourier cuantică, dar aceasta este probabil cea mai simplă metodă cunoscută. Odată ce știm cum să implementăm transformata Fourier cuantică cu un circuit cuantic, implementarea inversului este simplă: putem înlocui fiecare poartă cu inversul ei (sau, echivalent, cu transpusa conjugată) și aplica porțile în ordine inversă. Orice circuit cuantic compus exclusiv din porți unitare poate fi inversat în acest mod.

Implementarea este recursivă prin natură, deci aceasta este și cea mai naturală modalitate de a o descrie. Cazul de bază este $m=1,$ caz în care transformata Fourier cuantică este o operație Hadamard.

Pentru a efectua transformata Fourier cuantică pe $m$ qubiți când $m \geq 2,$ putem urma pașii de mai jos, ale căror acțiuni le vom descrie pentru stările bazei standard de forma $\vert x \rangle \vert a\rangle,$ unde $x\in\{0,\ldots,2^{m-1} - 1\}$ este un întreg codificat pe $m-1$ biți în notație binară și $a$ este un singur bit.

1. Mai întâi aplică transformata Fourier cuantică de dimensiune $2^{m-1}$ pe cei $m-1$ qubiți din stânga/de jos pentru a obține această stare:

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

   Acest lucru se face aplicând recursiv metoda descrisă pentru cu un qubit mai puțin, folosind operația Hadamard pe un singur qubit drept caz de bază.

2. Folosește qubitul din dreapta/de sus drept control pentru a injecta faza $\omega_{2^m}^y$ pentru fiecare stare a bazei standard $\vert y\rangle$ a celor $m-1$ qubiți rămași (după cum este descris mai sus) pentru a obține această stare:

   $$\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. Aplică o poartă Hadamard pe qubitul din dreapta/de sus pentru a obține această stare:

   $$\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. Permută ordinea qubiților astfel încât bitul cel mai puțin semnificativ să devină bitul cel mai semnificativ, cu toți ceilalți deplasați în sus/dreapta:

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

De exemplu, iată circuitul obținut pentru $N = 32 = 2^5.$ În această diagramă, qubiților li se dau nume care corespund vectorilor bazei standard $\vert x\rangle \vert a\rangle$ (pentru intrare) și $\vert b\rangle \vert y\rangle$ (pentru ieșire), pentru claritate.

Analiză

Formula cheie de care avem nevoie pentru a verifica că circuitul tocmai descris implementează transformata Fourier cuantică de dimensiune $2^m$ este aceasta:

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

Această formulă este valabilă pentru orice alegere a întregilor $a,$ $b,$ $x,$ și $y,$ dar o vom folosi doar pentru $a,b\in\{0,1\}$ și $x,y\in\{0,\ldots,2^{m-1}-1\}.$ Se poate verifica expandând produsul din exponent din membrul drept,

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

unde a doua egalitate utilizează observația că

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

Transformata Fourier cuantică de dimensiune $2^m$ este definită după cum urmează pentru orice $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$$

Dacă scriem $u$ și $v$ ca

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

pentru $a,b\in\{0,1\}$ și $x,y\in\{0,\ldots,2^{m-1} - 1\},$ obținem

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

În final, gândindu-ne la stările bazei standard $\vert x \rangle \vert a\rangle$ și $\vert b \rangle \vert y \rangle$ ca la codificări binare ale unor întregi din intervalul $\{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}$$

vedem că circuitul de mai sus implementează operația necesară. Dacă această metodă de a efectua transformata Fourier cuantică ți se pare remarcabilă, este pentru că și este: este în esență transformata Fourier rapidă sub forma unui circuit cuantic.

În final, să numărăm câte porți sunt utilizate în circuitul tocmai descris. Porțile de fază controlată nu fac parte din setul standard de porți discutat în lecția anterioară, dar pentru început vom ignora acest lucru și vom număra fiecare dintre ele ca o singură poartă.

Fie $s_m$ numărul de porți necesare pentru fiecare alegere posibilă a lui $m.$ Dacă $m=1,$ transformata Fourier cuantică este doar o operație Hadamard, deci

$$s_1 = 1.$$

Dacă $m\geq 2,$ atunci în circuitul de mai sus avem nevoie de $s_{m-1}$ porți pentru transformata Fourier cuantică pe $m-1$ qubiți, plus $m-1$ porți de fază controlată, plus o poartă Hadamard, plus $m-1$ porți swap, deci

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

Putem obține o expresie de formă închisă prin sumare:

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

De fapt, nu avem nevoie de atâtea porți swap câte descrie metoda. Dacă rearanjăm ușor porțile, putem împinge toate porțile swap spre dreapta și reduce numărul de porți swap necesare la $\lfloor m/2\rfloor.$ Asimptotic vorbind, aceasta nu este o îmbunătățire majoră: obținem în continuare circuite cu dimensiunea $O(m^2)$ pentru efectuarea lui $\mathrm{QFT}_{2^m}.$

Dacă dorim să implementăm transformata Fourier cuantică folosind numai porți din setul nostru standard, trebuie să construim sau să aproximăm fiecare dintre porțile de fază controlată cu porți din setul nostru. Numărul necesar depinde de cât de multă precizie cerem, dar ca funcție de $m$ costul total rămâne pătratic.

Este, de fapt, posibil să aproximăm transformata Fourier cuantică destul de precis cu un număr sub-pătratic de porți, folosind faptul că $P_{\alpha}$ este foarte aproape de operația identitate când $\alpha$ este foarte mic — ceea ce înseamnă că putem pur și simplu omite majoritatea porților de fază controlată fără a suferi o pierdere prea mare în termeni de precizie.

Procedura generală și analiza

Acum vom examina procedura de estimare a fazei în general. Ideea este de a extinde versiunea cu doi qubiți a estimării fazei pe care am considerat-o mai sus, în modul natural sugerat de diagrama următoare.

Observă că, pentru fiecare qubit de control adăugat în partea de sus, dublăm numărul de ori în care operația unitară $U$ este efectuată. Acest lucru este indicat în diagramă prin puterile lui $U$ pentru fiecare dintre operațiile unitare controlate.

Cel mai simplu mod de a implementa o operație controlată-$U^k$ pentru o alegere oarecare a lui $k$ este pur și simplu să repete o operație controlată-$U$ de $k$ ori. Dacă aceasta este într-adevăr metodologia folosită, trebuie recunoscut că adăugarea qubiților de control contribuie semnificativ la dimensiunea circuitului: dacă avem $m$ qubiți de control, precum descrie diagrama, sunt necesare în total $2^m - 1$ copii ale operației controlate-$U$. Aceasta înseamnă că un cost computațional semnificativ este generat pe măsură ce $m$ crește — dar, după cum vom vedea, duce și la o aproximare semnificativ mai precisă a lui $\theta.$

Este important de menționat, totuși, că pentru unele alegeri ale lui $U$ ar putea fi posibil să creezi un circuit care implementează operația $U^k$ pentru valori mari ale lui $k$ într-un mod mai eficient decât simpla repetare de $k$ ori a circuitului pentru $U.$ Vom vedea un exemplu specific în contextul factorizării întregi mai târziu în lecție, unde algoritmul eficient pentru exponențierea modulară discutat în lecția anterioară vine în ajutor.

Acum să analizăm circuitul tocmai descris. Starea imediat înainte de transformata Fourier cuantică inversă arată astfel:

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

Similar cu ceea ce am făcut în cazul $m=2$, vom lua în considerare mai întâi cazul special în care $\theta = y/2^m$ pentru $y\in\{0,\ldots,2^m-1\}.$ În acest caz, starea anterioară transformatei cuantice Fourier inverse poate fi scrisă alternativ astfel:

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

Astfel, când se aplică transformata cuantică Fourier inversă, starea devine

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

iar măsurătorile dezvăluie $y$ (codificat în binar).

Mărginirea probabilităților

Pentru alte valori ale lui $\theta,$ adică cele care nu iau forma $y/2^m$ pentru un întreg $y,$ rezultatele măsurătorilor nu vor fi certe, dar putem demonstra limite asupra probabilităților pentru diferite rezultate. În continuare, să considerăm o alegere arbitrară a lui $\theta$ care satisface $0\leq \theta < 1.$

După efectuarea transformatei cuantice Fourier inverse, starea circuitului este aceasta:

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

Prin urmare, când se efectuează măsurătorile pe primii $m$ qubiți, observăm fiecare rezultat $y$ cu probabilitatea

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

Pentru a înțelege mai bine aceste probabilități, vom folosi aceeași formulă pe care am văzut-o anterior, pentru suma porțiunii inițiale a unei serii geometrice.

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

Putem simplifica suma care apare în formula pentru $p_y$ luând $\alpha = e^{2\pi i (\theta - y/2^m)}.$ Iată ce obținem.

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

Astfel, în cazul în care $\theta = y/2^m,$ găsim că $p_y = 1$ (cum știam deja din considerarea acestui caz special), iar în cazul în care $\theta \neq y/2^m,$ găsim că

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

Putem afla mai multe despre aceste probabilități gândindu-ne la relația dintre lungimile arcelor și lungimile coardelor pe cercul unitar. Iată o figură care ilustrează relațiile de care avem nevoie pentru orice număr real $\delta\in \bigl[ -\frac{1}{2},\frac{1}{2}\bigr].$

În primul rând, lungimea coardei (desenată în albastru) nu poate fi mai mare decât lungimea arcului (desenată în violet):

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

Raportând aceste lungimi în cealaltă direcție, observăm că raportul dintre lungimea arcului și lungimea coardei este maxim când $\delta = \pm 1/2,$ iar în acest caz raportul este jumătate din circumferința cercului împărțită la diametru, adică $\pi/2.$ Astfel, avem

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

și deci

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

O analiză bazată pe aceste relații dezvăluie următoarele două fapte.

1. Presupune că $\theta$ este un număr real și $y\in \{0,\ldots,2^m-1\}$ satisface

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

   Aceasta înseamnă că $y/2^m$ este fie cea mai bună aproximare cu $m$ biți a lui $\theta,$ fie se află exact la mijloc între $y/2^m$ și $(y-1)/2^m$ sau $(y+1)/2^m,$ deci este una dintre cele mai bune două aproximări ale lui $\theta.$

   Vom demonstra că $p_y$ trebuie să fie destul de mare în acest caz. Din ipoteza pe care o considerăm, rezultă că $\vert 2^m \theta - y \vert \leq 1/2,$ deci putem folosi a doua observație de mai sus privind lungimile arcelor și coardelor pentru a concluziona că

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

   Putem folosi de asemenea prima observație despre lungimile arcelor și coardelor pentru a concluziona că

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

   Folosind aceste două inegalități pentru $p_y$ obținem

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

   Aceasta explică observația noastră că cel mai bun rezultat apare cu probabilitate mai mare de $40\%$ în versiunea $m=2$ a estimării de fază discutată anterior. Nu este chiar 40%, ci $4/\pi^2,$ și de fapt această limită se menține pentru orice alegere a lui $m.$

2. Acum presupune că $y\in \{0,\ldots,2^m-1\}$ satisface

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

   Aceasta înseamnă că există o aproximare mai bună $z/2^m$ a lui $\theta$ între $\theta$ și $y/2^m.$

   De această dată vom demonstra că $p_y$ nu poate fi prea mare. Putem începe cu observația simplă că

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

   care rezultă din faptul că oricare două puncte de pe cercul unitar pot diferi în valoare absolută cu cel mult $2.$

   Putem folosi de asemenea a doua observație despre lungimile arcelor și coardelor de mai sus, de această dată lucrând cu numitorul lui $p_y$ în loc de numărător, pentru a concluziona

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

   Combinând cele două inegalități obținem

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

   De remarcat că, deși această limită este suficient de bună pentru scopurile noastre, ea este destul de brută — probabilitatea este de obicei mult mai mică decât $1/4.$

Concluzia importantă a acestei analize este că aproximările foarte apropiate ale lui $\theta$ au probabilitate mare să apară — vom obține cea mai bună aproximare cu $m$ biți cu probabilitate mai mare de $40\%$ — în timp ce aproximările care diferă cu mai mult de $2^{-m}$ au probabilitate mai mică să apară, cu probabilitate mărginită superior de $25\%.$

Având aceste garanții, este posibil să ne creștem încrederea repetând procedura de estimare a fazei de mai multe ori, pentru a aduna dovezi statistice despre $\theta.$ Este important de remarcat că starea $\vert\psi\rangle$ a colecției inferioare de qubiți rămâne neschimbată de procedura de estimare a fazei, deci poate fi folosită pentru a rula procedura de câte ori dorim. În particular, de fiecare dată când rulăm circuitul, obținem cea mai bună aproximare cu $m$ biți a lui $\theta$ cu probabilitate mai mare de $40\%,$ în timp ce probabilitatea de a fi în afara cu mai mult de $2^{-m}$ este mărginită de $25\%.$ Dacă rulăm circuitul de mai multe ori și luăm cel mai frecvent rezultat care apare, este prin urmare extrem de probabil că rezultatul care apare cel mai des nu va fi unul care apare în cel mult $25\%$ din cazuri. Ca urmare, vom obține cu mare probabilitate o aproximare $y/2^m$ care se află la distanță mai mică de $1/2^m$ față de valoarea $\theta.$ Într-adevăr, probabilitatea mică de a fi în afara cu mai mult de $1/2^m$ scade exponențial cu numărul de ori în care se rulează procedura.

Iată două grafice care arată probabilitățile pentru trei valori consecutive ale lui $y$ când $m = 3$ și $m=4$ ca funcții de $\theta.$ (Doar trei rezultate sunt afișate pentru claritate. Probabilitățile pentru celelalte rezultate se obțin prin deplasarea ciclică a aceleiași funcții subiacente.)