Šorov algoritam

Šorov algoritam, nazvan po matematičaru Piteru Šoru (engl. Peter Shor), je kvantni algoritam (algoritam koji funkcionoše na kvantnom računaru) za razlaganje celih brojeva na proste činioce formulisan 1994. U suštini on rešava sledeći problem: Za dati ceo broj N, nalazi njegove proste činioce.

Na kvantnom računaru, da bi sveo broj N na proste činioce, Shor-ov algoritam radi u polinomijalnom vremenu (vreme potrebno za izvršavanje algoritma je polinom u log N, što je veličina ulaza). Precizno, potrebno mu je vreme O((log N)³), pokazujući da se problem rastavljanja broja na proste činioce može efikasno rešiti na kvantnom računaru i da se nalazi u klasi složenosti BQP (kvantno polinomijalno vreme sa ograničenom greškom) problema. Ovo je znatno brže od većine poznatih algoritama za rastavljanje na proste činioce, izuzetak je algoritam sita polja opšteg broja koji radi u pod-eksponencionalnom vremenu — otprilike O(e^{1.9 (log N)1/3 (log log N)2/3}). Efikasnost Šorovog algoritma je u efikasnosti kvantnih Furijeovih transformacija, i modularnom stepenovalju pomoću kvadrata broja.

Ako bi kvantni računar sa dovoljnim brojem kvantnih bita mogao da radi bez uticaja šumova i ostalih kvantnih smetnji, Šorov algoritam bi se mogao koristiti za razbijanje šema kriptografije javnog-ključa kao što su veoma poznate RSA (RSA) šema. RSA se zasniva na pretpostavci da je rastavljanje velikih brojeva na proste činioce računarski neizvodljivo. Za sada koliko je poznato, ova pretpostavka važi za klasične (ne-kvantne) računare; ne zna se ni za jedan klasičan algoritam koji može da rastavlja na proste činioce u polinomijalnom vremenu. Međutim, Šorov algoritam pokazuje da je rastavljanje na proste činioce efikasno na idealnom kvantnom računaru, tako da je moguće da se pobedi RSA konstrukcijom velikog kvantnog računara. To je takođe bila velika motivacija za dizajniranje i konstrukciju kvantnih računara i za učenje novih algoritama za kvantne računare. U isto vreme otpočelo je istraživanje novih kriptosistema koji su bili sigurni od kvantnih računara, celokupno nazvani post-kvantna kriptografija.

2001-e, Šorov algoritam je demonstrirala grupa sa IBM-a, koja je rastavila 15 na 3 × 5, koristeći NMR (Nuklearnu magnetnu resonansu) implementaciju kvantnog računara sa 7 kvantnih bitova. Ipak, javile su se neke sumnje oko toga da li je IBM-ov eksperiment bio prava demonstracija kvantnog računara, pošto nikakvo kvantno uplitanje nije viđeno. Od IBM-ove implementacije, nekoliko drugih grupa je implementiralo Šorov algoritam koristeći fotonske kvantne bitove, naglašavajući da je uplitanje viđeno. 2012-te, rastavljanje broja 15 je ponovljeno. Takođe 2012-te, rastavljanje broja 21 je postignuto, postavljajući tako rekord za najveći broj rastavljen na proste činioce sa kvantnim računarom.

Postupak

Problem koji pokušavamo da rešimo je: za dat neparan složen broj $N$, naći ceo broj $d$, strogo između $1$ i $N$, koji deli $N$. Nas zanimaju neparne vrednosti broja $N$ jer parne vrednosti broja $N$ imaju broj $2$ kao prost činilac. Možemo da iskoristimo algoritam za testiranje da li je broj prost da budemo sigurni da je broj $N$ stvarno složen.

Štaviše, da bi algoritam radio, potrebno je da $N$ ne bude stepen činioca. Ovo se može testirati nalaženjem kvadratnog, kubnog, ..., $k$-og korena od $N$, za $k\leq \log _{2}(N)$, i proveravanjem da ni jedna od ovih vrednosti nije ceo broj. (Ovo zapravo isključuje da je $N=M^{k}$ za neke cele brojeve $M$ i $k>1$.)

Pošto $N$ nije stepen činioca, on je proizvod dva uzajamno prosta broja veća od $1$. Kao posledica kineske teoreme ostatka, broj $1$ ima bar četiri različita korena modula $N$, dva su $1$ i $-1$. Cilj algoritma je da nađe koren $b$ od jedan, osim $1$ i $-1$; takav $b$ će dovesti do rastavljanja broja $N$, kao i u drugim algoritmima za rastavljanje broja na činioce kao kvadratno sito.

Zauzvrat, pronalaženje takvog $b$ je svedeno na pronalaženje broja $a$ parnog redosleda sa određenom dodatnom osobinom (kao što je objašnjeno dole, neophodno je da uslov Koraka 6 klasičnog dela ne bude ispunjen). Kvantni algoritam se koristi za nalaženje redosleda nasumično odabranog elementa $a$, jer je nalaženje pravog redosleda težak problem na klasičnom računaru.

Šorov algoritam se sastoji iz dva dela:

1. Smanjenja, koje se može izvesti na klasičnom računaru, problema rastavljanja na proste činioce na problem nalaženja pravog redosleda.
2. Kvantnog algoritma da reši problem redosleda.

Klasičan deo

1. Odabrati nasumičan broj a < N
2. Nalaženje NZD(a, N). Ovo se može uraditi koristeći Euklidov algoritam.
3. Ako je NZD(a, N) ≠ 1, onda postoji ne-trivijalan činilac od N, tako da smo završili.
4. U suprotnom, iskoristiti pod-rutinu za nalaženje redosleda (ispod) da bi se našlo r, redosled sledeće funkcije:

   $f(x)=a^{x}\ {\mbox{mod}}\ N$,

   redosled $r$ od $a$ u $(\mathbb {Z} _{N})^{\times }$, koji je najmanji pozitivan ceo broj r za koji važi $f(x+r)=f(x)$ or $f(x+r)=a^{x+r}\ {\mbox{mod}}\ N=a^{x}\ {\mbox{mod}}\ N$
5. Ako je r neparan, ide se nazad na Korak 1.
6. Ako je a ^{r /2} ≡ −1 mod N), idi nazad na Korak 1.
7. NZD(a^r/2 ± 1, N) je ne-trivijalni činilac N. Završili smo.

Na primer: $N=15,a=2,r=4$, gcd(4 ± 1, N)

Kvantni deo: Pod-rutina za nalaženje redosleda

Kvantna kola korišćena za ovaj algoritam su posebno napravljena za svaki izbor N i nasumično a korišćeno u f(x) = a^x mod N. Za dato N, naći Q = 2^q tako da $N^{2}\leq Q<2N^{2}$, iz čega sledi $Q/r>N$. Ulazni i izlazni kvantni bit registri moraju da zadrže vrednosti super-pozicija od 0 do Q − 1, i tako imamo q kvantnih bita pojedinačno. Korišćenjem duplo više kvantnih bitova nego što se čini potrebnim osiguravamo da ima barem N različitih x koji daju isto f(x), iako se redosled r približava N/2.

Postupamo na sledeći način:

1. Postaviti registre na

   $Q^{-1/2}\sum _{x=0}^{Q-1}\left|x\right\rangle \left|0\right\rangle$

   gde x ide od 0 do Q − 1. Ovo početno stanje je superpozicija Q stanja.
2. Napraviti f(x) kao kvantnu funkciju i primeniti je na gornje stanje, da bi se dobilo

   $Q^{-1/2}\sum _{x}\left|x\right\rangle \left|f(x)\right\rangle .$

   Ovo je i dalje superpozicija Q stanja.
3. Primeniti kvantne Furijeove transformacije na ulazni registar. Ova transformacija (radići na superpoziciji stepena dvojke Q = 2^q states) koristi Q^ti jedinični koren kao što je $\omega =e^{2\pi i/Q}$ da rasporedi amplitudu bilo kog datog $\left|x\right\rangle$ stanja jednakog među svim Q $\left|y\right\rangle$ stanja, i da uradi to na drugačiji način za svako različito x:

   $U_{QFT}\left|x\right\rangle =Q^{-1/2}\sum _{y}\omega ^{xy}\left|y\right\rangle .$

   Ovo vodi do poslednjeg stanja

   $Q^{-1}\sum _{x}\sum _{y}\omega ^{xy}\left|y\right\rangle \left|f(x)\right\rangle .$

   Ovo je superpozicija od mnogo više Q stanja, ali mnogo manje Q² stanja. Iako postoje Q² izrazi u sumi, stanje $\left|y\right\rangle \left|f(x_{0})\right\rangle$ se može zanemariti kad god x₀ i x daju istu vrednost. Neka je
   • $\omega =e^{2\pi i/Q}$ Q^ti jedinični koren,
   • r redosled f,
   • x₀ najmanji od skupa x koji daju isto zadato f(x) (imamo x₀ < r), i
   • b koje ide od 0 do $\lfloor (Q-x_{0}-1)/r\rfloor$ tako da $x_{0}+rb<Q.$
   Onda je $\omega ^{ry}$ jedinični vektor u složenoj ravni ($\omega$ je jedinični koren a r i y su celi brojevi), i koeficijent $Q^{-1}\left|y\right\rangle \left|f(x_{0})\right\rangle$ u poslednjem stanju je

   $\sum _{x:\,f(x)=f(x_{0})}\omega ^{xy}=\sum _{b}\omega ^{(x_{0}+rb)y}=\omega ^{x_{0}y}\sum _{b}\omega ^{rby}.$

   Svaki izraz u ovoj sumi predstavlja različit put do istog rezultata, i dolazi do kvantne smetnje—kada jedinični vektori $\omega ^{ryb}$pokazuju u skoro istom smeru na složenoj ravni, što zahteva da $\omega ^{ry}$ pokazuju uz duž pozitivne realne ose.
4. Izvršiti merenje. Dolazimo do nekog ishoda y na ulaznom registru i $f(x_{0})$ na izlaznom registru. Pošto je f periodično, verovatnoća merenja nekog para y i $f(x_{0})$ je data pomoću

   $\left|Q^{-1}\sum _{x:\,f(x)=f(x_{0})}\omega ^{xy}\right|^{2}=Q^{-2}\left|\sum _{b}\omega ^{(x_{0}+rb)y}\right|^{2}=Q^{-2}\left|\sum _{b}\omega ^{bry}\right|^{2}.$

   Analize danas pokazuju da je ova verovatnoća veća, što je jedinični vektor $\omega ^{ry}$ pozitivnoj realnoj osi, ili je yr/Q bliže celom broju. Ukoliko r nije stepen 2, on neće biti činilac Q.
5. Koristeći Verižni razlomak na y/Q da bi napravili njegovu aproksimaciju, i napravimo c/r′ od njega tako da zadovoljava dva uslova:
   • A: r′<N
   • B: |y/Q - c/r′| < 1/2Q.
   Уколико смо задовољили ова два услова, r′ би био прави редослед r са великом вероватноћом тачности.
6. Proveriti da li je f(x) = f(x + r′) $\Leftrightarrow$ $a^{r}\equiv 1{\pmod {N}}$ Ako jeste, završili smo.
7. U suprotnom, uzeti još kandidata za r koristeći vrednosti blizu y, ili multiplikatore r′. Ako bilo koji kandidat zadovoljava uslove, završili smo.
8. U suprotnom, vrati se nazad na Korak 1 pod-rutine.

Objašnjenje algoritma

Algoritam se sastoji iz dva dela. Prvi deo algoritma svodi problem rastavljanja broja na proste činioce na problem nalaženja redosleda funkcije, i može se implementirati klasično. Drugi deo nalazi redosled korišćenjem kvantnih Furijeovih transformacija, i odgovoran je za kvantno ubrzanje algoritma.

Nalaženje činilaca iz redosleda

Brojevi manji od N i uzajamno prosti sa N formiraju konačnu Abelovu grupu $G$ sa množenjem po modulo N. Veličina je data pomoću Ojlerove fi funkcije $\phi (N)$. Do kraja Koraka 3, imamo ceo broj a u ovoj grupi. Pošto je grupa konačna, a mora imati konačan poredak r, najmanji pozitivan ceo broj takav da

$a^{r}\equiv 1\ {\mbox{mod}}\ N.\,$

Stoga, N se deli (piše se i | ) a ^r − 1. Pretpostavimo da možemo dobiti r, i da je paran. (Ako je r neparan, pogledajte Korak 5.) Sada je $b\equiv a^{r/2}{\pmod {N}}$ kvadratni koren 1 modulo $N$, različit od 1. Ovo je jer je $r$ redosled od $a$ modulo $N$, tako da $a^{r/2}\not \equiv 1{\pmod {N}}$, inače bi redosled $a$ u ovoj grupi bio $r/2$. Ako je $a^{r/2}\equiv -1{\pmod {N}}$, do Koraka 6 bismo morali da ponovimo algoritam sa drugim proizvoljnim brojem $a$.

Najzad, morali bismo da pogodimo $a$, redosleda $r$ u $G$, takav da je $b\equiv a^{r/2}\not \equiv 1,-1{\pmod {N}}$. To je zato što je $b$ kvadratni koren 1 modulo $N$, osim 1 i $-1$, čije postojanje garantuje kineska teorija ostatka, pošto $N$ nije stepen činioca.

Mi tvrdimo da je $d=\operatorname {gcd} (b-1,N)$ pravi činilac od $N$, za, $d\neq 1,N$. U stvari ako je $d=N$, onda se $N$ deli na $b-1$, tako da $b\equiv 1{\pmod {N}}$, protiv nastanka $b$. Ako sa druge strane $d=\operatorname {gcd} (b-1,N)=1$, onda pomoću Bezuovog stava postoje celi brojevi $u,v$ takvi da

$(b-1)u+Nv=1$.

Množenjem obe strane sa $b+1$ dobijamo

$(b^{2}-1)u+N(b+1)v=b+1$.

Pošto $N$ deli $b^{2}-1\equiv a^{r}-1{\pmod {N}}$, dobijamo da $N$ deli $b+1$, tako da $b\equiv -1{\pmod {N}}$, ponovo kontradiktujući nastanku $b$.

Tako da je $d$ potrebni pravi činilac $N$.

Pronalaženje periode

Šorov algoritam pronalaženja periode se uglavnom oslanja na sposobnost kvantnog računara da se nalazi u više stanja istovremeno. Fizičari nazivaju ovo ponašanje „superpozicija“ stanja. Da bi izračunali periodu funkcije f, mi ocenjujemo funkciju u svim tačkama istovremeno.

Kvantna fizika nam ipak ne dozvoljava pristup svim ovim informacijama direktno. Merenje će dati samo jedno od svih mogućih vrednosti, uništavajući sva ostala. Da nije teoreme o ne-kloniranju, mogli bismo prvo da izmerimo f(x) bez merenja samog x, i onda napravili par kopija rezultujućeg stanja (što je superpozicija svih stanja koje imaju isto f(x)). Merenjem x-a u ovim stanjima bismo dobili različite x vrednosti koje daju isto f(x), što nas vodi do periode. Pošto ne možemo napraviti tačne kopije kvantnog stanja, ovaj metod ne funkcioniše. Stoga moramo pažljivo transformisati superpoziciju u drugo stanje koje će vratiti tačan odgovor sa najvećom verovatnoćom. Ovo se postiže kvantnim Furijeovim transformacijama.

Šor je stoga morao rešiti tri „implementaciona“ problema. Svi su morali biti implementirani „brzo“, što znači da mogu biti implementirani sa brojem kvantnih ulaza koji je polinomijalan u $\log N$.

1. Napraviti superpoziciju stanja. Ovo se može postići primenom Hadamard kola na sve kvantne bitove u ulaznom registru. Još jedan način bi bio da se iskoriste kvantne Furijeove transformacije (pogledati ispod).
2. Implementirati funkciju f kao kvantnu transformaciju. Da bi ovo postigao, Šor je koristio ponovljeno kvadriranje za njegovu modularnu eksponencijalnu transformaciju. Bitno je naglasiti da je ovaj korak teže implementirati nego kvantne Furijeove trahcformacije, jer ono zahteva pomoćne kvantne bitove i znatno više ulaza da bi se izvršilo.
3. Izvesti kvantne Furijeove transformacije. Koristeći ulaze sa kontrolom rotacije i Hadamard ulaze, Šor je dizajnirao kolo za kvantne Furijeove transformacije (sa Q = 2^q) samo $q(q-1)/2=O((\log Q)^{2})$ ulaza.

Posle svih ovih transformacija mera će dati aproksimaciju periode r. Zbog jednostavnosti pretpostavimo da postoji y takvo da je yr/Q ceo broj. Onda je verovatnoća da izmerimo y 1. Tada primećujemo da važi

$e^{-2\pi ibyr/Q}=1\,$

za sve cele brojeve b. Stoga će suma čiji nam kvadrat daje verovatnoću da izmerimo y biti Q/r pošto b zahteva otprilike Q/r vrednosti i tako je verovatnoća $1/r^{2}$. Postoje r y takvi da je yr/Q ceo broj i ujedno r mogućnosti za $f(x_{0})$, tako da se mogućnosti sumiraju na 1.

Beleška: još jedan način da se objasni Šorov algoritam jeste da se primeti da je on maskirani algoritam procene kvantne faze.

Usko grlo

Dužina trajanja uskog grla Šorovog algoritma je kvantno modularno stepenovanje, što je znatno sporije od kvantnih Furijeovih transformacija i klasičnog pre-/post-procesiranja. Postoji nekoliko pristupa da se naprave i optimizuju kola za modularno stepenovanje. Najlakši i (trenutno) najpraktičniji pristup jeste da se oponašaju konvencionalna aritmetička kola sa promenljivim ulazima, počevši sa sabiračima sa prenosom talasa. Znanje baze i modula stepenovanja olakšava dalju optimizaciju. Promenljiva kola tipično koriste oko $n^{3}$ ulaza za $n$ kvantnih bitova. Alternativne tehnike asimptotski poboljšavaju broj ulaza koristeći kvantne Furijeove transformacije, ali nisu konkurentni sa manje od 600 kvantnih bitova zbog velikih konstanti.

Diskretni logaritmi

Pretpostavimo da znamo da je $x=g^{r}{\pmod {p}}$, za neko r, i da želiom da izračunamo r, koje je diskretni logaritam: $r=\log _{g}x{\pmod {p}}$. Razmotrimo Abelovu grupu $\left(\mathbb {Z} _{p}\right)^{\times }\times \left(\mathbb {Z} _{p}\right)^{\times }$ gde svaki faktor odgovara modularnom množenju ne-nula vrednosti, pretpostavljajući da je p glavni. Sada, razmotrimo funkciju

$f(a,b)=g^{a}x^{-b}{\pmod {p}}.$

Ovo nam daje problem skrivenih Abelovih podgrupa, gde f odgovara grupnom homomorfizmu. Jezgro odgovara modularnom multiplikatoru (r,1). Tako da ako nađemo jezgro, mi možemo da nađemo i r.

Literatura

• Nielsen, Michael A. & Chuang, Isaac L. (2000), Quantum Computation and Quantum Information, Cambridge University Press .
• Phillip Kaye, Raymond Laflamme, Michele Mosca, An introduction to quantum computing, Oxford University Press, 2007, ISBN 0-19-857049-X
• "Explanation for the man in the street" by Scott Aaronson, "approved" by Peter Shor. (Shor wrote "Great article, Scott! That’s the best job of explaining quantum computing to the man on the street that I’ve seen."). An alternate metaphor for the QFT was presented in one of the comments. Scott Aaronson suggests the following 12 references as further reading (out of "the 10¹⁰⁵⁰⁰⁰ quantum algorithm tutorials that are already on the web.")
• Shor, Peter W. (1997), „Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer”, SIAM J. Comput. 26 (5): 1484–1509, arXiv:quant-ph/9508027v2, Bibcode 1999SIAMR..41..303S, DOI:10.1137/S0036144598347011 . Revised version of the original paper by Peter Shor ("28 pages, LaTeX. This is an expanded version of a paper that appeared in the Proceedings of the 35th Annual Symposium on Foundations of Computer Science, Santa Fe, NM, Nov. 20--22, 1994. Minor revisions made January, 1996").
• Quantum Computing and Shor's Algorithm, Matthew Hayward, 2005-02-17, imsa.edu, LaTeX2HTML version of the original 2750 line LaTeX document, also available as a 61 page PDF or postscript document.
• Quantum Computation and Shor's Factoring Algorithm, Ronald de Wolf, CWI and University of Amsterdam, January 12, 1999, 9 page postscript document.