Nagy szamok faktorizacioja aShor-algoritmussal

Koronka Gabor

May 31, 2012

1

Tartalomjegyzek

1 Bevezetes 3

2 A Shor-algoritmus vazlata 62.1 Az algoritmus lepesei . . . . . . . . . . . . . . . . . . . . . . . 62.2 Hatvany tulajdonsag ellenorzese . . . . . . . . . . . . . . . . . 72.3 Nem prımhatvany eseten a nem trivialis felbontas . . . . . . . 72.4 Pelda szamıtas . . . . . . . . . . . . . . . . . . . . . . . . . . 9

3 Kvantumszamıtogepek bevezetese 113.1 A kvantum bit . . . . . . . . . . . . . . . . . . . . . . . . . . . 113.2 A kvantum szamıtasok . . . . . . . . . . . . . . . . . . . . . . 123.3 Tenzorszorzat . . . . . . . . . . . . . . . . . . . . . . . . . . . 123.4 A kvantum kapuk . . . . . . . . . . . . . . . . . . . . . . . . . 143.5 Hagyomanyos szamıtogepek szimulalasa

kvantumszamıtogepen . . . . . . . . . . . . . . . . . . . . . . 163.6 Fourier-transzformacio kvantumszamıtogepekkel . . . . . . . . 17

4 Kvantum algoritmus a rend meghatarozasara 214.1 Az input kezelese, es regiszterek beallıtasa . . . . . . . . . . . 214.2 A rend adott fuggvenyenek meghatarozasa specialis esetben . 224.3 A rend adott fuggvenyenek meghatarozasa altalanos esetben . 234.4 A rend meghatarozasa az outputbol leolvashato fuggvenyebol . 274.5 A rend meghatarozasa peldaszamıtassal . . . . . . . . . . . . . 28

2

1 Bevezetes

A szamıtogepek altal megoldhato problemakkal es ezen megoldasokfutasidejevel, bonyolultsagaval a szamıtastudomany foglalkozik.

Ez a tudomanyag foglalkozik azzal is, hogy mely problemakat tudunkmegoldani es melyeket nem kulonbozo szamıtogepmodellek segıtsegevel.Ezzel a temaval kapcsolatos elso jelentosebb eredmenyek a huszadik szazadelejen jelentek meg, melyek tobbek kozt Church, Turing, es Post nevehezfuzodik.

Az eredmenyeik kozott szerepeltek Turing-geppel megoldhato es nemmegoldhato problemak. Turing tobbek kozott megmutatta, hogy letezik nemfelismerheto nyelv, vagyis leteznek olyan szavai ennek a nyelvnek, amirol nemtudjuk eldonteni Turing-geppel, hogy ez a bizonyos szo eleme-e a nyelvnek.Tehat ennek eldontese nem megoldhato Turing-geppel.

A legfontosabb tezis Church nevehez fuzodik, amelyben azt allıtja, hogyakarmilyen szamıtogepre ırt algoritmus szimulalhato Turing-geppel. Ennekazert van nagy jelentosege, mert ekkor minden, amit nem tudunk megoldania Turing-geppel, azt egyeb mas szamıtogepmodellekkel sem fogjuk tudnimegoldani. Church nevehez fuzodik az elobbi tezis egy erosebb verzioja is,amely azt mondja, hogy barmely fizikai gep lepesei szimulalhatoak Turing-geppel, megpedig annak polinomialisan sok lepesevel. Ez igen eros allıtas,mert ha P 6=NP, akkor semmilyen szamıtogeppel nem lesznek megoldhatoakgyorsan az NP nehez problemak.

A fenti egyenlotlensegben a P a determinisztikusan polinomialislepesszammal megoldhato problemak halmaza, mely problema megoldasanaklepesszama az input meretenek olyan fuggvenye, amit felulrol tudunk becsulniegy polinom fuggvennyel. A masik halmaz az NP-beli problemak halmaza,melynek elemeit nem determinisztikusan meg tudjuk polinom idoben oldani,vagyis a lepesszam az inputtol polinomialisan fugg. Ez a ket halmazlehet ugyanaz a ket halmaz, de jelenleg nem ismert bizonyıtas arra, hogymegegyeznenek, es cafolni sem tudtak meg.

Igy jelenleg azoknak a problemaknak, amikrol tudjak, hogy NP-beliek,de amelyekrol nem ismert, hogy P-beliek lennenek-e, a megoldasahozdeterminisztikus algoritmussal exponencialis lepesre van szukseg, amieleg nagy input eseten lefuttathatatlan. Ezert fontos kerdes, hogybizonyos problemak P-beliek-e, es ıgy polinom lepesben futo algoritmussalmegoldhatoak-e. Megjegyezhetjuk, hogy termeszetesen nagyon magas fokupolinom eseten, nagy inputra megint csak tul hosszu idore lenne szukseg egyilyen lepesszamu algoritmus lefuttatasahoz. Igy a gyakorlatban olyan, minel

3

gyorsabb algoritmusokat keresnek, amelyek lepesszamanak az inputtol valofuggese nagyon kisfoku polinommal felulrol becsulheto.

A fenti tezist cafolando csinaltak olyan elmeleti szamıtogepeket,amelyekkel meg lehet oldani polinom idoben NP nehez problemakat.Viszont ezek a cafolatok azert nem voltak sikeresek, mert nem feleltekmeg a fizika szabalyainak, ıgy kesobb nem is lehetett oket a valosagbanmegepıteni. Annak ellenere, hogy sokan dolgoztak kulonfele egyeb alternatıvszamıtogepek kitalalasaval es megcsinalasaval, meg nem sikerult olyanszamıtogepet epıteni, amellyel meg lehet oldani NP nehez problemat.

Igy jott az otlet, amelyet 1982-ben Richard Feynmann, Nobel-dıjas fizikusvetett fel, hogy lehetne epıteni olyan szamıtogepet, amely a kvantumfizika,a szamıtastechnikaban kulonlegesnek szamıto tulajdonsagait hasznalna ki.Kesobb tobb nagy matematikus is foglalkozott azzal a temaval, hogy errea szamıtogepre algoritmust ırjon, eddig viszont csak ket nagyobb eredmenyszuletett ebben a temaban, ami Grover es Shor nevehez fuzodik.

Shor-algoritmus nagy szamokat faktorizal. E problema tortenelmeregebbre nyulik vissza, es eleg nagy jelentoseguve valt a huszadik szazadban.

A nagy szamok faktorizalasanal ezen nagy szamok prımtenyezosfelbontasat keszıtjuk el. A faktorizalas jelentos muvelet, es a szamelmeletbenis nagy szerepe van. Egy adott szam sok kulonbozo szamelmeletifuggvenyeknel felvett erteke es tulajdonsagai a prımtenyezos felbontasarolleolvashatoak, es abbol kiszamıthatoak.

Maga a faktorizalas azert is kapott meg nagyobb figyelmet, mert kesobbolyan titkosıtasokat talaltak ki, amelyek szamelmeleti tulajdonsagokathasznalnak ki. Igy a faktorizalas segıtsegevel ki tudjuk szamıtani aszukseges szamelmeleti fuggvenyek erteket is, ami a titkosıtott informaciokvisszafejtesenek lehetoseget adja a kezunkbe.

Az egyik legfontosabb ilyen kod az RSA. Ezt a kodolast 1976-ban RonRivest, Adi Shamir es Len Adleman fejlesztette ki, es ezzel megjelent azelso nyılt kulcsu titkosıtas. Ennek azert van nagy jelentosege, mert nemkell a kodnyelven kommunikalo feleknek titkos talalkozon informaciokatmegosztaniuk.

Egy nyilvanos es egy titkos kulcson alapul az eljaras. Egy nyılt kulcssegıtsegevel barki bekodolhat uzenetet, de csak az tudja a kodot elolvasni,akinek a titkos kulcs is megvan. Ez a fel kuldi szet a nyilvanos kulcsotis. Ez az eljarassal fordıtott iranyban is mukodik, a titkos kulccsal bekodoltinformaciokat szetkuldi a folyamat, azaz mindenki el tudja olvasni a nyilvanoskulcs segıtsegevel a titkosıtott informaciot, de senki mas nem tud uzenetetırni, mert ahhoz szuksege lenne a titkos kulcsra is, ilyen modon keszıtenekdigitalis alaırasokat is.

4

A titkosıtasban es a titkosıtassal foglalkozo elmeletben ez nagy elorelepesvolt, es nagyon nagy hatassal volt a vilagra. Ilyen, es ehhez hasonlo kodokatalkalmaznak az internet kodolasakor. Peldaul egy internetes oldalt csaka titkosıto fel tudjon szerkeszteni, de mindenki kepes legyen megnyitni,olvasni es bongeszni. Hasonloan a bankoknal is gyakran hasznalnak ilyenkodolasokat. Mikor kulonbozo tranzakciokat vegzunk, ezek a kodok tesziklehetove, hogy az adott tranzakcio sikeres legyen, ahogyan azt is, hogy abankszamla vedett legyen.

Egyszoval, a mai vilagunkban nagyon megnott a szerepe a nyıltkulcsukodoknak. Ezzel termeszetesen egyutt jar, hogy probalnak kulonfelemodszereket talalni ezen titkosıtasok feltoresehez, visszafejtesehez. A fentemlıtett RSA kod matematikailag visszafejtheto, de olyan hosszu ideigtart egy-egy titkosıtott informacio visszafejtese, hogy mire dekodolnak egyuzenetet, mar regen elvesztette a lenyeget a dekodolt informacio. Raadasula kulcsokat, amin a titkosıtas alapul, viszonylag suru idokozonkent frissıtik,ıgy teljesen felesleges a dekodolast elkezdeni is. Tehat, ha valaki szeretnefeltorni egy ilyen kodot viszonylag gyors algoritmusra van szuksege. Ezsok matematikus es informatikus erdeklodeset is felkeltette, de mindeddiga hagyomanyos szamıtogepre nem sikerult ilyen algoritmust ırni.

Kesobb, amikor megjelentek uj szamıtogep modellek, es ezekrealgoritmusokat ırtak, sikerult Shornak kvantum polinomialis idobenmegoldani ezt a problemat, vagyis olyan algoritmust ırnia, amelyneklepesszama az input meretetol polinomialisan fugg es faktorizal egy szamot.Ennek segıtsegevel mar kenyelmesen visszafejtheto barmilyen titkosıtottinformacio.

A problema ezekkel a szamıtogepekkel, hogy megepıteni nem tudtak oket,csak az elmelet volt meg hozza. Igy volt ez a kvantumszamıtogeppel es aShor altal ırt algoritmussal is. Jelenleg sincsen olyan kvantumszamıtogep,ami eleg nagy inputot tudna kezelni egy mai kod feltoresehez. Azonban1998-ban az IBM, MIT, a Californiai Egyetem es az Oxford Egyetem kutatoikozosen kifejlesztettek egy kvantumszamıtogepet, aminek a processzorahidrogen es kloratomokbol allt. Ezzel a geppel eredmenyesen tudtakdemonstralni nehany alapmuveletet, es futtatni nehanyat a legegyszerubbalgorimusokbol, de a szamıtogep kapacitasa tul kicsi volt ahhoz, hogykomolyabb algoritmusokat futtassanak rajta. Mindeddig nem sikerult elegkapacitassal rendelkezo kvantumszamıtogepet epıteni.

5

2 A Shor-algoritmus vazlata

2.1 Az algoritmus lepesei

Kezdetben bemutatjuk az algoritmus lepeseit, es csak majd ezt kovetoenreszletezzuk, es magyarazzuk meg azokat.

Adott egesz szam inputra annak prımtenyezos felbontasat adja meg azalgoritmus.

Elsokent az N inputot, ha lehetseges, nem-trivialis modon felbontjukket egesz szam szorzatara, majd a szorzat tagjait ilyen modon tovabbbontjuk, amıg a szorzat egyik tagja sem bonthato tovabb. Ekkor a szorzatminden tagja mar prım. A kovetkezokben egy szam nem trivialis felbontasatreszletezzuk.

1. Lefutattunk egy prımtesztet N -re. Ha prım, nem bonthato tovabb, eskeszen vagyunk. Egyeb esetben futtatjuk a 2. lepest.

2. Ha N paros, akkor ismerjuk egy nem-trivialis felbontasat N -nek. Haparatlan, akkor futtatjuk a 3. lepest.

3. Megkeressuk, hogy mely s egesznek a hatvanya N . Ha talaltunk, akkorezzel N -et szorzatra bontottuk. Ha viszont nem talalunk ilyet, akkorN nem lehet prımhatvany, az 1. lepes miatt nem lehet prım, ezertlegalabb ket prımtenyezoje van, ekkor futtatjuk a 4. lepest.

4. Valasztunk veletlenszeruen egy m szamot. Legyen (m,N) = d, had 6= 1, akkor d × N

degy nem-trivialis felbontas. Ha d = 1 akkor

futtatjuk az 5. lepest.

5. Keressuk P -t, ahol ON(m) = P . Ebben a lepesben hasznaljuk ki akvantum szamıtogep tulajdonsagait, ıgy kvantum polinomialis idobenkiszamıthato m rendje, azaz P . Ezutan futtatjuk a 6. lepest.

6

6. Ha P paros, es (N,mP2 − 1) 6= 1, (N,m

P2 + 1) 6= 1, akkor

(N,mP2 − 1)× (N,m

P2 + 1) egy nem-trivailis felbontas. A feltetel nem

teljesulese eseten futtatjuk a 3. lepest.

2.2 Hatvany tulajdonsag ellenorzese

Megnezzuk minden 1 ≤ k ≤ logN eseten k√N egesz-e. Ezt ugy csinaljuk,

hogy N k-adik gyoket olyan pontossaggal kozelıtjuk, hogy csak nehanyegesz szam essen a hibahatarok koze. Ezeket az egesz szamokat k-dikra emelve ellenorizhetjuk, hogy N k-adik gyokei-e, es ıgy polinomialisidoben megtalaljuk az osszes egesz szamot, amelynek hatvanya N . Mivela gyokvonast ilyen pontossaggal polinomialis idoben el tudjuk vegezni.Hasonloan a visszaszorzasokat is konstansszor polinomialis idoben vegigtudjuk szamolni. Ezeket a muveleteket pedig annyiszor kell elvegezni, ahanyfele lehet k, vagyis logN -szer, amivel egyutt meg ıgy is polinomialis idobenfut az algoritmus ezen resze.

2.3 Nem prımhatvany eseten a nem trivialis felbontas

Egy veletlen m valasztasa utan az euklideszi-algoritmussal polinomialisidoben megkapjuk (N,m) = d-t. Ha d 6= 1 keszen vagyunk. Ha d = 1kiszamıtjuk P -t, hogy ON(m) = P . Ezt kesobb reszletezzuk.

Tegyuk fel, hogy P paros, es (N,mP2 − 1) 6= 1, (N,m

P2 + 1) 6= 1, ekkor

mP ≡ 1 (mod N),

vagyismP − 1 ≡ 0 (mod N),

esmP − 1 = (m

P2 − 1)(m

P2 + 1),

tehatN | (m

P2 − 1)(m

P2 + 1),

ıgy (N,mP2 − 1)× (N,m

P2 + 1) nem trivialis felbontasa N -nek.

7

Allıtas: P((P paratlan)vagy((N,mP2 − 1) = 1)vagy((N,m

P2 + 1) = 1)) ≤

14. Vagyis annak a valoszınusege, hogy a valasztott m szamunk segıtsegevel

nem tudjuk felbontani N -et, es uj veletlen szamot kell valasztanunk.

Bizonyıtas: Legyen∏k

i=1 pαii = N prımtenyezos felbontasa. Ekkor a kınai

maradektetelbol kovetkezoen

Z∗N izomorf Z∗p1α1 × Z∗p2α2 × Z∗p3α3 × · · · × Z∗pkαk -el,

az a↔ (a1, a2, a3, . . . , ak) kolcsonosen egyertelmu relaciotarto hozzarendelesrenezve, ahol Z∗N -ben mod N , mıg Z∗piαi -ben pedig mod pi

αi relaciokat tekintjuk.Itt a relaciotartast a kovetkezokeppen definialjuk:

a mod N ⇔ a1 mod pα11 , a2 mod pα2

2 , a3 mod pα33 , . . . , ak mod pαkk .

Tehat, a veletlenszeruen valasztottm helyett valaszthatunk veletlenszeruenegy az mi ∈ Z∗piαi elemekbol allo (m1,m2, . . . ,mk) vektort amivelegyertelmuen meghatarozzuk az m szamot.

Legyen m az a szam amelyre teljesul, hogy 1 ≤ m ≤ N , es mi-k altalmeghatarozott kongruencia-rendszer megoldasa m, vagyis

m ≡ m1 (mod pα11 ),m ≡ m2 (mod pα2

2 ), . . . ,m ≡ mk (mod pαkk )

Igy ha az (m1,m2, . . . ,mk) vektort egyenletesen valasztjuk, akkor ez a fentiekalapjan meghatarozott m-nek is egy egyenletes eloszlasu valasztasat adja.

Legyen gi a Z∗piαi multiplikatıv csoport generatoreleme, xi olyan, hogygxii ≡ mi (mod pαii ), ri = Opiαi (g

xii ), es Xi = {x : 1 ≤ x ≤ ri}.

Ekkor xi ↔ mi = gxii egy kolcsonosen egyertelmu hozzarendeles Xi elemeies Z∗piαi elemei kozt. Igy (x1 ∈ X1, x2 ∈ X2, . . . xk ∈ Xk)↔ a ∈ {1, 2, . . . , N}egy kongruenciatarto kolcsonosen egyertelmu hozzarendelesX1×X2×· · ·×Xk

elemei es {1, 2, . . . , N} elemei kozt.Ezert a fentiek alapjan veletlenszeruen valasztott m-et helyettesıthetjuk

egy veletlen (x1, x2, . . . , xk) vektorral, amely a gi-k kitevojekent egyertelmuenmeghatarozza mi-ket, es ıgy m-et is.

Legyen s az az index, melyre 2l | rs-t, viszont minden i-re 2l+1 - ri-t. Ha2 - P , akkor l = 0, es mivel 2 | Op

αii

(gi), ekkor 2 | xi szuksegszeruen, viszont

P(2 | xi) ≤ 12, ebbol pedig mar tisztan kovetkezik, hogy P(2 - P ) ≤ 1

2.

Legyen Opαii

(gi) legnagyobb ketto-hatvany osztoja 2hi . Ha minden 1 ≤i ≤ k-ra 2l | ri-t, ekkor 2hi−l | xi, de 2hi−l+1 - xi. Tetszoleges ismert, a fenti

8

modon definialt, rs eseten, ha i 6= s P(2hi−l | xi, 2hi−l+1 - xi) ≤ 12. Ekkor

tehat barmilyen is rs, i 6= s eseten az xi-knek maximum a fele teljesıti afeltetelt.Vagyis

P(2 - P, ∃l : ∀i(2l | ri, 2l+1 - ri)) ≤ (1

2)k + (

1

2)k−1

Ha nem prımhatvany N , akkor k ≥ 2, es ıgy legalabb 14

valoszınuseggelP paros, es letezik i, hogy 2l - ri. Erre az i-re

(gxii )P2 ≡ 1 (mod pαii ),

vagyis

mP2 ≡ 1 (mod pαii ),

ekkor viszont pαii | mP2 − 1.

Masreszt P az ri-k legkisebb kozos tobbszorose, ıgy P -nek is 2l-en alegnagyobb ketto-hatvany osztoja. Ezert, es mert ciklikus Z∗psαs

(gxss )P2 ≡ −1 (mod pαss ),

mP2 ≡ −1 (mod pαss ),

vagyis pαss | mP2 + 1. Tehat ekkor (N,m

P2 − 1) 6= 1, (N,m

P2 + 1) 6= 1.

2.4 Pelda szamıtas

Legyen az N = 21, erre az egesz inputra futtassuk az algoritmust. Akovetkezoben az algoritmus lepesein haladunk vegig erre az inputra.

1. Lefuttatunk egy prımtesztet a 21-re. A teszteles utan kiderul, hogynem prım, es az algoritmus futtatja a kovetkezo lepest.

2. Leellenorzi, hogy 21 paros-e, de 21 nem oszthato kettovel, ıgy azalgoritmus futtatja a 3. lepest.

3. Ebben a reszben keres egy szamot, amely valahanyadik gyoke 21-nek,de ilyet nem talal, mert 21 nem hatvany. Ezert futtatja a 4. lepest.

9

4. Valasszuk veletlenszeruen a 2-t. Megnezzuk a 2 es a 21 legnagyobbkozos osztojat. Mivel relatıv prımek, ezert a legnagyobb kozos osztojukaz 1. Tehat futtatjuk az 5. lepest.

5. Ebben a lepesben a kvantumszamıtogep kiszamolja a rendjet 2-nek 21modulus mellett. Ezt hagyomanyos szamıtogeppel jelenleg nem tudjukpolinomialis idoben megtenni, ezert fontos itt a kvantumszamıtogephasznalata. A rendmeghatarozo algoritmust kesobb taglaljuk, es apeldaval be is mutatjuk a mukodeset. A 2 rendje 6 lesz 21 modulusmellett.

6. Mivel a rend a 6 paros, ıgy megnezhetjuk 21 es a 262 −1 = 7 legnagyobb

kozos osztojat, ami a 7. Illetve megnezhetjuk a 21 es 262 + 1 = 9

legnagyobb kozos osztojat, ami a 3. Ilyen modon a 21-et faktorizaltuk21 = 7× 3. Az algoritmus befejezodik.

Megjegyezzuk, hogy a 3 es a 7 a prımtesztelesnel kiderul, hogy prımek,es ıgy ott az egesz algoritmus is megall.

A 2 valasztasa szerencses volt, mivel ezzel sikerul felbontani a 21-et. Egykis szamolassal kijon, hogy mely szamok azok amelyekkel felbomlik a 21.Ezek a szamok a 2, 3, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 18, 19. Ami tehatrossz valasztas lett volna az a 4, 16, 17, 20. Tehat a 19 szambol osszesen 4rossz volt, ıgy 4

5esellyel jot valasztottunk.

10

3 Kvantumszamıtogepek bevezetese

A kvantumszamıtogepek elonye abbol szarmazik, hogy adott meretu inputa meretehez kepest exponencialis informaciot hordoz. De ezek a mereseknelcsak bizonyos valoszınusegekkel kaphatoak meg.

3.1 A kvantum bit

A kvantumszamıtogep egy bitje alapesetben |0〉 vagy |1〉 lehet. Viszontszuperpozıcioban levo kvantumbit bizonyos valoszınusegekkel mindketerteket felveheti. Altalanos esetben a kvantumbitet egy C2 komplexeuklideszi ter egy egysegvektoraval modellezhetjuk, ıgy egy q kvantumbit,vagy mas neven qubit felırhato q = a|0〉 + b|1〉 alakban, ahol a, b ∈ C, es|a|2 + |b|2 = 1. Ez azt jelenti, hogy a kvantumbit meresekor |0〉-t kapunk |a|2es |1〉-et kapunk |b|2 valoszınuseggel.

Hasonloan mukodik tobb bitre is, ıgy peldaul egy szuperpozıcioban levoket kvantumbitbol allo rendszert a kovetkezokeppen ırhatunk le: a|00〉 +b|01〉 + c|10〉 + d|11〉, ahol a, b, c, d ∈ C, |a|2 + |b|2 + |c|2 + |d|2 = 1. Ekkorannak a valoszınusege, hogy |00〉-t, |01〉-t, |10〉-t, |11〉-t merunk, rendre |a|2,|b|2, |c|2, |d|2.

Altalanosabban, egy n kvantumbites rendszer modellje egy ϕ :

{0, 1, . . . , 2n−1} 7→ C2 hullamfuggveny, ahol ϕ =∑2n−1

i=0 ai|i〉, es∑2n−1

i=0 |ai|2 =1, |i〉 jelentse az i kettes szamrendszerbeli alakja altal meghatarozott n-bitesbazisvektort.

Masreszrol ezt a ϕ-t tekinthetjuk a C2n euklideszi ter egy egysegvektoranakis. Ekkor a hagyomanyos modon jelolve a bazisvektorokat, bizonyosszempontbol konnyebben kezelheto modellt kapunk. Ezek a 2n dimenziosstandard bazisvektorok.

|j〉 =

0...010...0

, ahol csak a j-edik tag 1, a tobbi 0. Vagyis peldaul egy bit

11

eseten |0〉 =

(10

), es |1〉 =

(01

).

Ekkor pedig∑2n−1

i=0 ai|i〉 =∑2n−1

i=0

0...0ai0...0

.

3.2 A kvantum szamıtasok

A kvantumszamıtogepek a kvantum regisztert modosıtva jutnak el azinputbol az outputig. A kvantumszamıtogep minden lepesben csakuniter transzformaciokat tud alkalmazni a kvantumregiszterre, mivel akvantumszamıtogep minden allapotaban csak egysegvektort tud tarolni, esıgy az input es az output is csak egysegvektor lehet. Tehat csak olyantranszformaciokat tudunk elvegezni, ami egysegvektorbol egysegvektorbakepez, vagyis uniter transzformaciokat. Ekkor U(ϕ0) = ϕ1, ahol U unitertranszformacio, ϕ0 pedig az input, es ıgy transzformaciot kovetoen a kapottϕ1 is egysegvektor lesz, tehat teljesıti a kvantum regiszterre vonatkozotulajdonsagokat.

Masreszrol feltetelezzuk, hogy a kvantumszamıtogepek csak konstansnagysagu matrixszal leırhato transzformaciot tudnak kezelni, illetve ıgy azoktenzorszorzatait. Ezzel a feltetelezessel a szamıtogep gyakorlatban valoelkeszıtesenek kriteriumait, es ıgy magat az elkeszıtest is egyszerusıthetjuk.

3.3 Tenzorszorzat

Legyen v =

v1v2...vn

, w =

w1

w2...wm

, ekkor a tenzorszorzatuk v ⊗ w =

v1w1

v1w2...

v2w1...

.

12

Peldaul legyen v =

011

, w =

(10

), ıgy a tenzorszorzatuk v ⊗ w =

001010

lesz.

Legyen V egy n, W pedig egy m dimenzios vektorter. Ekkor V ⊗ Wtenzorszorzat egy nm dimenzios vektorter lesz, melynek elemei a v ⊗ wvektorok linearis kombinacioi, ahol v ∈ V , w ∈ W . Emellett v1, v2 ∈ V ,w1, w2 ∈ W , es z ∈ C teljesıti a kovetkezoket:

1. z(|v1〉 ⊗ |w1〉) = (z|v1〉)⊗ |w1〉 = |v1〉 ⊗ (z|w1〉)

2. (v1+v2)⊗(w1+w2) = v1⊗(w1+w2)+v2⊗(w1+w2) =∑2

i=1

∑2j=1 vi⊗wj

Megjegyezzuk, hogy a tenzorszorzas nem kommutatıv. Linearis operatorokraa kovetkezokeppen definialjuk:

Legyen A, B linearis operator rendre V -n, illetve W -n ertelmezve. Ekkoraz A ⊗ B linearis operator V ⊗W -n. Az A ⊗ B-t reprezentalo matrixot akovetkezo kepen szamıthatjuk ki:

A⊗B =

a1,1B a1,2B · · · a1,nBa2,1B a2,2B · · · a2,nB

......

. . ....

am,1B am,2B · · · am,nB

.

Itt A egy n×n-es, B pedig egy m×m-es matrix, amik reprezentaljak rendreA, illetve B azonos betukkel jelolt linearis operatorokat. Igy a keletkezoA⊗B matrix nm× nm-es lesz.

Peldaul legyen A =

(0 11 0

), B =

1 0 00 1 00 0 1

,

ekkor az A⊗B a kovetkezo lesz:

A⊗B =

0 0 0 1 0 00 0 0 0 1 00 0 0 0 0 11 0 0 0 0 00 1 0 0 0 00 0 1 0 0 0

.

13

Uniter transzformaciok tenzorszorzata is uniter transzformacio. Igy unitertranszformaciok tenzorszorzatat is alkalmazhatjuk a kvantum regiszterre.Ezzel elerheto, hogy csak a j-edik bitjet modosıtsuk a regiszternek Ij−1×j−1⊗Uj ⊗ In−j×n−j, ahol I az identitas.

3.4 A kvantum kapuk

Elsokent az egy qubites kapukat nezzuk. Ebbol az identitas utan a

legalapvetobb a

[0 11 0

], ez a NOT kapu. Termeszetes modon a NOT kaput

ugy definialnank, hogy NOT |0〉 = |1〉, es NOT |1〉 = |0〉. Ez teljesul is.

Tekintsuk a bazisvektoros modellt, ekkor |0〉 =

[10

], |1〉 =

[01

]. Igy

NOT

[10

]=

[0 11 0

] [10

]=

[01

]NOT

[01

]=

[0 11 0

] [10

]=

[10

]A Hadamar kapunak hasonloan fontos a szerepe. Ennek egy q-bitre a

matrixa H = 1√2

[1 11 −1

]. Itt

H

[10

]=

1√2

[1 11 −1

] [10

]=

1√2

[11

]

H

[01

]=

1√2

[1 11 −1

] [01

]=

1√2

[1−1

]Vagyis H|0〉 = |0〉+|1〉√

2, H|1〉 = |0〉−|1〉√

2.

Ennek az onmagaval valo tenzorszorzatait veve hasonlo alakra jutunk a|0 . . . 0〉 inputra:

H⊗2|0〉|0〉 = (H ⊗H)(|0〉 ⊗ |0〉) = H|0〉 ⊗H|0〉 =|0〉+ |1〉√

2⊗ |0〉+ |1〉√

2

=1

2(|0〉|0〉+ |0〉|1〉+ |1〉|0〉+ |1〉|1〉) =

1

2(|0〉+ |1〉+ |2〉+ |3〉)

14

H⊗n|0 . . . 0〉 = (H|0〉)⊗n = (|0〉+ |1〉√

2)⊗n =

1√2n

2n−1∑i=0

|i〉

Masik fontos 2-qubites kapu a CNOT kapu. Itt az egyik a kontroll qubittolfuggoen valtozik meg a masik a cel qubit. Hasonloan mukodik mint a NOTkapu, csak az inputja a kontroll qubit lesz, mıg a cel qubitet modosıtja. Tehatha a kontroll qubit 0, nem tortenik semmi, viszont ha a kontroll qubit 1, a celqubit erteket megvaltoztatja. Peldaban bemutatjuk 2-qubites rendszerben akapu mukodeset. Tobb qubites rendszerben az identitasokkal tenzorszorozvaa 2-qubites CNOT kaput megkaphatunk barmely CNOT kaput, melynekkontroll es cel qubitje rendszer tetszoleges ket bitjen hat.

Ekkor tehat a CNOT |0〉|1〉 = |0〉|1〉, es a CNOT |0〉|0〉 = |0〉|0〉, viszontCNOT |1〉|0〉 = |1〉|1〉, es CNOT |1〉|1〉 = |1〉|0〉. Vagyis a CNOT kaputmodellezo matrixot a kovetkezokeppen ırhatjuk fel:

1 0 0 00 1 0 00 0 0 10 0 1 0

, mivel |00〉 =

1000

, |01〉 =

0100

, |10〉 =

0010

, |11〉 =

0001

,

ıgy tehat a CNOT kapu hatasa a bazisvektorokra ilyen modon szamolhato:

CNOT

1000

=

1 0 0 00 1 0 00 0 0 10 0 1 0

1000

=

1000

,

CNOT

0100

=

1 0 0 00 1 0 00 0 0 10 0 1 0

0100

=

0100

,

CNOT

0010

=

1 0 0 00 1 0 00 0 0 10 0 1 0

0010

=

0001

,

CNOT

0001

=

1 0 0 00 1 0 00 0 0 10 0 1 0

0001

=

0010

15

3.5 Hagyomanyos szamıtogepek szimulalasakvantumszamıtogepen

Ebben az alfejezetben azt targyaljuk, hogyan lehet kvantumszamıtogeppelugyanazokat a szamıtasokat elvegezni, mint hagyomanyos szamıtogepen.Ezzel arra is ramutatunk, hogy a kvantumszamıtogepekkel sokkal bovebbeszkoztar van a kezunkben, mint a hagyomanyos esetben.

A hagyomanyos szamıtogep processzora logikai kapukat hasznal aszamıtasok elvegzesehez. Alapvetoen harom logikai kapurol szoktunk beszelniaz AND, az OR, es a NOT . Azert eleg ezeket a kapukat hasznalni, mert ezeklogikailag teljes rendszert alkotnak, vagyis az AND, OR, NOT segıtsegevelbarmilyen f : {i, h}n 7→ {i, h} logikai fuggveny leırhato. Itt az OR es azAND kozul eleg csak az egyik kaput megcsinalni, mert azzal szimulalhato amasik is.

Tehat, ha a kvantumszamıtogeppel szimulalni szeretnenk egy hagyomanyosszamıtogepet, akkor eleg a NOT es az AND vagy az OR kapukatmegcsinalni. A problema alapvetoen az, hogy a kvantumszamıtogepbenlevo kapuk uniter transzformacioval leırhatoak, vagyis invertalhatoak is,de a logikai fuggvenyeknek legtobb esetben nincs egyertelmu inverze, ıgyazokat nem tudjuk uniter transzformaciokkal leırni. Ezt a problemat ugyoldjuk meg, hogy az outputunkban az input is benne lesz, a logikai muveleteredmenye mellett. Igy egyertelmu az inverze az outputnak, es ezt marmeg tudjuk csinalni uniter transzformacioval. Masreszrol az outputnak csakazt a reszet vesszuk figyelembe, ami a logikai muvelet vegeredmenye, es ıgyszimulalni tudjuk a hagyomanyos szamıtogepeket.

A NOT kapu szerencsesen hagyomanyos ertelemben is azt a muveletetvegzi el, amit a kvantum NOT kapu csinal, ahogy ezt a kapu bevezetesekoris megjegyeztuk. Igy eleg csak az AND vagy az OR kapu valamelyiketszimulalnunk.

Ezekhez a logikai muveletekhez bevezetjuk a Fredkin es Toffoli kapukat.Mindket kapunak 3-qubites az inputja es az outputja is. A Toffoli kapuoutputja csak akkor kulonbozik az inputtol, ha az elso ket inputbit 1-es, esekkor az output 3. bitje megvaltozik. A Fredkin kapu az input utolso ketbitjet felcsereli, ha az input elso bitje 0, es nem valtoztat semmit, ha azinput elso bitje 1-es.

16

Toffoli kapu Fredkin kapuinput output input output

0 0 0 0 0 0 0 0 0 0 0 00 0 1 0 0 1 0 0 1 0 1 00 1 0 0 1 0 0 1 0 0 0 10 1 1 0 1 1 0 1 1 0 1 11 0 0 1 0 0 1 0 0 1 0 01 0 1 1 0 1 1 0 1 1 0 11 1 0 1 1 1 1 1 0 1 1 01 1 1 1 1 0 1 1 1 1 1 1

Ekkor a Toffoli kapunal a harmadik inputbitet 1-re allıtva, es azoutputban kapott utolso bitet negalva, vagyis alkalmazva ra a NOT kaput,ugyanazt kapjuk, mintha az elso ket inputbitre alkalmaznank az ANDmuveletet. Hasonloan, ha a Fredkin kapunal az utolso inputbitet 0-ra allıtjuk,akkor az output masodik bitjenek erteke ugyan az, mint amit az elso ketinputbitre alkalmazott AND muvelet ad.

Tehat ıgy tudjuk kvantumszamıtogeppel szimulalni az AND kaput is, esa NOT kaput, amit az elozo fejezetben reszleteztunk. Ezek pedig logikailagteljes rendszert alkotnak, tehat a szamıtogepre ırt minden algoritmustkvantumszamıtogepen tudunk szimulalni.

3.6 Fourier-transzformacio kvantumszamıtogepekkel

A Fourier-transzformacionak eleg nagy szerepe van a kvantumalgoritmusokban.A Shor-algoritmusban is a leglenyegesebb lepesben is a Fourier-transzformaciotalkalmazzuk, aminek koszonhetoen adott szam rendjet kvantumpolinomialisidoben meg tudjuk hatarozni.

A Diszkret Fourier-transzformacio hagyomanyos definıcioja alapjan egy|j〉 bazisvektor transzformaltjat a kovetkezokeppen definialjuk:

DFT (|j〉) =1√N

N−1∑k=0

e2πijkN |k〉

A kovetkezokben a transzformalt alakot szeretnenk kiszamolni kvantumszamıtogeppel.Ehhez a szummat alakıtjuk at egy konnyebben kezelheto alakra, ahol aszummaban szereplo bazisvektorok kettes szamrendszerbeli alakja |k〉 =|k1k2 . . . kn〉:

17

DFT (|j〉) = 1√N

∑N−1k=0 e

2πijkN |k〉

DFT (|j〉) = 1√2n

∑1k1=0

∑1k2=0 · · ·

∑1kn=0 e

2πij∑nl=1

kl2l |k1〉⊗ |k2〉⊗ · · ·⊗ |kn〉

DFT (|j〉) = 1√2n

∑1k1=0

∑1k2=0 · · ·

∑1kn=0

⊗nl=1

(e2πij

kl2l |kl〉

)DFT (|j〉) = 1√

2n

⊗nl=1

∑1kl=0

(e2πij

kl2l |kl〉

)DFT (|j〉) = 1√

2n

⊗nl=1

(|0〉+ e

2πij

2l |1〉)

DFT (|j〉) =(|0〉+e

2πij2 |1〉√2

)⊗(|0〉+e

2πij

22 |1〉√2

)⊗ · · · ⊗

(|0〉+e

2πij2n |1〉√2

)Tehat peldaul ket qubit eseten a bazisvektorok diszkret fourier

transzformaltja a kovetkezo keppen nez ki:

DFT (|00〉) =(|0〉+|1〉√

2

)⊗ ( |0〉+|1〉√

2

)DFT (|01〉) =

(|0〉−|1〉√

2

)⊗ ( |0〉+i|1〉√

2

)DFT (|10〉) =

(|0〉+|1〉√

2

)⊗ ( |0〉−|1〉√

2

)DFT (|11〉) =

(|0〉−|1〉√

2

)⊗ ( |0〉−i|1〉√

2

)Igy egy bazisvektorra ki tudjuk szamolni n kaput alkalmazva, de mivel 2n

darab bazisvektorunk van, es mindre ki kell szamolni, ıgy ez exponencialisidoben menne csak. Ezert csinalunk egy olyan algoritmust, ami altalanosinput bazisvektorra annak a fourier transzformaltjat adja ki outputnak.

Elsokent a fent levezetett n tagu tenzorszorzat l-edik tagjat szamoljuk ki,

(|0〉+e

2πij

2l |1〉√2

)=(|0〉+e

2πi

∑nk=1 jk2

n−k

2l |1〉√2

)=(|0〉+e

2πi∑k=nk=l

jk2k−l+1 |1〉√

2

)Ehhez bevezetunk ket uj kaput az Rk-t, es a CRk-t, amit a |jk+l−1〉 qubit

kontrollal. Ha jk+l−1 = 0 a CRk identitas lesz, es nem valtoztat semmit, hajk+l−1 = 1 a CRk = Rk.

Rk =

[1 0

0 e2πi1

2k

], CRk =

[1 0

0 e2πijk+l−1

2k

]

18

Ekkor nevezzuk PRm-nek azt a modult, amelyben sorban alkalmazzuk aCRm-tol a CR1-ig a kapukat.

PRn+1−l = CRn+1−lCRn−l . . . CR1

PRn+1−l =∏1

k=n+1−l

[1 0

0 exp(

2πi jk+l−1

2k

)]

PRn+1−l =

[1 0

0 exp(

2πi(

jn2n−l+1

+ jn−1

2n−l + · · ·+ jl2

))]

PRn+1−l =

[1 0

0 exp(

2πi(

j2n−l+1

))]Legyen |+〉 = 1√

2(|0〉+ |1〉), ekkor az Hadamard kapu definıcioja miatt

H|jl〉 = |0〉+e2πijl2 |1〉√

2= CR1|+〉.

Ekkor pedig PRn+1−l|+〉 = |0〉+e2πi

j

2n−l+1 |1〉√2

. Ezzel eloallıtottuk atenzrszorzat n + 1 − l-edik tagjat, ıgy az l megfelelo valasztasaval a fentitenzorszorzat minden tagjat elo tudjuk allıtani.

Figyelnunk kell arra, hogy ne modosıtsuk azokat a biteket, amelyekkesobbi lepesben meg kontrollalo bitkent szerepelnek. Ezert az utolso bitetmodosıto modult kell elsonek alkalmazni a PRn-et. Itt meg az n-edik bit iskontrollalo bitkent szerepel, de kesobbi PRk-kra mar nincs hatassal. Majdsorban alkalmazzuk a modulokat n-tol egeszen 1-ig, ahol PR1-nel mar csakaz elso bitnek van kontrollalo szerepe.

Viszont azzal, hogy visszafele alkalmaztuk a kapukat, sajnos a bitsorrendis megfordul. Ahhoz, hogy a Fourier transzformaltat kapjuk, vagy fordıtottsorrendben olvassuk az outputot, vagy kell egy algoritmus, amely megfordıtjaa bitek sorrendjet. Ehhez elsokent mutatunk egy modult, amely kepes ketbitet felcserelni, majd ezutan ezt alkalmazzuk az elso es az n-edik bitre, majda masodik es (n− 1)-edik bitre, es ıgy tovabb, amıg vegul az bn

2c-edik es az

(n + 1− bn2c)− edik bitre is alkalmaztuk. Igy tehat mar a biteket fordıtott

sorrendben kapjuk.A kerdes most tehat, hogy hogyan lehet az l-edik es a k-adik biteket

felcserelni. Ehhez hasznaljuk fel a CNOT kaput. A modul harom lepesbolall. Elsokent az l-edik bit legyen a kontroll bit, es a k-adik a cel bit, masodiklepeskent a k-adik legyen a kontroll, es az l-edik a cel bit, vegul pedig megintlegyen az l-edik a kontroll es a k-adik a cel bit.

19

Ezt alkalmazva a |0〉 es |0〉 bitekre a kontroll bit 0 volta miatt a masodikbit erteke nem valtozik, es mindharom lepesben ez tortenik, ıgy vegul a |0〉es |0〉 biteket kapjuk outputkent. Ha |1〉 es |0〉 az input, az elso lepesben amasodik bit megvaltozik es |1〉 es |1〉 biteket kapjuk, a masodik lepesben azelso bit valtozik meg, ıgy |0〉 es |1〉-et kapunk, es vegul a harmadik lepesbennem modosul az ertek ıgy ez lesz az output is. Ha |0〉 es |1〉 az input, az elsolepesben nem valtozik az ertekuk, a masodik lepesben az elso bit megvaltozikes ıgy |1〉 es |1〉 lesz, vegul a harmadik lepesben modosul a masodik bit, esıgy az output |1〉 es |0〉 lesz. Az utolso eset pedig, ha |1〉 es |1〉 a ket bit.Ekkor az elso lepesben a masodik bit modosul, majd a kovetkezoben az elsobit nem modosul, es vegul a harmadik bit megint megvaltozik, es ıgy megint|1〉 es |1〉 lesznek az output bitek. Tehat minden esetben az input fordıtottjaaz output, ıgy ez a modul tenyleg felcsereli a ket bitet.

Tehat a Fourier transzformaltat megkaphatjuk a fenti modon megfordıtvaa PRk modulokat alkalmazo fenti algoritmus eredeti outputjat.

A fenti algoritmusban szereplo PRk-k maximum n darab kaputhasznalnak, es ıgy az adott kapuk segıtsegevel O(n2) idoben ki tudjukszamolni tetszoleges bazisvektor transzformaltjat. A kvantumparhuzamossagmiatt, ezt tetszoleges inputra alkalmazva, kvantumpolinomialisan megkaphatjukannak Fourier transzformaltjat.

20

4 Kvantum algoritmus a rend meghatarozasara

4.1 Az input kezelese, es regiszterek beallıtasa

Adott N szam faktorizalasanak problemajat redukaltuk egy veletlen m szamrendjenek meghatarozasara. Ezen problema megoldasahoz hasznaljuk akvantumszamıtogepet. Legyen t az a szam, melyre N2 ≤ 2t < 2N2, es npedig olyan, hogy n = dlog2Ne. Tovabba legyen a keresett ONm = P .

Elso lepeskent ket kezdeti allapotban levo kvantum regisztert inicializalunk.Az elsot t a masodikat n qubitesnek definialjuk. Ezeken futtatjuk a kvantumalgoritmust, es az algoritmus outputja ezeken a regisztereken mert ertek lesz.A kvantumszamıtogep allapotait ϕ-vel jeloljuk, ahol ϕk a k-adik lepes utaniallapot.

ϕ0 = |00 . . . 0〉|00 . . . 0〉

Ezt kovetoen alkalmazzuk a Hadamard kaput az elso regiszter mindenqubitjere. Ekkor azt kapjuk, hogy

ϕ1 =1√2t

2t−1∑j=0

|j〉|0〉.

Itt az elso regiszter szuperpozıcioba kerul azonos amplitudokkal,vagyis minden bazisvektort azonos valoszınuseggel kapnank meg meresieredmenykent, ha most mernenk meg az elso regisztert. A masodik regiszterekkor meg valtozatlan.

Legyen Vx az az uniter linearis operatort, amelyre

Vx(|j〉|k〉) = |j〉|k + xj〉.

Ezt alkalmazva a ket regiszterre a kovetkezot kapjuk:

Vx(ϕ1) = ϕ2 =1√2t

2t−1∑j=0

|j〉|xj〉.

Ezzel inicializaltuk es beallıtottuk a regisztereket, es innentol futtatjukaz algoritmus lenyegi reszet.

21

4.2 A rend adott fuggvenyenek meghatarozasa specialisesetben

A kezdeti beallıtas utan az elso regiszterben levo j-t bontsuk szet egyosszegre, amelynek egyik tagja P tobbszorose, a masik tagja pedig a maradek.Vagyis legyen a, b ∈ N, 0 ≤ b < P , es ekkor j = aP + b teljesuljon. Akovetkezokben P | 2t. Ebben a specialis esetben konnyen lathato, hogyhogyan egyszerusodik majd le a kifejezes, es a kesobbiekben reszletezzukmajd az altalanos esetet.

ϕ2 =1√2t

P−1∑b=0

( 2t

P−1∑

a=0

|aP + b〉

)|xb〉.

Ezutan az elso regiszterre alkalmazzuk a Fourier transzformaciot, majda belso kifejezest hatvanyazonossag szerint szorzatta alakıtjuk, hogy aszummabol majd kesobb kiemelhessuk a e2πijb-t:

ϕ3 =1√2t

P−1∑b=0

2t

P−1∑

a=0

(1√2t

2t−1∑k=0

e2πik(aP+b)

2t |k〉

)|xb〉,

ϕ3 =1

2t

P−1∑b=0

2t

P−1∑

a=0

(2t−1∑k=0

e2πikaP

2t e2πikb2t |k〉

)|xb〉.

A szummakat felcserelve, egy olyan alakot kapunk, ahol az adott xb

modulo N maradekok es az elso regiszterben szereplo j ertekekhez tartozoosszes egyutthatot osszegezzuk.

ϕ3 =1

2t

P−1∑b=0

2t−1∑k=0

( 2t

P−1∑

a=0

e2πikaP

2t e2πikb2t |k〉

)|xb〉.

ϕ3 =1

2t

P−1∑b=0

2t−1∑k=0

e2πikb2t

( 2t

P−1∑

a=0

e2πikaP

2t |k〉

)|xb〉.

ϕ3 =1

2t

P−1∑b=0

2t−1∑k=0

e2πikb2t

( 2t

P−1∑

a=0

exp(2πikP

2t

)a|k〉

)|xb〉.

A mertani sorozat osszegkepletebe∑n

i=1 qi = qn+1−1

q−1 , ahol q 6= 1

behelyettesıtve a q = exp(2πikP2t

)-t, ha a nevezo exp(2πikP2t

) − 1 6= 0,

22

akkor ertelmes lesz a keplet. Ekkor a szamlalo erteke exp(2πikP2t

)2t

P − 1 =

e2πikP

2t2t

P − 1 = exp(2πik)− 1 = 0, vagyis az egesz osszeg 0 lesz.

Most nezzuk meg mikor alkalmazhatjuk a fenti osszegkepletet. Azexp(2πikP

2t) − 1 6= 0 feltetel akkor teljesul, ha k 6= l 2

t

P, ahol l ∈ Z. Egyeb

esetben, amikor nem alkalmazhatjuk a fenti modszert k = l 2t

P. Ekkor

az osszegben szereplo tagok exp(2πiak P2t

) = exp(2πial 2t

PP2t

) = 1, vagyis

a szumma erteke ekkor 2t

P× 1 = 2t

P. Tehat ezen egyszerusıteseket, es

osszevonasokat elvegezve a merheto ertekek konnyebben atlathato alakjatkapjuk.

ϕ3 =1√P

P−1∑b=0

(e

2πijb

2t |l2t

P〉

)|xb〉.

4.3 A rend adott fuggvenyenek meghatarozasa altalanosesetben

Altalanos esetben is, hasonloan a fenti esethez, az elso regiszter eloszlasaspecialis. Vagyis |l 2t

P〉 ertekeket lenyegesen nagyobb valoszınuseggel merunk,

mint mas ertekeket. Megjegyezzuk, hogy altalanos esetben nullanalnagyobb valoszınuseggel merhetunk mas ertekeket is. A kovetkezokbenvegigszamoljuk altalanos esetet.

A jeloles egyszerusıtese erdekeben legyen 2t = Q, r legyen olyan, hogyr ≡ Q mod P , Q < P , es legyen Q0 = Q−r

P. Vagyis Q : P = Q0

P+ r egy

maradekos osztas. Valamint w = e2πi/2t

legyen.Ekkor a kovetkezo keppen ırhatjuk fel a ϕ3-at:

ϕ3 =1

Q

[ Q0P−1∑

a=0

P−1∑b=0

(Q−1∑k=0

wk(aP+b)|k〉

)|xb〉+

Q−1∑k=0

r−1∑b=0

wk(PQ0P

+b)|k〉 |xb〉

],

ϕ3 =1

Q

Q−1∑k=0

[ Q0P−1∑

a=0

P−1∑b=0

wk(aP+b)|k〉|xb〉+r−1∑b=0

wk(PQ0P

+b)|k〉 |xb〉

],

23

ϕ3 =1

Q

Q−1∑k=0

[P−1∑b=0

Q0P−1∑

a=0

wkaPwkb|k〉|xb〉+r−1∑b=0

wkPQ0P wkb|k〉 |xb〉

],

ϕ3 =1

Q

Q−1∑k=0

[P−1∑b=0

wkb

( Q0P−1∑

a=0

wkaP

)|k〉|xb〉+

r−1∑b=0

wkb

(wk

Q0PP

)|k〉 |xb〉

],

Ekkor a ket szummat osszevonhatjuk oly modon, hogy a kerekzarojelekben levoket egy szummaban ırjuk fel. Ezt azert tehetjuk meg mert a0-tol Q0

P− 1-ig megy, a masik feleben az osszegnek pedig Q0

Pvan. Ezt viszont

csak azon b-kre tehetjuk meg, amelyek szerepelnek mindket szummaban,vagyis csak r darabban.

ϕ3 =1

Q

Q−1∑k=0

[r−1∑b=0

wkb

( Q0P∑a=0

wkaP

)|k〉|xb〉+

P−1∑b=r

wkb

( Q0P−1∑

a=0

wkaP

)|k〉 |xb〉

].

A kerek zarojelben levo reszeket osszegezve, es leosztva Q-val megkapjukegy adott |k〉|xb〉 regiszter egyutthatojat. A fenti osszegzes abszoluterteket aszummak elejere kiemelt Q-val leosztva az egyutthato abszolutertek kapjuk,es ennek negyzete az adott bitsorozat meresenek valoszınusege. Az osszegzesta mertani sorozat osszegkepletenek segıtsegevel szamoljuk ki.

Ezt a kulonbozo b-kre osszegezve megkapjuk Prob(k)-t, amivel aztjeloljuk, hogy mekkora valoszınuseggel merunk az elso regiszterben k erteket.

Prob(k) =1

Q2

r−1∑b=0

∣∣∣∣∣Q0P∑a=0

wkaP

∣∣∣∣∣2

+1

Q2

P−1∑b=r

∣∣∣∣∣Q0P−1∑

a=0

wkaP

∣∣∣∣∣2

Prob(k) =r

Q2

∣∣∣∣∣Q0P∑a=0

wkaP

∣∣∣∣∣2

+P − rQ2

∣∣∣∣∣Q0P−1∑

a=0

wkaP

∣∣∣∣∣2

Prob(k) =r

Q2

∣∣∣∣∣wkP (Q0P

+1) − 1

wkP − 1

∣∣∣∣∣2

+P − rQ2

∣∣∣∣∣wkPQ0P − 1

wkP − 1

∣∣∣∣∣2

Prob(k) =r

Q2

∣∣∣∣∣e2πiQkP (

Q0P

+1) − 1

e2πiQkP − 1

∣∣∣∣∣2

+P − rQ2

∣∣∣∣∣e2πiQkP

Q0P − 1

e2πiQkP

− 1

∣∣∣∣∣2

24

Legyen {k}Q ≡ k mod Q, es −Q2< {k}Q ≤ Q

2. Vagyis {k}Q a legkisebb

abszoluterteku maradekat jeloli k-nak modulo Q-ra.A kovetkezokben megmutatjuk, hogy azon specialis esetek valoszınusege,

amikor∣∣∣π{kP}QQ

Q0

P

∣∣∣ < π2

az 1P

koruli ertek. Az egyenlotlenseget atrendezve a

kovetkezot kapjuk ∣∣∣π{kP}QQ

Q0

P

∣∣∣ =∣∣∣{kP}Q∣∣∣ 1

P

Q0

Qπ <

π

2∣∣∣{kP}Q∣∣∣ < P

2

Q

Q0

<P

2

Ezen specialis eseteket ket reszre kell bontanunk a mertani-sorozatosszegkepletere vonatkozo megkotes miatt, ıgy 0 < |{Pk}Q| ≤ P

2(1 − 1

N),

es {Pk}Q = 0 eseteket fogjuk elemezni, es ezek valoszınusegeit fogjuk mostkiszamolni. Elsokent egy-ket egyenloseget, es egyenlotlenseget emlıtunk meg,amelyek segıtsegevel fogjuk becsulni ezeket az ertekeket.

Q0

Q=Q− rQ

= 1− r

Q≥ 1− N

N2= 1− 1

N

Mivel Q = 2t-t ugy valasztottuk, hogy N2 ≤ 2t ≤ 2N2. Masreszt tudjuk,hogy ∣∣eiα − 1

∣∣2 =∣∣ cosα + i sinα− 1

∣∣2= (cosα− 1)2 + sin2 α

= cos2 α + sin2 α + 1− 2 cosα

= 2(

1− cos2α

2

)= 2

(1−

(1− 2 sin2 α

2

))= 4 sin2

(α

2

)

Ezek alapjan a fenti becslesben az abszolutertek negyzeteket a szinuszoskifejezesekre cserelve a kovetkezot kapjuk:

Prob(k) =r

Q2

sin2(

2π{kP}Q2Q

(Q0

P+ 1)

)sin2

(2π{kP}Q

2Q

) +P − rQ2

sin2(

2π{kP}Q2Q

Q0

P

)sin2

(2π2Q

)

25

Tovabba |α| < π2, eseten 4

π2α2 ≤ sin2 α ≤ α2, mivel 2

πα ≤ sinα ≤ α. Most

azon k-k valoszınuseget nezzuk, amikre∣∣∣π{kP}QQ

Q0

P

∣∣∣ < π2, itt felhasznalhatjuk

az egyenlotlenseget is.

Prob(k) ≥ r

Q2

4π2

(2π{kP}Q

2Q(Q0

P+ 1)

)2(

2π{kP}Q2Q

)2 +P − rQ2

4π2

(2π{kP}Q

2QQ0

P

)2(

2π{kP}Q2Q

)2

Prob(k) ≥r 4π2

(π{kP}Q

Q(Q0

P+ 1)

)2+ (P − r) 4

π2

(π{kP}Q

QQ0

P

)2Q2(π{kP}Q

)2Prob(k) ≥

r(

2{kP}QQ

(Q0

P+ 1)

)2+ (P − r)

(2{kP}QQ

Q0

P

)2(π{kP}Q

)2Prob(k) ≥ r

( 2

πQ

(Q0

P+ 1))2

+ (P − r)( 2

πQ

Q0

P

)2Prob(k) ≥ P

( 2

πQ

Q0

P

)2≥ 4

π2P

(Q0

Q

)2≥ 4

π2P

(1− 1

N

)2Most tekintsuk azokat a k ertekeket, amelyekre nem alkalmazhatjuk a

szummat egyszerusıto kepletet, mivel a kepletben szereplo nevezo nulla lenne,vagyis wkP = 1.

Prob(k) =r

Q2

∣∣∣∣∣Q0P∑a=0

wkaP

∣∣∣∣∣2

+P − rQ2

∣∣∣∣∣Q0P−1∑

a=0

wkaP

∣∣∣∣∣2

Prob(k) =r

Q2

∣∣∣∣∣Q0P∑a=0

1a

∣∣∣∣∣2

+P − rQ2

∣∣∣∣∣Q0P−1∑

a=0

1a

∣∣∣∣∣2

≥ Q20

PQ2

Fent belatott Q0

Q=≥ 1− 1

Nmiatt teljesul, hogy

Prob(k) ≥ Q20

PQ2≥ 1

P

(1− 1

N

)2

≥ 1

P

(1− 1

N2

)≥ 1

P

(1− 1

N

)

26

4.4 A rend meghatarozasa az outputbol leolvashatofuggvenyebol

Legyen most d olyan szam, ami kPQ

kerekıtett erteke, vagyis d ≈ kPQ

. Ekkor

|kP −Qd| = {Pk}Q ≤P

2

Amit tovabb ırhatunk ugy, hogy∣∣∣ kQ− d

P

∣∣∣ ≤ 1

2Q≤ 1

2N2≤ 1

2P 2

A kovetkezokben egy algoritmust mutatunk, amivel egy valos szamottudunk tetszolegesen megkozelıteni egy tortekbol allo sorozattal, amelytagoknak nevezoje es szamlaloja relatıv prımek. Ez az algoritmus a valosszamot atalakıtja lanctorte, es ugy adja meg a sorozat tagjait, hogy alanctort elso bizonyos szamu elemet veszi csak figyelembe, es az azok altalmeghatarozott tortet adja.

Az algoritmus lepesei soran minden olyan tort erteket felvesz, amelyreigaz, hogy

∣∣x − ab

∣∣ ≤ 12b2

. Vagyis a fent igazoltak alapjan az algoritmussegıtsegevel megkaphatjuk a P erteket, mint nevezot, ha relatıv prım d-hez.

Az alapgondolat az, hogy legyen egy a0, a1, a2 . . . sorozat, ahol a0 ≤ 0, es

x = a0 +1

a1 +1

a2 +1

a3 + . . .

(1)

Itt az x tetszoleges valos szam. Ekkor a0 = bxc, x0 = x−a0, es ha xn 6= 0,akkor an+1 =

⌊1xn

⌋, es xn+1 = 1

xn− an+1. Az an sorozat ezen definiciojaval

a fenti modon tetszolegesen megkozelıtheto az x erteke. Ha a sorozat elsonehany tagjara alkalmazzuk a fenti modszert, akkor egy racionalis szamotkapunk, amelyet felırhatunk pn

qnalakban, ahol pn es qn relatıv prımek.

Ugy adjuk meg ekkor ezt a ket szamot, hogy p0 = a0, p1 = a0a1 + 1,q0 = 1, q1 = a1, es pn = anpn−1 + pn−2, qn = anqn−1 + qn−2.

Tehat most ezen algoritmus segıtsegevel, ha P es d relatıv prımek, vegulkiszamolhato a rend, vagyis P .

Mivel tudjuk, hogy egy racionalis szamot alakıtunk lanctorte, ıgy tudjuk,hogy az algoritmus altal meghatarozott sorozat veges, es a sorozat elemszama

27

az input meretetol logaritmikusan fugg. Ekkor tehat a sorozatban szereplotagok nevezoinek valamelyike veszi fel P erteket, ıgy azokra ellenorizzuka rendre vonatkozo tulajdonsagot, vagyis, hogy mP ≡ 1 (mod N). Ahatvanyozast polinom idoben ki tudjuk szamolni, ezt pedig maximumannyiszor kell kiszamolni, ahany potencialis P van, es ezzel egyutt is polinomıdoben kiszamıthato.

Most mar csak azt kell ellenoriznunk, hogy P es d relatıv prımsegeneka valoszınusege egy konstanssal alulrol becsulheto. Ezt fogjuk becsulni akovetkezoben ugy, hogy k legyen az elso regiszterben mert ertek, d pediga fentebb leırt modon a k, Q es P -vel definialt ertek. Azon k ertekekbol,amelyek segıtsegevel tudunk szamolni, csak azok lesznek jok amik P -hezrelatıv prım d erteket adnak. Ez tovabb szukıti a jo meresek valoszınuseget.A d ertek altal felveheto P darab ertek kozul nekunk csak φ(P ) darab lesz

jo, es ezzel a jo meresek valoszınasege egy φ(P )P

-s szorzot kap.

Prob(k : (P, d) = 1) =4

π2

(1− 1

N

)2φ(P )

P

Bizonyos δ konstansokra megmutattak, hogy Prob(φ(P )P

)> δ

log logP. Ezt

felhasznalva tehat O(log logP ) idoben talalunk alkalmas d szamot.

Ezen d szam mellett megtalaljuk polinom idoben a m rendjet P -t, aminagy valoszınuseggel olyan lesz, hogy segıtsegevel mar N -t is szorzattatudjuk alakıtani. Egyeb esetben ujabb veletlen m szamot valasztunk, esarra futtatjuk az algoritmust. Igy tehat most mar polinom idoben tudjukfaktorizalni N -t kvantumszamıtogep segıtsegevel.

4.5 A rend meghatarozasa peldaszamıtassal

Elobbiekben egy peldan bemutattuk a Shor-algoritmus azon lepeseinekfutasat, amelyekhez nem szukseges kvantumszamıtogep. Most ezekkela szamokkal folytatjuk a peldat, es bemutatjuk, hogy mit csinal akvantumszamıtogep ezen inputokon.

A fentebb bemutatott peldaban N = 21-et valasztottuk, es hozzaveletlenszeruen a 2-t mint a 21-hez relatıv prımszam. Mivel N2 = 441,ezert N2 = 441 ≤ 2t = 512 = 29 < 2N2 = 882, vagyis t = 9.

Kezdeti allapotban mindket regiszter 0-n all.

ϕ0 = |00 . . . 0〉|00 . . . 0〉

28

Majd az elso regisztert a hadamard kapu segıtsegevel szetbontjuk egyenloegyutthatoju reszekre

ϕ1 =1√512

∑j=0

511|j〉|0〉

Ezutan a Vx operatort alkalmazzuk, es ıgy a masodik regiszterben a 2 azonhatvanyait kapjuk modulo 21, amelyek hatvanya az elso regiszterben levoertek.

ϕ2 =1√512

(|0〉|1〉+ |1〉|2〉+ |2〉|4〉+ |3〉|8〉+ |4〉|16〉+ |5〉|11〉+

|6〉|1〉+ |7〉|2〉+ |8〉|4〉+ |9〉|8〉+ |10〉|16〉+ |11〉|11〉+

|12〉|1〉+ · · ·+ |511〉|2〉)

Ezutan atcsoportosıtottuk a szummat a masodik regiszter szerint.

ϕ2 =1√512

[(|0〉+ |6〉+ |12〉+ · · ·+ |504〉+ |510〉)|1〉+

(|1〉+ |7〉+ |13〉+ · · ·+ |505〉+ |511〉)|2〉+

(|2〉+ |8〉+ |14〉+ · · ·+ |506〉)|4〉+

(|3〉+ |9〉+ |15〉+ · · ·+ |507〉)|8〉+

(|4〉+ |10〉+ |16〉+ · · ·+ |508〉)|16〉+

(|5〉+ |11〉+ |17〉+ · · ·+ |509〉)|11〉]

A mert veletlen ertek a masodik regiszterben legyen a 2, ezen mutattukbe a szamolasokat az elozo peldanal is. Ekkor nezzuk csak azokat a lehetsegesallapotokat, ahol a masodik regiszter 2, es ezekre megszorıtva vizsgaljuka tovabbi lepeseket. Itt a megszorıtas lenyegeben annyit jelent, hogy aszumma tobbi tagjat nem ırjuk le, ıgy egyszerusıtve a lepesek leırasat, esmivel felteteleztuk, hogy 2 lesz az ertek, amit merunk, ıgy a szumma tobbitagja nem is lenyeges az algoritmus szempontjabol.

ϕ2 =1√86

(|1〉+ |7〉+ |13〉+ · · ·+ |505〉+ |511〉)|2〉

Erre alkalmazzuk most a Diszkret Fourier-transzformaciot:

DFT (ϕ2) = ϕ3 = DFT

(1√86

85∑a=0

|6a+ 1〉)|2〉

29

ϕ3 =1√512

511∑j=0

([1√86

85∑a=0

e2πi6ja512

]e2πi

j512 |j〉

)|2〉

Most tekintsuk az elso regiszter meresenek lehetoseget. Ez mar a rendmeghatarozasa szempontjabol sokkal nagyobb szerepet jatszik, a masodikregiszterben mert ertek lenyegeben nem fontos. Az elso regiszterben merhetoertekek valoszınusege:

Prob(j) =1

512× 86

∣∣∣∣∣85∑a=0

e2πi6ja512

∣∣∣∣∣2

Itt a legtobb ertek kozel 0 valoszınuseggel merheto, de a 0, 85, 171, 256,341, 427 ertekeket nagy valoszınuseggel merhetjuk. Ezekbol, ha 0-t merunk,akkor ujra kell futtatni az algoritmust es uj merest kell vegeznunk. Mosttegyuk fel, hogy a 85 erteket merjuk.

Prob(85) =1

512× 86

∣∣∣∣∣85∑a=0

e2πi6×85×a

512

∣∣∣∣∣2

≈ 0, 1142

Ezutan a 85512

-hez tartozo lanctort segıtsegevel probaljuk megkeresni a rendet.

85

512=

1

6 +1

42 +1

2

(2)

Tehat, ezzel a modszerrel kapott konvergens sorozat tagjai, amelynek tagjaiolyan racionalis szamok, amelyeknek a nevezoje es szamlaloja relatıv prımek,a kovetkezoek: 1

6, 42253, 85512

. Ezek alapjan az elso tagra ellenorizzuk le elsokent,hogy teljesıti-e a feltetelt. Ha erre nem lenne igaz, akkor a kovetkezo tagrais ellenorizzuk, es ıgy tovabb. Az elso tag alapjan P = 6, vagyis 26 ≡ 1(mod 21) kongruenciat kell ellenoriznunk, ez pedig teljesul, vagyis a rend 6.

Irodalomjegyzek

[1] Peter W. Shor, ”Polynomial-Time Algorithms for Prime Factorization andDiscrete Logarithms on a Quantum Computer”, Proceedings of the 35th AnnualSymposiump on Foundations of Computer Science, Santa Fe (1994)

30

[2] SAMUEL J. LOMONACO, JR., ”A LECTURE ON SHOR’S QUANTUMFACTORING ALGORITHM VERSION 1.1” (2000)

[3] C. Lavor, L.R.U. Manssur, and R. Portugal, ”Shor’s Algorithm for Factoring LargeIntegers” (2008)

31