Algoritmul lui Shor

Acum ne vom îndrepta atenția spre problema factorizării numerelor întregi și vom vedea cum poate fi rezolvată eficient pe un calculator cuantic folosind estimarea de fază. Algoritmul pe care îl vom obține este algoritmul lui Shor pentru factorizarea numerelor întregi. Shor nu și-a descris algoritmul în mod specific în termenii estimării de fază, dar aceasta este o modalitate naturală și intuitivă de a explica cum funcționează.

Vom începe prin a discuta o problemă intermediară cunoscută drept problema găsirii ordinului și vom vedea cum estimarea de fază oferă o soluție pentru această problemă. Vom vedea apoi cum o soluție eficientă la problema găsirii ordinului ne oferă o soluție eficientă la problema factorizării numerelor întregi. (Când o soluție la o problemă oferă o soluție la altă problemă în acest mod, spunem că a doua problemă se reduce la prima — astfel, în acest caz reducem factorizarea numerelor întregi la găsirea ordinului.) Această a doua parte a algoritmului lui Shor nu folosește deloc calculul cuantic; este complet clasică. Calculul cuantic este necesar doar pentru a rezolva găsirea ordinului.

Problema găsirii ordinului

Câteva noțiuni de bază din teoria numerelor

Pentru a explica problema găsirii ordinului și cum poate fi rezolvată folosind estimarea de fază, va fi util să începem cu câteva concepte de bază din teoria numerelor și să introducem pe parcurs o notație convenabilă.

Pentru început, pentru orice număr întreg pozitiv $N$, definim mulțimea $\mathbb{Z}_N$ astfel.

$$\mathbb{Z}_N = \{0,1,\ldots,N-1\}$$

De exemplu, $\mathbb{Z}_1 = \{0\},\;$ $\mathbb{Z}_2 = \{0,1\},\;$ $\mathbb{Z}_3 = \{0,1,2\},\;$ și așa mai departe.

Acestea sunt mulțimi de numere, dar le putem privi ca mai mult decât simple mulțimi. În particular, putem gândi despre operații aritmetice în $\mathbb{Z}_N$ cum ar fi adunarea și înmulțirea — și dacă suntem de acord să luăm mereu rezultatele modulo $N$ (adică să împărțim la $N$ și să luăm restul ca rezultat), vom rămâne mereu în această mulțime atunci când efectuăm aceste operații. Cele două operații specifice de adunare și înmulțire, ambele luate modulo $N$, transformă $\mathbb{Z}_N$ într-un inel, care este un tip de obiect fundamental important în algebră.

De exemplu, $3$ și $5$ sunt elemente ale lui $\mathbb{Z}_7,$ iar dacă le înmulțim obținem $3\cdot 5 = 15,$ care lasă un rest de $1$ la împărțirea cu $7.$ Uneori exprimăm aceasta astfel.

$$3 \cdot 5 \equiv 1 \; (\textrm{mod } 7)$$

Dar putem scrie și simplu $3 \cdot 5 = 1$, cu condiția să fie clar că lucrăm în $\mathbb{Z}_7$, doar pentru a menține notația cât mai simplă.

Ca exemplu, iată tabelele de adunare și înmulțire pentru $\mathbb{Z}_6$.

$$\begin{array}{c|cccccc} + & 0 & 1 & 2 & 3 & 4 & 5 \\\hline 0 & 0 & 1 & 2 & 3 & 4 & 5 \\ 1 & 1 & 2 & 3 & 4 & 5 & 0 \\ 2 & 2 & 3 & 4 & 5 & 0 & 1 \\ 3 & 3 & 4 & 5 & 0 & 1 & 2 \\ 4 & 4 & 5 & 0 & 1 & 2 & 3 \\ 5 & 5 & 0 & 1 & 2 & 3 & 4 \\ \end{array} \qquad \begin{array}{c|cccccc} \cdot & 0 & 1 & 2 & 3 & 4 & 5 \\\hline 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 1 & 2 & 3 & 4 & 5 \\ 2 & 0 & 2 & 4 & 0 & 2 & 4 \\ 3 & 0 & 3 & 0 & 3 & 0 & 3 \\ 4 & 0 & 4 & 2 & 0 & 4 & 2 \\ 5 & 0 & 5 & 4 & 3 & 2 & 1 \\ \end{array}$$

Dintre cele $N$ elemente ale lui $\mathbb{Z}_N$, elementele $a\in\mathbb{Z}_N$ care satisfac $\gcd(a,N) = 1$ sunt speciale. Adesea, mulțimea ce conține aceste elemente este notată cu un asterisc astfel.

$$\mathbb{Z}_N^{\ast} = \{a\in \mathbb{Z}_N : \gcd(a,N) = 1\}$$

Dacă ne concentrăm atenția pe operația de înmulțire, mulțimea $\mathbb{Z}_N^{\ast}$ formează un grup — mai specific un grup abelian — care este un alt tip important de obiect în algebră. Este un fapt de bază despre aceste mulțimi (și despre grupurile finite în general) că, dacă alegem orice element $a\in\mathbb{Z}_N^{\ast}$ și îl înmulțim repetat cu el însuși, vom obține întotdeauna în cele din urmă numărul $1$.

Ca prim exemplu, să luăm $N=6$. Avem că $5\in\mathbb{Z}_6^{\ast}$ deoarece $\gcd(5,6) = 1$, iar dacă înmulțim $5$ cu el însuși obținem $1$, după cum confirmă tabelul de mai sus.

$$5^2 = 1 \quad \text{(lucrând în $\mathbb{Z}_6$)}$$

Ca al doilea exemplu, să luăm $N = 21$. Dacă parcurgem numerele de la $0$ la $20$, cele care au CMMDC egal cu $1$ față de $21$ sunt următoarele.

$$\mathbb{Z}_{21}^{\ast} = \{1,2,4,5,8,10,11,13,16,17,19,20\}$$

Pentru fiecare dintre aceste elemente, este posibil să ridicăm acel număr la o putere întreagă pozitivă pentru a obține $1$. Iată cele mai mici puteri pentru care acest lucru funcționează:

$$\begin{array}{ccc} 1^{1} = 1 \quad & 8^{2} = 1 \quad & 16^{3} = 1 \\[1mm] 2^{6} = 1 \quad & 10^{6} = 1 \quad & 17^{6} = 1 \\[1mm] 4^{3} = 1 \quad & 11^{6} = 1 \quad & 19^{6} = 1 \\[1mm] 5^{6} = 1 \quad & 13^{2} = 1 \quad & 20^{2} = 1 \end{array}$$

Firește, lucrăm în $\mathbb{Z}_{21}$ pentru toate aceste ecuații, lucru pe care nu ne-am mai obosit să îl scriem — îl considerăm implicit pentru a evita aglomerarea notației. Vom continua să procedăm astfel pe tot parcursul restului lecției.

Enunțul problemei și legătura cu estimarea fazei

Acum putem formula problema găsirii ordinului.

Găsirea ordinului

Date de intrare: numerele întregi pozitive $N$ și $a$ cu proprietatea că $\gcd(N,a) = 1$
Date de ieșire: cel mai mic număr întreg pozitiv $r$ astfel încât $a^r \equiv 1$ $(\textrm{mod } N)$

Alternativ, în termenii notației pe care tocmai am introdus-o mai sus, ni se dă $a \in \mathbb{Z}_N^{\ast}$, și căutăm cel mai mic număr întreg pozitiv $r$ astfel încât $a^r = 1$. Acest număr $r$ se numește ordinul lui $a$ modulo $N$.

Pentru a conecta problema găsirii ordinului cu estimarea fazei, să ne gândim la operația definită pe un sistem ale cărui stări clasice corespund lui $\mathbb{Z}_N$, în care înmulțim cu un element fix $a\in\mathbb{Z}_N^{\ast}$.

$$M_a \vert x\rangle = \vert ax \rangle \qquad \text{(pentru fiecare $x\in\mathbb{Z}_N$)}$$

Precizăm că înmulțirea se face în $\mathbb{Z}_N$, deci este implicit că luăm produsul modulo $N$ în interiorul ket-ului din membrul drept al ecuației.

De exemplu, dacă luăm $N = 15$ și $a=2$, atunci acțiunea lui $M_2$ asupra bazei standard $\{\vert 0\rangle,\ldots,\vert 14\rangle\}$ este următoarea.

$$\begin{array}{ccc} M_{2} \vert 0 \rangle = \vert 0\rangle \quad & M_{2} \vert 5 \rangle = \vert 10\rangle \quad & M_{2} \vert 10 \rangle = \vert 5\rangle \\[1mm] M_{2} \vert 1 \rangle = \vert 2\rangle \quad & M_{2} \vert 6 \rangle = \vert 12\rangle \quad & M_{2} \vert 11 \rangle = \vert 7\rangle \\[1mm] M_{2} \vert 2 \rangle = \vert 4\rangle \quad & M_{2} \vert 7 \rangle = \vert 14\rangle \quad & M_{2} \vert 12 \rangle = \vert 9\rangle \\[1mm] M_{2} \vert 3 \rangle = \vert 6\rangle \quad & M_{2} \vert 8 \rangle = \vert 1\rangle \quad & M_{2} \vert 13 \rangle = \vert 11\rangle \\[1mm] M_{2} \vert 4 \rangle = \vert 8\rangle \quad & M_{2} \vert 9 \rangle = \vert 3\rangle \quad & M_{2} \vert 14 \rangle = \vert 13\rangle \end{array}$$

Aceasta este o operație unitară cu condiția că $\gcd(a,N)=1$; ea permută elementele bazei standard $\{\vert 0\rangle,\ldots,\vert N-1\rangle\}$, deci ca matrice este o matrice de permutare. Din definiția sa reiese că această operație este deterministă, iar un mod simplu de a vedea că este inversabilă este să te gândești la ordinul $r$ al lui $a$ modulo $N$ și să observi că inversa lui $M_a$ este $M_a^{r-1}$.

$$M_a^{r-1} M_a = M_a^r = M_{a^r} = M_1 = \mathbb{I}$$

Există și un alt mod de a gândi inversa, care nu necesită cunoașterea lui $r$ (care, la urma urmei, este ceea ce încercăm să calculăm). Pentru orice element $a\in\mathbb{Z}_N^{\ast}$ există întotdeauna un element unic $b\in\mathbb{Z}_N^{\ast}$ care satisface $ab=1$. Notăm acest element $b$ prin $a^{-1}$, și el poate fi calculat eficient; o extensie a algoritmului lui Euclid pentru cel mai mare divizor comun o face cu un cost pătratic în $\operatorname{lg}(N)$. Și astfel

$$M_{a^{-1}} M_a = M_{a^{-1}a} = M_1 = \mathbb{I}.$$

Prin urmare, operația $M_a$ este atât deterministă, cât și inversabilă. Aceasta implică faptul că este descrisă de o matrice de permutare și, prin urmare, este unitară.

Acum să ne gândim la vectorii proprii și valorile proprii ale operației $M_a$, presupunând că $a\in\mathbb{Z}_N^{\ast}$. Cum tocmai am argumentat, această presupunere ne spune că $M_a$ este unitară.

$M_a$ are $N$ valori proprii, posibil incluzând aceeași valoare proprie repetată de mai multe ori, și în general există o anumită libertate în alegerea vectorilor proprii corespunzători — dar nu va trebui să ne facem griji în legătură cu toate posibilitățile. Să începem simplu și să identificăm doar un vector propriu al lui $M_a$.

$$\vert \psi_0 \rangle = \frac{\vert 1 \rangle + \vert a \rangle + \cdots + \vert a^{r-1} \rangle}{\sqrt{r}}$$

Numărul $r$ este ordinul lui $a$ modulo $N$, aici și pe tot parcursul restului lecției. Valoarea proprie asociată acestui vector propriu este $1$, deoarece acesta nu se modifică când înmulțim cu $a$.

$$M_a \vert \psi_0 \rangle = \frac{\vert a \rangle + \cdots + \vert a^{r-1} \rangle + \vert a^r \rangle}{\sqrt{r}} = \frac{\vert a \rangle + \cdots + \vert a^{r-1} \rangle + \vert 1 \rangle}{\sqrt{r}} = \vert \psi_0 \rangle$$

Aceasta se întâmplă deoarece $a^r = 1$, astfel încât fiecare stare a bazei standard $\vert a^k \rangle$ este deplasată la $\vert a^{k+1} \rangle$ pentru $k\leq r-1$, iar $\vert a^{r-1} \rangle$ este deplasată înapoi la $\vert 1\rangle$. Informal vorbind, e ca și cum am amesteca ușor $\vert \psi_0 \rangle$, dar acesta este deja complet amestecat, deci nimic nu se schimbă.

Iată un alt exemplu de vector propriu al lui $M_a$. Acesta este mai interesant în contextul găsirii ordinului și al estimării fazei.

$$\vert \psi_1 \rangle = \frac{\vert 1 \rangle + \omega_r^{-1} \vert a \rangle + \cdots + \omega_r^{-(r-1)}\vert a^{r-1} \rangle}{\sqrt{r}}$$

Alternativ, putem scrie acest vector folosind o sumă astfel.

$$\vert \psi_1 \rangle = \frac{1}{\sqrt{r}} \sum_{k = 0}^{r-1} \omega_r^{-k} \vert a^k \rangle$$

Observăm că numărul complex $\omega_r = e^{2\pi i/r}$ apare în mod natural, datorită modului în care funcționează înmulțirea cu $a$ modulo $N$. De această dată valoarea proprie corespunzătoare este $\omega_r$. Pentru a vedea aceasta, putem calcula mai întâi astfel.

$$M_a \vert \psi_1 \rangle = \frac{1}{\sqrt{r}}\sum_{k = 0}^{r-1} \omega_r^{-k} M_a\vert a^k \rangle = \frac{1}{\sqrt{r}}\sum_{k = 0}^{r-1} \omega_r^{-k} \vert a^{k+1} \rangle = \frac{1}{\sqrt{r}}\sum_{k = 1}^{r} \omega_r^{-(k - 1)} \vert a^{k} \rangle = \frac{1}{\sqrt{r}}\omega_r \sum_{k = 1}^{r} \omega_r^{-k} \vert a^{k} \rangle$$

Apoi, deoarece $\omega_r^{-r} = 1 = \omega_r^0$ și $\vert a^r \rangle = \vert 1\rangle = \vert a^0\rangle$, observăm că

$$\frac{1}{\sqrt{r}}\sum_{k = 1}^{r} \omega_r^{-k} \vert a^{k} \rangle = \frac{1}{\sqrt{r}}\sum_{k = 0}^{r-1} \omega_r^{-k} \vert a^k \rangle = \vert\psi_1\rangle,$$

so $M_a \vert\psi_1\rangle = \omega_r \vert\psi_1\rangle$.

Folosind același raționament, putem identifica perechi suplimentare vector propriu/valoare proprie pentru $M_a$. Pentru orice alegere $j\in\{0,\ldots,r-1\}$ avem că

$$\vert \psi_j \rangle = \frac{1}{\sqrt{r}} \sum_{k = 0}^{r-1} \omega_r^{-jk} \vert a^k \rangle$$

este un vector propriu al lui $M_a$ a cărui valoare proprie corespunzătoare este $\omega_r^j$.

$$M_a \vert \psi_j \rangle = \omega_r^j \vert \psi_j \rangle$$

Există și alți vectori proprii ai lui $M_a$, dar nu trebuie să ne preocupăm de ei — ne vom concentra exclusiv pe vectorii proprii $\vert\psi_0\rangle,\ldots,\vert\psi_{r-1}\rangle$ pe care tocmai i-am identificat.

Găsirea ordinului prin estimarea fazei

Pentru a rezolva problema găsirii ordinului pentru o alegere dată de $a\in\mathbb{Z}_N^{\ast}$, putem aplica procedura de estimare a fazei operației $M_a$.

Pentru a face asta, trebuie să implementăm eficient cu un circuit cuantic nu doar $M_a,$ ci și $M_a^2,$ $M_a^4,$ $M_a^8,$ și așa mai departe, mergând atât de departe cât este necesar pentru a obține o estimare suficient de precisă din procedura de estimare a fazei. Aici vom explica cum poate fi realizat acest lucru, iar mai târziu vom determina exact câtă precizie este necesară.

Să începem cu operația $M_a$ în sine. În mod natural, deoarece lucrăm cu modelul Circuit cuantic, vom folosi notația binară pentru a codifica numerele dintre $0$ și $N-1$. Cel mai mare număr pe care trebuie să-l codificăm este $N-1$, deci numărul de biți de care avem nevoie este

$$n = \operatorname{lg}(N-1) = \lfloor \log(N-1) \rfloor + 1.$$

De exemplu, dacă $N = 21$ avem $n = \operatorname{lg}(N-1) = 5$. Iată cum arată codificarea elementelor lui $\mathbb{Z}_{21}$ ca șiruri binare de lungime $5$.

$$\begin{gathered} 0 \mapsto 00000\\[1mm] 1 \mapsto 00001\\[1mm] \vdots\\[1mm] 20 \mapsto 10100 \end{gathered}$$

Și acum, iată o definiție precisă a felului în care $M_a$ este definit ca o operație pe $n$ Qubiți.

$$M_a \vert x\rangle = \begin{cases} \vert ax \; (\textrm{mod}\;N)\rangle & 0\leq x < N\\[1mm] \vert x\rangle & N\leq x < 2^n \end{cases}$$

Ideea este că, deși ne interesează doar cum funcționează $M_a$ pentru $\vert 0\rangle,\ldots,\vert N-1\rangle$, trebuie totuși să specificăm cum funcționează pentru celelalte $2^n - N$ stări din baza standard — și trebuie să facem asta într-un mod care să ne ofere în continuare o operație unitară. Definind $M_a$ astfel încât să nu facă nimic pentru stările rămase din baza standard, se îndeplinește această cerință.

Folosind algoritmii pentru înmulțirea și împărțirea numerelor întregi discutați în lecția anterioară, împreună cu metodologia pentru implementări reversibile și fără reziduuri ale acestora, putem construi un circuit cuantic care realizează $M_a$, pentru orice alegere de $a\in\mathbb{Z}_N^{\ast}$, la cost $O(n^2)$. Iată o modalitate prin care aceasta poate fi realizată.

1. Construiești un circuit pentru a realiza operația

   $$\vert x \rangle \vert y \rangle \mapsto \vert x \rangle \vert y \oplus f_a(x)\rangle$$

   unde

   $$f_a(x) = \begin{cases} ax \; (\textrm{mod}\;N) & 0\leq x < N\\[1mm] x & N\leq x < 2^n \end{cases}$$

   folosind metoda descrisă în lecția anterioară. Aceasta ne oferă un circuit de dimensiune $O(n^2)$.

2. Interschimbi cele două sisteme de $n$ Qubiți folosind $n$ Gate-uri swap pentru a interschimba Qubiții individual.

3. În mod similar cu primul pas, construiești un circuit pentru operația

   $$\vert x \rangle \vert y \rangle \mapsto \vert x \rangle \bigl\vert y \oplus f_{a^{-1}}(x)\bigr\rangle$$

   unde $a^{-1}$ este inversul lui $a$ în $\mathbb{Z}_N^{\ast}$.

Prin inițializarea celor $n$ Qubiți de jos și compunerea celor trei pași, obținem această transformare:

$$\vert x \rangle \vert 0^n \rangle \stackrel{\text{step 1}}{\mapsto} \vert x \rangle \vert f_a(x)\rangle \stackrel{\text{step 2}}{\mapsto} \vert f_a(x)\rangle \vert x \rangle \stackrel{\text{step 3}}{\mapsto} \vert f_a(x)\rangle \bigl\vert x \oplus f_{a^{-1}}(f_a(x)) \bigr\rangle = \vert f_a(x)\rangle\vert 0^n \rangle$$

Metoda necesită Qubiți de spațiu de lucru, dar aceștia sunt returnați la starea lor inițializată la final, ceea ce ne permite să folosim aceste circuite pentru estimarea fazei. Costul total al circuitului obținut este $O(n^2)$.

Pentru a realiza $M_a^2,$ $M_a^4,$ $M_a^8,$ și așa mai departe, putem folosi exact aceeași metodă, cu excepția că înlocuim $a$ cu $a^2,$ $a^4,$ $a^8,$ și așa mai departe, ca elemente ale lui $\mathbb{Z}_N^{\ast}.$ Adică, pentru orice putere $k$ pe care o alegem, putem crea un circuit pentru $M_a^k$ nu prin iterarea de $k$ ori a circuitului pentru $M_a,$ ci prin calcularea $b = a^k \in \mathbb{Z}_N^{\ast}$ și apoi folosirea circuitului pentru $M_b.$

Calculul puterilor $a^k \in \mathbb{Z}_N$ este problema exponențierii modulare menționată în lecția anterioară. Acest calcul poate fi efectuat clasic, folosind algoritmul de exponențiere modulară menționat în lecția anterioară (adesea numit algoritmul puterii în teoria computațională a numerelor). De fapt, avem nevoie doar de puteri ale lui $a$ care sunt puteri ale lui 2, în particular $a^2, a^4, \ldots a^{2^{m-1}} \in \mathbb{Z}_N^{\ast}$, și putem obține aceste puteri ridicând iterativ la pătrat de $m-1$ ori. Fiecare ridicare la pătrat poate fi realizată printr-un circuit boolean de dimensiune $O(n^2)$.

În esență, ceea ce facem efectiv aici este să transferăm problema iterării $M_a$ de până la $2^{m-1}$ ori către un calcul clasic eficient. Și este o mare șansă că acest lucru este posibil! Pentru o alegere arbitrară a unui Circuit cuantic în problema estimării fazei, este puțin probabil ca acest lucru să fie posibil — și în acel caz, costul rezultat pentru estimarea fazei crește exponențial în numărul de Qubiți de control $m$.

Soluție folosind un eigenvector convenabil

Pentru a înțelege cum putem rezolva problema găsirii ordinului folosind estimarea de fază, să începem prin a presupune că rulăm procedura de estimare a fazei pentru operația $M_a$ folosind eigenvectorul $\vert\psi_1\rangle$. A pune mâna pe acest eigenvector nu este ușor, după cum se dovedește, deci aceasta nu va fi finalul poveștii — dar este util să începem de aici.

Valoarea proprie a lui $M_a$ corespunzătoare eigenvectorului $\vert \psi_1\rangle$ este

$$\omega_r = e^{2\pi i \frac{1}{r}}.$$

Adică, $\omega_r = e^{2\pi i \theta}$ pentru $\theta = 1/r.$ Prin urmare, dacă rulăm procedura de estimare a fazei pentru $M_a$ folosind eigenvectorul $\vert\psi_1\rangle,$ vom obține o aproximare a lui $1/r.$ Calculând reciproca vom putea afla $r$ — cu condiția că aproximarea noastră este suficient de bună.

Mai în detaliu, când rulăm procedura de estimare a fazei folosind $m$ Qubiți de control, ceea ce obținem este un număr $y\in\{0,\ldots,2^m-1\}$. Luăm apoi $y/2^m$ ca estimare pentru $\theta$, care este $1/r$ în cazul de față. Pentru a afla ce este $r$ din această aproximare, lucrul natural de făcut este să calculăm reciproca aproximării și să rotunjim la cel mai apropiat număr întreg.

$$\left\lfloor \frac{2^m}{y} + \frac{1}{2} \right\rfloor$$

De exemplu, să presupunem că $r = 6$ și efectuăm estimarea de fază pentru $M_a$ cu eigenvectorul $\vert\psi_1\rangle$ folosind $m = 5$ biți de control. Cea mai bună aproximare pe $5$ biți a lui $1/r = 1/6$ este $5/32$, și avem o șansă destul de mare (aproximativ $68\%$ în acest caz) de a obține rezultatul $y=5$ din estimarea de fază. Avem

$$\frac{2^m}{y} = \frac{32}{5} = 6.4,$$

și rotunjind la cel mai apropiat număr întreg obținem $6$, care este răspunsul corect.

Pe de altă parte, dacă nu folosim suficientă precizie, este posibil să nu obținem răspunsul corect. De exemplu, dacă luăm $m = 4$ Qubiți de control în estimarea de fază, am putea obține cea mai bună aproximare pe $4$ biți a lui $1/r = 1/6$, care este $3/16$. Calculând reciproca obținem

$$\frac{2^m}{y} = \frac{16}{3} = 5.333 \cdots$$

și rotunjind la cel mai apropiat număr întreg obținem răspunsul incorect $5$.

Deci câtă precizie avem nevoie pentru a obține răspunsul corect? Știm că ordinul $r$ este un număr întreg și, intuitiv vorbind, avem nevoie de suficientă precizie pentru a distinge $1/r$ de posibilitățile apropiate, inclusiv $1/(r+1)$ și $1/(r-1)$. Numărul cel mai apropiat de $1/r$ de care trebuie să ne preocupăm este $1/(r+1)$, iar distanța dintre aceste două numere este

$$\frac{1}{r} - \frac{1}{r+1} = \frac{1}{r(r+1)}.$$

Deci, dacă vrem să ne asigurăm că nu confundăm $1/r$ cu $1/(r+1)$, este suficient să folosim suficientă precizie pentru a garanta că cea mai bună aproximare $y/2^m$ a lui $1/r$ este mai apropiată de $1/r$ decât de $1/(r+1)$. Dacă folosim suficientă precizie astfel încât

$$\left\vert \frac{y}{2^m} - \frac{1}{r} \right\vert < \frac{1}{2 r (r+1)},$$

astfel că eroarea este mai mică decât jumătatea distanței dintre $1/r$ și $1/(r+1)$, atunci $y/2^m$ va fi mai apropiată de $1/r$ decât de orice altă posibilitate, inclusiv $1/(r+1)$ și $1/(r-1)$.

Putem verifica dublu aceasta după cum urmează. Să presupunem că

$$\frac{y}{2^m} = \frac{1}{r} + \varepsilon$$

pentru $\varepsilon$ care satisface

$$\vert\varepsilon\vert < \frac{1}{2 r (r+1)}.$$

Când calculăm reciproca obținem

$$\frac{2^m}{y} = \frac{1}{\frac{1}{r} + \varepsilon} = \frac{r}{1+\varepsilon r} = r - \frac{\varepsilon r^2}{1+\varepsilon r}.$$

Maximizând la numărător și minimizând la numitor, putem limita cât de departe suntem de $r$ după cum urmează.

$$\left\vert \frac{\varepsilon r^2}{1+\varepsilon r} \right\vert \leq \frac{ \frac{r^2}{2 r(r+1)}}{1 - \frac{r}{2r(r+1)}} = \frac{r}{2 r + 1} < \frac{1}{2}$$

Suntem la mai puțin de $1/2$ distanță față de $r$, deci după cum era de așteptat vom obține $r$ când rotunjim.

Din nefericire, deoarece nu știm încă ce este $r,$ nu îl putem folosi pentru a determina câtă precizie avem nevoie. Ceea ce putem face în schimb este să folosim faptul că $r$ trebuie să fie mai mic decât $N$ pentru a ne asigura că folosim suficientă precizie. În particular, dacă folosim suficientă precizie pentru a garanta că cea mai bună aproximare $y/2^m$ a lui $1/r$ satisface

$$\left\vert \frac{y}{2^m} - \frac{1}{r} \right\vert \leq \frac{1}{2N^2},$$

atunci vom avea suficientă precizie pentru a determina corect $r$ când calculăm reciproca. Luând $m = 2\operatorname{lg}(N)+1$ ne asigurăm că avem o șansă mare de a obține o estimare cu această precizie folosind metoda descrisă anterior. (Luând $m = 2\operatorname{lg}(N)$ este suficient dacă suntem confortabili cu o limită inferioară de 40% pentru probabilitatea de succes.)

Soluție generală

După cum am văzut, dacă avem eigenvectorul $\vert \psi_1 \rangle$ al lui $M_a$, putem afla $r$ prin estimarea de fază, atât timp cât folosim suficienți Qubiți de control pentru a face acest lucru cu precizie suficientă. Din nefericire, nu este ușor să punem mâna pe eigenvectorul $\vert\psi_1\rangle$, deci trebuie să găsim o modalitate de a continua.

Să presupunem momentan că procedăm exact ca mai sus, cu excepția că folosim eigenvectorul $\vert\psi_k\rangle$ în locul lui $\vert\psi_1\rangle$, pentru orice alegere a lui $k\in\{0,\ldots,r-1\}$ la care vrem să ne gândim. Rezultatul pe care îl obținem din procedura de estimare a fazei va fi o aproximare

$$\frac{y}{2^m} \approx \frac{k}{r}.$$

Lucrând sub ipoteza că nu cunoaștem nici $k$ nici $r$, aceasta poate sau nu să ne permită identificarea lui $r$. De exemplu, dacă $k = 0$ vom obține o aproximare $y/2^m$ a lui $0$, ceea ce din nefericire nu ne spune nimic. Acesta este însă un caz neobișnuit; pentru alte valori ale lui $k$, vom putea cel puțin afla ceva despre $r$.

Putem folosi un algoritm cunoscut sub numele de algoritmul fracțiilor continue pentru a transforma aproximarea noastră $y/2^m$ în fracții apropiate — inclusiv $k/r$ dacă aproximarea este suficient de bună. Nu vom explica algoritmul fracțiilor continue aici. În schimb, iată o afirmație a unui fapt cunoscut despre acest algoritm.

Fapt

Dat un număr întreg $N\geq 2$ și un număr real $\alpha\in(0,1)$, există cel mult o alegere de numere întregi $u,v\in\{0,\ldots,N-1\}$ cu $v\neq 0$ și $\gcd(u,v)=1$ satisfăcând $\vert \alpha - u/v\vert < \frac{1}{2N^2}$. Dat $\alpha$ și $N$, algoritmul fracțiilor continue găsește $u$ și $v$, sau raportează că nu există. Acest algoritm poate fi implementat ca un circuit Boolean de dimensiune $O((\operatorname{lg}(N))^3)$.

Dacă avem o aproximare foarte bună $y/2^m$ a lui $k/r$, și rulăm algoritmul fracțiilor continue pentru $N$ și $\alpha = y/2^m$, vom obține $u$ și $v$, așa cum sunt descrise în fapt. O analiză a faptului ne permite să concluzionăm că

$$\frac{u}{v} = \frac{k}{r}.$$

Observă în special că nu neapărat aflăm $k$ și $r$, ci aflăm doar $k/r$ în forma ireductibilă.

De exemplu, și după cum am observat deja, nu vom afla nimic din $k=0$. Dar acesta este singurul valoare a lui $k$ pentru care se întâmplă asta. Când $k$ este diferit de zero, poate avea factori comuni cu $r$, dar numărul $v$ pe care îl obținem din algoritmul fracțiilor continue trebuie cel puțin să dividă $r$.

Este departe de a fi evident, dar este adevărat că dacă avem capacitatea de a afla $u$ și $v$ cu $u/v = k/r$ pentru $k\in\{0,\ldots,r-1\}$ ales uniform la întâmplare, atunci cu o probabilitate foarte mare vom putea recupera $r$ după doar câteva eșantioane. În particular, dacă estimarea noastră pentru $r$ este cel mai mic multiplu comun al tuturor valorilor pentru numitorul $v$ pe care le observăm, vom fi corecți cu probabilitate mare. Intuitiv vorbind, unele valori ale lui $k$ nu sunt bune pentru că împart factori comuni cu $r$, iar acești factori comuni ne sunt ascunși când aflăm $u$ și $v$. Dar alegerile aleatoare ale lui $k$ nu sunt susceptibile să ascundă factorii lui $r$ mult timp, iar probabilitatea că nu ghicim corect $r$ luând cel mai mic multiplu comun al numitorilor observați scade exponențial în numărul de eșantioane.

Rămâne de abordat problema cum punem mâna pe un eigenvector $\vert\psi_k\rangle$ al lui $M_a$ pe care să rulăm procedura de estimare a fazei. Se dovedește că nu avem nevoie să îi creăm!

Ceea ce vom face în schimb este să rulăm procedura de estimare a fazei pe starea $\vert 1\rangle$, prin care înțelegem codificarea binară pe $n$ biți a numărului $1$, în locul unui eigenvector $\vert\psi\rangle$ al lui $M_a$. Până acum, am vorbit doar despre rularea procedurii de estimare a fazei pe un eigenvector particular, dar nimic nu ne împiedică să rulăm procedura pe o stare de intrare care nu este eigenvector al lui $M_a$, și asta facem aici cu starea $\vert 1\rangle$. (Aceasta nu este un eigenvector al lui $M_a$ dacă $a=1$, ceea ce nu este o alegere care ne va interesa.)

Rațiunea pentru care alegem starea $\vert 1\rangle$ în locul unui eigenvector al lui $M_a$ este că următoarea ecuație este adevărată.

$$\vert 1\rangle = \frac{1}{\sqrt{r}} \sum_{k = 0}^{r-1} \vert \psi_k\rangle$$

O modalitate de a verifica această ecuație este să comparăm produsele interioare ale celor două membre cu fiecare stare din baza standard, folosind formule menționate anterior în lecție pentru a evalua rezultatele pentru membrul drept. Ca urmare, vom obține exact aceleași rezultate de măsurare ca și cum am fi ales $k\in\{0,\ldots,r-1\}$ uniform la întâmplare și am fi folosit $\vert\psi_k\rangle$ ca eigenvector.

Mai în detaliu, să ne imaginăm că rulăm procedura de estimare a fazei cu starea $\vert 1\rangle$ în locul unuia dintre eigenvectorii $\vert\psi_k\rangle$. După ce transformata Fourier cuantică inversă este efectuată, aceasta ne lasă cu starea

$$\frac{1}{\sqrt{r}} \sum_{k = 0}^{r-1} \vert \psi_k\rangle \vert \gamma_k\rangle,$$

unde

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

Vectorul $\vert\gamma_k\rangle$ reprezintă starea primilor $m$ Qubiți după ce inversa transformatei Fourier cuantice a fost efectuată asupra lor.

Deci, datorită faptului că $\{\vert\psi_0\rangle,\ldots,\vert\psi_{r-1}\rangle\}$ este o mulțime ortonormată, constatăm că o măsurare a primilor $m$ Qubiți produce o aproximare $y/2^m$ a valorii $k/r$ unde $k\in\{0,\ldots,r-1\}$ este ales uniform la întâmplare. Așa cum am discutat deja, aceasta ne permite să aflăm $r$ cu un grad înalt de încredere după mai multe rulări independente, ceea ce a fost scopul nostru.

Costul total

Costul implementării fiecărui $M_a^k$ unitar controlat este $O(n^2)$. Există $m$ operații unitare controlate, iar $m = O(n)$, deci costul total al operațiilor unitare controlate este $O(n^3)$. În plus, avem $m$ Gate-uri Hadamard (care contribuie cu $O(n)$ la cost), iar transformata cuantică Fourier inversă contribuie cu $O(n^2)$ la cost. Astfel, costul operațiilor unitare controlate domină costul întregii proceduri — care este, prin urmare$,O(n^3)$.

Pe lângă Circuit-ul cuantic în sine, există câteva calcule clasice care trebuie efectuate pe parcurs. Acestea includ calcularea puterilor $a^k$ în $\mathbb{Z}_N$ pentru $k = 2, 4, 8, \ldots, 2^{m-1}$, necesare pentru crearea Gate-urilor unitare controlate, precum și algoritmul fracțiilor continue care convertește aproximările lui $\theta$ în fracții. Aceste calcule pot fi efectuate de circuite booleene cu un cost total de $O(n^3)$.

Ca de obicei, toate aceste limite pot fi îmbunătățite folosind algoritmi asimptotic mai rapizi; aceste limite presupun că folosim algoritmi standard pentru operații aritmetice de bază.

Factorizare prin găsirea ordinului

Ultimul lucru pe care trebuie să-l discutăm este modul în care rezolvarea problemei de găsire a ordinului ne ajută să factorizăm. Această parte este complet clasică — nu are nimic specific de-a face cu calculul cuantic.

Iată ideea de bază. Vrem să factorizăm numărul $N$, și putem face acest lucru recursiv. Mai precis, ne putem concentra pe sarcina de împărțire a lui $N$, adică găsirea a doi întregi $b,c\geq 2$ pentru care $N = bc$. Acest lucru nu este posibil dacă $N$ este un număr prim, dar putem testa eficient dacă $N$ este prim folosind mai întâi un algoritm de testare a primalității, iar dacă $N$ nu este prim vom încerca să-l împărțim. Odată ce împărțim $N$, putem pur și simplu recurge pe $b$ și $c$ până când toți factorii noștri sunt primi și obținem descompunerea în factori primi a lui $N$.

Împărțirea numerelor pare este simplă: ieșim cu $2$ și $N/2$.

Este, de asemenea, ușor să împărțim puterile perfecte, adică numerele de forma $N = s^j$ pentru întregi $s,j\geq 2,$ aproximând rădăcinile $N^{1/2},$ $N^{1/3},$ $N^{1/4},$ și așa mai departe, și verificând numerele întregi din apropiere ca suspecți pentru $s.$ Nu trebuie să mergem mai departe de $\log(N)$ pași în această secvență, deoarece la acel punct rădăcina scade sub $2$ și nu va mai revela candidați suplimentari.

Este bine că putem face ambele lucruri, deoarece găsirea ordinului nu ne va ajuta să factorizăm numerele pare sau puterile prime, unde numărul $s$ se întâmplă să fie prim. Dacă $N$ este impar și nu este o putere primă, totuși, găsirea ordinului ne permite să împărțim $N$.

Algoritm probabilistic pentru a împărți un întreg impar, compus N care nu este o putere primă

1. Alege aleatoriu $a\in\{2,\ldots,N-1\}$.

2. Calculează $d=\gcd(a,N)$.

3. Dacă $d > 1$ atunci returnează $b = d$ și $c = N/d$ și oprește. Altfel continuă la pasul următor știind că $a\in\mathbb{Z}_N^{\ast}$.

4. Fie $r$ ordinul lui $a$ modulo $N$. (Aici avem nevoie de găsirea ordinului.)

5. Dacă $r$ este par:

   5.1 Calculează $x = a^{r/2} - 1$ modulo $N$
   5.2 Calculează $d = \gcd(x,N)$.
   5.3 Dacă $d>1$ atunci returnează $b=d$ și $c = N/d$ și oprește.

6. Dacă se ajunge în acest punct, algoritmul a eșuat în găsirea unui factor al lui $N$.

O rulare a acestui algoritm poate eșua în găsirea unui factor al lui $N$. Mai precis, acest lucru se întâmplă în două situații:

• Ordinul lui $a$ modulo $N$ este impar.
• Ordinul lui $a$ modulo $N$ este par și $\gcd\bigl(a^{r/2} - 1, N\bigr) = 1$.

Folosind teoria elementară a numerelor se poate demonstra că, pentru o alegere aleatorie a lui $a$, cu probabilitate de cel puțin $1/2$ niciunul dintre aceste evenimente nu se produce. De fapt, probabilitatea ca oricare dintre evenimente să se producă este de cel mult $2^{-(m-1)}$ unde $m$ este numărul de factori primi distincți ai lui $N$, motiv pentru care ipoteza că $N$ nu este o putere primă este necesară. (Ipoteza că $N$ este impar este, de asemenea, necesară pentru ca acest fapt să fie adevărat.)

Asta înseamnă că fiecare rulare are cel puțin 50% șanse să împartă $N$. Prin urmare, dacă rulăm algoritmul de $t$ ori, alegând aleatoriu $a$ de fiecare dată, vom reuși să împărțim $N$ cu probabilitate de cel puțin $1 - 2^{-t}$.

Ideea de bază din spatele algoritmului este următoarea. Dacă avem o alegere a lui $a$ pentru care ordinul $r$ al lui $a$ modulo $N$ este par, atunci $r/2$ este un întreg și putem considera numerele

$$a^{r/2} - 1\; (\textrm{mod}\; N) \quad \text{și} \quad a^{r/2} + 1\; (\textrm{mod}\; N).$$

Folosind formula $Z^2 - 1 = (Z+1)(Z-1)$, concluzionăm că

$$\bigl(a^{r/2} - 1\bigr) \bigl(a^{r/2} + 1\bigr) = a^r - 1.$$

Acum, știm că $a^r \; (\textrm{mod}\; N) = 1$ prin definiția ordinului — ceea ce este un alt mod de a spune că $N$ divide exact $a^r - 1$. Asta înseamnă că $N$ divide exact produsul

$$\bigl(a^{r/2} - 1\bigr) \bigl(a^{r/2} + 1\bigr).$$

Pentru ca acest lucru să fie adevărat, toți factorii primi ai lui $N$ trebuie să fie și factori primi ai lui $a^{r/2} - 1$ sau $a^{r/2} + 1$ (sau ai ambilor) — iar pentru o selecție aleatorie a lui $a$ se dovedește că este puțin probabil ca toți factorii primi ai lui $N$ să dividă unul dintre termeni și niciunul să nu dividă celălalt. Altfel, atâta timp cât unii dintre factorii primi ai lui $N$ divid primul termen și unii divid al doilea termen, vom putea găsi un factor netrivial al lui $N$ calculând CMMDC cu primul termen.