7 Modularna aritmetika
8.1 Iskanje periode funkcije
Imamo periodiˇcno funkcijo, ki slika ˇstevila {0,1, ..., M−1} v neko podmnoˇzicoS, s periodo r. Ker slikamoM ˇstevil in je perioda r, je ˇstevilo period ravno Mr. Za iskanje periode funkcije zahtevamo dve lastnosti. Prva je, da je na vsakem intervalu to injektivna funkcija, torej da se vrednosti funkcije na vsaki od period ne ponavljajo. Druga lastnost, ki jo zahtevamo, pa je, da r deli M. Ta lastnost ni potrebna, ˇce imamo funkcijo z veliko periodami, torej Mr r, ali drugaˇceM je mnogo veˇcji od r2.
V kvantnem raˇcunalniku je funkcija podana na naslednji naˇcin. Imamo vrata Cf, katere vhodni podatki so x in izhodni f(x). To je povsem klasiˇcno vezje.
Denimo, da ima vhodni podatek velikost M, ki je ˇstevilo s 1000 ˇstevkami. Torej je M ∼ 101000. r naj bo pribliˇzno √
M in zato ˇstevilo s 500 ˇstevkami, kar je ˇse vedno ogromna ˇstevilka. ˇCe bi ˇzeleli najti periodo r na klasiˇcen naˇcin, bi lahko recimo izbirali nakljuˇcne vhodne podatke, dokler ne bi dobili nekega vzorca.
Do-26
kler ne dobimo dveh enakih rezultatov funkcije za dva razliˇcna vhodna podatka o sami periodi nimamo prav nobenega podatka, saj sami rezultati funkcije navadno nimajo drugega vzorca, kot da se v nekem trenutku ponovijo. Pri tem, koliko ˇcasa potrebujemo, da na tak naˇcin najdemo vzorec (dobimo isti vrednosti funkcije za razliˇcna vhodna podatka), nam pomaga rojstnodnevni paradoks. Lahko, da bomo potrebovalir vhodnih podatkov, da bomo naˇsli vzorec, vendar se izkaˇze, da jih bo z verjetnostjo 12 dovolj ˇze√
r. Vendar pa je to ˇse vedno zelo veliko ˇstevilo, saj je v naˇsem primeru sestavljeno iz 250 ˇstevk, kar bi pomenilo, da potrebujemo pri-bliˇzno 10250 nakljuˇcno izbranih vhodnih podatkov. To je seveda preveˇc, kar nam onemogoˇca, da bi periodo funkcije lahko poiskali na klasiˇcen naˇcin.
Kvantni algoritem najprej pretvori klasiˇcno vezje v kvantnega.
Kot vhodne podatke vzame|xiin niˇcle |0i, izhodni podatki pa so|xiin|f(x)i.To deluje tudi na superpoziciji. (Dokaza, da je moˇzno vsako klasiˇcno vezje pretvoriti v kvantnega, v diplomi ne bomo pokazali, temelji pa na tem, da je moˇzno vsa klasiˇcna vrata nadomestiti z enimi samimi (NAND), ta pa lahko na primeren naˇcin nadomestimo s kvantnimi vrati.) Priredimo enakomerno superpozicijo na x (amplitude so enake) in potem poˇzenemo vezje. Tako za izhodni podatek dobimo normirano vsoto
√1 M
M−1
X
x=0
|xi|f(x)i.
V naslednjem koraku izmerimo izhodne podatke |f(x)i v drugem registru. Ko izmerimo, dobimo nakljuˇcno vrednost f(a) =c za nek a, oz. superpozicijo
√1 M
M−1
X
x=0
αx|f(x)i,
kjer je αx neniˇceln le za tiste x, za katere je f(x) = c in je za vse te x enak.
Namreˇc, ker sta registra |xi in |f(x)i prepletena, tudi |xi preide v superpozicijo tistih stanj x, za katera je f(a) =c.
Spomnimo se, da zamik vhodne superpozicije ne vpliva na izhodni podatek.
Zato lahko to periodiˇcno superpozicijo v nadaljnjem razmiˇsljanju brez izgube sploˇsnosti zamaknemo v levo ali desno, tako da bo naˇsa prva neniˇcelna ampli-tudaα0. Seveda se perioda pri tem ohranja. Ta zamik storimo zato, da bodo naˇse neniˇcelne amlitude ravno veˇckratniki periode. Superpozicija je sedaj
r r M
M r−1
X
j=0
|jri.
Sedaj lahko naredimoFourierovo vzorˇcenje, to je izvedemo Fourierovo transforma-cijo in izmerimo stanje. Rezultat Fourierovega merjenja je nakljuˇcen veˇckratnik
M
r . Ko veˇckrat poˇzenemo eksperiment, dobimo razliˇcne veˇckratnike. Z uporabo Evklidovega algoritma za raˇcunanje najveˇcjega skupnega delitelja teh rezultatov dobimo Mr. Sedaj preprosto dobimo r, tako da M delimo z Mr .
Poglejmo, kako izgleda kvantno vezje, ki ustreza zgornjemu algoritmu za iska-nje periode funkcije.
Zaˇcnemo s samimi |0i in izvedemo kvantno Fourierovo transformacijo, ki nam vrne enakomerno superpozicijo √1
M
PM−1
x=0 |xi.Nato na vratihUf uporabimo funk-cijo f, ki nam preslika trenutno superpozicijo v prvem registru v superpozicijo
√1 M
PM−1
x=0 |xi|f(x)i. Sedaj lahko izmerimo rezultat, ki je shranjen v drugem regi-stru, ni pa to pomembno, saj bo konˇcni rezultat v vsakem primeru enak. Gre za princip odloˇzenega merjenja, ki pove, da dokler ni nobene komunikacije med kubiti v prvem in drugem registru, ni pomembno ali izmerimo kubite v drugem registru ali ne. V prvem registru bomo vselej dobili enak rezultat. Denimo, da vseeno
iz-28
merimo rezultat funkcije in dobimof(a). Sedaj naredimo Fourierovo vzorˇcenje na prvem registru, kjer imamo periodiˇcno superpozicijo. Ker fazni zamik vhodnega podatka ne vpliva na konˇcni rezultat, lahko privzamemo, da smo ga zamaknili in kot rezultat merjenja dobili f(0). Ko izvedemo Fourierovo vzorˇcenje, dobimo na-kljuˇcni veˇckratnik Mr . Celoten postopek veˇckrat ponovimo in izraˇcunamo najveˇcji skupni delitelj rezultatov in tako dobimo Mr .Iz tega preprosto dobimo periodo r, tako daM delimo z Mr.
Pomislimo ˇse na primer, ko r ne deli M. Predpostavljamo, da je M dovolj velik, denimo veˇcji od 2r2. Drugaˇce,
M r >2r,
kar pomeni, da je ˇstevilo period veˇcji od same periode. V tem primeru vezje ostane popolnoma enako. Za konˇcen rezultatL velja, da je
L M ∼ t
r,
za neko celo ˇstevilo t. L je rezultat algoritma, M poznamo, r bi radi poznali, t pa je neka neznana spremenljivka. Na tem mestu uporabimo, da je tr najboljˇsi pribliˇzek za ML s tako majhnim imenovalcem, kot je r. Torej uporabimo dejstvo, da je r zelo majhen, manjˇsi od √
M . Tako lahko pokaˇzemo, da je tr najboljˇsi tak pribliˇzek, ki ga lahko dobimo za ML, kjer je imenovalec manjˇsi od√
M .Glede na to, lahko razstavimo tr z uporabo veriˇznih ulomkov, to pa lahko zelo hitro naredimo tudi na klasiˇcnih raˇcunalnikih. Torej lahko najdemo periodo funkcije tudi takrat, kor ne deliM.
8.2 Algoritem
Sedaj, ko imamo vso potrebno znanje, poglejmo, kako Shorov algoritem v celoti deluje. V pomoˇc nam bo primer N = 21 in x= 2 skupaj s tabelo
a 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 f(a) 1 2 4 8 16 11 1 2 4 8 16 11 1 2 4 8 16
.
Algoritem zaˇcnemo z vhodnim podatkom, ki je ˇstevilo, ki ga ˇzelimo faktorizi-rati. Izberemo nakljuˇcno ˇstevilo 1< x < N, denimo x= 2.
V prvi register naloˇzimo same niˇcle. Na tem mestu moramo izbrati takM,da bomo imeli veˇcjo verjetnost, da bo naˇs algoritem uspeˇsen. M moramo torej izbrati tako, da bo dovolj velik oz. da zadosti pogojem iskanja periode, torej M > 2r2 oz.
M
r >2r, kjer je Mr ˇstevilo ponovitev periode. Vendar o r vemo le to, da je manjˇsi od N. Zato lahko vzamemo tak M, da bo zadostoval pogoju M > 2N2. Za naˇs primer moramo torej vzeti M >2·212 = 882, vzemimo M = 1002. Na vhodnem podatku izvedemo kvantno Fourierovo transformacijo, ki nam kot rezultat vrne enakomerno superpozicijo stanj |0i,|1i, ...|M −1i, v naˇsem primeru je to
√ 1 1002
1002
X
k=0
|ki.
Na tej superpoziciji izvedemo funkcijof(a) = xa(modN) = 2a(mod21).Ustvarimo novo superpozicijo vezanih stanj
√1 M
M
X
a=0
|ai|f(a)i.
Sedaj iˇsˇcemo periodo. Izmerimo stanje drugega registra, v katerem je shranjen rezultat funkcije f kot superpozicija stanj |f(a)i, in dobimo neko vrednost, v naˇsem primeru denimo f(a) = 4. Superpozicija vezanih stanj √1
M
PM
a=0|ai|f(ai se sedaj spremeni in postane superpozicija tistih stanj, katerih vrednosti funkcije f je 4. Takih stanj je natanko Mr,zato je amplituda vsakega moˇznega stanja enaka pr
M :
r 6
1002|2i|4i+ r 6
1002|7i|4i+. . .+ r 6
1002|997i|4i.
30
Torej je superpozicija prvega registra enaka P1001
a=0 αa|ai, kjer je αa neniˇceln za a = 2,8,14, ...,998. V naslednjem koraku naredimo Fourierovo vzorˇcenje na pr-vem registru. Uporabimo lastnost Fourierove transformacije, ki pravi, da zamik vhodnega podatka ne vpliva na konˇcni rezultat in zamaknimo superpozicijo tako, da bo prva neniˇcelna amplituda amplituda prvega stanja: P1001
a=0 αa|ai, kjer je αa neniˇceln za a = 0,6,12, ...,996. Na prvem registru izvedemo Fourierovo vzorˇcenje torej Fourierovo transformacijo in meritev. Kot smo videli pri poglavju o Fouri-erovi transformaciji, nam ta superpozicijo s periodo r preslika v superpozicijo s periodo Mr. V naˇsem primeru tako dobimo novo superpozicijo
1001
X
a=0
βa|ai,
kjer jeβa neniˇceln za a= 0,167,334,501,668,835,kar so ravno veˇckratniki 10026 = 167. Ko izmerimo register, dobimo torej nek veˇckratnik Mr, na primer 501. Ko ta korak veˇckrat ponovimo, z Evklidovim algoritmom za iskanje najveˇcjega skupnega delitelja dobimo ravno Mr = 167. Sedaj lahko periodor izraˇcunamo s preprostim raˇcunom:
M : M
r = 1002 : 167 = 6.
Ko imamo periodorfunkcijef, preverimo, ˇce jersodo ˇstevilo inxr/2 6=±1(mod(N).
Ce to velja, se algoritem ustavi, razstavimoˇ N in smo konˇcali. V nasprotnem primeru poskusimo ponovno. Ker vemo, da bomo uspeli z verjetnostjo 12, nam algoritma ne bo potrebno velikokrat ponoviti. V naˇsem primeru se bomo ustavili, saj je 6 sodo ˇstevilo in 23 = 8 6= ±1(mod21). Razstavimo ˇstevilo 21 z iskanjem najveˇcjega skupnega delitelja:
D(21,8−1) = 7, D(21,8 + 1) = 3.