UNIVERZA V LJUBLJANI PEDAGOˇ SKA FAKULTETA
NEˇ ZKA RUGELJ
SHOROV ALGORITEM
DIPLOMSKO DELO
LJUBLJANA, 2017
UNIVERZA V LJUBLJANI PEDAGOˇ SKA FAKULTETA
DVOPREDMETNI U ˇ CITELJ: matematika - raˇ cunalniˇstvo
NEˇ ZKA RUGELJ
Mentor: Prof. dr. Janez Demˇsar
SHOROV ALGORITEM
DIPLOMSKO DELO
LJUBLJANA, 2017
“ ˇCe te kvantna mehanika ni popolnoma ˇsokirala, je ˇse nisi povsem razumel.”
(Niels Bohr)
V prvi vrsti se iskreno zahvaljujem mentorju prof. dr. Janezu Demˇsarju za izje- mno potrpeˇzljivost in vso pomoˇc pri pisanju diplomskega dela.
Zahvalila bi se tudi svoji druˇzini in fantu za vso vzpodbudo in podporo v ˇcasu celotnega ˇstudija.
Hvala tudi prijateljem za vse trenutke, ki so lepˇsali ˇstudijska leta.
Povzetek
V diplomskem delu obravnavamo Shorov algoritem za faktorizacijo ˇstevil, ki se izvaja na kvantnih raˇcunalnikih.
V zaˇcetku dela najprej razloˇzimo nekaj osnovnih pojmov kvantnega raˇcunalniˇstva.
Nato na kratko opiˇsemo Fourierovo in diskretno Fourierovo transformacijo iz ka- tere naprej izpeljemo kvantno Fourierovo transformacijo.
V zadnjem delu diplomskega dela ponovimo osnove modularne aritmetike.
Nato opiˇsemo naˇcin faktorizacije, ki jo uporablja Shorov algoritem. Diplomsko delo zakljuˇcimo z natanˇcnim opisom delovanja algoritma na kvantnih raˇcunalnikih in preprostim primerom.
Kljuˇcne besede: Shorov algoritem, kvantno raˇcunalniˇstvo, faktorizacija, kvan- tna Fourierova transformacija
Abstract
In this diploma paper we present the Shor’s algorithm for factorising numbers, which runs on quantum computers.
Initially, we explain the basics of quantum computing. Afterwards, we present a general review of the Fourier and the discrete Fourier transform, from which we derive the quantum Fourier transform.
In the last part, we first give a short introduction to modular arithmetics. La- ter on, we describe the concept of factorization that is used in Shor’s algorithm.
Diploma thesis ends with a detailed review of how the algorithm works on quan- tum computers and a simple example.
Key words: Shor’s algorithm, quantum computation, factorization, quantum Fourier transform
ix
Kazalo
I Uvod 1
II Kvantni raˇ cunalniki 2
1 Kvantni bit 2
2 Sistemi kubitov 3
3 Prepletenost 5
4 Kvantni raˇcunalnik 5
III Fourierova transformacija 12
5 Vektorji in skalarni produkt 12
6 Fourierova transformacija 14
6.1 Kvantna Fourierova transformacija . . . 17
IV Shorov algoritem 22
7 Modularna aritmetika 22
8 Faktorizacija 24
8.1 Iskanje periode funkcije . . . 26 8.2 Algoritem . . . 29
V Zakljuˇ cek 32
Del I
Uvod
Razcep ˇstevil ali faktorizacija je znan kot teˇzek problem, za katerega (ˇse) ne po- znamo uˇcinkovitega algoritma, ki bi tekel na obiˇcajnih raˇcunalnikih. To pomeni, da velikih ˇstevil (npr. ˇstevil s 1000 ˇstevkami) klasiˇcen raˇcunalnik ne razstavi v ne- kem doglednem ˇcasu. Temu ne bo veˇc tako, ko bodo sestavili kvantni raˇcunalnik z dovolj velikim kvantnim registrom, ki mu bo to uspelo. Eden od moˇznih algo- ritmov za to je Shorov algoritem, ki je hkrati eden prvih algoritmov, namenjenih kvantnim raˇcunalnikom.
Shorov algoritem je imenovan po matematiku Petru Shoru in je bil formuliran ˇze leta 1994. Algoritem je sestavljen iz dveh delov. V prvem delu se problem razcepa na prafaktorje pretvori v problem iskanja periode funkcije, v drugem delu pa to periodo najdemo s pomoˇcjo kvantne Fourierove transformacije.
Kvantni raˇcunalniki hranijo podatke v kvantnih bitih ali kubitih. Zanimivo pri njih je, da se nekako ne odloˇcijo, v katerem izmed moˇznih stanj so, vse dokler jih ne pogledamo oz. izmerimo. Pred tem lahko njihovo stanje zgolj opiˇsemo s superpozicijo stanj.
Kvantne raˇcunalnike sicer ˇsele razvijamo, kljub temu pa lahko ˇze razmiˇsljamo in ustvarjamo algoritme, saj vemo, na kakˇsnem principu bodo temeljili. Tako smo poleg Shorovega algoritma razvili tudi mnoge druge algoritme za reˇsevanje problemov, ki imajo na klasiˇcnih raˇcunalnikih veliko ˇcasovno zahtevnost.
Del II
Kvantni raˇ cunalniki
V tem poglavju je na kratko opisano, kaj je kvantni raˇcunalnik in kako deluje, opisani so osnovni pojmi in koncepti, ki nam bodo pomagali pri razumevanju nadaljevanja diplomskega dela. (Povzeto po [2] in [4].)
1 Kvantni bit
Bit (krajˇse za ang. “binary digit”) je osnovna enota za merjenje koliˇcine podat- kov, ki so shranjeni v klasiˇcnem raˇcunalniku. Vlogo bita v kvantnem raˇcunalniku predstavlja kvantni bit ali krajˇse kubit.
Fiziˇcno kubit predstavlja osnovni fizikalni delec, npr. elektron ali foton, obiˇcajno pa o kubitu razmiˇsljamo kot o abstraktnem matematiˇcnem objektu, ki ga najveˇckrat obravnavamo kot enotski vektor v 2-dimenzionalnem vektorskem prostoru.
Podobno, kot je klasiˇcen bit v enem izmed stanj, ki ju obiˇcajno oznaˇcimo z 0 in 1, je v nekem stanju tudi kvantni bit. Vendar pa kubit ni v toˇcno doloˇcenem stanju, temveˇc v superpoziciji moˇznih stanj. Doloˇcene so le verjetnosti stanj, v katerih se bo nahajal ob meritvi. Zato trenutno stanje delca opiˇsemo z linearno kombinacijo stanj, ki ji reˇcemo superpozicija. Bazna vektorja tega prostora stanj z Diracovo notacijo oznaˇcimo z |0i in |1i. Linearna kombinacija stanj kubita je torejα0|0i+α1|1i, pri ˇcemer sta α0 inα1 kompleksni ˇstevili. Ko kubit izmerimo, se bo ta nahajal v stanju 0 z verjetnostjo |α0|2 ali v stanju 1 z verjetnostjo |α1|2. Ker je dogodek, da se bo kubit nahajal v stanju 0 ali v stanju 1, gotov dogodek, velja|α0|2+|α1|2 = 1. Geometrijsko to pomeni, da je stanje kubita normalizirano, torej ima dolˇzino 1.
Sposobnost kubita, da se nahaja v superpoziciji stanj, je nenaravno v smislu naˇsega dojemanja sveta okoli nas. Klasiˇcen bit je kot kovanec - ali je grb ali pa
2
cifra. Nasprotno pa je lahko kubit kjerkoli v prostoru stanj med|0i in|1i, vendar le dokler ga ne izmerimo. Ko ga izmerimo, bo rezultat vedno 0 ali 1. Tako je lahko kubit na primer v stanju
√1
2|0i+ 1
√2|1i
in bo v polovici meritev dal rezultat 0 in v drugi polovici rezultat 1. Zgornje stanje veˇckrat oznaˇcimo s |+i in ga bomo v nalogi ˇse videli.
Fiziˇcno je kubit lahko npr. elektron. Osnovno stanje oznaˇcimo z |0i, prvo vzbujeno stanje pa |1i. ˇCe atomu dovajamo dovolj energije, se bo elektron iz sta- nja |0i premaknil v stanje |1i.
Ker se lahko kubit nahaja kjerkoli med stanjema |0i in |1i, bi si lahko mislili, da lahko hrani neskonˇcno podatkov. Vendar zaradi obnaˇsanja kubita pri merjenju temu ni tako. Merjenje namreˇc spremeni stanje kubita iz superpozicije stanj |0i in |1i v konkretno stanje. Na primer, kubit, ki je v stanju |+i, izmerimo in ta s tem preide v stanje |0i ali |1i. Z enim samim merjenjem torej dobimo zgolj en bit podatkov o stanju kubita. Vrednosti α0 in α1 iz enaˇcbeα0|0i+α1|1i bi lahko pridobili le z neskonˇcno meritvami “identiˇcno pripravljenega” kubita, kar pa zaradi zakonov kvantne fizike (kubitov ni mogoˇce klonirati) ni moˇzno.
2 Sistemi kubitov
Denimo, da je naˇs sistem sestavljen iz dveh kubitov (delcev), ki imata po 2 moˇzni stanji. V klasiˇcnem raˇcunalniˇstvu bi to pomenilo, da imamo 2 bita, ki imata vrednost 0 ali 1, skupaj pa tvorita ˇstiri moˇzna stanja in sicer 00, 01, 10 in 11.
Oglejmo si sistem dveh kubitov na primeru dveh elektronov. Oba elektrona sta v superpoziciji stanj |0i in |1i. Stanje prvega elektorna zapiˇsemo kot α0|0i+ α1|1i,ki je vektor v dvodimenzionalnem kompleksnem vektorskem oz. Hilbertovem prostoru (oznaˇcimo ga s H1), stanje drugega pa β0|0i+ β1|1i, ki je prav tako vektor v dvodimenzionalnem Hilbertovem prostoru (tega oznaˇcimo s H2). Ceˇ ta dva sistema zdruˇzimo, je stanje novega sistema vektor v 4-dimenzionalnem
Hilbertovem prostoru, oznaˇcimo ga sH. Hilbertova prostoraH1inH2 smo zdruˇzili s tenzorskim produktom, ki ga oznaˇcimo z ⊗. Tenzorski produkt je operacija, ki vektorjemau∈H1inv ∈H2priredi vektoru⊗v ∈H. Tem produktnim vektorjem reˇcemoosnovni tenzorji. Tenzorski produkt ima dve pomembni lastnosti:
• je bilinearen; (|u1i +|u2i)⊗ |vi = |u1i ⊗ |vi+|u2i ⊗ |vi in analogno za
|ui,|v1i,|v2i;
• bazne vektorje preslika v bazne vektorje;bazne vektorje prostora H pridobimo iz baznih vektorjev prostorov H1 in H2:
|0i ⊗ |0i=|0i|0i=|00i
|0i ⊗ |1i=|0i|1i=|01i
|1i ⊗ |0i=|1i|0i=|10i
|1i ⊗ |1i=|1i|1i=|11i.
Ker je H =H1⊗H2 vektorski prostor, definirajmo skalarni produkt:
h|u1i ⊗ |v1i,|u2i ⊗ |v2ii=hu1, u2i · hv1, v2i.
Ko imamo definiran skalarni produkt za osnovne tenzorje, lahko definiramo skalarni produkt za vsak vektor v H. Tako lahko vsak vektor iz H izrazimo kot linearno kombinacijo osnovnih tenzorjev.
Pomudimo se ˇse pri merjenju sistema kubitov. Podobno kot pri enem kubitu je rezultat merjenja sistema dveh kubitov lahko 00, 01, 10 ali 11, pri ˇcemer je ver- jetnost, da je rezultat X, enaka |αX|2. Ob merjenju sistem preide iz superpozicije stanj v stanje |X >.
Tudi ˇce izmerimo le enega izmed dveh kubitov sistema, se stanje celotnega sistema spremeni (saj se je prvi kubit iz superpozicije “premaknil”v eno od stanj).
Vzemimo sistem v stanju
α00|00i+α01|01i+α10|10i+α11|11i.
4
Ce smo izmerili, da se prvi kubit nahaja v stanjuˇ |0i, za kar je bila verjetnost
|α00|2+|α01|2, je torej novo stanje sistema linearna kombinacija stanj|00iin |01i.
Torej je stanje sistema po merjenju
|ψnovoi= α00|00i+α01|01i p|α00|2+|α01|2 .
Stanje po merjenju enega kubita je normalizirano s faktorjemp
|α00|2+|α01|2, da je vektor stanja ˇse vedno normiran (ima dolˇzino 1).
3 Prepletenost
S tenzorskim produktom smo ustvarili nov Hilbertov prostor, ki ima svoje bazne vektorje. Ta Hilbertov prostor je sestavljen iz dveh mnoˇzic vektorjev; mnoˇzice osnovnih tenzorjev in mnoˇzice vektorjev, ki jih pridobimo kot linearno kombinacijo baznih vektorjev, a jih ne moremo zapisati kot produkt vektorjev izH1 inH2. Tak je na primer vektor, ki opisuje t. i. Bellovo stanje
|ψ >= 1
√2(|00i+|11i).
Ce je sistem v takem stanju, reˇˇ cemo da je v prepletenem ali vezanem stanju. ˇCe izmerimo stanje enega kubita v zgornjem stanju sistema kubitov, bomo dobili sta- nje celega sistema. Torej, ˇce je rezultat merjenja enega kubita 0 (z verjetnostjo 12), sistem preide v stanje |00i, ˇce pa je rezultat 1, sistem preide v stanje|11i. Torej v tem primeru merjenje drugega kubita vedno da enak rezultat kot merjenje prvega kubita.
4 Kvantni raˇ cunalnik
Kvantni raˇcunalnik je raˇcunalnik, ki podatke shranjuje v kvantnih bitih. Sestavljen je iz kvantnih vezij, ki so skupek vodil in kvantnih vrat, ki prenaˇsajo in delujejo na kvantne podatke, sicer pa so analogna logiˇcnim vratom navadnega raˇcunalnika.
Pomembna razlika med klasiˇcnimi in kvantnimi logiˇcnimi vrati je ta, da kvan- tna logiˇcna vrata ne delujejo tako, da bi spreminjala stanje |0i oz. |1i, saj nam to ne bi povedalo niˇc o superpoziciji stanja, v kateri se nahaja kubit, predno ga izmerimo. Kvantna vrata deluejo linearno, tako da spreminjajo amplitudi α0 in α1. Tako se torej spreminjata verjetnosti, v katerem stanju se bo nahajal kubit, ko ga izmerimo.
Zaradi linearnosti lahko kvantna logiˇcna vrata predstavimo s kvadratnimi ma- trikami. Obratno, vsaka primerna kvadratna matrika predstavlja kvantna logiˇcna vrata. Ni pa vsaka matrika primerna. Ker zaα0 inα1 velja enakost|α0|2+|α1|2 = 1, mora to veljati za novo stanje kubita |ψ0i = α00|0i+α01|1i po delovanju vrat.
Izkaˇze se, da bo ta lastnost veljala natanko takrat, ko bo matrika unitarna, torej bo veljalo U†U =U U† =I, kjer je I enotska matrika in U† = (UT)∗;
a b c d
†
=
a∗ c∗ b∗ d∗
.
Kvantna logiˇcna vrata lahko razdelimo na tista, ki delujejo na enem kubitu in tista, ki delujejo na veˇc kubitih hkrati.
• Logiˇcna vrata, ki delujejo na enem kubitu
V klasiˇcnem raˇcunalniˇstvu imamo zgolj ena netrivialna logiˇcna vrata, ki de- lujejo na enem bitu, to so vrata “NE”. V kvantnem raˇcunalniˇstvu pa je teh vrat veˇc.
– Vrata “NE”
Logiˇcna vrata “NE” v klasiˇcnem raˇcunalniku bitu z vrednostjo 0 na- stavijo vrednost 1 in obratno. Kvantna logiˇcna vrata pa kot ˇze ome- njeno delujejo na superpozicijo stanj. Vrata “NE” tako superpozicijo α0|0i+α1|1i preslikajo v superpozicijo α1|0i+α0|1i.
V skicah vezij ta vrata oznaˇcimo z ’X’. Kvadratna matrika, ki ustreza
6
tem logiˇcnim vratom, je
X =
0 1 1 0
.
Preverimo, da so taka vrata dobro definirana, torej da je pripadajoˇca matrika enotska oz. da veljaX†X =XX† =I.Ker jeX† =X,moramo preveriti, ali je X2 =I:
0 1 1 0
0 1 1 0
=
0·0 + 1·1 0·1 + 1·0 1·0 + 0·1 1·1 + 1·0
=
1 0 0 1
.
– Vrata, ki zamenjajo predznak
Ta vrata delujejo na superpozicijo α0|0i+α1|1i tako, da nastavi am- plitudo α1 na−α1. Nova superpozicija je torej α0|0i −α1|1i. Ustrezna matrika, ki jo oznaˇcimo z Z, je
Z =
1 0
0 −1
. Ce kubit, ki je na zaˇˇ cetku v stanju
|+i= 1
√2|0i+ 1
√2|1i, poˇsljemo skozi Z, ta preide v stanje
|−i= 1
√2|0i − 1
√2|1i in obratno.
Tudi tokrat bi morali preveriti, ali je matrika unitarna, kar pa bi po- kazali na enak naˇcin kot pri vratih “NE”, zatorej bomo tokrat dokaz izpustili.
– Hadamardova vrata oz. transformacija
Hadamardova vrata se velikokrat pojavijo v kvantnih vezjih. Oznaˇcimo
jih s H, pripadajoˇca matrika pa je H =
√1 2
√1 2
√1 2 −√1
2
. Stanje |0i Hadamardova transformacija slika v
H|0i=
√1 2
√1 2
√1 2 −√1
2
1 0
=
√1 2
√1 2
, torej stanje |0i slika v stanje √1
2|0i+ √1
2|1i = |+i, podobno pa stanje
|1i slika v stanje √12|0i − √12|1i, ki ga oznaˇcimo tudi z|−i.
Zopet moramo preveriti, ˇce je transformacija unitarna, torej ali velja enakost H†H = I. H† = H, saj so vsi elementi realni in s simetrijo ostane enaka.
H2 =
√1 2
√1 2
√1
2 −√12
√1 2
√1 2
√1
2 −√12
=
2·(√1
2)2 (√1
2)2−(√1
2)2 (√12)2 −(√12)2 2·(√12)2
H2 =
1 0 0 1
=I.
Ker je H unitarna transformacija, pomeni, da ob ponovitvi dobimo na- zaj zaˇcetno stanje.
Hadamardova transformacija kot reˇceno slika stanje|0i → √12|0i+√12|1i in stanje|1i → √1
2|0i−√1
2|1i.Na prvi pogled izgleda, kot da smo izgubili vse informacije o zaˇcetnem stanju kubita, saj sta verjetnosti stanja|0iin
|1isedaj enaki. Vendar je ta podatek shranjen v predznaku (+ ali -). ˇCe ponovno izvedemo transformacijo, bomo to informacijo povrnili v bitno informacijo in bomo tako, ko bomo izmerili stanje kubita, pravzaprav natanko vedeli, s katerim stanjem smo zaˇceli.
• Kvantna vrata, ki delujejo na dveh kubitih
Zaˇcetno stanje dveh kubitov je superpozicija vseh ˇstirih moˇznih stanj α00|00i+α01|01i+α10|10i+α11|11i.
8
Izhodna superpozicija je podobna kot vhodna, le z drugaˇcnimi amplitudami:
α000 |00i+α001|01i+α010|10i+α011|11i.
Vsako stanje lahko opiˇsemo kot vektor v 4-dimenzionalnem vektorskem pro- storu, zato lahko transformacije zapiˇsemo kot matrike velikosti 4×4 s kom- pleksnimi elementi.
– Vrata CNOT (iz ang. “controlled NOT”)
So zelo preprosta kvantna logiˇcna vrata, ki jih pogosto uporabljamo.
Shema vezja je prikazana na spodnji sliki.
Prvemu kubitu a reˇcemo kontrolni kubit, drugemu kubitu b pa ciljni kubit. Vrata stanja kontrolnega kubita ne spreminjajo, na ciljnem pa izvedejo operacijo “NE” natanko tedaj, ko je stanje kontrolnega kubita enako 1. Pripadajoˇca matrika je
CN OT =
1 0 0 0 0 1 0 0 0 0 0 1 0 0 1 0
.
Transformacija slika stanja:
|00i → |00i
|01i → |01i
|10i → |11i
|11i → |10i.
Vhodna superpozicija
α00|00i+α01|01i+α10|10i+α11|11i
se torej preslika v
α00|00i+α01|01i+α11|10i+α10|11i.
Preverimo ˇse, da je CN OT unitarna transformacija. To lahko prepro- sto vidimo ˇze po tem, da ˇce transformacijo izvedemo dvakrat, bomo iz zaˇcetne superpozicije dobili enako superpozicijo, kot je bila prva vho- dna. Torej je transformacija res unitarna.
– Druga vrata, ki delujejo na dveh kubitih
Vrata, ki delujejo na dveh kubitih, lahko dobimo tudi drugaˇce. Na vsakem od vhodnih kubitov posebej lahko uporabimo kvantna logiˇcna vrata, ki delujejo na enem kubitu. Denimo, da na prvem kubitu upo- rabimo transformacijo U1 in na drugem U2. Naj bo
U1 =
a c b d
in
U2 =
e g f h
. Tedaj je transformacija U podana z matriko
U =
a
e g f h
c
e g f h
b
e g f h
d
e g f h
.
Oznaˇcimo vrstice in stolpce po vrsti z 00,01,10 in 11. Ce se osre-ˇ dotoˇcimo zgolj na prvi bit, nam prvi dve vrstici predstavljata 0 in drugi dve 1 ter prva dva stolpca 0 in druga dva 1. To se vidi po koeficientih ˇstirih podmatrik a, b, c in d. Ko izmerimo prvi kubit, nam za vsako moˇznost ostaneta dve moˇznosti za drugi kubit, zato je v vsakem kva- drantu podmatrika U2.
10
Tak naˇcin sestavljanja vrat deluje. U1 delujejo na stanje |0i tako:
U1|0i = a|0i+b|1i, vrata U2 pa U2|0i = e|0i+f|1i. Na stanju |00i uporabimo U1 inU2 in dobimo novo stanje
U1U2|00i= (a|0i+b|1i)(e|0i+f|1i) =ae|00i+af|01i+be|10i+bf|11i, kar je razvidno tudi iz prvega stolpca matrikeU. Podobno velja za slike
|01i,|10i in |11i.
Del III
Fourierova transformacija
Eden najuˇcinkovitejˇsih naˇcinov reˇsevanja problemov v matematiki ali raˇcunalniˇstvu je preoblikovanje oz. transformacija problema v nek drug problem, katerega reˇsitev je znana ali laˇzje reˇsljiva. Nekatere transformacije so pogosto uporabne na razliˇcnih primerih, zato jih preuˇcujemo ˇze zaradi njih samih. Ena izmed takih je tudi Fouri- erova transformacija. V tem delu diplomskega dela bomo najprej ponovili osnove linearne algebre, nato spoznali Fourierovo transformacijo in nazadnje ˇse kvantno obliko le te. Ta razdelek je povzet po [1], [3], [4] in [5].
5 Vektorji in skalarni produkt
Vektor je koliˇcina, ki ima poleg velikosti tudi smer. Velikosti vektorja lahko reˇcemo tudi dolˇzina, najbolj sploˇsna beseda pa je norma. Oznaˇcimo ga na razliˇcne naˇcine, npr. s puˇsˇcico~a, v geometrijskem prostoru ga lahko oznaˇcimo z zaˇcetno in konˇcno toˇcko, npr. AB, lahko zgolj z~ a,AB ... Na kakˇsen naˇcin ga piˇsemo, je odvisen od situacije oz. konteksta, pomembno je le, da vedno vemo, kdaj oznaka predstavlja vektor. Obiˇcajno avtorji besedil na zaˇcetku omenijo, kateri zapis bodo uporabljali v besedilu. V tem poglavju bomo uporabili kar a.
Dva vektorja stalinearno neodvisna, ˇce ne moremo enega zapisati kot veˇckratnik drugega. Vektor 0 je linearno odvisen od vseh ostalih vektorjev. Nabor vektorjev je linearno neodvisen, ˇce nobenega izmed njih ne moremo zapisati kot linearno kombinacijo ostalih.
Vektorski prostor nad poljem F je mnoˇzica vektorjev, zaprta za seˇstevanje in mnoˇzenje s skalarjem iz F. Ogrodje vektorskega prostora je mnoˇzica vseh vektor- jev, s katerimi lahko z linearno kombinacijo opiˇsemo vse druge vektorje vektorskega prostora. Baza vektorskega prostora je najmanjˇse ogrodje. Vsebuje same linearno
12
neodvisne vektorje.
Naj bo V vektorski prostor nad poljem F. Skalarni produkt je funkcija dveh spremenljivk hi:V ×V →F, ki ima naslednje lastnosti:
• hx, xi ≥0 in hx, xi= 0 ⇔x= 0
• hx+y, zi=hx, zi+hy, zi
• hλx, yi=λhx, yi
• hx, yi=hy, xi.
S skalarnim produktom lahko vsakemu vektorju doloˇcimo normo. Normo vek- torjax oznaˇcimo z ||x|| in definiramo kot
||x||=p hx, xi.
Vektor xje pravokoten aliortogonalenna vektor y, ˇce je njun skalarni produkt enak 0, torejhx, yi= 0. Ortogonalna mnoˇzicaU⊥ je mnoˇzica paroma ortogonalnih vektorjev.
Vektorxje normiran, ˇce je njegova norma enaka 1. Mnoˇzica vektorjev tvorior- tonormiran sistem, ˇce so vsi vektorji normirani in paroma ortogonalni. ˇCe kakˇsen tak sistem tvori bazo kakˇsnega vektorskega prostora, mu reˇcemo tudi ortonormi- rana baza.
Naj bo mnoˇzica vektorjevB ={b1, b2, ...bn}bazan-razseˇznostnega vektorskega prostora V. Tedaj lahko poljuben vektor v ∈ V enoliˇcno zapiˇsemo kot linearno kombinacijo baznih vektorjev bi:
v =λ1b1+λ2b2+...+λnbn. Ce je baza ortonormirana, za koeficienteˇ λi velja
λi =hv, bii.
To enostavno preverimo, saj je za v =λ1b1+λ2b2+...+λnbn
hv, bii=λ1hb1, bii+λ2hb2, bii+. . .+λihbi, bii+. . .+λnhbn, bii=λi.
S preslikavo, ki je na tem mestu ne bomo podrobneje definirali, lahko vektor preslikamo v matriˇcni stolpec, katerega koeficienti so skalarji λi. Torej razvoj vektorja v po bazi B lahko zapiˇsemo kot
v =
λ1 λ2 ... λn
.
Razvoj vektorjev po bazi nam velikokrat pomaga pri nadaljnjem reˇsevanju pro- blemov. Najveˇckrat uporabimo ortonormirano bazo s spretno izbranimi baznimi vektorji.
6 Fourierova transformacija
Denimo, da imamo vektorski prostor gladkih kompleksnih funkcij, torej funkcij f :C→C,
ki so neskonˇcnokrat odvedljive. Skalarni produkt funkcij tedaj definiramo kot doloˇcen integral produkta funkcij:
hf, gi= Z 2π
0
f(x)g(x)dx.
Na tem mestu bi bilo dobro preveriti, ˇce je tako definiran skalarni produkt dobro definiran (ali veljajo vse lastnosti skalarnega produkta), vendar bomo v tem di- plomskem delu to kar privzeli.
14
Seveda tudi za vektorski prostor funkcij lahko najdemo bazo, torej nabor takih funkcij, s katerimi bomo lahko opisali vse ostale funkcije. Ker ima prostor vseh gladkih kompleksnih funkcij neskonˇcno dimenzijo, baza vsebuje neskonˇcno mnogo baznih vektorjev.
Fourierovo transformacijo si lahko predstavljamo kot funkcijo, katere vhodni podatek je sadni napitek, rezultat pa recept, koliko posameznega sadja vsebuje.
Posamezne vrste sadja predstavljajo bazo vektorskega prostora, po kateri razvi- jemo posmezen napitek, s ˇcimer bomo toˇcno vedeli iz koliko enot posameznega sadja je bil napitek pripravljen. V matematiˇcnih besedah, Fourierova transforma- cija kot vhodni podatek dobi neko funkcijo in jo nato razvije po neki bazi. Bazo sestavljajo linearno neodvisne funkcije, razvoj po bazi pa nam praktiˇcno pove, ko- liko posamezne bazne funkcije vsebuje originalna funkcija.
Fourierova transformacija za bazne vektorje uporablja sinusne in kosinusne funkcije, saj so te med seboj paroma pravokotne. To lahko pokaˇzemo s skalarnim produktom, a ker za nadaljevanje naˇsega diplomskega dela dokaz ni pomemben, ga bomo izpustili.
Vsako dano funkcijo torej s Fourierovo transformacijo zapiˇsemo kot vsoto si- nusnih in kosinusnih funkcij. Nad poljem realnih ˇstevil bi izgledala tako:
f(x) =
∞
X
t=0
(λt1sin(tx) +λt2costx).
V kompleksnem prostoru pa je “pripravna” funkcija eik = cosk+isink. Tako je nad poljem kompleksnih ˇstevil Fourierova transformacija definirana kot:
fb(x) = Z ∞
−∞
f(t)e−2πitxdt.
Zgornja enaˇcba izhaja iz ˇstudije Fourierovih vrst, ki obravnava periodiˇcne funkcije in jih zapiˇse kot vsoto sinusnih in kosinusnih funkcij. Fourierova transformacija
“dopuˇsˇca”, da je perioda neskonˇcno velika.
Ker v praksi seveda ne moremo izraˇcunati funkcij v vseh neskonˇcno mnogo toˇckah in zapisati funkcije kot vsote neskonˇcno mnogo funkcij, uporabimodiskretno Fourierovo transformacijo, ki preslika vektor x0, x1, ..., xN−1 dolˇzine N v vektor y0, y1, ..., yN−1, kjer je
yk = 1
√N
N−1
X
n=0
xne2πiknN. Definirajmo ω=e2πiN in dobimo
yk = 1
√N
N−1
X
n=0
xnωkn. ω je N-ti koren enote, saj zanjo velja
ωN = (e2πiN )N =e2πi= cos(2π) +isin(2π) = 1, inωk 6= 1 za 0< k < N. Norma vektorja ω je
||ω||= q
(e2πiN )2 = p
eN22πi = 1.
Diskretno Fourierovo transformacijo na vektorjih dolˇzine N lahko zapiˇsemo tudi kot matriko velikosti N ×N, katere elementi so (ω√jkN)j,k=0,1,...,N−1:
DF TN = 1
√ N
1 1 1 1 · · · 1
1 ω ω2 ω3 · · · ωN−1
1 ω2 ω4 ω6 · · · ω2(N−1) 1 ω3 ω6 ω9 · · · ω3(N−1)
... ... ... ... . .. ... 1 ωN−1 ω2(N−1) ω3(N−1) · · · ω(N−1)2
.
Oglejmo si primer diskretne Fourierove transformacije na vektorjih dolˇzine 2 in na vektorjih dolˇzine 4.
16
• N = 2
ω =e2πi2 =eπi = cos(πi) +isin(πi) =−1 Predstavimo jo lahko s kvadratno matriko velikosti 2×2 :
DF T2 = 1
√2
1 1 1 ω
= 1
√2
1 1
1 −1
.
Vidimo torej, da je Hadamardova transformacija le poseben primer Fourie- rove.
• N = 4
ω =e2πi4 =eπi2 = cos(πi) +isin(πi) = i Predstavimo jo lahko s kvadratno matriko velikosti 4×4 :
DF T4 = 1 2
1 1 1 1
1 ω ω2 ω3 1 ω2 ω4 ω6 1 ω3 ω6 ω9
= 1 2
1 1 1 1
1 i −1 −i
1 −1 1 −1
1 −i −1 i
.
6.1 Kvantna Fourierova transformacija
Fourierova transformacija ima dve lepi lastnosti, ki si jih bomo ogledali kar na kvantni Fourierovi transformaciji.
Prva lastnost je ta, da fazni zamik vhodnega podatka ne vpliva na konˇcen rezultat. Imejmo vhodno superpozicijo N stanj
α0|0i+α1|1i+α2|2i+. . .+αN−1|N −1i
in ustrezno Fourierovo transformacijo dimenzije N, ki jo predstavimo z matriko:
QF TN = 1
√ N
1 1 1 1 · · · 1
1 ω ω2 ω3 · · · ωN−1
1 ω2 ω4 ω6 · · · ω2(N−1) ... ... ... ... . .. ... 1 ωN−1 ω2(N−1) ω3(N−1) · · · ω(N−1)2
.
Na vhodnem podatku izvedemo Fourierovo transformacijo in dobimo:
QF TN = 1
√N
1 1 1 1 · · · 1
1 ω ω2 ω3 · · · ωN−1
1 ω2 ω4 ω6 · · · ω2(N−1) ... ... ... ... . .. ... 1 ωN−1 ω2(N−1) ω3(N−1) · · · ω(N−1)2
α0 α1 α2
... αN−1
=
β0 β1 β2
... βN−1
.
Torej je nova superpozicija
β0|0i+β1|1i+β2|2i+. . .+βN−1|N −1i.
Ko stanje superpozicije izmerimo, bo stanje sistema |ji z verjetnostjo |βj|2. Na- redimo sedaj Fourierovo transformacijo na vhodnem podatku, ki se od prejˇsnjega razlikuje po tem, da je zamaknjen v desno:
αN−1|0i+α0|1i+α1|2i+. . .+αN−2|N −1i.
Izhodni podatek je sedaj:
QF TN = 1
√N
1 1 1 1 · · · 1
1 ω ω2 ω3 · · · ωN−1
1 ω2 ω4 ω6 · · · ω2(N−1) ... ... ... ... . .. ... 1 ωN−1 ω2(N−1) ω3(N−1) · · · ω(N−1)2
αN−1
α0
α1 ... αN−2
=
β0 ωβ1
ω2β2 ... ωN−1βN−1
.
Kaj smo torej dobili? Zamaknili smo vhodni podatek, dobili pa smo praktiˇcno enak rezultat, le da so amplitude pomnoˇzene. Spomnimo se, ωk so koreni enote
18
in imajo normo 1, zato ob merjenju sistema kubitov dobimo stanje |ji z enako verjetnostjo kot prej,|βj|2.
Ko torej ˇzelimo izvesti Fourierovo transformacijo, ni pomembno kako zamaknemo vhodni podatek, saj to ne bo vplivalo na porazdelitev verjetnosti.
Druga lepa lastnost Fourierove transformacije se nanaˇsa na periodiˇcne funkcije.
Denimo, da je naˇsa vhodna superpozicijaM stanj periodiˇcna s periodo r, torej je enaka, ˇce jo zamaknemo za r amplitud v levo ali desno.
Ko naredimo kvantno Fourierovo transformacijo na tej periodiˇcni funkciji, se izkaˇze, da je transformacija neniˇcelna le na veˇckratnikih Mr , torej na 0,Mr,2Mr , . . . ,M·Mr . Zapiˇsimo to bolj formalno: Na naˇsi vhodni superpoziciji
α0|0i+α1|1i+. . . αr−1|r−1i+α0|ri+α1|r+ 1i+. . . αr−2|M −2i+αr−1|M−1i naredimo kvantno Fourierovo transformacijo in dobimo superpozicijo
β0|0i+βM
r |M
r i+β2M
r |2M
r i+. . .+βMM
r |MM r i.
Zaradi zapletenosti dokaza te lastnosti ne bomo dokazovali. Oglejmo pa si poseben primer in pokaˇzimo, da zanj velja ta lastnost Fourierove transformacije, saj bomo ravno tak primer sreˇcali pri Shorovem algoritmu. Naj bo naˇsa vhodna superpozi- cija z amplitudami αj periodiˇcna s periodor. Dodatno, αj naj bo neniˇcelna le za j ∈ {r,2r,3r, ..., M−r}. Teh neniˇcelnih amplitud je natanˇcno Mr.Ce ˇˇ zelimo super- pozicijo normalizirati in dobiti enotski vektor, mora biti amplituda vseh neniˇcelnih komponent enaka
s 1
M r
= r r
M.
Kvantna Fourierova transformacija dimenzije M to superpozicijo preslika v su- perpozicijo z amplitudami βj. Tudi nova superpozicija je periodiˇcna, vendar s
periodo Mr , saj so amplitude neniˇcelne le za stanja |kMr i. Neniˇcelne amplitude so sedajj ∈ {0,Mr,2Mr,3Mr , ...(r−1)Mr }. In ker jih je natankor, mora biti βj za vsak tak j natanko
q1 r.
Preverimo, da je to res. Zapiˇsimo obe superpoziciji z enaˇcbami. Vhodna superpozicija je:
r r M
M r−1
X
j=0
|jri, izhodna pa
M−1
X
j=0
=βj|ji.
Zanimajo nas amplitude βj. Ko je j veˇckratnik Mr, je
βkM
r =
M r−1
X
j=0
r r M
√1
MωjrkMr =
M r−1
X
j=0
r r M
√1
MωjkM.
Enakost smo dobili iz produkta kMr -te vrstice matrike kvantne Fourierove trans- formacije in matriˇcnega stolpca vhodne superpozicije. Ker so elementi vrstic k 6=r,2r, ..., M −r v stolpcu vhodne superpozicije enaki 0, bo neniˇcelen del vsote vsak produkt elementaωkMr jr(element v kMr -ti vrstici inj·r-tem stolpcu) zj·r-tim elementom stolpca vhodne superpozicije, ki pa so vsi enaki pr
M. Ker je ωkM = (e2πiM )kM =ek2πi = 1,
jeω(jk)M = 1,in so zato vse amplitude βkM
r enake. Ker jih je natanko Mr, dobimo:
βkM
r = M
r
√r M =
√r r = 1
√r. Ker je za kMr faktorkmed 0 inr−1, je amplitudβkM
r natankor. Tehrkomponent skupaj ˇze tvori enotski vektor (dolˇzina je 1), tako da morajo biti vse amplitude βj, za katerejni veˇckratnik Mr , enak 0. Torej smo dobili celotno izhodno superpozicijo.
Kvantna Fourierova transformacija je pravzaprav diskretna Fourierova transfor- macija, ki jo izvajamo na kvantnih raˇcunalnikih. Uporabimo jo na stanju sistema
20
α0|0i+α1|1i+...+αk|kiin dobimo novo stanjeβ0|0i+β1|1i+...+βk|ki.Oglejmo si primer. Imejmo sistem dveh kubitov in njegovo stanje zapiˇsimo kot
α0|0i+α1|1i+α2|2i+α3|3i.
Denimo, da je bil sistem pred uporabo Fourierove transformacije v stanju |2i.
QF T4|2i= 1 2
1 1 1 1
1 i −1 −i
1 −1 1 −1
1 −i −1 i
0 0 1 0
= 1 2
1
−1 1
−1
.
Konˇcno stanje sistema je torej 12|0i − 12|1i+ 12|2i − 12|3i. Ko klasiˇcno raˇcunamo rezultat diskretne Fourierove transformacije na vektorju dolˇzine N, naredimo N operacij za vsako komponento izhodnega vektorja. Ker je teh komponent N, sku- paj naredimo N ·N =N2 operacij. Hitra Fourierova transformacija je algoritem, ki se izvaja na klasiˇcnih raˇcunalnikih za predelavo digitalnih signalov, katerega ˇcasovna zahtevnost je O(NlogN). V klasiˇcnem raˇcunalniku je vhodni podatek torej kompleksni vektor dolˇzine N. V kvantnem raˇcunalniku pa je vstopni vektor superpozicija stanj sistema nkubitov, ki skupaj tvorijo n2 =N moˇznih stanj. Za- nima nas, koliko kvantnih vrat potrebujemo za izraˇcun Fourierove transformacije, kar nam pove tudi ˇcasovno zahtevnost. Izkaˇze se, da je ˇcasovna zahtevnost kvan- tne Fourierove transformacije O(n2). Casovna zahtevnost se je tako eksponentnoˇ zmanjˇsala.
V kvantnih raˇcunalnikih je moˇzno vezje diskretne Fourierove transformacije uˇcinkovito sestaviti z zaporedjem Hadamardovih vrat. Vezje temelji na podobni ideji kot hitra Fourierova transformacija in je v osnovi rekurzivno, pri ˇcemer je Hadamardova transformacija funkcija, ki jo izvedemo ob koncu rekurzije, ko raˇcunamo Fourierovo transformacijo za en sam bit. Zaradi preproste izvedbe in sploˇsne uporabnosti je Fourierova transformacija eden od osnovnih gradnikov kvan- tnih raˇcunalnikov.
Del IV
Shorov algoritem
Shorov algoritem reˇsuje problem faktoriziranja ˇstevil. Denimo, da imamo ˇstevilo N, recimo 60, in ga ˇzelimo zapisati kot produkt praˇstevil. Za naˇse ˇstevilo je to N = 60 = 22·3·5,v sploˇsnem pa zapiˇsemoN =pe11pe22...pekk.Najzanimivejˇsi primer faktorizacije je, ko je N produkt dveh zelo velikih praˇstevil P in Q, ki sta si po dolˇzini precej podobni. Tak primer se uporablja pri ˇsifriranju RSA, ki je najbolj razˇsirjeno ˇsifriranje javnega kljuˇca. RSA namreˇc izkoriˇsˇca teˇzavnost faktoriziranja (velikih) ˇstevil. Do sedaj najhitrejˇsi algoritmi na klasiˇcnem raˇcunalniku delujejo v eksponentnem ˇcasu: ˇce je n dolˇzina ˇstevila N v bitih, je ˇcasovna zahtevnost obiˇcajnih algoritmov O(2n). ˇCasovna zahtevnost najboljˇsih, moˇcno izboljˇsanih al- goritmov, ki upoˇstevajo ogromno ugotovitev teorije ˇstevil in razliˇcnih tehnik, je ˇse vedno 2O(3
√n). S temi algoritmi je zato trenutno nemogoˇce v doglednem ˇcasu razstaviti ˇstevila, ki so dolga npr. 1000 bitov in veˇc.
V zadnjem delu diplomskega dela bomo najprej ponovili modularno aritmetiko.
Nato si bomo pogledali naˇcin faktorizacije ˇstevil, ki ga uporablja Shorov algoritem in nazadnje ˇse podrobno opisali algoritem sam.
Razdelek je povzet po [2], [4] in [6].
7 Modularna aritmetika
Da bomo razumeli, kako kvantni raˇcunalniki reˇsujejo problem faktorizacije, si naj- prej poglejmo elementarno modularno aritmetiko, oz. raˇcunanje po modulu. Za laˇzje razumevanje si bomo v razdelku pomagali s primerom, denimo N = 21. Ko reˇcemo, da je a kongruentnoˇstevilu b po modulu N, kar zapiˇsemo a ≡b(modN), pomeni, da je a ostanek pri deljenju ˇstevila b s ˇstevilom N in lahko piˇsemo
b=qN +a.
22
V primeruN = 21 je tako recimo 3≡24(mod21). −1 po modulu 21 pa je 20, saj je −1≡21 + (−1)≡20.
V modularni aritmetiki lahko seˇstevamo dve ˇstevili:
24 + 35(mod21) ≡3 + 14≡17(mod21), ali mnoˇzimo:
24·30(mod21) ≡3·9≡27≡6(mod21).
Te operacije na klasiˇcnem raˇcunalniku lahko izvajamo zelo hitro, saj nas prav- zaprav zanima ostanek pri deljenju z N. Operacije v modularni aritmetiki torej lahko izvajamo uˇcinkovito.
Stevilom lahko poiˇsˇˇ cemo najveˇcjega skupnega delitelja. Najveˇcji skupni delitelj dveh ˇstevil lahko dobimo tako, da vsakega zapiˇsemo kot produkt samih praˇstevil in
“vzamemo” tiste, ki so skupne, ter jih zmnoˇzimo. Lahko pa to storimo tudi brez faktorizacije ˇstevil in sicer z Evklidovim algoritmom. Postopek na konkretnem primeru je sledeˇc.
Zelimo najti najveˇˇ cji skupni delitelj ˇstevil 21 in 15.
• 21 delimo s 15 in dobimo: 21 = 1·15 + 6
• Deljenje ponovimo s ˇsteviloma 15 in 6: 15 = 2·6 + 3.
• Tokrat ponovimo s ˇsteviloma 6 in 3: 6 = 2·3 + 0.
• 3 je zadnji neniˇcelni ostanek pri deljenju, zatorej je to rezultat iskanja najveˇcjega skupnega delitelja.
Kljub temu, da ne znamo uˇcinkovito faktorizirati ˇstevil na klasiˇcnem raˇcunalniku, lahko najdemo najveˇcjega skupnega delitelja.
8 Faktorizacija
Vrnimo se na naˇs primer N = 21. Problem faktorizacije prevedemo na problem iskanja reˇsitve enaˇcbe x2 = 1(mod21). Iˇsˇcemo torej tako ˇstevilo po modulu 21, katerega kvadrat je enak 1 po modulu 21. Reˇsitev te enaˇcbe je veˇc, najpreprostejˇsa je seveda x= 1. Druga reˇsitev je−1. Preverimo.
−1(modN)≡N −1(modN)
(−1)2(modN)≡(N−1)2(modN)≡N2−2N+1(modN)≡N(N−2)+1(modN) = 1 V naˇsem konkretnem primeru je−1≡20(mod21) in tako 20·20 = 400≡1(mod21).
Ti dve reˇsitvi sta trivialni, nista pa to edini reˇsitvi. Drugim reˇsitvam reˇcemo netrivialni koren enice po modulu N. V dotiˇcnem primeru je taka reˇsitev npr.
x= 8, saj
x2 = 8·8 = 64(mod21) ≡1(mod21).
Torej:
82 ≡1(mod21), 82−1≡0(mod21).
Opazimo, da pri deljenju ˇstevila 82 −1 s ˇstevilom 21 dobimo ostanek 0. Torej 21 deli 82 −1, kar pa je enako (8−1)(8 + 1). Vendar 21 ne deli niti 8 −1 niti 8 + 1. Edini naˇcin, kako je torej moˇzno, da 21 deli 82−1 je, ˇce faktoriziramo 21 in dobimo 21 = 3·7. Pri tem eden od teh faktorjev deli 8−1, drugi pa 8 + 1.
(Pra)faktorje lahko torej pridobimo tako, da izraˇcunamo najveˇcji skupni delitelj ˇstevil 21 in 8-1 ter najveˇcji skupni delitelj ˇstevil 21 in 8+1. Najveˇcja skupna de- litelja sta torej D(21,7) = 7 in D(21,9) = 3. Tako lahko faktoriziramo ˇstevilo ˇze samo z izraˇcunom netrivialnega korena 1 po modulu 21.
V naˇsem primeru pa 8 ni edina reˇsitev, druga je recimo -8, kar je enako 13 po modulu 21.
132 ≡169≡1(mod21).
24
Ce torej najdemo tako ˇsteviloˇ x 6= ±1, katerega kvadrat je x2 = 1(modN), bomo priˇsli do reˇsitve, saj vemo, daN deli (x+ 1)(x−1) in hkratiN ne delix+ 1 ozx−1 (saj x=±16≡0(mod21)). To je moˇzno samo v primeru, ko “del” ˇstevila N deli x+ 1 in drugi del deli x−1. Torej, ˇce izraˇcunamo najveˇcja skupna delitelja ˇstevilD= (N, x±1), dobimo netrivialna delitelja ˇstevila N (torej sta razliˇcna od 1 in N).
Netrivialni koren ˇstevila N najdemo na sledeˇci naˇcin. Naj bo N ˇse vedno 21 in izberimo poljubno ˇstevilox, denimox= 2. Zapiˇsimo tabelo potenc ˇstevila 2 po modulu 21.
20 ≡1(mod21) 21 ≡2(mod21) 22 ≡4(mod21) 23 ≡8(mod21) 24 ≡16(mod21) 25 ≡11(mod21) 26 ≡1(mod21)
26 lahko zapiˇsemo tudi kot 23·23, torej velja (23)2 ≡1(mod21). Dobili smo, da je 23 = 8 netrivialni koren enote.
V sploˇsnem izberemo nakljuˇcen x in izraˇcunamo njegove potence vse do pr- vega takega r, da je xr ≡ 1(modN). Temu r reˇcemo red ˇstevila x po modulu N. Ce imamo sreˇˇ co, je r sod, zato lahko piˇsemo (xr/2)2 ≡ 1(modN), in hkrati ve- lja xr/2 6= ±1(modN). Tako dobimo netrivialen koren 1 po modulu N. Obstaja lema, ki trdi, da ˇce nakljuˇcno izberemo x med 0 in N −1 in je to ˇstevilo tuje N (D(x, N) = 1), imamo natanko polovico moˇznosti, da bomo imeli sreˇco in bomo s postopkom dobili kvadratni koren enote (r bo sod in xr/2 6=±1). ˇCe ugotovimo, da je D(x, N) 6= 1, smo pravzaprav imeli ˇse veˇcjo sreˇco, saj smo tako ˇze dobili enega od faktorjev ˇstevila N.
Naj bo spet N = 21 in x = 2. Definirajmo funkcijo f(a) = xa(modN) in razˇsirimo prejˇsnjo 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 f(a) je torej periodiˇcna funkcija. V naˇsem primeru je perioda r enaka 6.
Naˇs problem sedaj lahko zmanjˇsamo na iskanje periode dotiˇcne funkcije, saj bomo s periodo (nakljuˇcno) izbranega ˇstevila x enostavno priˇsli do reˇsitve naˇsega osnovnega problema. Ta naloga pa ni tako enostavna, kot se zdi na prvi pogled, saj je velikost periode lahko primerljiva z velikostjo ˇstevilaN. ˇCe jeN sestavljeno iz 1000 ˇstevk, je lahko perioda eksponentno velika. Vendar za kvantne raˇcunalnike to ni teˇzava, saj lahko to periodo najde v polinomskem ˇcasu, ne da bi si prej eks- plicitno izraˇcunali zgornjo tabelo potenc.
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.
Del V
Zakljuˇ cek
V diplomskem delu smo korak za korakom gradili osnovno znanje, ki smo ga po- trebovali, da smo lahko dokaj natanˇcno opisali Shorov algoritem za faktorizacijo ˇstevil. ˇCeprav lahko trdimo, da natanˇcno vemo, kako deluje algoritem, pa nimamo raˇcunalnika, na katerem bi ga poganjali. Shorov algoritem pa ni edini algoritem za kvantne raˇcunalnike, obstaja jih ˇse mnogo veˇc. ˇCeprav tudi o sestavi in delo- vanju kvantnega raˇcunalnika vemo ˇze veliko, je teˇzava v tem, da ˇse nismo odkrili materiala, v katerem bi se osnovni delec, ki bi predstavljal kubit, obdrˇzal. Vendar s tem, da teorija prehiti praktiˇcno rabo, matematika nikoli ni imela problemov.
32
Literatura
[1] Malniˇc, A. (2013). Zapiski pri predmetu algebrske strukture. Ljubljana: Pe- dagoˇska fakulteta.
[2] Nielsen, M. in Chuang, I. (2010). Quantum Computation and Quantum In- formation. New York: Cambridge University Press.
[3] Slapar, M. (2012). Osnove kompleksne analize. Ljubljana: Pedagoˇska fakul- teta.
[4] Vazirani, U. (2013).Quantum Mechanics and Quantum Computation. Prido- bljeno 27. 7. 2016, s https://courses.edx.org/.
[5] Discrete Fourier transform.(2017). Pridobljeno 28. 8. 2017, s ht- tps://en.wikipedia.org/wiki/Discrete Fourier transform.
[6] To factorize n, find a non-trivial square root of 1 mod n.(2009). Tricki. Pri- dobljeno 21. 8. 2016, s http://www.tricki.org/.
