Algoritmul lui Shor

Pentru acest modul Qiskit în Sală de Clasă, studenții trebuie să aibă un mediu Python funcțional cu următoarele pachete instalate:

• qiskit v2.1.0 sau mai nou
• qiskit-ibm-runtime v0.40.1 sau mai nou
• qiskit-aer v0.17.0 sau mai nou
• qiskit.visualization
• numpy
• pylatexenc

Pentru a configura și instala pachetele de mai sus, consultă ghidul Instalează Qiskit. Pentru a rula joburi pe calculatoare cuantice reale, studenții vor trebui să își creeze un cont IBM Quantum® urmând pașii din ghidul Configurează-ți contul IBM Cloud.

Acest modul a fost testat și a folosit trei secunde de timp QPU. Aceasta este doar o estimare. Utilizarea ta reală poate varia.

# Added by doQumentation — required packages for this notebook
!pip install -q numpy qiskit qiskit-ibm-runtime

# Uncomment and modify this line as needed to install dependencies
#!pip install 'qiskit>=2.1.0' 'qiskit-ibm-runtime>=0.40.1' 'qiskit-aer>=0.17.0' 'numpy' 'pylatexenc'

Introducere

La începutul anilor 1990, entuziasmul față de potențialul calculatoarelor cuantice de a rezolva probleme dificile pentru calculatoarele clasice era în creștere. Câțiva informaticieni talentați concepuseră algoritmi care demonstrau puterea calculului cuantic pentru unele probleme de nișă și artificiale, dar nimeni nu găsise o singură „aplicație ucigașă" a calculului cuantic care să fie sigur că va revoluționa domeniul. Asta până în 1994, când Peter Shor a elaborat ceea ce este acum cunoscut ca algoritmul lui Shor pentru factorizarea numerelor mari.

Era bine știut la acea vreme că găsirea factorilor primi ai unui număr mare era extrem de dificilă pentru un calculator clasic. De fapt, protocoalele de securitate pe internet se bazau pe această dificultate. Shor a găsit o modalitate de a descoperi acești factori exponențial mai eficient, delegând unii dintre pașii mai dificili unui calculator cuantic teoretic, din viitor.

În acest modul, vom explora algoritmul lui Shor. Mai întâi, vom oferi puțin mai mult context algoritmului, formalizând problema pe care o rezolvă și explicând relevanța pentru securitatea cibernetică. Apoi, vom face o introducere în matematica modulară și cum să o aplicăm problemei de factorizare, arătând cum factorizarea se reduce la o altă problemă numită „găsirea ordinului". Vom arăta cum intervin Transformata Fourier Cuantică și Estimarea Fazei Cuantice, pe care le-am studiat într-un modul anterior, și cum să le folosim pentru a rezolva problema găsirii ordinului.

În final, vom rula algoritmul lui Shor pe un calculator cuantic real! Ține minte, totuși, că acest algoritm va fi cu adevărat util abia când vom avea un calculator cuantic mare, tolerant la erori, lucru care mai este încă la câțiva ani distanță. Prin urmare, vom factoriza doar un număr mic pentru a demonstra cum funcționează algoritmul.

Problema factorizării

Scopul problemei de factorizare este de a găsi factorii primi ai unui număr $N$. Pentru unele numere $N$, acest lucru este destul de simplu. De exemplu, dacă $N$ este par, unul dintre factorii săi primi va fi 2. Dacă $N$ este o putere a unui număr prim, adică $N=p^k$ pentru un număr prim $p$, este, de asemenea, destul de ușor de găsit $p$: aproximăm pur și simplu rădăcina $k^{\text{th}}$ a lui $N$ și căutăm numere prime apropiate care ar putea fi $p$.

Unde calculatoarele clasice întâmpină dificultăți este atunci când $N$ este impar și nu este o putere a unui număr prim. Acesta este cazul cu care se ocupă algoritmul lui Shor. Algoritmul găsește doi factori $p$ și $q$ astfel încât $N=pq$. El poate fi aplicat recursiv până când toți factorii sunt primi. În secțiunile următoare vom vedea cum este abordată această problemă.

Relevanța pentru securitatea cibernetică

Multe scheme criptografice au fost construite pe baza faptului că factorizarea numerelor mari este dificilă, inclusiv una utilizată frecvent astăzi, numită RSA. În RSA, o cheie publică este creată prin înmulțirea a două numere prime mari pentru a obține $N = p\cdot q$. Apoi, oricine poate folosi această cheie publică pentru a cripta date. Dar numai cineva care deține cheia privată, $p$ și $q$, poate decripta acele date.

Dacă $N$ ar fi ușor de factorizat, atunci oricine ar putea determina valorile lui $p$ și $q$ și ar sparge criptarea. Dar nu este. Aceasta este o problemă de notorietate pentru dificultatea sa. De fapt, factorii primi ai unui număr numit RSA1024, care are 1024 de cifre binare și 309 de cifre zecimale, nu au fost găsiți până în prezent, în ciuda unui premiu de $100.000 oferit pentru factorizarea sa încă din 1991.

Soluția lui Shor

În 1994, Peter Shor și-a dat seama că un calculator cuantic poate factoriza un număr mare exponențial mai eficient decât un calculator clasic. Intuiția sa s-a bazat pe relația dintre această problemă de factorizare și aritmetica modulară. Vom trece printr-o scurtă introducere în aritmetica modulară, apoi vom vedea cum putem folosi acest lucru pentru a factoriza $N$.

Aritmetica modulară

Aritmetica modulară este un sistem de numărare ciclic, adică, deși numărătoarea începe în mod obișnuit, cu numerele întregi 0, 1, 2 etc., la un moment dat, după o perioadă $N$, numărătoarea reîncepe de la capăt. Să vedem cum funcționează cu un exemplu. Să spunem că perioada noastră este 5. Atunci, pe măsură ce numărăm, acolo unde în mod normal am ajunge la 5, reîncepem de la 0:

$0, 1, 2, 3, 4, 0, 1, 2, 3, 4, 0, 1, 2, ...$

Aceasta se datorează faptului că în lumea „modulo-5", 5 este echivalent cu 0. Spunem că $5\bmod 5 \ = 0$. De fapt, toate multiplele lui 5 vor fi echivalente cu $0\bmod 5$.

Verifică-ți înțelegerea

Citește întrebarea (întrebările) de mai jos, gândește-te la răspuns, apoi dă clic pe triunghi pentru a dezvălui soluția.

Folosește aritmetica modulară pentru a rezolva următoarea problemă:

Pleci într-o călătorie lungă cu trenul transcontinental la ora 8 dimineața. Călătoria cu trenul durează 60 de ore. La ce oră ajungi?

Răspuns:

Perioada este 24, deoarece într-o zi sunt 24 de ore. Astfel, această problemă poate fi scrisă în aritmetică modulară ca:

$(8+60)\text{mod}(24) = 20$

Deci, ai ajunge la destinație la ora 20:00, adică 8 seara.

$\mathbb{Z}_N$ și $\mathbb{Z}_N^*$

Este adesea util să introducem două mulțimi, $\mathbb{Z}_N$ și $\mathbb{Z}_N^*$. $\mathbb{Z}_N$ este pur și simplu mulțimea numerelor care există într-o lume „modulo-$N$". De exemplu, când număram modulo-5, mulțimea ar fi $\mathbb{Z}_5=\{0,1,2,3,4\}$. Un alt exemplu: $\mathbb{Z}_{15} = \{0,1,2,3,4,5,6,7,8,9,10,11,12,13,14\}$. Putem efectua adunări și înmulțiri (modulo $N$) pe elementele din $\mathbb{Z}_N$, iar rezultatul fiecăreia dintre aceste operații este, de asemenea, un element din $\mathbb{Z}_N$, ceea ce face din $\mathbb{Z}_N$ un obiect matematic numit inel.

Există un subset special al lui $\mathbb{Z}_N$ care prezintă un interes deosebit pentru noi în cazul algoritmului lui Shor. Acesta este subsetul numerelor din $\mathbb{Z}_N$ astfel încât cel mai mare divizor comun dintre fiecare element și $N$ este 1, deci fiecare element este „coprim" cu $N$. Dacă luăm mulțimea acestor numere împreună cu operația de înmulțire modulară, aceasta formează un alt obiect matematic, numit grup. Numim acest grup $\mathbb{Z}_N^*$. Se dovedește că în cazul $\mathbb{Z}_N^*$ (și al grupurilor finite în general), dacă alegem orice element $a \in \mathbb{Z}_N^*$ și îl înmulțim repetat cu el însuși, vom obține întotdeauna în cele din urmă numărul $1$. Numărul minim de ori de câte ori trebuie să înmulțești $a$ cu el însuși pentru a obține $1$ se numește ordinul lui $a$. Acest fapt va fi foarte important în discuția noastră despre cum să factorizăm numerele de mai jos.

Verifică-ți înțelegerea

Citește întrebarea (întrebările) de mai jos, gândește-te la răspuns, apoi dă clic pe triunghi pentru a dezvălui soluția.

Care este $\mathbb{Z}_{15}^*$?

Răspuns:

$\mathbb{Z}_{15}^* = \{1,2,4,7,8,11,13,14\}$

Am exclus următoarele numere:

$$\begin{aligned} 3: GCD(3,15)=3 \\ 5: GCD(5,15)=5 \\ 6: GCD(6,15)=3 \\ 9: GCD(9,15)=3 \\ 10: GCD(10,15)=5 \\ 12: GCD(12,15)=3 \\ \end{aligned}$$

Care este ordinul fiecăruia dintre elementele din $\mathbb{Z}_{15}^*$?

Răspuns:

Ordinul $r$ este cel mai mic număr astfel încât $a^r\text{mod}(15)=1$ pentru fiecare element $a$.

$$\begin{aligned} 1^1\text{mod}(15) = 1, r=1 \\ 2^4\text{mod}(15) = 1, r=4 \\ 4^2\text{mod}(15) = 1, r=2 \\ 7^4\text{mod}(15) = 1, r=4 \\ 8^4\text{mod}(15) = 1, r=4 \\ 11^2\text{mod}(15) = 1, r=2 \\ 13^4\text{mod}(15) = 1, r=4 \\ 14^2\text{mod}(15) = 1, r=2 \\ \end{aligned}$$

Rețineți că, deși am reușit să găsim ordinul numerelor din $\mathbb{Z}_{15}^*$, aceasta NU este o sarcină ușoară în general, pentru $N$ mai mare. Acesta este miezul problemei de factorizare și motivul pentru care avem nevoie de un calculator cuantic. Vom vedea de ce pe măsură ce parcurgem restul notebook-ului.

Aplică aritmetica modulară problemei de factorizare

Cheia pentru găsirea factorilor $p$ și $q$ astfel încât $N=pq$ constă în găsirea unui alt număr întreg $x$ astfel încât

$x^2 \equiv 1 \bmod N$ și $x \not\equiv \pm 1 \bmod N.$

Cum ne ajută găsirea lui $x$ să găsim factorii $p$ și $q$? Să parcurgem argumentul acum. Deoarece $x^2 \equiv 1 \bmod N$, înseamnă că $x^2 - 1 \equiv 0 \bmod N$. Cu alte cuvinte, $x^2 - 1$ este un multiplu al lui $N$. Deci, pentru un număr întreg $l$,

$x^2 - 1 = l N$

Putem factoriza $x^2 - 1$ pentru a obține:

$(x+1)(x-1) = l N$

Din ipotezele noastre inițiale știm că $x \not\equiv \pm 1 \bmod N$, deci $N$ nu se împarte exact în nici $x+1$, nici $x-1$. Astfel, cei doi factori ai lui $N$, $p$ și $q$, trebuie să se împartă fiecare în $x-1$ și $x+1$. Fie $p$ este un factor al lui $x-1$ și $q$ este un factor al lui $x+1$, fie invers. Prin urmare, dacă calculăm cel mai mare divizor comun (CMMDC) dintre $N$ și atât $x-1$, cât și $x+1$, vom obține factorii $p$ și $q$. Calcularea CMMDC dintre două numere este o sarcină clasic ușoară, care poate fi realizată, de exemplu, folosind algoritmul lui Euclid.

Verifică-ți înțelegerea

Citește întrebarea (întrebările) de mai jos, gândește-te la răspuns, apoi dă clic pe triunghi pentru a dezvălui soluția.

Poate fi dificil să înțelegi fiecare pas din logica de mai sus, deci încearcă să parcurgi un exemplu. Folosește $N=15$ și $x=11$. Mai întâi, verifică că $x^2 \equiv 1 \text{mod}(N)$ și $x \not\equiv \pm 1 \bmod N$. Apoi continuă să verifici fiecare pas. În final, calculează $\text{GCD}(11\pm1,15)$ și verifică că aceștia sunt factorii lui $15$.

Răspuns:

$11^2 = 121$, care este $15*8 + 1$, deci $11^2\bmod 15 = 1$. $\checkmark$

$11 - 1 = 10$, care nu este echivalent cu $0\bmod 15$. $\checkmark$

$11 + 1 = 12$, care nu este echivalent cu $0\bmod 15$. $\checkmark$

Acum, știm că $(x+1)(x-1) = l N$ pentru un număr întreg $l$. Aceasta se verifică când introducem $x$ și $N$: $(12)(10) = l 15$ când $l = 8$. $\checkmark$

Acum, trebuie să calculăm $\text{GCD}(12,15)$ și $\text{GCD}(10,15)$.

$$\begin{aligned} \text{GCD}(12,15) = 3 \\ \text{GCD}(10,15) = 5 \end{aligned}$$

Astfel, am găsit factorii lui $15$!

Algoritmul

Acum că am văzut cum găsirea unui întreg $x$ astfel încât $x^2 \equiv 1\bmod N$ ne ajută să factorizăm $N$, putem parcurge algoritmul lui Shor. Practic, totul se reduce la găsirea lui $x$:

1. Alege un întreg aleatoriu Alege un întreg aleatoriu $a$ astfel încât $1 < a < N$.

• Calculează $\text{GCD}(a, N)$ clasic.
  • Dacă $\text{GCD}(a, N) > 1$, ai găsit deja un factor. Oprește-te.
  • Altfel, continuă.

2. Găsește ordinul $r$ al lui $a$ modulo $N$ Găsește cel mai mic întreg pozitiv $r$ care satisface $a^r \equiv 1 \pmod N$.

3. Verifică dacă ordinul este par

• Dacă $r$ este impar, întoarce-te la pasul 1 și alege un nou $a$.
• Dacă $r$ este par, continuă la pasul 4.

4. Calculează $x = a^{r/2} \bmod N$

• Verifică că $x \not\equiv 1 \pmod N$ și $x \not\equiv -1 \pmod N$.
  • Dacă $x \equiv \pm 1 \pmod N$, întoarce-te la pasul 1 și alege un nou $a$.
• Altfel, calculează cel mai mare divizor comun pentru a extrage factorii:

$$p = \text{GCD}(x-1, N), \quad q = \text{GCD}(x+1, N)$$

Aceștia vor fi factori netriviali ai lui $N$.

5. Factorizează recursiv dacă este necesar

• Dacă $p$ și/sau $q$ nu sunt primi, aplică algoritmul recursiv pentru a-i factoriza complet.
• Odată ce toți factorii sunt primi, factorizarea este completă.

Pe baza acestei proceduri, s-ar putea să nu fie evident de ce este nevoie de un calculator cuantic pentru a finaliza această sarcină. Este necesar deoarece pasul 2, găsirea ordinului lui $a$ modulo $N$, este clasic o problemă foarte dificilă. Complexitatea scalează exponențial în funcție de $N$. Dar cu un calculator cuantic, trebuie doar să folosim Estimarea de Fază Cuantică pentru a o rezolva. Pasul 4, găsirea celui mai mare divizor comun a două numere întregi, este de fapt un lucru destul de ușor de făcut clasic. Astfel, singurul pas care necesită cu adevărat puterea unui calculator cuantic este pasul de găsire a ordinului. Spunem că problema factorizării „se reduce" la problema găsirii ordinului.

Partea dificilă: găsirea ordinului

Acum vom parcurge modul în care putem folosi un calculator cuantic în găsirea ordinului. Mai întâi, să clarificăm ce înțelegem prin „ordin." Bineînțeles, ți-am spus deja ce înseamnă ordinul matematic: este primul întreg non-zero $r$ astfel încât $a^r = 1 \pmod N.$ Dar haideți să vedem dacă putem câștiga puțin mai multă intuiție pentru acest concept.

Pentru $N$ suficient de mic, putem determina ordinul pur și simplu calculând fiecare putere a lui $a$, luând modulul $N$ al acelui număr, apoi oprindu-ne când găsim puterea $r$ care satisface $a^r = 1 \text{mod}(N)$. Asta am făcut cu exemplul nostru, $N=15$, mai sus. Să aruncăm o privire la câteva grafice ale acestor puteri modulare pentru câteva valori de exemplu ale lui $a$ și $N$:

Observi ceva? Acestea sunt funcții periodice! Și ordinul $r$ este același cu perioada! Deci, găsirea ordinului este echivalentă cu găsirea perioadei.

Calculatoarele cuantice sunt foarte bine adaptate pentru găsirea perioadei funcțiilor. Pentru aceasta, putem folosi o subrutină algoritmică numită Estimarea de Fază Cuantică. Am discutat QPE și relația sa cu Transformata Fourier Cuantică în modulul precedent. Pentru o recapitulare detaliată, mergi la modulul QFT sau la lecția lui John Watrous despre Estimarea de Fază Cuantică din cursul său de Algoritmi Cuantici. Vom trece prin esența procedurii acum:

În Estimarea de Fază Cuantică (QPE), pornim cu un unitar $U$ și o stare proprie a acelui unitar $|\psi\rangle$. Apoi, folosim QPE pentru a aproxima valoarea proprie corespunzătoare, care, deoarece operatorul este unitar, va fi de forma $e^{2\pi i \theta}$. Deci, găsirea valorii proprii este echivalentă cu găsirea valorii $\theta$ în funcția periodică. Circuitul arată astfel:

unde numărul de Qubiți de control (cei $m$ Qubiți din vârf în figura de mai sus) determină precizia aproximării.

În algoritmul lui Shor, folosim QPE pe operatorul unitar $M_a$:

$M_a|y\rangle \equiv |ay \mod N \rangle .$

Aici, $|y\rangle$ denotă o stare de bază computațională a registrului multi-Qubit, unde valoarea binară a Qubiților corespunde întregului $y$. De exemplu, dacă $N=15$ și $y = 2$, atunci $|y\rangle$ este reprezentat de starea de bază cu patru Qubiți $|0010\rangle$, deoarece patru Qubiți sunt necesari pentru a codifica numere până la 15. (Dacă acest concept nu îți este familiar, consultați modulul introductiv Qiskit în clase pentru o recapitulare a codificării binare a stărilor cuantice.)

Acum, trebuie să identificăm o stare proprie a acestui unitar. Dacă am porni din starea $|1\rangle$, putem vedea că fiecare aplicare succesivă a lui $U$ va înmulți starea registrului nostru cu $a \pmod N$, și după $r$ aplicări vom ajunge din nou la starea $|1\rangle$. De exemplu cu $a = 3$ și $N = 35$:

$$\begin{aligned} M_3|1\rangle &= |3\rangle & \\ M_3^2|1\rangle &= |9\rangle \\ M_3^3|1\rangle &= |27\rangle \\ & \vdots \\ M_3^{(r-1)}|1\rangle &= |12\rangle \\ M_3^r|1\rangle &= |1\rangle \end{aligned}$$

Deci superpozițiile stărilor din acest ciclu ($|\psi_j\rangle$) de forma:

$|\psi_j\rangle = \tfrac{1}{\sqrt{r}}\sum_{k=0}^{r-1}{e^{\frac{2 \pi i j k}{r}} |a^k \rangle}$

sunt toate stări proprii ale lui $M_a$. (Există mai multe stări proprii decât doar acestea. Dar ne interesează doar cele de forma de mai sus.)

Verifică-ți înțelegerea

Citește întrebarea (întrebările) de mai jos, gândește-te la răspuns, apoi apasă pe triunghi pentru a dezvălui soluția.

Găsește o stare proprie a unitarului corespunzător lui $a=2$ și $N = 15$.

Răspuns:

$$\begin{aligned} M_2|1\rangle &= |2\rangle & \\ M_2^2|1\rangle &= |4\rangle \\ M_2^3|1\rangle &= |8\rangle \\ M_2^4|1\rangle &= |1\rangle \\ \end{aligned}$$

Deci, ordinul $r=4$. Stările proprii care ne interesează vor fi o superpoziție egală a tuturor stărilor prin care s-a trecut mai sus, cu diverse faze:

$$\begin{aligned} |\psi_0\rangle &= \frac{1}{2}(|1\rangle+|2\rangle+|4\rangle+|8\rangle) \\ |\psi_1\rangle &= \frac{1}{2}(e^{2 \pi i \frac{0}{4}}|1\rangle+e^{2 \pi i \frac{1}{4}}|2\rangle+e^{2 \pi i \frac{2}{4}}|4\rangle+e^{2 \pi i \frac{3}{4}}|8\rangle) \\ &= \frac{1}{2}(|1\rangle+i|2\rangle-|4\rangle-i|8\rangle) \\ |\psi_2\rangle &= \frac{1}{2}(e^{2 \pi i \frac{0}{4}}|1\rangle+e^{2 \pi i \frac{2}{4}}|2\rangle+e^{2 \pi i \frac{4}{4}}|4\rangle+e^{2 \pi i \frac{6}{4}}|8\rangle) \\ &= \frac{1}{2}(|1\rangle-|2\rangle+|4\rangle-|8\rangle) \\ |\psi_3\rangle &= \frac{1}{2}(e^{2 \pi i \frac{0}{4}}|1\rangle+e^{2 \pi i \frac{3}{4}}|2\rangle+e^{2 \pi i \frac{6}{4}}|4\rangle+e^{2 \pi i \frac{9}{4}}|8\rangle) \\ &= \frac{1}{2}(|1\rangle-i|2\rangle-|4\rangle+i|8\rangle) \\ \end{aligned}$$

Să presupunem că am fi capabili să inițializăm starea Qubitului nostru într-una din aceste stări proprii (spoiler — nu putem. Sau, cel puțin nu ușor. Vom explica de ce și ce putem face în schimb în scurt timp). Atunci am putea folosi QPE pentru a estima valoarea proprie corespunzătoare, $\omega_j = e^{2 \pi i \theta_j}$ unde $\theta_j = \frac{j}{r}$. Apoi, vom putea determina ordinul $r$ prin simpla ecuație:

$r = \frac{j}{\theta_j}.$

Dar ține minte, am spus că QPE estimează $\theta_j$ — nu ne oferă o valoare exactă. Avem nevoie ca estimarea să fie suficient de bună pentru a diferenția între $r$ și $r+1$. Cu cât avem mai mulți Qubiți de control $m$, cu atât estimarea va fi mai bună. În problemele de la sfârșitul lecției, ți se va cere să determini $m$-ul minim necesar pentru a factoriza un număr $N$.

Acum, trebuie să rezolvăm o problemă. Toată explicația de mai sus despre cum să găsim $r$ începe cu pregătirea stării proprii $|\psi_j\rangle = \tfrac{1}{\sqrt{r}}\sum_{k=0}^{r-1}{e^{\frac{2 \pi i j k}{r}} |a^k \rangle}$. Dar nu știm cum să facem asta fără să cunoaștem deja $r$. Logica este circulară. Avem nevoie de o modalitate de a estima valoarea proprie fără a inițializa starea proprie.

În loc să pornim cu o stare proprie a lui $M_a$, putem pregăti starea inițială în starea de $n$ Qubiți corespunzătoare lui $|1\rangle$ în binar (adică $|000...01\rangle$). Deși această stare în sine nu este în mod evident o stare proprie a lui $M_a$, ea este o superpoziție peste toate stările proprii $|\psi_k\rangle$:

$|1\rangle = \frac{1}{\sqrt{r}} \sum\limits_{k=0}^{r-1}{|\psi_k\rangle}$

Verifică-ți înțelegerea

Citește întrebarea (întrebările) de mai jos, gândește-te la răspuns, apoi apasă pe triunghi pentru a dezvălui soluția.

Verifică că $|1\rangle$ este echivalent cu superpoziția peste stările proprii pe care le-ai găsit pentru $N=15$ și $a=2$ în întrebarea de verificare anterioară.

Răspuns:

Cele patru stări proprii au fost:

$$\begin{aligned} |\psi_0\rangle &= \frac{1}{2}(|1\rangle+|2\rangle+|4\rangle+|8\rangle) \\ |\psi_1\rangle &= \frac{1}{2}(|1\rangle+i|2\rangle-|4\rangle-i|8\rangle) \\ |\psi_2\rangle &= \frac{1}{2}(|1\rangle-|2\rangle+|4\rangle-|8\rangle) \\ |\psi_3\rangle &= \frac{1}{2}(|1\rangle-i|2\rangle-|4\rangle+i|8\rangle) \\ \end{aligned}$$

Deci,

$$\begin{aligned} \frac{1}{\sqrt{r}} \sum\limits_{k=0}^{r-1}{|\psi_k\rangle} &= \frac{1}{2}(|\psi_0\rangle + |\psi_1\rangle + |\psi_2\rangle + |\psi_3\rangle ) \\ &= \frac{1}{4}(|1\rangle+|2\rangle+|4\rangle+|8\rangle+|1\rangle+i|2\rangle-|4\rangle-i|8\rangle+|1\rangle-|2\rangle+|4\rangle-|8\rangle + |1\rangle-i|2\rangle-|4\rangle+i|8\rangle) \\ &= \frac{1}{4}(4|1\rangle) = |1\rangle \end{aligned}$$

Cum ne ajută asta să găsim ordinul $r$? Deoarece starea de pornire este o superpoziție peste toate stările proprii de forma listată mai sus, atunci algoritmul QPE estimează simultan fiecare dintre $\theta_k$ corespunzătoare acestor stări proprii. Deci, măsurarea celor $m$ Qubiți de control la final va produce o aproximare a valorii $k/r$ unde $k \in \{0,1,2,...,r-1\}$ este una dintre valorile proprii alese aleatoriu. Dacă repetăm acest Circuit de câteva ori și obținem câteva eșantioane cu valori diferite ale lui $k$, vom putea deduce rapid $r$.

Implementează în Qiskit

Așa cum am menționat mai devreme, hardware-ul nostru nu este la punctul în care putem factoriza numere uriașe precum RSA1024. Vom factoriza doar un număr mic pentru a demonstra cum funcționează algoritmul. Pentru această demonstrație, vom folosi o versiune simplificată a codului prezentat în tutorialul algoritmului lui Shor. Dacă vrei mai multe detalii, te rog să vizitezi tutorialul.

Vom rula algoritmul folosind cadrul nostru standard pentru rezolvarea problemelor cuantice, numit cadrul de tipare Qiskit. Acesta constă din patru pași:

1. Maparea problemei tale la un Circuit cuantic
2. Optimizarea Circuitului pentru a fi rulat pe hardware cuantic
3. Executarea Circuitului tău pe calculatorul cuantic
4. Post-procesarea măsurătorilor

1. Mapare

Să factorizăm $N=15$, selectând $a=2$ ca număr întreg co-prim.

Mai întâi, trebuie să construim Circuitul care va implementa unitarul de înmulțire modulară, $M_a$. Aceasta este de fapt partea cea mai dificilă a întregii implementări și poate fi foarte costisitoare din punct de vedere computațional, în funcție de modul în care este realizată. Pentru aceasta, vom trișa puțin: știm că pornim din starea $|1\rangle$, și dintr-o întrebare de verificare anterioară,

$$\begin{aligned} M_2|1\rangle &= |2\rangle & \\ M_2|2\rangle &= |4\rangle \\ M_2|4\rangle &= |8\rangle \\ M_2|8\rangle &= |1\rangle \\ \end{aligned}$$

Deci, vom construi un unitar care efectuează operațiile corecte pe aceste patru stări, dar lasă toate celelalte stări neschimbate. Aceasta este o trișare deoarece folosim cunoștințele noastre despre ordinul lui $2\bmod 15$ pentru a simplifica unitarul. Dacă am încerca de fapt să factorizăm un număr ai cărui factori ne sunt necunoscuți, nu am putea face acest lucru.

Verifică-ți înțelegerea

Citește întrebarea(întrebările) de mai jos, gândește-te la răspuns, apoi apasă triunghiul pentru a dezvălui soluția.

Cu cunoștințele tale despre modul în care operatorul $M_2$ transformă stările de mai sus, construiește operatorul dintr-o serie de gate-uri SWAP, care schimbă stările a doi qubiți. (Indiciu: rescrierea fiecărei stări $|i\rangle$ în binar te va ajuta.)

Răspuns:

Să rescriem acțiunea lui $M_2$ asupra stărilor în binar:

$$\begin{aligned} M_2|0001\rangle &= |0010\rangle \\ M_2|0010\rangle &= |0100\rangle \\ M_2|0100\rangle &= |1000\rangle \\ M_2|1000\rangle &= |0001\rangle \\ \end{aligned}$$

Fiecare dintre aceste acțiuni poate fi realizată cu un simplu SWAP. $M_2|0001\rangle$ se obține prin schimbarea stărilor qubitului $0$ și $1$. $M_2|0010\rangle$ se obține prin schimbarea stărilor qubitului $1$ și $2$. Și așa mai departe. Astfel, putem descompune matricea $M_2$ în următoarea serie de gate-uri SWAP:

$$M_2 = SWAP(0,1)SWAP(1,2)SWAP(2,3)$$

Amintindu-ne că operatorii acționează de la dreapta la stânga, să verificăm că aceasta are efectul dorit asupra fiecărei stări:

$$\begin{aligned} M_2|0001\rangle &= SWAP(0,1)SWAP(1,2)SWAP(2,3)|0001\rangle \\ &= SWAP(0,1)SWAP(1,2)|0001\rangle \\ &= SWAP(0,1)|0001\rangle \\ &=|0010\rangle \checkmark \\ M_2|0010\rangle &= SWAP(0,1)SWAP(1,2)SWAP(2,3)|0010\rangle \\ &= SWAP(0,1)SWAP(1,2)|0010\rangle \\ &= SWAP(0,1)|0100\rangle \\ &=|0100\rangle \checkmark \\ M_2|0100\rangle &= SWAP(0,1)SWAP(1,2)SWAP(2,3)|0100\rangle \\ &= SWAP(0,1)SWAP(1,2)|1000\rangle \\ &= SWAP(0,1)|1000\rangle \\ &=|1000\rangle \checkmark \\ M_2|1000\rangle &= SWAP(0,1)SWAP(1,2)SWAP(2,3)|1000\rangle \\ &= SWAP(0,1)SWAP(1,2)|0100\rangle \\ &= SWAP(0,1)|0010\rangle \\ &=|0001\rangle \checkmark \\ \end{aligned}$$

Acum putem scrie codul Circuit-ului echivalent cu acest operator în Qiskit.

Mai întâi, importăm pachetele necesare:

# Import necessary packages

import numpy as np
from fractions import Fraction
from math import floor, gcd, log

from qiskit import QuantumCircuit, QuantumRegister, ClassicalRegister
from qiskit.circuit.library import QFTGate
from qiskit.transpiler import generate_preset_pass_manager
from qiskit.visualization import plot_histogram

from qiskit_ibm_runtime import QiskitRuntimeService
from qiskit_ibm_runtime import SamplerV2 as Sampler

Apoi, construim operatorul $M_2$:

def M2mod15():
    """
    M2 (mod 15)
    """
    b = 2
    U = QuantumCircuit(4)

    U.swap(2, 3)
    U.swap(1, 2)
    U.swap(0, 1)

    U = U.to_gate()
    U.name = f"M_{b}"

    return U

# Get the M2 operator
M2 = M2mod15()

# Add it to a circuit and plot
circ = QuantumCircuit(4)
circ.compose(M2, inplace=True)
circ.decompose(reps=2).draw(output="mpl", fold=-1)

Algoritmul QPE folosește un Gate controlled-$U$. Acum că avem un Circuit $M_2$, trebuie să îl transformăm într-un Circuit controlled-$M_2$:

def controlled_M2mod15():
    """
    Controlled M2 (mod 15)
    """
    b = 2
    U = QuantumCircuit(4)

    U.swap(2, 3)
    U.swap(1, 2)
    U.swap(0, 1)

    U = U.to_gate()
    U.name = f"M_{b}"
    c_U = U.control()

    return c_U

# Get the controlled-M2 operator
controlled_M2 = controlled_M2mod15()

# Add it to a circuit and plot
circ = QuantumCircuit(5)
circ.compose(controlled_M2, inplace=True)
circ.decompose(reps=1).draw(output="mpl", fold=-1)

Acum avem Gate-ul nostru controlled-$U$. Dar pentru a rula algoritmul de Estimare Cuantică a Fazei, vom avea nevoie de controlled-$U^2$, controlled-$U^4$, până la controlled-$U^{2^{m-1}}$, unde $m$ este numărul de qubiți folosiți pentru estimarea fazei. Cu cât mai mulți qubiți, cu atât mai precisă va fi estimarea fazei. Vom folosi $m=8$ qubiți de control pentru procedura noastră de estimare a fazei. Deci, avem nevoie de:

$$M_{a^{2^k}}|y\rangle \equiv |a^{2^k} y \bmod N \rangle$$

unde indicele $k$, cu $0 \le k \le m-1 = 7$, corespunde Qubitului de control. Acum să calculăm $a^{2^k}\bmod N$ pentru fiecare valoare a lui $k$:

def a2kmodN(a, k, N):
    """Compute a^{2^k} (mod N) by repeated squaring"""
    for _ in range(k):
        a = int(np.mod(a**2, N))
    return a

k_list = range(8)
b_list = [a2kmodN(2, k, 15) for k in k_list]

print(b_list)

[2, 4, 1, 1, 1, 1, 1, 1]

Deoarece $a^{2^k} \bmod N = 1$ pentru $k \ge 2$, toți operatorii corespunzători ($M_8$ și mai mari) sunt echivalenți cu identitatea. Deci, trebuie să construim încă o singură matrice, $M_4.$ Notă: Această simplificare funcționează aici doar pentru că ordinul lui $2 \bmod 15$ este $4$. Odată ce $k=2$ (adică $2^k = 4$), fiecare putere ulterioară a operatorului este identitatea. În general, pentru numere mai mari $N$ sau alegeri diferite ale lui $a$, nu poți sări peste construirea puterilor superioare. Acesta este unul dintre motivele pentru care acesta este considerat un exemplu didactic: numerele mici permit scurtături care nu ar funcționa pentru cazuri mai mari.

def M4mod15():
    """
    M4 (mod 15)
    """
    b = 4
    U = QuantumCircuit(4)

    U.swap(1, 3)
    U.swap(0, 2)

    U = U.to_gate()
    U.name = f"M_{b}"

    return U

# Get the M4 operator
M4 = M4mod15()

# Add it to a circuit and plot
circ = QuantumCircuit(4)
circ.compose(M4, inplace=True)
circ.decompose(reps=2).draw(output="mpl", fold=-1)

Și ca înainte, îl transformăm într-un operator controlat-$M_4$:

def controlled_M4mod15():
    """
    Controlled M4 (mod 15)
    """
    b = 4
    U = QuantumCircuit(4)

    U.swap(1, 3)
    U.swap(0, 2)

    U = U.to_gate()
    U.name = f"M_{b}"
    c_U = U.control()

    return c_U

# Get the controlled-M4 operator
controlled_M4 = controlled_M4mod15()

# Add it to a circuit and plot
circ = QuantumCircuit(5)
circ.compose(controlled_M4, inplace=True)
circ.decompose(reps=1).draw(output="mpl", fold=-1)

Acum putem pune totul laolaltă pentru a găsi ordinul lui $2\bmod 15$ cu un Circuit cuantic, folosind estimarea de fază:

# Order finding problem for N = 15 with a = 2
N = 15
a = 2

# Number of qubits
num_target = floor(log(N - 1, 2)) + 1  # for modular exponentiation operators
num_control = 2 * num_target  # for enough precision of estimation

# List of M_b operators in order
k_list = range(num_control)
b_list = [a2kmodN(2, k, 15) for k in k_list]

# Initialize the circuit
control = QuantumRegister(num_control, name="C")
target = QuantumRegister(num_target, name="T")
output = ClassicalRegister(num_control, name="out")
circuit = QuantumCircuit(control, target, output)

# Initialize the target register to the state |1>
circuit.x(num_control)

# Add the Hadamard gates and controlled versions of the
# multiplication gates
for k, qubit in enumerate(control):
    circuit.h(k)
    b = b_list[k]
    if b == 2:
        circuit.compose(
            M2mod15().control(), qubits=[qubit] + list(target), inplace=True
        )
    elif b == 4:
        circuit.compose(
            M4mod15().control(), qubits=[qubit] + list(target), inplace=True
        )
    else:
        continue  # M1 is the identity operator

# Apply the inverse QFT to the control register
circuit.compose(QFTGate(num_control).inverse(), qubits=control, inplace=True)

# Measure the control register
circuit.measure(control, output)

circuit.draw("mpl", fold=-1)

2. Optimizează

Acum că am mapat Circuit-ul nostru, următorul pas este să îl optimizăm pentru a rula pe un anumit calculator cuantic. Mai întâi trebuie să încărcăm Backend-ul.

service = QiskitRuntimeService()

backend = service.backend("ibm_marrakesh")

Dacă nu ai timp disponibil în contul tău sau dorești să folosești un simulator din orice motiv, poți rula celula de mai jos pentru a configura un simulator care va imita dispozitivul cuantic pe care l-am selectat mai sus:

pm = generate_preset_pass_manager(optimization_level=2, backend=backend)

transpiled_circuit = pm.run(circuit)

print(f"2q-depth: {transpiled_circuit.depth(lambda x: x.operation.num_qubits==2)}")
print(f"2q-size: {transpiled_circuit.size(lambda x: x.operation.num_qubits==2)}")
print(f"Operator counts: {transpiled_circuit.count_ops()}")
transpiled_circuit.draw(output="mpl", fold=-1, style="clifford", idle_wires=False)

2q-depth: 188
2q-size: 281
Operator counts: OrderedDict({'sx': 548, 'rz': 380, 'cz': 281, 'measure': 8, 'x': 6})

3. Execută

# Sampler primitive to obtain the probability distribution
sampler = Sampler(backend)

# Turn on dynamical decoupling with sequence XpXm
sampler.options.dynamical_decoupling.enable = True
sampler.options.dynamical_decoupling.sequence_type = "XpXm"
# Enable gate twirling
sampler.options.twirling.enable_gates = True

pub = transpiled_circuit
job = sampler.run([pub], shots=1024)

result = job.result()[0]
counts = result.data["out"].get_counts()

plot_histogram(counts, figsize=(35, 5))

Vedem patru vârfuri clare la 00000000, 01000000, 10000000 și 11000000, cu câteva numărători în alte șiruri de biți din cauza zgomotului din calculatorul cuantic. Le vom ignora pe acestea și vom păstra doar cele patru dominante impunând un prag: doar numărătorile de peste acest prag sunt considerate un semnal real peste zgomot.

# Dictionary of bitstrings and their counts to keep
counts_keep = {}
# Threshold to filter
threshold = np.max(list(counts.values())) / 2

for key, value in counts.items():
    if value > threshold:
        counts_keep[key] = value

print(counts_keep)

4. Post-procesare

Pentru algoritmul lui Shor, o mare parte din algoritm se execută clasic. Prin urmare, vom pune restul în pasul de „post-procesare", după ce am obținut măsurătorile de la calculatorul cuantic. Fiecare dintre măsurătorile de mai sus poate fi convertită în numere întregi care, după ce le împărțim la $2^m$, reprezintă aproximările noastre pentru $\frac{k}{r}$, unde $k$ este aleatoriu de fiecare dată.

a = 2
N = 15

FACTOR_FOUND = False
num_attempt = 0

while not FACTOR_FOUND:
    print(f"\nATTEMPT {num_attempt}:")
    # Here, we get the bitstring by iterating over outcomes
    # of a previous hardware run with multiple shots.
    # Instead, we can also perform a single-shot measurement
    # here in the loop.
    bitstring = list(counts_keep.keys())[num_attempt]
    num_attempt += 1
    # Find the phase from measurement
    decimal = int(bitstring, 2)
    phase = decimal / (2**num_control)  # phase = k / r
    print(f"Phase: theta = {phase}")

    # Guess the order from phase
    frac = Fraction(phase).limit_denominator(N)
    r = frac.denominator  # order = r
    print(f"Order of {a} modulo {N} estimated as: r = {r}")

    if phase != 0:
        # Guesses for factors are gcd(a^{r / 2} ± 1, 15)
        if r % 2 == 0:
            x = pow(a, r // 2, N) - 1
            d = gcd(x, N)
            if d > 1:
                FACTOR_FOUND = True
                print(f"*** Non-trivial factor found: {x} ***")

ATTEMPT 0:
Phase: theta = 0.0
Order of 2 modulo 15 estimated as: r = 1

ATTEMPT 1:
Phase: theta = 0.75
Order of 2 modulo 15 estimated as: r = 4
*** Non-trivial factor found: 3 ***

Concluzie

După parcurgerea acestui modul, s-ar putea să ai o nouă apreciere pentru strălucirea lui Peter Shor, care a venit cu un algoritm atât de ingenios. Dar sperăm că ai atins și un nou nivel de înțelegere a simplității sale înșelătoare. Deși algoritmul poate părea impresionant de complex (sau intimidant), dacă îl descompui în fiecare pas de logică și îl parcurgi încet, vei reuși și tu să rulezi algoritmul lui Shor.

Deși suntem departe de a folosi acest algoritm pentru a factoriza numere precum RSA1024, calculatoarele noastre cuantice devin mai bune în fiecare zi, iar odată ce se atinge un prag numit toleranță la defecte, algoritmi precum aceștia vor urma în scurt timp. Este o perioadă entuziasmantă în care să înveți despre calculul cuantic!

Probleme

Concepte esențiale:

• Sistemele criptografice moderne se bazează pe dificultatea clasică a factorizării numerelor întregi mari.
• Aritmetica modulară — inclusiv structurile $\mathbb{Z}_N$ și $\mathbb{Z}_N^*$ — furnizează fundația matematică a algoritmului lui Shor.
• Problema factorizării unui număr întreg $N$ poate fi redusă la problema găsirii ordinului unui număr modulo $N$.
• Găsirea cuantică a ordinului folosește tehnici de estimare cuantică a fazei pentru a determina perioada funcției $a^x \mod N$.
• Algoritmul lui Shor constă dintr-un flux de lucru hibrid clasic-cuantic care selectează o bază, efectuează găsirea cuantică a ordinului și apoi calculează clasic factorii din rezultat.

Adevărat/Fals:

1. A/F Eficiența algoritmului lui Shor amenință securitatea criptării RSA.
2. A/F Algoritmul lui Shor poate fi executat eficient pe orice calculator cuantic modern.
3. A/F Algoritmul lui Shor utilizează estimarea cuantică a fazei (QPE) ca subrutină esențială.
4. A/F Partea clasică a algoritmului lui Shor implică calcularea celui mai mare divizor comun (CMDC).
5. A/F Algoritmul lui Shor funcționează numai pentru factorizarea numerelor pare.
6. A/F O rulare reușită a algoritmului lui Shor garantează întotdeauna factorii corecți.

Răspuns scurt:

1. De ce este considerat algoritmul lui Shor o potențială amenințare viitoare la adresa criptării RSA?
2. De ce este utilă găsirea perioadei, sau ordinului, a unei funcții exponențiale modulare pentru factorizarea unui număr în algoritmul lui Shor?

Probleme de provocare:

1. De câți Qubiți de control $m$ avem nevoie pentru un număr dat $N$ pe care încercăm să îl factorizăm, pentru a obține precizia în QPE necesară găsirii valorii corecte a ordinului $r$?

2. Urmând procedura pe care am descris-o aici pentru a factoriza 15, încearcă acum să factorizezi 21.