Univerzita Karlova v Praze Matematicko-fyzik´aln´ı fakulta ´ RSK ˇ ´ PRACE ´ BAKALA A
ˇ Petr Skoda Kvantov´ e algoritmy ´ Ustav ˇc´asticov´e a jadern´e fyziky Vedouc´ı bakal´aˇrsk´e pr´ace: Doc. RNDr. Pavel Cejnar, Dr. Studijn´ı program: obecn´a fyzika 2007
Chtˇel bych podˇekovat Pavlovi Cejnarovi za trpˇelivou spolupr´aci, d˚ ukladn´e ˇcten´ı prvn´ıch verz´ı pr´ace a hlavnˇe za obrovskou podporu.
Prohlaˇsuji, ˇze jsem svou bakal´aˇrskou pr´aci napsal samostatnˇe a v´ yhradnˇe s pouˇzit´ım citovan´ ych pramen˚ u. Souhlas´ım se zap˚ ujˇcov´an´ım pr´ace. V Praze dne 3
Obsah ´ 1 Uvod
9
2 Elementy kvantov´ eho poˇ c´ıt´ an´ı 2.1 Kvantov´e bity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.2 Kvantov´a hradla . . . . . . . . . . . . . . . . . . . . . . . . . . . 2.3 Asymptotick´a sloˇzitost . . . . . . . . . . . . . . . . . . . . . . . .
9 10 10 13
3 Kvantov´ a Fourierova transformace
13
4 Shor˚ uv algoritmus 4.1 Urˇcen´ı f´aze . . 4.2 Hled´an´ı ˇr´adu . 4.3 Faktorizace . . 4.4 Algoritmus . . .
. . . .
16 17 18 20 20
5 Implementace 5.1 Modul´arn´ı umocˇ nov´an´ı . . . . . . . . . . . . . . . . . . . . . . . . 5.2 Rozvoj do ˇretˇezov´eho zlomku . . . . . . . . . . . . . . . . . . . .
21 21 22
6 Shrnut´ı
23
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
5
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
. . . .
N´azev pr´ace: Kvantov´e algoritmy ˇ Autor: Petr Skoda ´ Katedra (´ ustav): Ustav ˇc´asticov´e a jadern´e fyziky Vedouc´ı bakal´aˇrsk´e pr´ace: Doc. RNDr. Pavel Cejnar, Dr. e-mail vedouc´ıho:
[email protected] Abstrakt: C´ılem bakal´aˇrsk´e pr´ace je sezn´amit ˇcten´aˇre se z´akladn´ımi principy kvantov´eho poˇc´ıt´an´ı. Na zˇrejmˇe nejzn´amˇejˇs´ım kvantov´em algoritmu, Shorovˇe algoritmu na faktorizaci ˇc´ısel, jsou pˇredvedeny postupy budov´an´ı kvantov´ ych algoritm˚ u, jejich probl´emy a nedostatky. Pˇrirozen´ ym prostˇredkem pro z´apis algoritm˚ u jsou programovac´ı jazyky. Jedn´ım z jazyk˚ um pro kvantov´e algoritmy je Quantum Computation Language (QCL), ve kter´em je jako souˇc´ast pr´ace implementov´an Shor˚ uv algoritmus. Kvantov´e algoritmy jsou v souˇcasn´e dobˇe ve stˇredu pozornosti hlavnˇe d´ıky potenci´aln´ımu zrychlen´ı nˇekter´ ych klasick´ ych algoritm˚ u, proto se pr´ace soustˇred´ı i na srovn´an´ı zn´am´ ych klasick´ ych a kvantov´ ych algoritm˚ u. Kl´ıˇcov´a slova: kvantov´ y algoritmus, Shor, QCL
Title: Quantum Algorithms ˇ Author: Petr Skoda Department: Institute of Particle and Nuclear Physics Supervisor: Doc. RNDr. Pavel Cejnar, Dr. Supervisor’s e-mail address:
[email protected] Abstract: The goal of the bachelor work is to explain the basic principles of the quantum computation. The Shor’s algorithm for the number factorization, one of the best known quantum algorithms, represents a good example where the techniques of building quantum algorithms, common problems, and disadvantages can be shown. Using a programming language is the natural way how to describe an algorithm. Quantum Computation Language (QCL) is a programming language for quantum algorithms. As a part of the work, the Shor’s algorithm is written in QCL. One of the reasons why the quantum algorithms are studied in present is the potencial speed up of some classical algorithms. Therefore, the work concentrates on the comparing classical and quantum algorithms. Keywords: quantum algorithm, Shor, QCL
7
1
´ Uvod
Teorie kvantov´e mechaniky vznikla na poˇc´atku 20. stolet´ı, aby popsala jevy jako kvantov´an´ı energi´ı emitovan´ ych foton˚ u ˇci stabiln´ı dr´ahy elektron˚ u kolem atomov´ ych jader, kter´e klasick´a fyzika vysvˇetlit nedovedla. Bˇehem 20. stolet´ı se pak rozvinula v jednu z nejd˚ uleˇzitˇejˇs´ıch souˇcasn´ ych teori´ı. Kvantov´a teorie ovˇsem vynik´a nad ostatn´ı teorie svoj´ı neintuitivnost´ı a mnoho zn´am´ ych fyzik˚ u se snaˇzilo prok´azat jej´ı ne´ uplnost. Pˇresto vˇsechny dosavadn´ı experimenty potvrzuj´ı d˚ usledky kvantov´e mechaniky. Jedn´ım z mnoha obor˚ u kvantov´e mechaniky je kvantov´e poˇc´ıt´an´ı, kter´e se zamˇeˇruje na vyuˇzit´ı kvantov´ ych syst´em˚ u k v´ ypoˇctu algoritmick´ ych u ´loh. Jedn´ım z model˚ u pro kvantov´e poˇc´ıt´an´ı jsou kvantov´e obvody. Kvantov´ y obvod se skl´ad´a z kvantov´ ych bit˚ u (q-bit˚ u), kter´e jsou analogi´ı klasick´ ych bit˚ u, a kvantov´ ych hradel, pomoc´ı nichˇz prob´ıh´a kvantov´ y v´ ypoˇcet. D˚ uleˇzit´ ym prvkem v´ ypoˇctu v kvantov´em syst´emu je mˇeˇren´ı, pomoc´ı kter´eho ˇcteme hodnoty q-bit˚ u. Hlavn´ı myˇslenkou kvantov´eho poˇc´ıt´an´ı je paralelizace v´ ypoˇctu. Zat´ımco klasick´ y poˇc´ıtaˇc je vˇzdy v jednom konkr´etn´ım stavu dan´em hodnotami jeho bit˚ u, kvantov´ y poˇc´ıtaˇc m˚ uˇze b´ yt v libovoln´e superpozici moˇzn´ ych stav˚ u. V´ ypoˇcet tedy m˚ uˇze prob´ıhat pro v´ıce (aˇz 2n , kde n je poˇcet q-bit˚ u) hodnot najednou. Potud to vypad´a jednoduˇse, probl´em ovˇsem nast´av´a, jak tyto v´ ysledky z´ıskat. Mˇeˇren´ım stavu poˇc´ıtaˇce z´ısk´ame pouze jednu n´ahodnou hodnotu. Zn´am´e kvantov´e algoritmy, kter´e jsou rychlejˇs´ı neˇz analogick´e klasick´e, pracuj´ı zcela jin´ ym zp˚ usobem a vyuˇz´ıvaj´ı pr´avˇe vlastnost´ı kvantov´eho syst´emu. Pr´ace je rozdˇelena do ˇctyˇr na sebe navazuj´ıc´ıch ˇc´ast´ı. V ˇc´asti 2 jsou pops´any z´akladn´ı kvantov´a hradla a vysvˇetleny principy kvantov´eho poˇc´ıt´an´ı. D˚ uleˇzit´ ym prvkem kvantov´ ych algoritmu je diskr´etn´ı Fourierova transformace, kter´a je pops´ana v ˇc´asti 3. V ˇc´asti 4 se zamˇeˇr´ım na Shor˚ uv algoritmus. Posledn´ı ˇc´ast 5 je vˇenov´ana implementaci Shorova algoritmu v jazyce Quantum Computer Language.
2
Elementy kvantov´ eho poˇ c´ıt´ an´ı
V t´eto sekci zavedu z´akladn´ı prostˇredky kvantov´eho poˇc´ıt´an´ı, konkr´etnˇe kvantov´e bity a kvantov´a hradla. Pˇredpokl´ad´am z´akladan´ı znalosti kvantov´ ych syst´em˚ u napˇr´ıklad z Form´anka [1]. Pˇredkl´adan´e informace o kvantov´em poˇc´ıt´an´ı a kvantov´ ych algoritmech jsem ˇcerpal z knihy Nielsena a Chuanga [2]. Od kvantov´eho bitu oˇcek´av´ame, ˇze v analogii s klasick´ ym bitem bude nab´ yvat dvou hodnot 0 a 1. Zat´ımco klasick´ y bit je vˇzdy pravˇe v jednom z tˇechto moˇzn´ ych stav˚ u, kvantov´ y bit m˚ uˇze b´ yt v obou z´aroveˇ n“. ”
9
2.1
Kvantov´ e bity
Kvantov´ y bit Q, neboli q-bit, je takov´ y kvantovˇe mechanick´ y syst´em, kter´ y lze plnˇe popsat jako superpozici dvou ortonorm´aln´ıch b´azov´ ych vektor˚ u, kter´e oznaˇc´ıme |0i a |1i. Stavov´ y prostor je Hilbert˚ uv prostor Q = C2 s baz´ı B = {|0i, |1i}, kter´e ˇr´ık´ame v´ypoˇcetn´ı b´aze. Q-Bit se m˚ uˇze bˇehem v´ ypoˇctu nach´azet v libovoln´em stavu |ψi, kter´ y m˚ uˇzeme vyj´adˇrit jako line´arn´ı kombinaci b´azov´ ych vektor˚ u |ψi = α|0i + β|1i .
(1)
Pˇri mˇeˇren´ı q-bitu hodnoty |α|2 a |β|2 urˇcuj´ı pravdˇepodobnost nalezen´ı q-bitu ve stavu |0i, resp. |1i. Proto poˇzadujeme, aby platila normovac´ı podm´ınka |α|2 + |β|2 = 1 .
(2)
V re´aln´em svˇetˇe je mnoho kvantovˇe mechanick´ ych syst´em˚ u, kter´e se chovaj´ı jako kvantov´e bity. Polarizace fotonu, spin elektronu ˇci dvouhladinov´ y atom jsou bˇeˇzn´e pˇr´ıklady. Skupinˇe n q-bit˚ u ˇr´ık´ame registr R o velikosti n. Je to kvantovˇe-mechanick´ ym 2n n syst´em popsateln´ y Hilbertov´ ym prostorem R = C dimenze 2 . Jako pˇrirozenou v´ ypoˇcetn´ı b´azi vol´ıme vektory z B1 ×B2 ×· · ·×Bn , kde Bi je b´aze i-t´eho q-bitu, a znaˇc´ıme je |k1 , . . . , kn i = |k1 i|k2 i · · · |kn i, kde |ki i je b´azov´ y vektor i-t´ eho q-bitu. P Pokud posloupnost bit˚ u k1 , . . . , kn ch´apu jako bin´arn´ı z´apis ˇc´ısla k = ni=1 ki 2i−1 , m˚ uˇzeme ps´at |k1 , . . . , kn i ≡ |ki. B´azov´ ych vektor˚ u je celkem N ≡ 2n a obecn´ y stav |ψi syst´emu lze zapsat jako jejich superpozici |ψi =
N −1 X k=0
ψk |ki .
(3)
Uvˇedomte si, ˇze pokud bychom chtˇeli tento stav uloˇzit v poˇc´ıtaˇci potˇrebovali bychom uloˇzit pˇribliˇznˇe N ≡ 2n komplexn´ıch ˇc´ısel s dostateˇcnou pˇresnost´ı. V kvantov´em poˇc´ıtaˇci n´am na to staˇc´ı n q-bit˚ u. Registry nemaj´ı v pˇr´ırodˇe pˇrirozenou reprezentaci. D˚ uvodem je u velk´ ych kvantov´ ych syst´em˚ u velmi rychl´a dekoherence, tedy interakce syst´emu s prostˇred´ım nebo mezi ˇc´astmi syst´emu, pˇri kter´e syst´em pˇrech´az´ı z ˇcist´eho stavu do sm´ıˇsen´eho stavu, tedy do statistick´e smˇesi ˇcist´ ych stav˚ u. S t´ımto probl´emem se zat´ım pot´ ykaj´ı vˇsechny pokusy o v´ yrobu kvantov´eho poˇc´ıtaˇce.
2.2
Kvantov´ a hradla
Primitivn´ı operace nad q-bity prov´adˇej´ı kvantov´ a hradla. Kvantov´e hradlo je reprezentov´ano unit´arn´ım oper´atorem U , kter´ y zmˇen´ı kvantov´ y stav |ψi na stav U |ψi. Pˇripomeˇ nme, ˇze unit´arn´ı oper´ator se d´a ch´apat jako rotace vektor˚ u v 10
Hilbertovˇe prostoru, protoˇze se pˇri aplikaci oper´atoru nemˇen´ı velikost ani u ´hel (resp. skal´arn´ı souˇcin) sv´ıran´ y zobrazen´ ymi vektory. Kvantov´ y v´ ypoˇcet je pak sloˇzen z posloupnosti kvantov´ ych hradel, kterou m˚ uˇzeme reprezentovat jedinn´ ym oper´atorem U = Un Un−1 . . . U2 U1 , kde Ui jsou oper´atory pˇr´ısluˇsn´e jednotliv´ ym hradl˚ um. Nejprve si vˇsimnˇeme d˚ uleˇzit´eho rozd´ılu mezi kvantov´ ym a klasick´ ym v´ ypoˇctem: Protoˇze oper´atory jsou unit´arn´ı, kaˇzd´ y v´ ypoˇcet na kvantov´em stroji je z definice reversibiln´ı. Nevratnost vnese do v´ ypoˇctu aˇz mˇeˇren´ı hodnot q-bit˚ u. Uk´azalo se, ˇze vˇetˇsina jednoduch´ ych hradel lze implementovat v re´aln´ ych kvantovˇe mechanick´ ych syst´emech. Nˇekolik z´akladn´ıch hradel si nyn´ı pop´ıˇseme. Libovoln´ y stav registru lze ve v´ ypoˇcetn´ı b´azi vyj´adˇrit jako vektor z Hilbertova pro2n storu C . Mˇejme obecn´ y stav |ψi dan´ y superpozic´ı (3), pak pˇr´ısluˇsn´ y vektor ψ m´a sloˇzky ψi . Hradla pak budeme reprezentovat unit´arn´ımi maticemi 2n × 2n z pron n storu C2 ·2 , kde n je poˇcet q-bit˚ u, na kter´ ych hradlo pracuje. Aplikace hradla na stav syst´emu je nyn´ı ekvivalentn´ı n´asoben´ı vektoru stavu matic´ı pˇr´ısluˇsn´e hradlu: U |ψi → Uψ. Pod´ıvejme se na z´akladn´ı jednobitov´a hradla, kter´ ymi jsou Pauliho matice: 1 0 0 −i 0 1 . (4) ; Z≡ ; Y≡ X≡ 0 −1 i 0 1 0 Hradlo X je zn´amˇejˇs´ı jako oper´ator bitov´e negace not, kter´ y stav |0i pˇrevede na stav |1i a naopak. N´asleduj´ıc´ı tˇri hradla hraj´ı velkou roli pˇri skl´ad´an´ı sloˇzitˇejˇs´ıch hradel. 1 1 1 1 0 1 0 . (5) ; T≡ ; S≡ H≡ √ 0 exp(iπ/4) 0 i 2 1 −1 Hadamardovo hradlo H se pouˇz´ıv´a napˇr´ıklad pˇri pˇr´ıpravˇ e stavu tvoˇren´eho super1 pozic´ı vˇsech stav˚ u. Vezmˇeme q-bit ve stavu |0i = . Po aplikaci Hadamardova 0 hradla dostaneme stav |0i + |1i 1 1 1 = √ . H =√ 0 2 1 2 Pokud m´ame n-bitov´ y registr v z´akladn´ım stavu |0i ≡ |0 . . . 0i, pak aplikac´ı Hadamardova hradla na vˇsechny jeho bity dostaneme stav N −1 1 X
2N/2
k=0
|ki ,
(6)
coˇz je superpozice vˇsech moˇzn´ ych stav˚ u registru, kde kaˇzd´ y stav m´a stejnou pravdˇepodobnost. F´azov´e hradlo S a π/8 hradlo T se pouˇz´ıvaj´ı napˇr´ıklad pˇri konstrukci obvodu pro diskr´etn´ı Fourierovu transformaci. 11
H
Obr´azek 1: Obvod s jedn´ım bitem, na kter´ y je aplikov´ano Hadamardovo hradlo.
ˇ a teˇcka znaˇc´ı kontroln´ı bit, b´ıl´a teˇcka Obr´azek 2: Obvod s cnot hradlem. Cern´ negovan´ y bit. Je zˇrejm´e, ˇze pouze s jednobitov´ ymi hradly pˇr´ıliˇs zaj´ımav´ ych oper´ator˚ u nezkonstruujeme, potˇrebujeme k tomu i hradla dvoubitov´a. Z´akladn´ım prvkem klasick´eho v´ ypoˇctu je vˇetven´ı v´ ypoˇctu pomoc´ı bˇeˇzn´e konstrukce if...then...else. K sestrojen´ı analogick´eho podm´ınˇen´eho v´ ypoˇctu v kvantov´em obvodu se pouˇz´ıv´a hradlo controlled-not (cnot). Je to dvoubitov´e hradlo, kter´e provede negaci druh´eho bitu, pouze pokud je prvn´ı bit ve stavu |1i. cnot lze ve v´ ypoˇcetn´ı b´azi popsat matic´ı 1 0 0 0 0 1 0 0 (7) CN = 0 0 0 1. 0 0 1 0
Pomoc´ı nˇeho lze vytvoˇrit z libovoln´e unit´arn´ı operace U operaci controlled-U , kter´a se provede pouze v pˇr´ıpadˇe, ˇze je nastaven kontroln´ı bit. Nyn´ı vyvst´av´a ot´azka: Kolik druh˚ u hradel potˇrebujeme, abychom z nich dok´azali sloˇzit libovoln´ y unit´arn´ı oper´ator? Odpovˇed’ nen´ı v˚ ubec lehk´a, Chuang a Nielsen [2] ukazuj´ı, ˇze libovoln´ y unit´arn´ı oper´ator lze sloˇzit z jednobitov´ ych hradel a cnot hradel. Pokud bychom ovˇsem chtˇeli naj´ıt pouze koneˇcnou mnoˇzinu hradel, nelze jiˇz vˇsechny unit´arn´ı oper´atory sloˇzit pˇresnˇe, protoˇze jich je nekoneˇcnˇe mnoho. Proto se pˇristupuje k aproximaci oper´ator˚ u, kterou se zab´ yv´a cel´a teorie kvantov´ ych samoopravn´ ych k´od˚ u. Kvantov´a hradla sestavujeme do kvantov´ ych obvod˚ u. Jako u klasick´ ych obvod˚ u jsou jednotliv´e bity vedeny po dr´atech“ zleva do hradla a zprava vede ” v´ ystup operace. Pro obvod s jedn´ım q-bitem a jedn´ım jednobitov´ ym Hadamardov´ ym hradlem vypad´a obvod jako na obr´azku 1. Protoˇze hradla pouze mˇen´ı stav q-bit˚ u, nad kter´ ymi pracuj´ı, poˇcet vstup˚ u a v´ ystup˚ u je vˇzdy stejn´ y. Pro controlled-not hradlo v obvodu m´ame speci´aln´ı znaˇcen´ı zn´azornˇen´e na obr´azku 2. ˇ Cernou teˇckou znaˇc´ıme kontroln´ı bit, b´ılou teˇckou negovan´ y bit. Podobn´ ym zp˚ usobem znaˇc´ıme controlled-U operaci (viz. obr´azek 3). Svazkem ˇcar znaˇc´ıme, ˇze hradlo U m˚ uˇze pracovat na v´ıce bitech. Prohozen´ı stav˚ u dvou q-bit˚ u lze prov´est pomoc´ı jednoduch´eho obvodu swap, kter´ y pouˇzijeme pˇri konstrukci obvodu pro kvantovou Fourierovu transformaci. 12
U
Obr´azek 3: Obvod s obecn´ ym controlled-U hradlem. Skupina ˇcar znaˇc´ı, ˇze hradlo U m˚ uˇze pracovat na v´ıce q-bitech.
Obr´azek 4: Obvod swap, kter´ y prohazuje kvantov´e stavy dvou bit˚ u. Obvod se sklad´a ze tˇr´ı hradel cnot zapojen´ ych podle obr´azku 4.
2.3
Asymptotick´ a sloˇ zitost
Na z´avˇer sekce se jeˇstˇe pod´ıv´ame na mˇeˇren´ı efektivity algoritm˚ u. Na klasick´ ych poˇc´ıtaˇc´ıch se z´ab´ yv´ame ˇcasovou sloˇzitost´ı algoritm˚ u, coˇz je funkce T (n) nab´ yvaj´ıc´ı pro kaˇzdou velikost vstupu n nejvˇetˇs´ı poˇcet element´arn´ıch krok˚ u algoritmu, kter´e provede nad nˇejak´ ym vstupem o velikosti n. Protoˇze je ale funkce T (n) ˇcasto sloˇzit´a a n´as zaj´ım´a hlavnˇe jej´ı z´akladn´ı chov´an´ı, zavad´ı se asymptotick´ a sloˇzitost. ˇ ık´ame, ˇze T (n) je asymptoticky menˇs´ı nebo rovno f (n) a p´ıˇseme T (n) = R´ O(f (n)), pokud existuj´ı pevn´e kladn´e konstanty c a n0 , ˇze pro kaˇzd´e n vˇetˇs´ı neˇz n0 je T (n) < c · f (n). Znamen´a to, ˇze funkce T (n) roste do nekoneˇcna pomaleji nebo stejnˇe rychle jako f (n). ˇ ık´ame, ˇze T (n) je asympoticky rovn´e f (n) (T (n) se chov´a ˇr´adovˇe jako f (n)) a R´ p´ıˇseme T (n) = Θ(f (n)), pokud existuj´ı dvˇe kladn´e konstanty c1 , c2 , ˇze pro n > n0 plat´ı c1 f (n) < T (n) < c2 f (n). Jin´ ymi slovy funkce T (n) roste do nekoneˇcna stejnˇe rychle jako f (n). Na kvantov´ ych poˇc´ıtaˇc´ıch bude element´arn´ım krokem algoritmu jedno element´arn´ı hradlo, a proto n´as bude zaj´ımat, kolik element´arn´ıch hradel obsahuj´ı obvody, kter´e budujeme. Podobnˇe jako u klasick´ ych algoritm˚ u n´as bude poˇcet hradel zaj´ımat jen asymptoticky.
3
Kvantov´ a Fourierova transformace
Diskr´etn´ı Fourierova transformace m´a vysok´e uplatnˇen´ı v matematice i v praxi, proto by zrychlen´ı v´ ypoˇctu transformace mˇelo velk´ y pˇr´ınos samo o sobˇe. Kvantov´a Fourierova transformace je z´akladem pro nˇekolik algoritm˚ u, mezi nimiˇz je i Shor˚ uv algoritmus.
13
|j1 i
H
R2
R3
Rn−1
|0i + e2πi0.j1 ...jn |1i
Rn
|j2 i
R2
H
|0i + e2πi0.j2 ...jn |1i
Rn−1
|0i + e2πi0.j3 ...jn |1i
|j3 i |jn−1 i
H
|jn i
|0i + e2πi0.jn−1 jn |1i
R2 H
|0i + e2πi0.jn |1i
Obr´azek 5: Obvod pro kvantovou Fourierovu transformaci. Diskr´etn´ı Fourierova transformace je zobrazen´ı, kter´e komplexn´ımu vektoru se sloˇzkami x0 , . . . , xN −1 , kde N je pevn´a velikost vektoru, pˇriˇrad´ı vektor o sloˇzk´ach y0 , . . . , yN −1 , kde hodnoty yk jsou d´any n´asledovnˇe: N −1 1 X yk ≡ √ xj e2πijk/N N j=0
(8)
Kvantov´a Fourierova transformace je stejn´a transformace, kter´a je provedena nad vektorem reprezentuj´ıc´ım stav syst´emu. Transformace obecn´eho stavu je n´asleduj´ıc´ı: N −1 N −1 X X xj |ji −→ yk |ki (9) j=0
k=0
kde koeficienty yk jsou v´ ysledkem diskr´etn´ı Fourierovy transformace na koeficientech xj . Nyn´ı jsme popsali kvantovou Fourierovu transformaci jako v´ ysledek transformace obecn´eho stavu. Aby mˇela transformace fyzik´aln´ı smysl, mus´ıme ovˇsem uk´azat, ˇze tato transformace je unit´arn´ı oper´ator. Unitarita vyplyne z konstrukce obvodu pro v´ ypoˇcet transformace, ale d´a se uk´azat i pˇr´ımo. Pro konstrukci obvodu transformace se pod´ıv´ame, jak p˚ usob´ı na b´azov´ y stav |ji. D´ıky principu superpozice se pak obecn´ y stav transformuje na souˇcet transformovan´ ych b´azov´ ych stav˚ u. N −1 1 X 2πijk/N e |ki |ji −→ √ N k=0
(10)
Rovnici si jeˇstˇe trochu uprav´ıme. K tomu bude uˇziteˇcn´e pracovat se stavem |ji v jeho bin´arn´ı podobˇe |j1 , . . . , jn i ≡ |j1 i|j2 i · · · |jn i. Podobnˇe zavedeme znaˇcen´ı 0.jl jl+1 . . . jm jako z´apis bin´arn´ıho zlomku jl /2 + jl+1 /4 + · · · + jm /2m−l+1 . n
|ji −→
2 −1 1 X
2n/2
k=0
n
e2πijk/2 |ki 14
(11)
= = = = =
1 1 X
2n/2 1 2n/2 1 2n/2 1 2n/2
k1 =0 1 X
k1 =0 n O
··· ··· "
1 X
Pn
e2πij (
kl 2−l )
kn =0 n 1 O X
kn =0 l=1
1 X
e2πijkl
|k1 , . . . , kn i
e2πijkl 2 |kl i −l
2−l
l=1 kl =0 n h O l=1
l=1
|kl i
|0i + e2πij2 |1i −l
i
2πi(0.jn−1 jn ) |0i + e |1i ··· 2n/2 · · · |0i + e2πi(0.j1 j2 ...jn ) |1i 1
|0i + e2πi(0.jn ) |1i
#
Nyn´ı uˇz vytvoˇr´ıme obvod pro kvantovou Fourierovu transformaci pˇr´ımoˇcaˇre. Budeme k tomu potˇrebovat hradla Rk 1 0 (12) Rk = k 0 e2πi/2 Vˇsimnˇete si, ˇze R1 a R2 jsou ve skuteˇcnosti dˇr´ıve popsan´a hradla S a T . Hlavn´ı ˇc´ast obvodu pro kvantovou Fourierovu transformaci je zn´azornˇena na sch´ematu 5. Popiˇsme, co dˇel´a tento obvod pro vstup |j1 , . . . , jn i. Aplikac´ı Hadamardova hradla na prvn´ı bit dostaneme stav |0i + e2πi(0.j1 ) |1i |j2 , . . . , jn i,
1 21/2
protoˇze e2πi(0.j1 ) je rovno −1, pokud j1 = 1 a +1, pokud j1 = 0. Po proveden´ı controlled-R2 hradla, dostaneme stav |0i + e2πi(0.j1 j2 ) |1i |j2 , . . . , jn i
1
21/2 a po proveden´ı controlled-R3 aˇz controlled-Rn hradel dokonˇc´ıme generovan´ı stavu prvn´ıho bitu ve stavu 1
|0i + e2πi(0.j1 j2 ···jn ) |1i |j2 , . . . , jn i .
21/2 Podobn´ ym zp˚ usobem z´ısk´ame v´ ysledn´ y stav na druh´em bitu 1
|0i + e2πi(0.j1 ···jn ) |1i
22/2 Na konci obvodu jsme z´ıskali stav 1 2n/2
|0i + e2πi(0.j1 ···jn ) |1i
|0i + e2πi(0.j2 ···jn ) |1i |j3 , . . . , jn i .
|0i + e2πi(0.j2 ···jn ) |1i · · · |0i + e2πi(0.jn ) |1i , 15
(13)
kter´ y se liˇs´ı od vzorce (11) v poˇrad´ı stav˚ u na jednotliv´ ych bitech. Prohozen´ı stav˚ u dvou kvantov´ ych bit˚ u provedeme pomoc´ı jednoduch´eho swap obvodu z pˇredchoz´ı sekce. Staˇc´ı n´am tedy n/2 prohozen´ı, abychom z´ıskali stav v ˇz´adan´em tvaru (11). Vˇsimnˇete si, ˇze vˇsechna pouˇzit´a hradla jsou unit´arn´ı, a proto je i kvantov´a Fourierova transformace unit´arn´ı. Pod´ıvejme se kolik hradel tento obvod pouˇz´ıv´a. Na prvn´ım bit je aplikov´ano Hadamardovo hradlo a n − 1 Ri hradel, na druh´ y bit o jedno hradlo m´enˇe, aˇz na n-t´ y bit pouze jedno hradlo. Hlavn´ı ˇc´ast obvodu pouˇz´ıv´a n + (n − 1) + · · · + 1 = n(n + 1)/2 hradel. Operac´ı swap je nejv´ yˇse n/2 a kaˇzd´a lze reprezentovat pomoc´ı tˇr´ı controlled-not hradel. Celkov´ y poˇcet hradel je tedy Θ(n2 ). Abychom dok´azali zhodnotit rychlost kvantov´e Fourierovy transformace, srovnejme ji s klasick´ ym poˇc´ıtaˇcem. Nejrychlejˇs´ı algoritmy jako je rychl´a Fourierova transformace, kter´a bˇeˇz´ı v ˇcase Θ(n2n ), jsou exponenci´alnˇe pomalejˇs´ı. M˚ uˇzeme tedy pouˇz´ıt kvantovou Fourierovu transformaci k poˇc´ıt´an´ı diskr´etn´ı Fourierovy transformace v praktick´ ych aplikac´ıch jako je komprese dat nebo zpracov´an´ı obrazu? Odpovˇed’ je bohuˇzel z´aporn´a. Nezn´ame totiˇz ˇz´adn´ y zp˚ usob, jak zmˇeˇrit amplitudy transformovan´eho stavu, dokonce ani nedok´aˇzeme efektivnˇe pˇripravit konkr´etn´ı vstupn´ı stav. Pˇresto je na kvantov´e Fourierovˇe transformaci postavena cel´a skupina algoritm˚ u.
4
Shor˚ uv algoritmus
Kvantov´ y algoritmus na faktorizaci ˇc´ısel publikoval Peter Shor [3] ve sv´em ˇcl´anku z roku 1994, kter´ y pot´e vyˇsel znovu v roce 1997 v SIAMu. Neˇz se dostaneme k Shorovˇe algoritmu, budeme muset proj´ıt jeˇstˇe dlouhou cestu. Nejprve si uk´aˇzeme obvod na zjiˇstˇen´ı vlastn´ıch ˇc´ısel libovoln´eho unit´arn´ıho oper´atoru (phase estimation). Ten pak vyuˇzijeme k vytvoˇren´ı obvodu pro v´ ypoˇcet ˇra´du grupy (orderfinding problem). Uk´aˇzeme, ˇze faktorizace se d´a pˇrev´est na probl´em nalezen´ı ˇr´adu konkr´etn´ı multiplikativn´ı grupy a tento ˇr´ad najdeme jako f´azi speci´aln´ıho oper´atoru. T´ım dostaneme zn´am´ y Shor˚ uv algoritmus. Pro vlastn´ı ˇc´ıslo λ unit´arn´ıho oper´atoru U plat´ı |λ| = 1, coˇz odvod´ıme pro vlastn´ı vektor x oper´atoru U pˇr´ısluˇsn´ y vlastn´ımu ˇc´ıslu λ. Pouˇzijeme k tomu definici unit´arn´ıho oper´atoru U U ∗ = Id. Ux x U∗ x∗ U ∗ U x x∗ x |λ|2 |λ| ∗
= = = = = =
16
λx ¯ ∗ λx |λ|2 x∗ x |λ|2 x∗ x 1 1
Lze uk´azat, ˇze unit´arn´ı operace zachov´av´a velikost vektoru, m˚ uˇzeme se na ni d´ıvat jako na otoˇcen´ı kolem poˇc´atku.
4.1
Urˇ cen´ı f´ aze
Jak jsme pr´avˇe uk´azali, vlastn´ı ˇc´ıslo λ unit´arn´ıho oper´atoru je komplexn´ı ˇc´ıslo o velikosti 1, a proto ho m˚ uˇzeme zapsat ve tvaru λ = e2πiϕ . Naˇs´ım c´ılem bude zjistit hodnotu f´aze ϕ. K tomu vytvoˇr´ıme obvod se dvˇemi registry. Poˇcet q-bit˚ u prvn´ıho c´ılov´eho registru oznaˇc´ıme t a z´avis´ı na pˇresnosti s jakou chceme f´azi ϕ zmˇeˇrit. Druh´ y oper´atorov´y registr m´a stejn´ y poˇcet q-bit˚ u jako unit´arn´ı oper´ator U , jehoˇz f´azi mˇeˇr´ıme. Prvn´ı ˇc´ast obvodu je zn´azornˇena na obr´azku 6. Oper´atorov´ y registr je na zaˇc´atku ve stavu |ui, kde |ui je vlastn´ı vektor oper´atoru U pˇr´ısluˇsn´ y vlastn´ımu ˇc´ıslu λ. C´ılov´ y registr je na zaˇc´atku ve stavu |0i, ale v prvn´ım kroku ho pˇriprav´ıme do superpozice vˇsech stav˚ u pomoc´ı Hadamardov´ ych hradel. K z´apisu pouˇzijeme tvar souˇcinu jako v sekci 3. ! t −1 2X 1 |ki |ui 2t/2 k=0 =
1
2t/2
(|0i + |1i) (|0i + |1i) · · · (|0i + |1i) |ui
(14)
i
Pot´e provedeme controlled-U 2 operace pro i = 0, . . . , t−1, kde kontrolovac´ı q-bit je (i + 1)-n´ı nejvyˇsˇs´ı q-bit v druh´em registru. Po prvn´ım kroku (i = 0) bude |0i + e2πiϕ |1i stav nejvyˇsˇs´ıho q-bitu c´ılov´eho registru. V i-t´em kroku nastav´ıme stav i+1 (i + 1)-n´ıho nejvyˇsˇs´ıho q-bitu c´ılov´eho registru na |0i + e2 πiϕ |1i. Po proveden´ı vˇsech kontrolovan´ ych operac´ı m´ame syst´em ve stavu 1 2πi2t−1 ϕ 2πi2t−2 ϕ 2πi20 ϕ |0i + e |1i |0i + e |1i · · · |0i + e |1i |ui 2t/2 2n −1 1 X 2πiϕk e |ki . (15) = t/2 2 k=0 Na v´ ysledn´ y stav c´ılov´eho registru provedeme zpˇetnou Fourierovu transformaci. Aproximaci hledan´e f´aze ϕ z´ısk´ame jako v´ ysledek mˇeˇren´ı c´ılov´eho registru. Pro lepˇs´ı pˇredstavu o fungov´an´ı obvodu pˇredpokl´adejme, ˇze f´aze ϕ lze zapsat jako bin´arn´ı desetinn´e ˇc´ıslo o t cifr´ach. Pouˇzijeme stejn´ y z´apis jako v sekci 3, ϕ = 0.ϕ1 ϕ2 . . . ϕt . Po proveden´ı vˇsech kontrolovan´ ych operac´ı m´ame syst´em ve stavu 1 2t/2
|0i + e2πi(0.ϕt ) |1i
|0i + e2πi(0.ϕt−1 ϕt ) |1i · · · |0i + e2πi(0.ϕ1 ...ϕt ) |1i |ui . (16)
Tento stav jsem jiˇz vidˇeli v (11). Je to stav kvantov´e Fourierovy transformace vektoru o sloˇzk´ach ϕi . Provedeme inverzn´ı kvantovou Fourierovu transformaci na 17
|0i
H
|0i + e2πi0.ϕn |1i
|0i
H
|0i + e2πi0.ϕ2 ...ϕn |1i
|0i
H
|0i + e2πi0.ϕ1 ...ϕn |1i
|ui
U2
0
U2
1
U2
t
|ui
Obr´azek 6: Prvn´ı ˇc´ast obvodu pro urˇcen´ı f´aze vlastn´ıho ˇc´ısla unit´arn´ıho oper´atoru. c´ılov´ y registr a dostaneme stav |ϕi|ui. V´ ysledkem mˇeˇren´ı oper´atorov´eho registru je poˇzadovan´a f´aze ϕ pˇresnˇe. Pokud m´a ϕ m´enˇe neˇz t desetinn´ ych cifer, dok´aˇzeme zmˇeˇrit ϕ pˇresnˇe. V obecn´em pˇr´ıpadˇe se ale mus´ıme spokojit s t´ım, ˇze s velkou pravdˇepodobnost´ı se zmˇeˇren´ y odhad ϕ e nebude od skuteˇcn´e f´aze pˇr´ıliˇs liˇsit. V knize Nielsena a Chuanga [2] je dok´az´an n´asleduj´ıc´ı odhad. K tomu, abychom zmˇeˇrili pˇresnˇe ϕ na n bit˚ u s pravdˇepodobnost´ı alespoˇ n 1 − ε, staˇc´ı zvolit velikost c´ılov´eho registru 1 t = n + log 2 + . (17) 2ε Zat´ım jsme pˇredpokl´adali, ˇze zn´ame vlastn´ı vektor oper´atoru U a hlavnˇe ˇze dok´aˇzeme druh´ y registr do vlastn´ıho stavu |ui pˇripravit. My ovˇsem m˚ uˇzeme tento pˇredpoklad y registr pˇriprav´ıme do nˇejak´eho obecn´eho P obej´ıt t´ım, ˇze druh´ stavu |ψi = c |ui. Pak, po proveden´ ı algoritmu Urˇcen´ı f´aze, dostaneme stav u u P 2 cu |ϕ eu i|ui. S pravdˇepodobnost´ı |cu | tedy dostaneme vlastn´ı ˇc´ıslo pˇr´ısluˇsn´e vlastn´ımu vektoru |ui.
4.2
Hled´ an´ı ˇ r´ adu
Nyn´ı si uk´aˇzeme si uk´aˇzeme, jak vyuˇz´ıt algoritmu Urˇcen´ı f´aze k vyˇreˇsen´ı probl´emu Hled´an´ı ˇr´adu, kter´ y je zcela odliˇsn´ y. Mˇejme dvˇe pˇrirozen´a nesoudˇeln´a ˇc´ısla x a N , 1 < x < N . Pak ˇr´ad x modulo N je nejmenˇs´ı pˇrirozen´e ˇc´ıslo r takov´e, ˇze plat´ı kongruentn´ı rovnice xr ≡ 1 (mod N ), kde (mod N ) znamen´a, ˇze v´ ypoˇcet prob´ıh´a nad tˇelesem Zn . Probl´em Hled´an´ı ˇr´adu poˇzaduje pro dan´e x a N nal´ezt ˇr´ad x modulo N . ˇ ad x modulo N nalezneme trikem. Najdeme speci´aln´ı unit´arn´ı oper´ator U , R´ z jehoˇz vlastn´ıho ˇc´ısla jiˇz tento ˇr´ad spoˇc´ıt´ame. Oper´ator U pracuje na b´azov´ ych stavech podle formule U |yi → |xy (mod N )i
18
(18)
Vlastn´ımi stavy U jsou r−1
1 X exp |us i ≡ √ r k=0
−2πisk r
|xk (mod N )i
pro 0 ≤ s ≤ r − 1, jak ukazuje n´asleduj´ıc´ı rovnice r−1 1 X −2πisk U |us i ≡ √ |xk+1 (mod N )i exp r r k=0 −2πis |us i ≡ exp r
(19)
(20)
Vlastn´ımi ˇc´ısly U jsou ˇc´ısla exp(2πis/r). Pouˇzijeme algoritmus Urˇcen´ı f´aze na oper´ator U jehoˇz v´ ysledkem bude pro vlastn´ı stav |us i f´aze s/r, ze kter´e se n´am jiˇz r podaˇr´ı z´ıskat, jak uk´aˇzeme pozdˇeji. Vyvst´avaj´ı dva z´akladn´ı probl´emy. Prvn´ım probl´emem je, jak zkonstuovat pˇr´ısluˇsn´ y unit´arn´ı oper´ator U a jeho mocniny. Tento probl´em se ˇreˇs´ı pomoc´ı modul´arn´ıho mocnˇen´ı, kter´e je struˇcnˇe pops´ano v sekci Implementace. Druh´ ym probl´emem je, jak vytvoˇrit vlastn´ı stav |us i oper´atoru U . To se zat´ım efektivnˇe neum´ı, ale probl´em lze obej´ıt jednoduch´ ym trikem, kdyˇz si vˇsimneme, ˇze plat´ı r−1
1 X √ |us i = |1i. r s=0
(21)
Takto m˚ uˇzeme pˇripravit druh´ y registr do stavu |1i m´ısto do vlastn´ıho stavu oper´atoru U . Po proveden´ı obvodu urˇcen´ı f´aze dostaneme v prvn´ım registru superpozici vˇsech vlastn´ıch ˇc´ısel, ze kter´ ych mˇeˇren´ım dostaneme jedno n´ahodn´e. Pod´ıvejme se nyn´ı, jak z pod´ılu s/r z´ıskat ˇr´ad r. Prvn´ı podm´ınkou je, aby s bylo nesoudˇeln´e s r. Naˇstˇest´ı tato podm´ınka je splnˇena s pravdˇepodobnost´ı alespoˇ n 1/(2 log N ), viz. [2]. Opakov´an´ım mˇeˇren´ı 2 log N kr´at dostaneme s dobrou pravdˇepodobnost´ı nesoudˇeln´ y pod´ıl s/r. Lze pouˇz´ıt i chytˇrejˇs´ıch metod z [2], kter´ ym staˇc´ı pouze konstantn´ı poˇcet opakov´an´ı mˇeˇren´ı. Jin´ ym probl´emem je pˇresnost zmˇeˇren´ı s/r. Zmˇeˇren´a f´aze ve tvaru a/2t , kde t je poˇcet bit˚ u prvn´ıho registru, se od zlomku s/r trochu liˇs´ı. Pouˇzijeme metodu na zjiˇstˇen´ı nejbliˇzˇs´ıho zlomku ve tvaru p/q k a/2t , kde q < N . Jmenovatel q pak bude dobr´ ym odhadem r, protoˇze v´ıme, ˇze ˇr´ad r je menˇs´ı neˇz N . T´eto metodˇe se ˇr´ık´a rozvoj do ˇretˇezov´eho zlomku (the continued fraction expansion). Pod´ıl a/2t pˇrevedeme do tvaru ˇretˇezov´eho zlomku [a0 , . . . , aM ] = a0 +
1 a1 +
1 a2 +
(22)
1 ...+ a 1 M
jednoduch´ ym rekurzivn´ım algoritmem, kter´ y je pops´an v sekci Implementace. Vˇsimnˇete si, ˇze z´apis do ˇretˇezov´eho zlomku je jednoznaˇcn´ y a pro kaˇzd´e racion´aln´ı 19
ˇc´ıslo koneˇcn´ y. Posloupnost [a0 , . . . , ak ] znaˇc´ı pˇr´ısluˇsn´ y ˇretˇezov´ y zlomek, u kter´eho zapomeneme na koeficienty ak+1 , . . . aM . Nyn´ı vezmeme nejvˇetˇs´ı k takov´e, aby zlomek s/r = [a0 , . . . , ak ] odpov´ıdaj´ıc´ı prvn´ım k ˇclen˚ u posloupnosti mˇel r < N . Z´ıskan´ y ˇr´ad r je nejlepˇs´ım odhadem ˇr´adu a v´ ystupem algoritmu.
4.3
Faktorizace
Faktorizace je rozklad ˇc´ısla na jeho prvoˇcinitele. Probl´em je nal´ezt k dan´emu sloˇzen´emu ˇc´ıslu N jednoho jeho dˇelitele. Dosud nen´ı zn´am ˇz´adn´ y klasick´ y algoritmus, kter´ y by k tomu nepotˇreboval ˇr´adovˇe exponenci´aln´ı poˇcet krok˚ u v poˇctu bit˚ u N . Toho se vyuˇz´ıv´a v modern´ı kryptografii a jsou na tom zaloˇzeny nˇekter´e protokoly pro ˇsifrov´an´ı s veˇrejn´ ymi kl´ıˇci (napˇr. RSA). Pokraˇcujme d´ale v pˇrev´adˇen´ı jednoho probl´emu na druh´ y. Nyn´ı si uk´aˇzeme, jak pˇrev´est faktorizaci na hled´an´ı ˇr´adu. Oznaˇcme si N faktorizovan´e ˇc´ıslo. Pokud bychom mˇeli netrivi´aln´ı ˇreˇsen´ı rovnice x2 = 1 (mod N ), x 6= ±1 (mod N ), pak uˇz nalezneme dˇelitele N , protoˇze x2 − 1 = (x + 1)(x − 1) = 0 (mod N ),
(23)
kde lze pˇredpokl´adat, ˇze 1 < x < N − 1, a tedy alespoˇ n jedno ˇc´ıslo z x + 1 a x − 1 je netrivi´aln´ım dˇelitelem N . Jak nalezneme takov´e x? Pro ˇc´ıslo y < N nesoudˇeln´e s N z definice plat´ı r y = 1 (mod N ), kde r je ˇr´ad y modulo N . Pokud je nav´ıc r sud´e a y r/2 6= ˇ ıslo y m˚ ±1 (mod N ), pak x ≡ y r/2 (mod N ) je n´ami hledan´e x. C´ uˇzeme vybrat n´ahodnˇe. Dle [2] plat´ı, ˇze pokud m´a ˇc´ıslo alespoˇ n dva r˚ uzn´e prvoˇc´ıseln´e dˇelitele, r/2 je pravdˇepodobnost P [r je sud´e, y 6= ±1 (mod N )] ≥ 3/4.
4.4
Algoritmus
Shor˚ uv algoritmus se skl´ad´a z mnoha oddˇelen´ ych krok˚ u, kter´e je nutn´e spojit do jednoho algoritmu. Pokus´ım se nyn´ı cel´ y algoritmus zkr´acenˇe zapsat: Faktorizace: • Vstup: cel´e sloˇzen´e ˇc´ıslo N , N nen´ı mocnina prvoˇc´ısla • V´ ystup: dˇelitel ˇc´ısla N • Algoritmus: 1. N´ahodnˇe vybereme ˇc´ıslo 1 < x < N nesoudˇeln´e s N . Pokud by bylo x soudˇeln´e s N , pak x je hledan´ y dˇelitel N a algoritmus ukonˇc´ıme. 2. Pro ˇc´ıslo x vyvoˇr´ıme oper´ator U : |yi → |yx (mod N )i s vlastn´ımi ˇc´ısly e2πis/r , pˇr´ısluˇsn´ ych vlastn´ım vektor˚ um |us i, s = 0, . . . , r −1. Pouˇzijeme 20
obvod u |1i = Pr−1 urˇcen´ı f´aze oper´atoru U na superpozici vlastn´ıch vektor˚ |u i. Dostaneme superpozici vlastn´ ıch ˇ c ´ ısel, ze kter´ y ch mˇ eˇren´ım s s=0 vybereme n´ahodn´e z nich.
3. Z pomˇeru s/r z´ısk´ame odhad re ˇr´adu r pomoc´ı pˇrevodu na ˇretˇezov´ y zlomek. Tento odhad re je roven r, pokud s a r jsou nesoudˇeln´e a pokud byl pod´ıl s/r zmˇeˇren dostateˇcnˇe pˇresnˇe. V tom pˇr´ıpadˇe plat´ı xre = 1.
4. Pokud je r sud´e a plat´ı xr/2 6= ±1 (mod N ), pak z´ısk´ame dˇelitele N jako jedno z ˇc´ısel gcd(xr/2 + 1, N ) a gcd(xr/2 − 1, N ), kde gcd znaˇc´ı nejvˇetˇs´ıho spoleˇcn´eho dˇelitele.
5
Implementace
¨ Pro psan´ı a testov´an´ı program˚ u na kvantov´e poˇc´ıtaˇce napsal Omer [4] jako svoji diplomovou pr´aci programovac´ı jazyk QCL pro kvantov´e poˇc´ıtaˇce. Jazyk QCL je podobn´ y programovac´ımu jazyku C, ale pouˇz´ıv´a pouze z´akladn´ı konstrukce jazyka a jednoduch´e datov´e typy. Nav´ıc definuje prostˇredky pro tvorbu obvod˚ u na kvantov´ ych poˇc´ıtaˇc´ıch jako jsou kvantov´e registry, oper´atory a kvantov´e funkce. K jazyku QCL je k dispozici i jeho interpretr, kter´ y simuluje kvantov´e v´ ypoˇcty na klasick´em poˇc´ıtaˇci. Dokumentace jazyka a interpretr je veˇrejnˇe ke st´ahnut´ı na internetov´e adrese http://tph.tuwien.ac.at/∼oemer/qcl.html. V jazyku QCL jsem implementoval Shor˚ uv algoritmus. Pop´ıˇsi nˇekter´e d˚ uleˇzit´e ˇc´asti programu, cel´ y program je pˇriloˇzen v dodatku.
5.1
Modul´ arn´ı umocˇ nov´ an´ı
J´adrem algoritmu je urˇcen´ı f´aze oper´atoru U : |yi → |xy (mod N )i. Pˇripomeˇ nme jak vypad´a obvod pro urˇcen´ı f´aze ze sekce 4.1. Po pˇripraven´ı c´ılov´eho registru i do superpozice vˇsech stav˚ u n´asleduje blok controlled-U 2 hradel. Ovˇsem vytvoˇrit i ˇ sen´ı spoˇc´ıv´a hradlo pro oper´ator U 2 je tˇeˇzk´e, ale naˇstˇest´ı to nen´ı potˇreba. Reˇ v modul´arn´ım umocˇ nov´an´ı, kter´e vypad´a n´asledovnˇe. Pˇredstavme si, ˇze c´ılov´ y registr nen´ı v superpozici vˇsech stav˚ u, ale pouze v jednom konkr´etn´ım stavu |zi. Z linearity plyne, ˇze p˚ usoben´ı oper´atoru na superpozici stav˚ u je stejn´e jako kdybychom aplikovali oper´ator na jednotliv´e stavy a vzali superpozici v´ ysledku. 2i Proveden´ım controlled-U operac´ı na stav |zi dostaneme t−1
|zi|yi → |ziU zt 2
t−1
0
· · · U z1 2 |yi
0
= |zi|xzt 2 × · · · × xz1 2 y (mod N )i = |zi|xz y (mod N )i.
(24)
Proto se tomuto obvodu ˇr´ık´a modul´arn´ı umocˇ nov´an´ı. Budeme k nˇemu potˇrebovat postavit aritmetick´a hradla. Zaˇcneme sˇc´ıt´an´ım, kter´e pouˇzijeme na n´asoben´ı a nakonec na umocˇ nov´an´ı. V dodatku jsou hradla pops´ana v jazyce QCL. 21
V kvantov´em poˇc´ıt´an´ı se ˇcasto pouˇz´ıv´a chytr´a myˇslenka, kter´e se ˇr´ık´a vratn´e poˇc´ıt´ an´ı. Mˇejme ˇctyˇri kvantov´e registry x, y, z a w, jejich hodnoty budeme znaˇcit (x, y, z, w). Chceme spoˇc´ıtat sloˇzitou funkci f (x), kde x je kvantov´ y registr a pˇritom pouˇzijeme registry y a z k pomocn´ ym v´ ypoˇct˚ um. Aby byl v´ ypoˇcet kvantov´ y unit´arn´ı oper´ator, mus´ı b´ yt reversibiln´ı, nem˚ uˇzeme tedy hodnotu registru pˇrepsat jinou hodnotou, protoˇze by v´ ypoˇcet nebyl reversibiln´ı. M˚ uˇzeme si ale pˇripravit pomocn´e registry y a z do stavu |0i. Pak proveden´ım v´ ypoˇctu dostaneme (x, 0, 0, w) → (x, g(x), f (x), w),
kde g(x) je v´ ysledek nˇejak´eho pomocn´eho v´ ypoˇctu. Nyn´ı pˇrijde hlavn´ı myˇslenka: Bin´arnˇe pˇriˇcteme vypoˇctenou hodnotu do registru w a pot´e provedeme inverzn´ı v´ ypoˇcet, kter´ y po sobˇe uklid´ı pouˇzit´e registry. (x, 0, 0, w) → (x, g(x), f (x), w ⊕ f (x)) → (x, 0, 0, w ⊕ f (x)) ˇ Casto pak pomocn´e registry vynech´av´ame a p´ıˇseme pouze (x, w) → (x, w ⊕f (x)). Jako pˇr´ıklad uvedeme pˇrevod kvantov´eho mocnˇen´ı na kvantov´e n´asoben´ı. t−1 t−2 0 |xz (mod N )i = xzt 2 (mod N ) xzt−1 2 (mod N ) · · · xz1 2 (mod N )
Je-li obvod ve stavu |zi|yi, pak kvantov´ ym vyn´asoben´ım druh´eho registru ˇc´ısly i−1 x2 (mod N ) za podm´ınky, ˇze zi = 1, d´av´a obvod pro kvantov´e modul´arn´ı mocnˇen´ı.
5.2
Rozvoj do ˇ retˇ ezov´ eho zlomku
Pod´ıvejme se jeˇstˇe na algoritmus pro rozvoj do ˇretˇezov´eho zlomku, kter´ y se vyuˇz´ıv´a pˇri odhadu jmenovatele zlomku. Pˇripomeˇ nme, ˇze c´ılem je naj´ıt pro zlomek a/b a ˇc´ıslo m nejbliˇzˇs´ı zlomek p/q takov´ y, ˇze q ≤ m. Myˇslenka algoritmu je vytv´aˇret postupnˇe rozvoj a/b do ˇretˇezov´eho zlomku a pˇritom poˇc´ıtat jmenovatele ˇretˇezov´eho zlomku. Jakmile pˇrekroˇc´ıme mez m vr´at´ıme posledn´ıho jmenovatele menˇs´ıho nebo rovn´eho m. Algoritmus bude pracovat po kroc´ıch. V k-t´em kroku budeme m´ıt zlomek a/b rozvinut´ y na prvn´ıch k ˇclen˚ u ˇretˇezov´eho zlomku. Oznaˇcme xk a yk jeˇstˇe nerozvinutou ˇc´ast zlomku z rozvoje [a0 , . . . , ak ](yk /xk ) = a0 +
1 ... +
1 y ak + xk
,
(25)
k
pak ak+1 = ⌊xk /yk ⌋, xk+1 = yk a yk+1 = xk (mod y)k . Necht’ se d´a jmenovatel zlomku [a0 , . . . , ak ](rk ) zapsat ve tvaru pk · rk + qk . Pokud je rk ve tvaru rk = 1/(ak+1 + rk+1 ), pak se d´a jmenovatel zlomku [a0 , . . . , ak+1 ](rk+1 ) zapsat ve tvaru qk ak+1 + pk + qk · rk+1 a tedy qk+1 = qk ak+1 + pk a pk+1 = qk . Nyn´ı algoritmus form´alnˇe zap´ıˇseme. 22
• Vstup: Cel´a ˇc´ısla a, b, m • Inicializace: x0 = a, y0 = b, p0 = 0, q0 = 1, i = 1 • V´ ystup: Jmenovatel q nejbliˇzˇs´ıho zlomku p/q ke zlomku a/b, kde q ≤ m • Algoritmus: 1. pokud xi−1 mod yi−1 = 0 pak vrat’ qi−1 2. xi = yi−1 yi = xi−1 mod yi−1 3. pi = qi−1 qi = ⌊xi /yi ⌋ · qi−1 + pi−1
4. pokud qi > m pak vrat’ qi−1 jinak i := i + 1 a pokraˇcuj od prvn´ıho bodu
Hodnota yi se v kaˇzd´em kroku zmenˇs´ı alespoˇ n na polovinu, takˇze algorimtus bˇeˇz´ı v ˇcase O(log b). Tento algoritmus je implementov´an ve funkci denominator.
6
Shrnut´ı
Pr´ace se snaˇz´ı popsat apar´at kvantov´eho poˇc´ıt´an´ı, n´aslednˇe postavit Shor˚ uv algoritmus a vysvˇetlit jeho princip. V sekci 2 jsou zavedeny kvantov´e bity, z nich pak sestaveny kvantov´e registry, pˇredstaveny element´arn´ı hradla a uk´az´any z´akladn´ı obvody. N´asleduj´ıc´ı sekce 3 popisuje stavebn´ı prvek mnoha kvantov´ ych algoritm˚ u, kvantovou Fourierovu transformaci. Shor˚ uv algoritmus je vybudov´an od z´aklad˚ u v sekci 4. Nejprve je uk´az´an obvod na urˇcen´ı f´aze, kter´ y se vyuˇzije pro vytvoˇren´ı obvodu na v´ ypoˇcet ˇr´adu grupy. Koneˇcnˇe se uk´aˇze, ˇze faktorizace se d´a pˇrev´est na nalezen´ı ˇr´adu konkr´etn´ı multiplikativn´ı grupy. T´ım je Shor˚ uv algroritmus hotov a v sekci 5 se zab´ yv´am ot´azkami jeho implementace v jazyce QCL. Jako souˇc´ast pr´ace jsem implementoval Shor˚ uv algoritmus v jazyce QCL. Program je pˇriloˇzen v dodatku A. V dodatku B pro ilustraci proch´az´ım po kroc´ıch v´ ypoˇcet Shorova algoritmu pro konkr´etn´ı data a ukazuji nˇekter´e v´ ystupy programu.
Literatura ´ [1] J. Form´anek: Uvod do kvantov´e teorie I, Academia, Praha, 2004.
23
[2] M. A. Nielsen, I. L. Chuang: Quantum Computation and Quantum Information, Cambridge University Press, 2000. [3] P. Shor: Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer, SIAM Journal of Computing 26, 1997, pp. 1484-1509. ¨ [4] B. Omer: Quantum Programming in QCL, master thesis computing science, TU Vienna, 2000. ¨ [5] B. Omer: Structured Quantum Programming, dissertation, TU Vienna, 2003.
24
Dodatek A /∗ I m p l e m e n t a t i o n o f The Shor ’ s a l g o r i t h m i n QCL ∗/ qufunct f l i p ( qureg q ) { int i ; f o r i = 0 to #q /2 − 1 { Swap ( q [ i ] , q[#q−i − 1 ] ) ; } } /∗ d f t ∗/ operator d f t ( qureg q ) { const n = #q ; int i ; int j ; f o r i = 1 to n { H( q [ n−i ] ) ; f o r j = i +1 to n { V( p i / 2 ˆ ( j −i ) , q [ n−i ] & q [ n−j ] ) ; } } f l i p (q ); } /∗ F u n c t i o n s ∗/ int v e c t o r e u c l i d e ( int a , int b ) { int v e c t o r r [ 3 ] ; int v e c t o r s [ 3 ] ; i f b == 0 { return v e c t o r ( a , 1 , 0 ) ; } else { r = e u c l i d e ( b , a mod b ) ; s [0] = r [0]; s [1] = r [2]; s [ 2 ] = r [ 1 ] − ( a /b ) ∗ r [ 2 ] ; return s ; } } i n t invmod ( i n t a , i n t n ) { int v e c t o r r [ 3 ] ; r = euclide (n , a ) ; return ( r [ 2 ] + n ) mod n ; }
25
i n t i e x p n ( i n t a , i n t exp , i n t n ) { int s = a ; int r = 1 ; int i = 0 ; int e = 1 ; while e <= exp { i f b i t ( exp , i ) { r = ( r ∗ s ) mod n ; } s = ( s ∗ s ) mod n ; i = i + 1; e = 2 ∗ e; } return r ; } int i l o g ( int x ) { i n t l g =0; i n t i =1; while i lg = i = i } return
< x { lg + 1; ∗2; lg ;
} /∗ O p e r a t o r s ∗/ cond qufunct f u l l a d d b i t ( boolean b , quconst q , qureg sum , qureg c a r r y ) { if b { CNot ( c a r r y , sum ) ; Not ( sum ) ; } CNot ( c a r r y , sum & q ) ; CNot ( sum , q ) ; } cond qufunct h a l f a d d b i t ( boolean b , quconst q , qureg sum ) { if b { Not ( sum ) ; } CNot ( sum , q ) ; } cond qufunct sum ( i n t b , quconst q , quvoid sum ) { int i ; f o r i = 0 to #q − 2 { f u l l a d d b i t ( b i t ( b , i ) , q [ i ] , sum [ i ] , sum [ i + 1 ] ) ; } h a l f a d d b i t ( b i t ( b , #q −1) , q[#q − 1] , sum[#q − 1 ] ) ; }
26
cond qufunct l t ( i n t b , qureg q , quvoid f l a g , quvoid junk ) { int i ; Not ( f l a g ) ; f o r i = 0 to #q−1 { i f bit (b , i ) { Not ( q [ i ] ) ; CNot ( junk [ i ] , f l a g ) ; CNot ( f l a g , q [ i ] & junk [ i ] ) ; } else { Not ( junk [ i ] ) ; CNot ( junk [ i ] , f l a g ) ; CNot ( f l a g , q [ i ] & junk [ i ] ) ; } } } cond qufunct summodn ( i n t b , i n t n , quconst q , quvoid sum , quvoid f l a g ) { qureg junk [#q ] ; qureg qq = q ; qureg f [ 1 ] ; l t ( n−b , qq , f , junk ) ; CNot ( f l a g , f ) ; ! l t ( n−b , qq , f , junk ) ; if flag { sum(2ˆ#q+b−n , q , sum ) ; } else { sum ( b , q , sum ) ; } } cond qufunct cswap ( qureg a , qureg b ) { int i ; f o r i = 0 to #a−1 { CNot ( a [ i ] , b [ i ] ) ; CNot ( b [ i ] , a [ i ] ) ; CNot ( a [ i ] , b [ i ] ) ; } } cond qufunct i n p l a c e s u m ( i n t b , i n t n , qureg sum ) { qureg junk [#sum ] ; qureg f l a g [ 1 ] ; summodn ( b , n , sum , junk , f l a g ) ; cswap ( sum , junk ) ; Not ( f l a g ) ; ! summodn ( n−b , n , sum , junk , f l a g ) ; }
27
cond qufunct mul ( i n t b , i n t n , quconst q , qureg r ) { int i ; f o r i = 0 to #q−1 { if q[ i ] { i n p l a c e s u m ( b ∗2ˆ i mod n , n , r ) ; } } } cond qufunct ipmuln ( i n t b , i n t n , qureg q ) { qureg junk [#q ] ; i f gcd ( b , n ) > 1 { e x i t ” ipmuln : b and n have t o be r e l a t i v e l y prime ” ; } mul ( b , n , q , junk ) ; cswap ( junk , q ) ; ! mul ( invmod ( b , n ) , n , q , junk ) ; } /∗ expn :
28
/∗ The c o n t i n u e d f r a c t i o n e x p a n s i o n ∗/ i n t denominator ( i n t a , i n t b , i n t max) { i n t x=a ; i n t y=b ; int z ; i n t q0 =0; i n t q1 =0; i n t q2 =1; { q0 = q1 ; q1 = q2 ; z = x mod y ; i f z == 0 { break ; } x = y; y = z; q2 = ( x/y ) ∗ q1 + q0 ; } u n t i l q2 >= max ; return q1 ; } /∗ computes t h e f a c t o r o f n ∗/ i n t g e t f a c t o r ( i n t m, i n t x , i n t n , i n t w) { int y ; int d ; d = denominator (m, 2ˆw, n ) ; i f d mod 2 == 1 { i f 2∗d < n { print ”The denominator i s odd , m u l t i p l y i n g by 2 . . . ” ; d = 2∗d ; } else { print ”The denominator i s odd : ” , d ; return 1 ; } } print ”The denominator i s ” , d ; i f i e x p n ( x , d , n ) != 1 { print ”The denominator i s n ’ t o r d e r o f ” , x ; return 1 ; } y = iexpn (x , d/2 , n ) ; i f y == 1 or y == n−1 { print ”x ˆ ( d / 2 ) i s +− 1 ” ; return 1 ; } return max( gcd ( y −1 , n ) , gcd ( y+1 , n ) ) ; }
29
/∗ Shor ’ s A l g o r i t h m ∗/ procedure s h o r ( i n t n ) { int w = i l o g ( n ) ; int x ; int y ; i n t m; int f a c t o r ; qureg t [ 2 ∗w ] ; qureg u [ w ] ; print ” F a c t o r i n g number” , n ; factor = 0; { reset ; { x = f l o o r ( random ( ) ∗ ( n −2))+2; } u n t i l gcd ( x , n ) == 1 ; print ”Random x i s ” , x ; order (x , n , t , u ) ; measure t , m; i f m == 0 { print ” Zero measured ” ; } else { print ” Measured : ” , m; f a c t o r = g e t f a c t o r (m, x , n , 2∗w ) ; } } until f a c t o r > 1 ; print ” F a c t o r o f ” , n , ” i s ” , f a c t o r ; }
30
Dodatek B Pr˚ ubˇeh Shorova algoritmu si uk´aˇzeme na pˇr´ıkladu. Necht’ chceme naj´ıt dˇelitele ˇc´ısla N = 39. Jako n´ahodn´e ˇc´ıslo pro hled´an´ı ˇr´adu modulo N zvol´ıme x = 20. Na zaps´an´ı ˇc´ısla N potˇrebujeme w = 6 bit˚ u a z tohoto poˇctu odvod´ıme velikost kvantov´ ych registr˚ u. Jak jsme uk´azali v sekci Implementace, hlavn´ı ˇc´ast algoritmu je modul´arn´ı umocˇ nov´an´ı, kter´e vyˇzaduje dva registry. Oper´atorov´ y registr o velikosti w na vlastn´ı stavy oper´atoru U : |yi → |yx (mod N )i, jejichˇz f´aze urˇcujeme, a c´ılov´ y registr, kter´ y m´a tolik q-bit˚ u, s jakou pˇresnot´ı chceme urˇcit f´azi. Pro naˇsi potˇrebu zvol´ıme velikost t = 8. Zaˇcneme t´ım, ˇze c´ılov´ y registr pˇriprav´ıme do superpozice vˇsech stav˚ u a oper´atorov´ y registr do stavu |1i, coˇz je superpozice vlastn´ıch stav˚ u U . Pot´e provedeme modul´arn´ı mocnˇen´ı a zpˇetnou Fourierovu transformaci. Nyn´ı m´ame v c´ılov´em registru poˇzadovanou f´azi, ve skuteˇcnosti superpozici vˇsech f´az´ı vlastn´ıch ˇc´ısel pˇr´ısluˇsn´ ych vlastn´ım stav˚ u U . Interpreter QCL n´am umoˇzn ˇuje vyn´est do grafy amplitudy pravdˇepodobnost´ı jednotliv´ ych stav˚ u, vyuˇzijeme toho k zobrazen´ı amplitud pravdˇepodobnost´ı stav˚ u c´ılov´eho registr na obr´azku 7. Amplitudy pravdˇepodobnosti tvoˇr´ı p´ıky, kter´e jsou zp˚ usobeny t´ım, ˇze ˇr´ad x modulo N nedˇel´ı t ˇ celkov´ y poˇcet stav˚ u 2 . C´ım jsou p´ıky ˇsirˇs´ı, t´ım je vˇetˇs´ı ˇsance, ˇze nezmˇeˇr´ıme ˇr´ad dostateˇcnˇe pˇresnˇe. Zvˇetˇsen´ım c´ılov´eho registru m˚ uˇzeme zvˇetˇsit poˇcet zmˇeˇren´ ych bit˚ u ˇr´adu a t´ım zvˇetˇsit pravdˇepodobnost z´ısk´an´ı spr´avn´eho ˇr´adu, jak popisuje rovnice (17). Zmˇeˇr´ıme c´ılov´ y registr a necht’ dostaneme hodnotu m = 107, jej´ıˇz pravdˇepodobnost byla 5.7%. Rozvinut´ım do ˇretˇezov´eho zlomku dostaneme, ˇze zlomek m/2t = 107/256 je nejbl´ıˇze zlomku 5/12 a v tomto pˇr´ıpadˇe opravdu dost´av´ame ˇr´ad r = 12. Protoˇze je ˇr´ad sud´ y a xr/2 = 25 6= ±1 (mod N ), alespoˇ n jedno z ˇc´ısel r/2 r/2 x + 1 a x − 1 m´a s N netrivi´aln´ıho spoleˇcn´eho dˇelitele. Nejvˇetˇs´ı spoleˇcn´ y r/2 dˇelitel ˇc´ısel x + 1 a N je 13, coˇz je hledan´ y dˇelitel. Na z´avˇer jeˇstˇe uk´aˇzeme dva grafy amplitud pravdˇepodobnosti c´ılov´eho registru po proveden´ı obvodu urˇcen´ı f´aze. Na obr´azku 8 m´a c´ılov´ y registr 12 q-bit˚ u, na obr´azku 9 m´a pouze 5 q-bit˚ u.
31
t (8 qubits) Obr´azek 7: Amplitudy pravdˇepodobnosti c´ılov´eho registru po proveden´ı obvodu urˇcen´ı f´aze pro N = 39, x = 20 a t = 8
32
t (12 qubits) Obr´azek 8: Amplitudy pravdˇepodobnosti c´ılov´eho registru po proveden´ı obvodu urˇcen´ı f´aze pro N = 55, x = 51 a t = 12
33
t (5 qubits) Obr´azek 9: Amplitudy pravdˇepodobnosti c´ılov´eho registru po proveden´ı obvodu urˇcen´ı f´aze pro N = 26, x = 15 a t = 5
34
