OSNOVE KVANTNEGA RAČUNALNIŠTVA, 2. DEL MATIJA PRETNAR Fakulteta za matematiko in fiziko Univerza v Ljubljani Math. Subj. Class. (2010): 68Q12, 81P68 V drugem delu članka si ogledamo Deutschev algoritem, ki je bil prvi kvantni algoritem, ter najznamenitejsa kvantna algoritma: Groverjev algoritem za iskanje v neurejeni tabeli in Shorov algoritem za razcep na prastevila. THE BASICS OF QUANTUM COMPUTING, PART 2 The second part looks at Deutsch's algorithm, which was the first quantum algorithm, and at two most famous quantum algorithms: Grover's search algorithm and Shor's factorization algorithm. Simulacija klasičnih vezij Preden se začnemo navduševati nad učinkovitostjo kvantnih računalnikov, najprej preverimo, ali lahko z njimi res izračunamo vse, kar bi Želeli. Torej, za vsako funkcijo f: {0,1}m ^ {0,1}n, ki jo znamo izračunati na običajnem računalniku, zelimo poiskati ustrezno unitarno preslikavo oziroma kvantno vezje Uf, ki bo dajala enake odgovore. Kaj pomeni, da bodo odgovori enaki? Ce nastavimo kubite na začetno bazno stanje |x) = |xoXi ■ ■ ■ xm-1), kjer so Xi posamezni vhodni biti, potem zelimo s pomočjo Uf izračunati stanje |f(x)) = |y0y1 ■ ■ ■ yn-1). Toda kako lahko z unitarnimi preslikavami izračunamo funkčijo, ki nima inverza? Se več: kaj, če funkčija f nima enakega stevila vhodnih in izhodnih bitov? Obema tezavama se izognemo tako, da vezje poleg vhoda |x) sprejme se nekaj dodatnih kubitov, na katere bomo shranili izhod |f (x)). Za začetek si oglejmo primer, ko f izračuna en bit, torej ko je n = 1. Vezje Uf tedaj iz stanja |x)|0) izračuna stanje |x)|f(x)). Natančneje: iz stanja |x)|b) bomo izračunali stanje |x)|b © f (x)), kjer je ekskluzivni ali © podan z: 0 © 0 = 0 0 © 1 = 1 1 © 0 = 1 1 © 1 = 0. Iz enakosti cnot|x)|b) = |x)|b © x) izvira tudi oznaka za cnot v kvantnih vezjih. Ce je izhodnih kubitov več, ravnamo podobno: iz vhoda |x)|b), kjer je b zdaj zaporedje n kubitov, enako izračunamo |x)|b © f (x)), le da tokrat © deluje po posameznih kubitih. Obzornik mat. fiz. 61 (2014) 2 41 Matija Pretnar Na splošni superpoziciji vezje Uf deluje linearno: stanje J2xb ax,b|x)|b), kjer x b označuje vsoto po vseh 2m moZnih baznih stanjih |x) in vseh 2n moZnih stanjih kubitov za odgovor |b), spremeni v ^xbax,b|x)|6 © f (x)). Običajno pa bodo kubiti za odgovor nastavljeni na |0), zato bo odgovor kar superpozicija ax|x)|f (x)). Ali lahko na tak način simuliramo vsa klasična vezja? Vemo, da lahko vsa taka vezja sestavimo iz negacije in konjunkcije. Negacijo simuliramo tako, da s kontrolirano negacijo stanje kontrolnega kubita presnamemo na ciljni kubit, nato pa ciljni kubit negiramo z vrati X. Zaradi izreka o ne-podvajanju seveda ne moremo presneti splosnega stanja, le bazni stanji |0) in |1), a to je za simulacijo klasicnega vezja dovolj. Za konjunkcijo pa uporabimo Toffolijeva vrata T. Ta delujejo podobno kot cnot, le da imajo dva kontrolna in en ciljni kubit, ki ga negiramo takrat, ko sta oba kontrolna kubita enaka |1). Velja torej T1110) = 1111) in T1111) = 1110), vsa druga bazna stanja pa vrata T pustijo pri miru. S pomocjo teh dveh vrat lahko izrazimo vsa preostala vezja, na primer disjunkcijo. Disjunkcijo lahko s pomocjo negacije in konjunkcije izrazimo kot x1 V x2 = —(—XI A —x2), to pa implementiramo z naslednjim vezjem: |xi) |x2) |0) |0) |0) |0) C > X U r X VJ U r > - VJ w • r X VJ i) xi) X2) -Xi) -X2) —x1 A —x2) Xi V x2) (1) Pri tem smo zaradi sorodnega delovanja vrata T oznacili podobno kot cnot. Na tak nacin vsako klasicno funkcijo f simuliramo s kvantnim vezjem Rf, ki poleg vhodnih podatkov dobi se nekaj kubitov delovnega prostora, poleg odgovora pa vrne se nekaj smeti, ki so posledica pomoznih racunov. Teh smeti se hocemo znebiti, saj zaradi prepletenosti vplivajo na stanja vhodnih in izhodnih kubitov. K sreci tudi tu obstaja re sitev: po uporabi vezja Rf odgovor presnamemo na dodatne kubite, nato pa uporabimo inverz R-1, ki kubite z odgovorom in smetmi povrne v prvotno prazno stanje, na dodatnih kubitih pa ostane kopija odgovora. |x) |0) |0) |x) |0) |f (x)) 42 Obzornik mat. fiz. 61 (2014) 2 Osnove kvantnega računalništva, 2. del Ker so vsa vezja unitarna, vemo, da inverz obstaja. Toda kako ga izračunamo? Kot vemo, velja (UV)-1 = V-1U-1, zato inverz dobimo tako, da inverze posameznih vrat sestavimo v obratnem vrstnem redu. Ker so vrata X, Y, Z, H, cnot in T sama svoj inverz, lahko vsako vezje, ki je sestavljeno iz njih, obrnemo kar tako, da ga izvedemo od desne proti levi (nekatere implementacije to enostavno dopusčajo). Deutschev algoritem Spodobi se, da si kot prvi kvantni algoritem ogledamo Deutschev algoritem [1], saj je bil to prvi kvantni algoritem, ki je deloval učinkoviteje od klasičnega. Recimo, da zelimo za nam neznano funkcijo f: {0,1} ^ {0,1} ugotoviti, ali je konstantna, pri tem pa imamo na voljo le "črno skatlo", torej neko napravo, ki na nam neznan način računa vrednosti f. Ce je ta črna skatla klasično vezje, nam ne ostane drugega kot to, da jo uporabimo dvakrat, da izračunamo f (0) in f (1), nato pa odgovora primerjamo. Ce pa imamo na voljo kvantno vezje Uf: |x> — Uf f — IX - |b © f (x)>, nam Deutsčhev algoritem odgovor izračuna z le eno uporabo Uf. Glavni ideji sta dve. Prva je očitna: na vhodnem kubitu podamo super-pozičijo |+>, da hkrati izračunamo Uf na |0> in |1>. Druga pa je bolj zvita: na izhodnem kubitu namesto |0> podamo |->. Po uporabi vezja na |x>|—> je stanje namrečč enako Uf |x>|—> = ^Uf | x>| 0> - TUf |x>|1> = ^|x>|0 © f (x)> - T| x>11 © f (x)>. Ce je f (x) = 0, je končno stanje enako | x> | ->, če pa je f (x) = 1, je izhodno stanje enako — |x>|—>. Torej v splosnem velja, da je izhodni kubit v stanju (-1)f (x)|x>|—>. Ce za vhod podamo |+>, dobimo Uf |+>|—> = T Uf |0>|—> + T Uf |1>|—> = T (—1)f (0) |0>|—> + T (—1)f (1)|1>|—> = (—1)f (0) (^7510> + |1>)|—>. Ce je f konstantna in je f (0) = f (1), je prvi kubit v stanju |+>, sičer pa je v stanju |—>. Kako ugotovimo, v katerem stanju je? Po uporabi vezja na prvem kubitu uporabimo Hadamardova vrata H. Ta |+> slikajo v |0>, |—> pa v |1>, kar potem izmerimo na običajen način. 41-51 43 Matija Pretnar Podobno lahko stanje pomerimo v vsaki ortonormirani bazi, le namesto H moramo izbrati ustrezno unitarno preslikavo. Celoten Deutschev algoritem izvedemo s sledečim vezjem: >> f (0) = f (1) |1> f (0) = f (1) Ce je funkcija f konstantna, izmerimo |0>, če ni, pa |1>. Vprasanje, na katero odgovori Deutschev algoritem, ni ravno najbolj zanimivo, a v odgovoru nanj smo videli nekaj glavnih trikov, ki se uporabljajo v skoraj vseh kvantnih algoritmih. Groverjev algoritem Zanimivejsa je naslednja naloga: za funkcijo f: {0,1,..., N — 1} ^ {0,1} zelimo poiskati x, za katerega velja f (x) = 1. To je tako, kot bi v (papirnatem) telefonskem imeniku iskali osebo, ki zivi na danem naslovu. Ker je imenik urejen po priimkih in ne po naslovih, nam ne ostane drugega, kot da ga preiscemo od zacetka do konca. Ce imamo sreco, osebo najdemo takoj, ce ne, pa lahko sele cisto na koncu. Cas, ki ga potrebujemo za tako iskanje, narasca linearno z velikostjo imenika: za stokrat vecji imenik potrebujemo stokrat vec casa. Pravimo, daje casovna zahtevnost problema enaka O(N). Groverjev algoritem [3] pa isti problem na kvantnem racunalniku resi s casovno zahtevnostjo O(VN), kar pomeni, da za stokrat vecji imenik potrebujemo le desetkrat vec casa. Ideja je sledeca: zacnemo s superpozicijo vseh baznih stanj, nato pa amplitudi ustreznih stanj zamenjamo predznak, nazadnje pa vse amplitude »prezrcalimo« prek povprecja, s cimer se amplituda vseh ustreznih stanj poveca (slika 1). ttx M o oo (a) » ttx M (b) |x> (c) |x> a x Slika 1. Amplitude baznih stanj pri (a) začetnem stanju, (b) obratu faz ustreznih stanj in (c) zrcaljenju amplitud prek povprečja M- Ustrezna stanja so označena z znakom •. Ta dva koraka nato dovoljkrat ponovimo, na koncu pa izmerimo stanje. Z veliko verjetnostjo bo to izmerjeno stanje ravno eno od ustreznih. Ustreznost izmerjenega stanja nato preverimo se s prvotno funkcijo f, in ce odgovor ni ustrezen, postopek ponovimo. Najprej moramo pokazati, da sta obrat faze in zrcaljenje prek povprecja unitarni preslikavi, nato pa se 44 Obzornik mat. fiz. 61 (2014) 2 Osnove kvantnega računalništva, 2. del ugotoviti, kolikokrat ju moramo ponoviti, da pridemo do odgovora. Zaradi enostavnosti bomo privzeli, da je N = 2n, in stanja |0), |1),..., |N — 1) izenačili z vsemi baznimi stanji |x) sistema n kubitov. Obrat faze F je seveda unitarna preslikava: vsa ustrezna bazna stanja imajo lastno vrednost —1, vsa preostala pa 1. Implementiramo jo tako, da izhodni kubit pri vezju Uf, ki računa funkcijo f, nastavimo na |—). Tako kot pri Deutschevem algoritmu vidimo, daje Uf|x)|—) = (—1)f(x)|x)|—). Zrcaljenje prek povprečja definiramo kot D = 2|^)(^| — I, pri čemer je |,0) = h®n|0n) superpozicija vseh 2n baznih stanj, pa ortogonalni projektor na vektor saj |^>) slika v = = (0|<^)|'0). Preslikava D res zrcali prek povprecja saj iz D E ax|x) = E M2|^| — I)|x) = E (2ax|^)(^|x) — |x)) x x = 2 E i7Xf|^> — E ax|x) = 2 E 3= E — E ax|x) x x' — I )|x) = 2^(2ax| x «x' VN'r/ ~^ VN^ VN' x x =2 Ex' ax' N —Y1 ax|x) = |x)—Y1 ax|x) = —ax)|x) xx |x) — > ax|x) = x x x vidimo, da amplitudo ax spremeni v ^ — (ax — = 2^ — ax. Ker je = H®n|0n) in ker je H®n sebi adjungirana, lahko pisemo: D = 2|'0)('0| — I = 2H ®n|0n)(0n|H®n — H®nH®n = H ®n(2|0n){0n| — I)H ®n Preslikava 2|0n)(0n| — I bazni vektor |0n) slika v |0n), vse druge bazne vektorje |x) pa v —|x), zato je unitarna, torej je unitarna tudi preslikava D. Poleg tega tudi vidimo, kako implementiramo D. Med dvoje Walsh-Hadamardovih vezij vrinemo vezje, ki obrne fazo vsem baznim stanjem, razlicnim od |0n). To spet lahko dosezemo tako, da na izhodnem kubitu |—) uporabimo vezje, ki |0n) slika v |1), preostala bazna stanja |x) pa v |0). Tako vezje lahko naredimo s konjunkcijo negacij vseh vhodnih kubitov. Vezje, ki izvede celoten korak Groverjevega algoritma, je torej: - df |p) Kolikokrat moramo izvesti ta korak? Vidimo, da se vsem ustreznim stanjem amplituda spreminja hkrati. Podobno velja za vsa neustrezna stanja. Privzemimo, da vemo, da je vseh ustreznih stanj p. Tedaj lahko definiramo superpozicijo ustreznih stanj |^>i) = Exf(x)=1|x) in superpozicijo 41-51 45 Matija Pretnar neustreznih stanj |^>0) = (x)=0|x). Tedaj je superpozicija vseh stanj enaka = l^i) + 1^0)- Ce označimo iJjN = sin$, velja = sin $|<^i) + cos $|^>0). Očitno velja, da obrat faze F deluje kot F|^i) = ) in F|^>0) = |^>0), saj vsem ustreznim stanjem obrne fazo, neustrezna pa pusti pri miru. Za zrcaljenje prek povprečja D pa lahko pokazemo D|pi) = 2|^)<^i) - |^i) = 2sin$|^) - |^i) = 2 sin $(sin $|^>i) + cos $|^>0)) — |^i) = — cos2$|^i) + sin 2$|^>0) in podobno D|^>0) = sin2$|^>i) + cos2$|^>0). Torej za korak G = DF velja G|pi) = — D|pi) = cos 2$|^>i) — sin2$|^0), G|^) = D|^0) = sin2%i) + cos2$|^i), zato je G rotacija za kot 2$. Iz zacetnega stanja = sin$|^>i) + cos$|^>0) po k rotacijah tako pridemo v stanje Gk= sin(2k + 1)$|^i) +cos(2k + 1)$|^>0). Ce izberemo k, za katerega bo (2k + 1)$ blizu |, bo v koncnem stanju prevladovala superpozicija ) in z veliko verjetnostjo bomo izmerili eno od ustreznih stanj. Veljati mora torej k « 2(2? — 1), zato izberemo kar k = |_J. Ce je ustreznih stanj malo (kar je klasicno najtezje), je sin $ = majhno s tevilo. Tedaj velja $ « sin $, zato moramo izvesti priblizno 4 korakov, zaradi cesar je casovna zahtevnost Groverjevega algoritma enaka O(^N). Kaj pa, ce ne vemo, koliko je p? Tedaj lahko najprej poskusimo primere, ko je p = 1,2,4,8,..., in z veliko verjetnostjo bomo v vsaj enem od poskusov izmerili ustrezen odgovor. Poleg tega pa obstajajo algoritmi, ki ocenijo p, njihova casovna zahtevnost pa je prav tako O(^N). Shorov algoritem Za konec si oglejmo se najznamenitej s i kvantni algoritem: Shorov algoritem za prastevilski razcep [4]. V resnici bomo re s evali osnovnej s o nalogo: namesto razcepa stevila N bomo iskali neki njegov pravi delitelj, torej stevilo 1 < d < N, ki deli N. Kajti ce najdemo tak d, lahko postopek ponovimo na d in N/d ter tako scasoma pridemo do celotnega prastevilskega razcepa. Stevilo d najenostavneje poi scemo tako, da pregledamo vsa naravna stevila, ki so vecja od 2 in manjsa od VN, ter se ustavimo, ko eno izmed njih 46 Obzornik mat. fiz. 61 (2014) 2 Osnove kvantnega računalništva, 2. del deli N. Časovna zahtevnost takega postopka je torej O(\/N): za štirikrat večje število potrebujemo dvakrat več časa. Seveda obstajajo tudi učinkovitejši algoritmi, a vseeno iz prastevil p in q veliko laZe izračunamo p ■ q kot pa iz zmnozka p ■ q dobimo nazaj razcep na p in q. Šifriranje RSA, ki je danes prečej pogosto uporabljano, se zana sa ravno na tezavnost pra stevilskega razcepa. Č asovna zahtevnost Shorovega algoritma pa je le O((log N)3). Hitrost takega razcepa si najbolje predstavljamo s primerjavo časov, ki jih za razcep potrebujejo različni algoritmi (tabela 1). velikost stevila « 106 » 1010 » 1020 » 1030 » 1040 » 1050 naivni algoritem 1 ms 100 ms 3 h 30 let 3 ■ 106 let 3 ■ 1011 let algoritem GNFS 1 ms 75 ms 3 min 10 h 1 meseč 6 let Shorov algoritem 1 ms 4 ms 40 ms 125 ms 300 ms 600 ms Tabela 1. Casi, potrebni za razcep števila z naivnim algoritmom (O(vN)), trenutno najučinkovitejšim klasičnim algoritmom GNFS (O(e(64/91ogN)1/3(1og1ogN)2/3)) in s Shoro-vim algoritmom (O((log N)3)). Za laZjo primerjavo predpostavimo, da vsi trije algoritmi za razcep stevil okoli milijona potrebujejo eno milisekundo. Shorov algoritem temelji na ideji, da poisčemo naravno stevilo x, za katero velja x2 = 1 (mod N). Tedaj je x2 — 1 deljivo z N, zato ima vsaj eno od stevil x — 1 in x + 1 skupni delitelj z N, ki pa ga lahko hitro izračunamo z Evklidovim algoritmom. Stevilo x poi sčemo v zaporedju a mod N, a2 mod N, a3 mod N,..., kjer je a neko stevilo, ki je tuje N. Ker je vseh ostankov pri deljenju z N le končno mnogo, se mora neki člen v zaporedju ponoviti. Rečimo, da za stevili m in r velja am = am+r (mod N). Tedaj velja am(ar — 1) = 0 (mod N), in ker je a in s tem tudi am tuje N, je ar = 1 (mod N). Zato je r perioda zaporedja, in če je stevilo r sodo, bo ar/2 ravno iskani x. Za primer vzemimo N = 21 in a = 10. Tedaj je zaporedje ostankov potenč enako 10,16,13,4,19,1,10,16,... Perioda zaporedja je enaka 6 in iskani x je enak 103 = 13 (mod 21). Torej je stevilo 132 — 1 deljivo z 21 in iskani delitelj najdemo tako z D(12, 21) = 3, kot z D(14, 21) = 7. Če je stevilo r liho, pa tak prijem ne deluje, zato postopek ponovimo za neki drug a. S tem in drugimi manj simi zapleti se tu ne bomo ukvarjali, temveč se bomo posvetili ključnemu delu Shorovega algoritma: izračunu periode. Kogar tema bolj zanima, si lahko vse podrobnosti ogleda v [2]. Posamezne člene zaporedja aj mod N lahko izračunamo prečej učinkovito. Če je j sodo, velja aj = (aj/2)2, sičer pa velja aj = a ■ (a(j-1)/2)2. Tako postopoma zelo hitro izračunamo poljubno potenčo. Na primer, a42 41-51 47 Matija Pretnar izračunamo iz a21, to iz a10, to iz a5, to iz a2 in to iz a. Poleg tega ves čas računamo le z ostanki, kar nam stvari Se olajSa, saj nam ni treba delati s Stevili, večjimi od N. A kljub temu s postopnim računanjem členov ne bomo prisli daleč, saj je perioda lahko skoraj tako velika kot N. Na tej točki prvič uporabimo prednosti kvantnih računalnikov: členov ne bomo računali drugega za drugim, temveč vse hkrati. Klasično vezje, ki potenče računa po zgornjem postopku, namreč znamo pretvoriti v kvantno vezje U, za katero velja U|j)|0) = |j)|aj mod N}. Nato to vezje uporabimo na superpozičiji = Zj!-1 Ij)|0) za neko dovolj veliko stevilo M, da dobimo superpozičijo —M(|0}|a° mod N) + |1)|a1 mod N) + ■ ■ ■ + |M - 1)|aM-1 mod N)). Nato pomerimo izhodni register. Izmerili bomo |am mod N) za neki naključno izbran in nam neznan m < r. Ta vrednost nam sičer ne bo pomagala, vendar bomo s tem dosegli, da se bo na vhodu obdrzala le superpozičija tistih stanj | j), za katera je aj mod N = am mod N. Stanje vhoda bo torej |^>) = —n (|m) + |m + r) + |m + 2r) + ■ ■ ■ + |m + (n — 1)r)), pri čemer je n = |_M-mJ stevilo vseh stanj v superpozičiji. Ta superpozičija pa je sestavljena ravno iz baznih stanj, razmaknjenih za periodo r. Na primer, za N = 21, a = 10 in M = 64 iz začetne superpozičije 8 ^6=°|j)|0) z uporabo vezja U dobimo stanje 1 (|0)|1) + 11 )| 10) + 12)| 16) + 13 )| 13) + |4)|4) + |5)|19) + |6)|1) + |7)|10) + |8)| 16) + 19)| 13) + ■ ■ ■ + 161 )| 10) + |62)|16) + |63)|13)). Rečimo, da pri meritvi izhoda izmerimo 113). Tedaj je stanje vhodnega registra enako |^>) = —tj(|3) + |9) + 115) + ■ ■ ■ + 163)). Ce bi pri meritvi izmerili kak drug izhod, bi dobili drugačno stanje vhoda, a v vsakem primeru bi bila stanja v superpozičiji razmaknjena ravno za periodo r. To periodo bomo izlusčili tako, da bomo na |^>) uporabili kvantno Fou-rierevo transformacijo. To je unitarna preslikava, podana z matriko Q = VM 1 WM"1 W2(M"1) 1 1 ■ ■ 1 w2 ■ ■ WM-1 w2 w4 ■ ■ w2(M-1) W(M-1)(M-1) 1 48 Obzornik mat. fiz. 61 (2014) 2 Osnove kvantnega računalništva, 2. del kjer je w = e2ni/M kompleksni koren enote. Najprej si oglejmo, kako kvantna Fouriereva transformacija deluje, nato pa Se to, kako jo učinkovito implementiramo s kvantnim vezjem. S tem bomo tudi preverili, da je unitarna. Delovanje kvantne Fouriereve transformacije si najlaZe predstavljamo, če si ogledamo amplitude baznih stanj v sliki Q|^>), torej skalarne produkte vrstic matrike Q s stanjem |^>) = (|m) + |m+r) + - ■ - + |m+(n-1)r)). Am- plituda pri |0) je tako enaka a0 = \pM, pri |1) pa a1 = ^n=o . K tej vsoti torej prispevajo le potence, ki ustrezajo baznim stanjem, ki so v superpoziciji |^>). Predstavljamo si lahko, da hodimo po enotski kroznici in se v vsakem koraku premaknemo za eno potenco, v vsoto pa stejemo vsako r-to obiskano potenco (slika 2a). Potence so razporejene enakomerno, bazna stanja pa nastopajo periodicno, zato se upostevane potence medsebojno (skoraj) iznicijo in amplituda je blizu 0. u ,27 u u33' «i u u (a) u " .2.15; «2 • u ,..••■ u2-27 ,2-57 (b) aii (c) Slika 2. Potence korena enote u = e2ni/64, ki jih upoštevamo pri izračunu amplitud baznih stanj (a) |1), (b) |2) in (c) |11) v kvantni Fourierevi transformaciji superpozicije |<^) = (|3) + |9) + • • • + |63)). Amplituda je oznacena z znakom • na sredini kroga, zaradi berljivosti pa so nekatere oznake izpuscene. Pri izracunu amplitude stanja |2) ravnamo podobno, le da se s koraki premikamo za dve potenci. Ker so upostevane potence zopet razporejene enakomerno (vsaj za dovolj velike M), bo amplituda zopet zanemarljiva (slika 2b). Tudi pri nadaljnjih stanjih sklepamo enako — vse dokler ne pridemo do nekega stanja |i), pri katerem med dvema upostevanima potencama priblizno obhodimo celotno kroznico. Tedaj namrec upostevane potence niso vec enakomerno razporejene po kroznici, temvec so si blizu, zato se njihovi prispevki ne iznicijo (slika 2c). V vsakem koraku se premaknemo za i potenc, potenco pa upostevamo na vsakih r korakov. Tako bomo z veliko verjetnostjo izmerili le stanja |i), za katera bo ir cim blize polnega obhoda, torej stevila M ali pa nekega njegovega veckratnika. Ko izmerimo stanje |i), prek razvoja v verizni ulo-mek izracunamo zaporedne priblizke ulomka M ■ Izkaze se [2], da je prvi priblizek, ki se od M razlikuje za manj kot 2Mf, oblike k za neki k, s cimer lahko koncno izracunamo periodo r. 2 9 , ,2-39 u i5 u u 9 u 23 u 3 u Hu63 11-3i 2 63 • u •u57 251 •. u 1163 51 221 u u 41-51 49 Matija Pretnar 15% 10% 5% 0% |0> |11> |21> |32> |43> |53> Slika 3. Verjetnosti posameznih baznih stanj po uporabi kvantne Fouriereve transformacije na superpoziciji s periodo 6 pri M = 64. Ob vsakem vrhu je poleg ustreznega baznega stanja |^> zapisan tudi ulomek, ki ga dobimo z razvojem stevila M v verizni ulomek. Iz števila r izračunamo x = ar/2 mod N, iz tega pa D(x — 1,N) in D(x + 1,N). Ce smo našli pravi delitelj števila N, končamo. V primeru neuspeha poskusimo še z nekaj večkratniki dobljenega imenovalca, saj imata lahko k in r skupni delitelj, zato bo dobljeni ulomek okraj san. Ce tudi to ne uspe, poskusimo se s stevili, ki so blizu saj, kot vidimo na sliki 3, obstaja manj sa verjetnost, da smo izmerili stevilo blizu vrha. Ce tudi v tem primeru ne najdemo stevila r, čeloten postopek ponovimo. Nazadnje poglejmo se, kako kvantno Fourierevo transformacijo učinkovito implementiramo. Kot pri Groverjevem algoritmu bo tudi tu najenostavneje, če vzamemo M oblike 2q in stanja |0), |1),..., |M — 1) izenačimo z vsemi baznimi stanji |x) sistema q kubitov. Stanje |xoXi ••• xq_i) torej predstavlja |x02q_1 + x12q_2 + ■ ■ ■ + xq-1). Poleg tega kvantno Fourierevo transformačijo pri M = 2q označimo s Qq, koren enote e2ni/2q pa z wq. Poglejmo, kako lahko Qq rekurzivno izrazimo s pomočjo Qq-1 in s tem njeno računanje prevedemo na enostavnej si primer. C e Qq uporabimo na nekem sodem stanju |2k) in v dobljeni vsoti zdruzimo člene, razmaknjene za 2q-1, dobimo 2q — 1 2q — 1 Qq|2k) = ^E