Èeské vysoké uèení te hni ké v PrazeFakulta jaderná a fyzikálnì in¾enýrská

BAKALÁØSKÁ PRÁCEQuantum Algorithms

2007 Vá lav Potoèek

PodìkováníRád by h tímto podìkoval vedou ímu bakaláøské prá e, panu prof. Ing. Igoru Jexovi, DrS .,nejen za podnìtné konzulta e a ve¹kerou podporu pøi tvorbì této prá e, ale pøedev¹ím za umo¾-nìní okam¾itého a bezproblémového pøístupu k nejvýznamnìj¹ím aktuálním kni¾ním titulùmk tématu prá e i tématùm souvisejí ím a k dùle¾itým èlánkùm.

Název prá e:Kvantové algoritmyAutor: Vá lav PotoèekObor: Matemati ké in¾enýrstvíZamìøení: Matemati ká fyzikaDruh prá e: Bakaláøská prá eVedou í prá e: Prof. Ing. Igor Jex, DrS ., KF, FJFI, ÈVUTAbstrakt: Tato prá e seznamuje ètenáøe se základy problematiky kvantový h algoritmù. Spí¹ene¾ na detailní popisy jednotlivý h známý h algoritmù je kladen dùraz na vysvìtlení elkovépodstaty problematiky a vztahu kvantový h algoritmù s jeji h klasi kými protìj¹ky.Klíèová slova: kvantové algoritmy, prohledávání databáze, Groverùv algoritmus, kvantové ná-hodné pro házeníTitle:Quantum algorithmsAuthor: Vá lav PotoèekAbstra t: This thesis shows basi s of quantum algorithm topi s. Its purpose is not to des ribe indetail every single known algorithm of some importan e. More likely, emphasis is put in explainingthe main on epts and relations of quantum algorithms to their lassi al ounterparts.Key words: quantum algorithms, database sear h, Grover's algorithm, quantum random walks

ObsahÚvod . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11. Základy kvantové me haniky . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21.1 Postuláty kvantové me haniky . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21.2 Kvantové mìøení . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41.3 Dira ùv formalismus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81.4 Koneènìdimenzionální prostory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 91.5 Provázané stavy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 111.6 Paradox EPR . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121.7 Mati e hustoty . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141.8 Redukovaná mati e hustoty . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 182. Kvantová me hanika a zpra ování informa e . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 202.1 Dvoudimenzionální prostory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 202.2 Pauliho mati e . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 222.3 Kvantová hradla . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 232.4 Univerzální mno¾ina hradel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 282.5 Simula e klasi ký h obvodù kvantovými hradly . . . . . . . . . . . . . . . . . . . . . . . . . . . 283. Kvantové algoritmy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 323.1 Kvantová teleporta e . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 323.2 Shorùv algoritmus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 343.3 Kvantová Fourierova transforma e . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 363.4 Fourierova transforma e ve Shorovì algoritmu . . . . . . . . . . . . . . . . . . . . . . . . . . . . 384. Groverùv algoritmus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 404.1 Zadání vyhledáva ího algoritmu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 404.2 Popis Groverova algoritmu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 414.3 Groverùv algoritmus v krajní h pøípade h . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 444.4 Varia e Groverova algoritmu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 454.5 Realiza e hradel v Groverovì algoritmu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 464.6 Vztah Groverova algoritmu a problému nerozli¹itelnosti neortogonální h stavù . . . 485. Prohledávání, sítì a náhodné hození . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 495.1 Náhodné pro házení . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 495.2 Kvantové náhodné pro házení . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 505.3 Vyhledávání na hyperkry hli . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 535.4 Dal¹í vlastnosti prohledávání na hyperkry hli . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 585.5 Podobné vyhledáva í algoritmy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 605.6 Pro házení na obe ný h grafe h, opti ké sítì . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60Závìr . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 64Pøílohy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65A.1 Program grover . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 66A.2 Program qrw-line . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67A.3 Program qrw- ube . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68Pou¾itá literatura . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70Prohlá¹ení . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72

ÚvodTato prá e si klade za íl podat úvod do elkem nové a nadìjné oblasti kvantové fyziky,kvantový h algoritmù. Kvantové algoritmy jsou obdobou klasi ký h algoritmù, realizovaný hv elektroni ký h výpoèetní h jednotká h { zaøízení, které realizuje kvantový algoritmus, se tedynazývá kvantový poèítaè. Pøes tento honosný název v¹ak v dobì uvedení prá e ve¹keré pokusy, aèprokazují í pravdivost teoreti ký h závìrù, probíhají pouze v mìøítku laboratorní h experimentù.Od ètenáøe se oèekává znalost lineární algebry na úrovni prvního roèníku vysoké ¹koly,v rozsahu [1℄. V nìkterý h míste h budeme pou¾ívat i pokroèilej¹í partie lineární algebry, uvedenénapø. v [2℄, jmenovitì Hilbertùv prostor, tenzorový souèin a stopu lineárního operátoru, pouzev¹ak pro prostory koneèné dimenze, kde bývají tyto pojmy také souèástí sylabu v první h lete hstudia matematiky. Znalost základù kvantové me haniky je výhodou, ale èásti potøebné propo hopení tématu budou shrnuty v první kapitole.V ní jsou uvedeny postuláty kvantové me haniky v obe ném tvaru a pozdìji zú¾ené dojednodu¹¹ího, koneènìdimenzionálního znìní, ve kterém budou plnì postaèují ími pro vìt¹inunásledují ího textu. Dále je uvedeno nìkolik dal¹í h termínù a prin ipù, které mají v teoriikvantový h algoritmù pøímé vyu¾ití.Druhá kapitola je ji¾ zamìøena na vyu¾ití kvantové me haniky pro nalezení blízké analogielogi ký h obvodù. Nejprve se uká¾e zobe nìní bitu na kvantový bit, qubit, zavedeme prin ipkvantový h hradel jako obdoby klasi ký h digitální h hradel, a uká¾eme, jak pøes jisté odli¹nostijsme s hopni pomo í tì hto nástrojù simulovat libovolný digitální obvod.Ve tøetí kapitole uká¾eme na nìkolika nejznámìj¹í h pøíklade h mo¾nosti, které poskytujeidea kvantový h algoritmù jako výhody oproti klasi kým algoritmùm. Tato kapitola je v¹akuva¾ována pouze jako struèný náhled do problematiky, která je jako elek ji¾ natolik rozsáhlá,¾e tato prá e se vìnuje detailnìji jen jedné její úzké èásti.Touto èástí jsou vyhledáva í algoritmy, jeji h¾ základní my¹lenky jsou popsány ve ètvrtékapitole. Detailnì je pak probrán první vyhledáva í algoritmus, jeho¾ autorem je Lov Grovera který vedle kvantové faktoriza e tvoøí jeden z hlavní h pilíøù souèasné znalosti kvantový halgoritmù.V páté kapitole je diskutována ponìkud mlad¹í my¹lenka pøevedení my¹lenky náhodnéhopro házení do svìta kvantový h algoritmù a pøedev¹ím jeho vyu¾ití v my¹len e vyhledáva í halgoritmù, algoritmus vyhledávají í na hyperkry hli. Struènì je nastínìna problematika realiza ekvantový h vyhledáva í h algoritmù v opti ký h sítí h a uveden pøíklad na tomto vyhledáva ímalgoritmu.Jako pøílohy prá e jsou uvedeny výpisy zdrojový h kódù nìkolika programù, které bylypou¾ívány k tvorbì grafù a v rùzný h obmìná h i k samostatnému zkoumání numeri ký h øe¹enínìkterý h problémù. Dùle¾itìj¹í vlastní závìry jsou uvedeny v paragrafe h 4.3 a 5.4.1

Kapitola 1Základy kvantové me hanikyKvantová me hanika tvoøí matemati ký model, na jeho¾ základì kvantové algoritmy pra ují.V prvním a druhém paragrafu této kapitoly tak uvedeme postuláty, na ni h¾ je kvantová me ha-nika zalo¾ena. Ve tøetím a ètvrtém paragrafu zavedeme prvky formalismu, který budeme dálev rám i této prá e vyu¾ívat. V poslední h paragrafe h uvedeme nìkteré pokroèilej¹í poznatkyteorie ví eslo¾kový h systémù, které se tématu prá e dotýkají.1.1 Postuláty kvantové me hanikyKvantová me hanika není podle [3℄ sama fyzikální teorií, pouze matemati kým vzorem, najeho¾ základì jsou zalo¾eny jednotlivé teorie nazývané spoleènì kvantovou teorií.Takové oznaèení ov¹em nemusí být z ela jednoznaèné { uèebni e [4℄ napøíklad uvádí pod stej-ným názvem jednu z takový h fyzikální h teorií, která tvoøí obdobu klasi ké me haniky. V takovépodobì byla kvantová me hanika popsána E. S hrödingerem ve dva átý h lete h 20. století. Daloby se tedy øí i, ¾e existují rùzné stupnì matemati ké abstrak e této formula e. V této prá i bu-deme pou¾ívat vý¹e naznaèenou matemati kou formula i kvantové me haniky, øízenou sadoupostulátù, ve formì, kterou uvádí [3℄. Jedná se o sjedno ení rùzný h smìrù, kterými se kvantováme hanika v dobì svého vzniku vyvíjela { toto sjedno ení, známé od pøelomu 20. a 30. let, jepra í P.A.M. Dira a a J. von Neumanna.Uveïme tedy nyní jednotlivé postuláty této formula e, a nìkolik první h poznámek ke ka¾-dému z ni h.1. Stavovým prostorem libovolného izolovaného fyzikálního systému je Hilbertùv prostor. Stavsystému je pak plnì popsán jednotkovým vektorem z tohoto prostoru, stavovým vektorem.Dohoda o pou¾ívání jednotkový h vektorù v tomto postulátu je spí¹e konven í. V¹e hnyvzor e kvantové me haniky popisují í fyzikální vlastnosti systému (napø. pøedpokládané výsledkypozorování) je toti¾ mo¾no pøeformulovat tak, aby nerozli¹ovaly mezi daným vektorem a ¾ádnýmjeho nenulovým násobkem [4℄, tedy aby bylo mo¾no z ni h délku ka¾dého pou¾itého vektoruvytknout v nulové mo ninì.Výjimku v pøed hozímu odstav i tvoøí nulový vektor stavového prostoru. Kdyby hom z po-stulátu vyøadili po¾adavek na jednotkovou délku stavového vektoru, bylo by tøeba pøidat tvr-zení, ¾e nulový vektor nemá fyzikální význam { nepopisuje stav ¾ádného fyzikálního systému.Uvidíme, ¾e èasovým vývojem uzavøeného fyzikálního systému nemù¾e pøejít nenulový stavovývektor v nulový a ¾e pokud by jakákoliv jiná situa e mìla tento dùsledek, nebude mo i nastat.Podmínka pou¾ívání pouze jednotkový h vektorù v¹ak stále neimplikuje jednoznaènost pøi-øazení mezi tìmito vektory a skuteènými fyzikálními stavy { ve smyslu tvrzení o nerozli¹itelnostimezi vektorem a libovolným jeho nenulovým násobkem existuje stále je¹tì þvolnostÿ ve volbìfáze (zvané globální fáze), tedy koe� ientu tvaru libovolné komplexní jednotky: stavové vektory a eiϕ jsou fyzikálnì ekvivalentní pro ka¾dé ' 2 R.2

Mno¾inu jednotkový h vektorù s identi�ka í vektorù li¹í í h se pouze globální fází mù¾emepøípadnì popsat matemati kou konstruk í zvanou projektivní prostor, o¾ je jistá varieta s di-menzí o 2 men¹í oproti pùvodnímu prostoru. Tento postup nebudeme pøíli¹ vyu¾ívat, proto¾eopou¹tí hrani e pou¾itelnosti lineární algebry (nemá napøíklad de�novány ¾ádné vektorové ope-ra e).Nakone v rám i této prá e budeme pra ovat s koneènìdimenzionálními (prehilbertovými)vektorovými prostory, o¾ znaènì usnadní výklad a matemati ký formalismus a rovnì¾ zamezívzniku problémù, které je tøeba øe¹it v jiný h aplika í h kvantové me haniky [4℄. Ve z ela vý-jimeèný h pøípade h pou¾ijeme v krátký h úse í h textu i nekoneènìdimenzionální prostor sespoèetnou bází (separabilní). V takový h pøípade h se budeme spoléhat na intuitivní roz¹íøeníplatnosti zavedeného formalismu a rovnì¾ nebudeme dokazovat oprávnìnost pou¾itý h opera ís tím, ¾e ètenáø si v pøípadì zájmu dohledá potøebné informa e v literatuøe, napø. [2℄. Na takovámísta bude pøedem upozornìno.2. Vývoj uzavøeného kvantového systému je dán unitární transforma í závisejí í pouze na po-èáteèním a kon ovém èase.Tento postulát je tøeba hápat tak, ¾e z konstruk e uva¾ovaného fyzikálního systému vyplýváexisten e takového unitárního operátoru U na stavovém prostoru, parametrizovaného poèáteè-ním a kon ovým èasem nìjakého zkoumaného èasového intervalu, ¾e a» byl systém na zaèátkuintervalu ve stavu popsaném kterýmkoliv stavovým vektorem , na kon i intervalu bude ve stavupopsaném vektorem U .Dùsledkem linearity unitárního operátoru je prin ip superpozi e: jestli¾e èasový vývoj stavusystému pøi rùzný h poèáteèní h podmínká h, popsaný h rùznými stavovými vektory i v poèá-teèním èase, je popsán vektorovými funk emi i(t), známe i èasový vývoj v pøípadì, ¾e poèáteènístav systému je popsán libovolnou lineární kombina í = n∑

i=1

i { (1:1 a){ v ka¾dém okam¾iku bude pak stav systému popsán odpovídají í lineární kombina í(t) = n∑

i=1

i(t): (1:1 b)Tento postulát je mo¾no ekvivalentnì pøeformulovat tak, ¾e uzavøený systém se vyvíjí podlediferen iální rovni e �(t)�t = � i�hH(t)(t); (1:2)kde (t) je stavový vektor systému v èase t, �h redukovaná Plan kova konstanta a H(t) hermi-tovský operátor pro libovolné t [3℄.1Operátor H, obe nì závislý na èase, má ve S hrödingerovì reprezenta i kvantové me hanikypøímý fyzikální význam { jak popí¹eme ní¾e, je operátorem jistým zpùsobem odpovídají ím1 Jako poznámku uveďme, že pro definici derivace vektorové funkce potřebujeme předpoklad úplného

vektorového prostoru, což je však jednou z podmínek Hilbertova prostoru.3

energii systému. Nazývá se Hamiltonùv operátor nebo Hamiltonián [4℄. Zde má také velký významuvedení redukované Plan kovy konstanty v rovni i (1.2). V matemati ké formula i se konstantauvádí z tohoto histori kého dùvodu, jinak by ji bylo mo¾no zahrnout do de�ni e operátoru H.Pøi ka¾dé unitární opera i se za hovává délka vektoru, o¾ je dùvodem, proè je mo¾no v prv-ním postulátu uva¾ovat pouze jednotkové vektory, a souèasnì, kdyby hom tento po¾adavek od-stranili, proè ¾ádný nenulový vektor nemù¾e èasovým vývojem pøejít v nepovolený nulový.3. Stavový prostor slo¾eného fyzikálního systému je tenzorovým souèinem stavový h prostorùjednotlivý h komponent. Dále jestli¾e jednotlivé komponenty oèíslujeme èísly 1 a¾ n a pøed-pokládáme, ¾e i-tá komponenta byla pøipravena ve stavu i, stav slo¾eného systému je 1 : : : n.Toto krátké tvrzení (spolu s prin ipem superpozi e) v sobì ukrývá zdroj v¹í síly kvantový hpoèítaèù a vùbe není intuitivní. Ètenáøe by mohla napadnout i jiná øe¹ení otázky, jak pra ovats ví eèásti ovými systémy. Pøipomeòme napøíklad, ¾e v klasi ké me hani e je stavový prostorslo¾eného systému tvoøen direktním souètem stavový h prostorù jeho komponent.V paragrafe h 1.5 a 1.8 uká¾eme nìkteré dùle¾ité dùsledky, které tento postulát pøiná¹íi mimo oblast kvantový h algoritmù.1.2 Kvantové mìøeníPoslední postulát kvantové me haniky popisuje výsledky mìøení stavu fyzikálního systémua vliv mìøení na jeho èasový vývoj. V jednotlivý h fyzikální h teorií h na základì kvantovéme haniky je rùzným zpùsobem zdùvodòováno, proè by mìøení mìlo systém výraznì ovlivòovat,z matemati kého hlediska se v¹ak jedná pouze o dal¹í z postulátù.4. Ka¾dé kvantové mìøení je popsáno mno¾inou fMmg lineární h operátorù, zvaný h mìøi íoperátory, na stavovém prostoru mìøeného systému. Indexy m odpovídají rùzným mo¾nýmvýsledkùm mìøení. Jestli¾e stav systému okam¾itì pøed provedením mìøení je , pravdìpo-dobnost, ¾e namìøíme výsledek m, je rovnap(m) = kMm k2 (1:3 a)a stav systému v okam¾iku ukonèení mìøení je1kMm kMm : (1:3 b)Operátory Mm pøitom musí splòovat tzv. rovni i úplnosti2∑

m

M†mMm = I: (1:3 )

2 Křížkem (†) se v literatuře ke kvantové mechanice značí sdružení.4

V¹imnìme si pravdìpodobnostního harakteru mìøení { dokud mìøení neprovádíme, je vývojizolovaného fyzikálního systému plnì deterministi ký pro es a díky unitaritì èasového vývojedokon e v ka¾dém pøípadì vratný. Tento postulát je jediným bodem, který takové pravidloporu¹uje, ale zároveò jediným zpùsobem zji¹»ování informa í o stavu systému, který kvantováme hanika nabízí.Vzhledem k tomu, ¾e o operátore h Mm nepo¾adujeme, aby byly prosté, mìøení dále neníobe nì ani vratným pro esem. V dùsledku toho nemù¾eme postupnými mìøeními získávat stáledetailnìj¹í informa e o stavu systému. Snadno dokon e uká¾eme dùle¾ité tvrzení, ¾e ¾ádnýmmìøením není mo¾no spolehlivì vzájemnì odli¹it dva rùzné vektory, pokud nejsou ortogonální,v dùsledku èeho¾ není mo¾no stav systému nikdy kompletnì urèit:Ne h» a ' jsou dva neortogonální jednotkové vektory, ne h»M1 aM2 jsou mìøi í operátorytvoøí í mìøení, o nìm¾ pøedpokládáme, ¾e dá výsledek 1 pro vektor a 2 pro vektor ', obojís jistotou. Tedy kM1 k = kM2'k = 1; (1:4 a)souèasnì musí platit kM1'k = kM2 k = 0: (1:4 b)Utvoøme ortogonální rozklad vektoru ' do podprostorù [ ℄λ a [ ℄⊥λ : ' = � +�u, j�j2+j�j2 = 1,kuk = 1, (u; ) = 0, � 6= 0. Díky linearitì M2 musí platit1 = kM2'k = k�M2uk = j�jkM2uk � j�j; (1:4 ) o¾ je spor s j�j2 = 1� j�j2 < 1.Uvidíme, ¾e nemo¾nost zjistit kompletní informa i o stavu kvantového systému bude tvoøitvelkou pøeká¾ku pro vyu¾ívání kvantové me haniky k realiza i výpoètù.Mìøením je ve smyslu pøed hozí h odstav ù tedy obe nì3 naru¹en i unitární èasový vývojsystému. To není ve sporu s druhým postulátem z dùvodu, ¾e fyzikální systém, na nìm¾ provádímemìøení, nemù¾e být uzavøený { musí jistì nìjak interagovat s pou¾itým mìøi ím aparátem.Jako poslední poznámku k uvedenému znìní postulátu uveïme, ¾e rovni e úplnosti, uvedenáv tvrzení postulátu, je ekvivalentní po¾adavku, aby souèet pravdìpodobností byl roven 1:∑

m

p(m) =∑

m

(Mm ;Mm ) =∑

m

( ;M†mMm ) = ( ;∑

m

M†mMm ) : (1:5 a)Proto¾e jednotkový vektor splòuje rovni i ( ; ) = 1, bude výraz na pravé stranì roven 1 právìtehdy, kdy¾ bude pro ka¾dý jednotkový vektor platit

( ;(∑m

M†mMm � I) ) = 0; (1:5 b) o¾ je ekvivalentní rovni i úplnosti.Zmiòme, jak by bylo tøeba znìní postulátu upravit, kdyby hom v postulátu 1 nahradilipo¾adavek na pou¾ívání jednotkový h vektorù pouze zákazem nulového vektoru. De�ni e mìøi í h

3 Stále zde připomínáme slovo „obecněÿ z důvodu, že definici vyhovuje i měření s jediným měřicímoperátorem I, které dá svůj jediný výsledek s jistotou a stav systému nezmění.5

operátorù Mm ani rovni i úplnosti není tøeba upravovat, ale souèet pravdìpodobností podlepùvodního znìní by vy¹el roven dle odvození pou¾itého vý¹e ( ; ) = k k2. Toto hování by setedy opravilo vzor em p(m) = kMm k2k k2 : (1:6)Stav po mìøení zato mù¾eme uva¾ovat jednodu¹¹í, Mm . Z dùvodu, ¾e výsledek m, pro který byMm bylo nulovým vektorem, má z obou de�ni nulovou pravdìpodobnost, nehrozí, ¾e by mohlnulový vektor být stavem po provedení mìøení, a v pùvodním znìní jistì nenastane dìlení nulou.Dùle¾itou skupinu mìøení tvoøí projektivní mìøení: ta jsou popsána jediným hermitovskýmoperátorem, zvaným pozorovatelná (velièina). V koneènìdimenzionální h prostore h má ka¾dýhermitovský operátor H spektrální rozklad4H = ∑

λ∈σ(H)

�Pλ; (1:7)kde �(H) je spektrum operátoru H, � jsou jeho vlastní èísla a Pλ jsou ortogonální projektory navlastní podprostory odpovídají í vlastním èíslùm �. Pro tvrzení pùvodního postulátu budemeuva¾ovat vlastní èísla � jako výsledky mìøení a Pλ jako mìøi í operátory. Rovni e úplnosti jesplnìna díky vlastnostem spektrálního rozkladu.Projektory ve spektrálním rozkladu splòují rovnost PλPµ = ÆλµPλ. Po namìøení výsledku �se tak systém dostane do stavu popsaného vektorem ′ = 1kPλ kPλ ; (1:8 a)pro který platí Pµ ′ = Æλµ ′; (1:8 b)tedy pøípadné okam¾itì následují í mìøení stejné pozorovatelné (tedy bez uva¾ování èasovéhovývoje mezi mìøeními) dá stejný výsledek jako první mìøení s jistotou. Popsaný jev se nazývákolaps do stavu ′.S projektivními mìøeními se setkáme pøedev¹ím ve S hrödingerovì reprezenta i, kde jsoupozorovatelné pøiøazeny jednotlivým fyzikálním velièinám. Pozorovatelné jsou konstruovány tak,¾e vlastní hodnoty � mají fyzikální rozmìr a velikost skuteèný h výsledkù mìøení odpovída-jí í h fyzikální h velièin. Hamiltonùv operátor H, uvedený u druhého postulátu, je napøíkladpozorovatelnou odpovídají í energii systému a rovni e (1.2) se nazývá S hrödingerova rovni e.Problematika kvantového mìøení je mnohem rozsáhlej¹í a projektivní mìøení jsou veli edobøe prozkoumána, základní poznatky viz [3℄, [4℄, v zájmu udr¾ení tématu prá e v¹ak dal¹ídetaily uvádìt nebudeme.V teorii kvantový h algoritmù budeme pou¾ívat jistý kompromis mezi uvedenými dvìmaformula emi { mìøení, jeji h¾ mìøi í operátory budou vzájemnì ortogonální projektory, nebude4 Spektrální rozklad a projektivní měření jsou dobře definovány i v prostorech nekonečné dimenze.

Jak však již bylo nejednou řečeno, složitějším matematickým konstrukcím v takovém případě se budemevyhýbat. 6

nás v¹ak zajímat, jaké hodnotì které fyzikální velièiny výsledek odpovídá. Dùle¾ité budou oboryhodnot jednotlivý h projektorù.V koneènìrozmìrný h stavový h prostore h budeme de�novat dva dùle¾ité pøípady kvanto-vého mìøení:{ Jestli¾e bude dána ortonormální báze f igni=1 stavového prostoru, mù¾eme uva¾ovat mìøeníurèené v¹emi n ortogonálními projektory na jednorozmìrné podprostory [ i℄λ. Takové mì-øení dává v pøípadì ka¾dého bázového stavu odpovídají í výsledek s jistotou a doká¾e mezibázovými stavy jednoznaènì rozli¹it. Nazývá se úplné mìøení v dané ortonormální bázi.{ Uva¾ujme pøípad ví eslo¾kového systému, pro který stavové prostory jednotlivý h slo¾ekoznaèíme H1, H2, : : : , Hm, ne h» f igni=1 je ortonormální báze zvoleného prostoru Hk,1 � k � m. Podle tøetího postulátu je stavovým prostorem slo¾eného systému H = H1 H2 : : : Hm. Oznaème IHjjednotkový operátor na prostoru Hj , oznaème Pi 2 L(Hk)ortogonální projektor na [ i℄λ, i = 1; : : : ; n. Ortogonální projektoryIH1 : : : IHk−1

Pi IHk+1 : : : IHm

(1:9)pak de�nují mìøení, které nazveme mìøením na i-tém podsystému, opìt v odpovídají í bázi.Pøedveïme tvrzení postulátu o mìøení na pøíkladì úplného mìøení: oznaème ortonormálníbázi uva¾ovaného stavového prostoru stejnì jako v pøed hozí h bode h a uva¾ujme obe nousuperpozi i = n∑

i=1

�i i: (1:10 a)Délka vektoru je dle de�ni e ortonormální bázek k =√√√√ n∑

i=1

k�ik2 (1:10 b)a po¾adavek, aby byl jednotkový vektor, tedy znín∑

i=1

k�ik2 = 1: (1:10 )Pravdìpodobnost, ¾e mìøení dá výsledek i odpovídají í projektoru na [ i℄λ, kterou budemenazývat pravdìpodobností namìøení i-tého bázového vektoru, je rovna k�ik2. Je tedy druhoumo ninou absolutní hodnoty koe� ientu lineární kombina e u vektoru i, kterou budeme nazývatamplituda vektoru i.Tímto je tedy vymezena sada postulátù, na jeji h¾ platnost se budeme v hlavní èásti prá espoléhat. Upozornìme v¹ak s pøedstihem, ¾e z fyzikálního hlediska tyto postuláty nejsou z elaobe né { odpovídají jistým ideálním pøedpokladùm o popisovaném systému a mo¾noste h na¹íznalosti jeho stavu. V paragrafu 1.7 pøedstavíme alternativní sadu postulátù, která je za stejný hpøedpokladù matemati ky ekvivalentní [3℄, ale univerzálnìj¹í pro prakti ké pou¾ití.7

1.3 Dira ùv formalismusV lineární algebøe se pou¾ívá mnoho rùzný h zpùsobù znaèení jednotlivý h matemati ký hobjektù. V tomto textu budeme vyu¾ívat znaèení obvyklé pøedev¹ím v literatuøe k teorii kvantovéinforma e, tzv. Dira ovu nebo bra-ketovou nota i. Shròme tedy nyní jeho pravidla.Vektory, které budeme pova¾ovat za nadále nedìlitelné (viz ní¾e), budeme znaèit jako tzv.kety: napø. jxi. Takový symbol má pøesnì stejný význam jako v jiný h nota í h x, ~x nebo x,pøíkladem lineární kombina e vektorù jxi a jyi tak mù¾e být 12 jxi+ ijyi.Dira ova nota e nám dává mo¾nost vyu¾ívat jako þvnitøekÿ ketu rùzné skupiny symbolù:bì¾ná jsou písmena latinské i øe ké abe edy, èísli e i jiné matemati ké znaèky (èasto se setkámenapø. s kety j+i a j�i), v dal¹í h oblaste h kvantové fyziky se pou¾ívají i jiné znaèky (j"i, jva i,j~pi apod.)Dùle¾itá poznámka je, ¾e v kvantové me hani e se ketové oznaèení ve skuteènosti pou¾ívávýhradnì pro jednotkové vektory { toto pravidlo budeme také dùslednì dodr¾ovat. Pokud bu-deme pra ovat s jedním Hilbertovým prostorem, vektory oznaèené èísly j0i; j1i; : : : budou dáleoznaèovat jeho ortonormální bázi a jeji h ortogonality budeme vyu¾ívat bez dal¹ího pøipomínání.Upozornìme v¹ak pøedem, ¾e èasto budeme pra ovat s nìkolika Hilbertovými prostory souèasnìa tehdy bude tøeba upøesnit, o kterém mluvíme, pøípadnì toto pravidlo upravit.Dal¹ím prvkem Dira ovy nota e jsou bra-vektory. Jestli¾e oznaèíme kety prvky nìjakéhovektorového prostoru, dle nejobe nìj¹í de�ni e jsou bra vektory z prostoru k nìmu duálního,tedy spojité lineární funk ionály [2℄. Je v¹ak známo, ¾e duální prostor k Hilbertovu prostoru jenový Hilbertùv prostor s ním izometri ký a dále, ¾e prvky obou prostorù lze identi�kovat podleRieszovy vìty [1℄: ke ka¾dému bra-vektoru h'j je tak jednoznaènì urèen jeden ket-vektor jyi, ¾eak e h'j (jako funk ionálu) na libovolný vektor jxi je dána skalárním souèinem:h'j(jxi) = (jyi; jxi): (1:11)Øíkáme pak, ¾e bra-vektor h'j je duální ke ket-vektoru jyi. Tento jeji h vztah budeme znaèittak, ¾e pro þvnitøekÿ pou¾ijeme stejný symbol: h'j = hyj.První zmìnou zavedenou pou¾itím Dira ovy nota e je, ¾e v ak i funk ionálu na vektor vy-ne háme závorky a spojíme svislé linky, èím¾ vznikne výraz h'jxi. Podle tvrzení itovaného vý¹eje tedy ekvivalentnì hyjxi zápisem pro skalární souèin vektorù jxi a jyi.Jako dal¹í zmìnu oproti ostatním nota ím nebudeme v tomto pøípadì vy¾adovat násobenívektoru èíslem pouze zleva, matemati ky øeèeno tedy dode�nujeme opera i násobení èíslemzprava se stejným výsledkem. Napøíklad výraz jxihyjzi tak je násobek vektoru jxi urèený koe�- ientem hyjzi.5 Toto nám umo¾ní zavést výrazy tvaru jxihyj6 tak, ¾e budou pùsobit na vektoryzleva a výsledkem bude jxihyj(jzi) = jxihyjzi. Snadno nahlédneme, ¾e se tedy jedná o jistou tøídulineární h operátorù.5 Ve skutečnosti se budeme opačnému zápisu 〈y|z〉|x〉 vyhýbat, protože označení |z〉|x〉 použijeme

později pro tenzorový součin.6 Anglicky outer product. Tento pojem nebudeme překládat vzhledem k možné záměně s pojmem

vnějšího součinu, exterior product, z teorie Grassmannových algeber.8

Mezi tìmito lineárními operátory jsou dále významné operátory tvaru jxihxj { ka¾dý takovýoperátor je ortogonálním projektorem na podprostor [jxi℄λ. Úplné mìøení v bázi fjiigni=0 jetedy urèeno mno¾inou mìøi í h operátorù fMigni=0, Mi = jiihij pro i = 0; 1; : : : ; n. Jestli¾emìøení dá i-tý výsledek, øekneme, ¾e jsme systém namìøili ve stavu jii, podobnì s mìøením napodsystéme h.Ve smyslu pøed hozího paragrafu budeme èasto potøebovat je¹tì oznaèení pro tenzorovýsouèin dvou vektorù (obe nì z rùzný h prostorù). I pro ten umo¾òuje Dira ova nota e zavéstjednodu hé konzistentní oznaèení: ve výrazu jxi jyi vyne háme znaèku tenzorového souèinua budeme psát jxijyi. Pokud naví budou násobené vektory prvky stejného prostoru, mù¾emedokon e vyne hat vnitøní dvoji i závorek: jxijyi = jxyi. To je v souladu s tím, ¾e tenzorovýmsouèinem jednotkový h vektorù vzniká opìt jednotkový vektor.V¹imnìme si, ¾e díky pøíslu¹ným axiomùm a de�ni ím a díky dodané komutativitì násobenívektoru a èísla pak mù¾eme v Dira ovì nota i provádìt rùzné intuitivní úpravy pøipomínají íroznásobování (èi vytýkání): (�hxj+ �hyj)jzi = �hxjzi+ �hyjzihxj(�jyi+ �jzi) = �hxjyi + �hxjzihxj Æ jyihzj = hxjyijzijaihbj Æ j ihdj = jaihbj ihdj(�jxi+ �jyi)jzi = �jxijzi+ �jyijzi� � � (1:12)V tomto místì upozornìme na výraz tvaru hxjhyj. Z pøed hozího textu nevyplývá, jak by mìlbýt de�nován, a bohu¾el existují dva mo¾né pøístupy s rùzným výsledkem: buï uva¾ujeme, ¾evýraz vzniknul vyne háním v hxjhyj, pak podle de�ni e tenzorového souèinu dvou lineární hzobrazení musí platit hxjhyj(jaijbi) = hxjaihyjbi; (1:13)bli¾¹í smyslu pøed hozího odstav e by v¹ak bylo, kdyby hom jej de�novali jako hyj hxj, abyplatilo hxjhyj(jaijbi) = hxjhyjaijbi = hyjaihxjbi: (1:14)Oba pøístupy jsou oprávnìné a je na rozmy¹lení autora daného textu, který vyu¾ije. My tutoopera i rovnì¾ budeme pøíle¾itostnì potøebovat { ne h» se tedy u nás hová prvním popsanýmzpùsobem.1.4 Koneènìdimenzionální prostoryPodívejme se struènì, o si mù¾eme pøedstavit pod jednotlivými prvky Dira ovy nota ev pøípadì koneènìdimenzionální h Hilbertový h prostorù C n , které pro nás budou podstatné.Pøedpokládejme, ¾e C n je prostor sloup ový h vektorù. To je elkem obvyklá konven e,i kdy¾ pøíklad [1℄ ukazuje, ¾e ne z ela zaruèená.Je tøeba stanovit, jak budeme v tomto prostoru reprezentovat bázové vektory fjiign−1i=0 . Jistìmusíme za hovat podmínku ortonormality. Skalární souèin v C n v¹ak není dán jednoznaènì9

(mù¾e jím být libovolná hermitovská forma s pozitivnì de�nitní diagonálou) a jeho vhodnouvolbou by hom mohli zajistit pro libovolnì zvolenou bázi, aby byla ortonormální. Stanovmeproto, ¾e v prostore h C n v¾dy budeme uva¾ovat standardní skalární souèin. S tím mù¾emede�novat jii = ei+1: j0i =

10...0; : : : ; jn� 1i =

0...01: (1:15)Ne h» tedy jxi a jyi jsou prvky C n ,jxi =

x1x2...xn

; jyi =

y1y2...yn: (1:16 a)Jeji h standardním skalárním souèinem je pak komplexní èíslohxjyi = (jxi; jyi) = n∑

i=1

xiyi: (1:16 b)Vidíme, ¾e stejného výsledku dosáhneme, kdy¾ vynásobíme mati e(x1 � � � xn ) y1...yn (1:16 )a identi�kujeme výslednou ètver ovou mati i prvního øádu s jejím jediným prvkem. Opera e,kterou jsme pøitom provedli se sloup ovým vektorem jxi, braným jako mati e typu n � 1, jekombina í transpozi e a komplexního srdu¾ení prvkù, tedy analogií sdru¾ení pro obdélníkovémati e.Je tedy mo¾né uva¾ovat duální prostor jako prostor øádkový h vektorù a obe nì polo¾ithxj = (x1 x2 � � � xn ) = jxi†: (1:17)Skuteènost, ¾e takový tvar pak mù¾eme dosadit napøíklad do výrazù tvaru jxihyj, plynesnadno z aso iativity násobení mati .Tenzorový souèin Hilbertový h prostorù je, jak by hom se doèetli v [2℄, nový Hilbertùvprostor urèený jednoznaènì a¾ na izometrii. Není tedy dáno jednoznaènì, o je tenzorový souèinmati . Bì¾nì se pou¾ívá jeho reprezenta e známá jako Krone kerùv souèin, viz napø. [5℄: z mati A 2 C a,b a B 2 C c,d utvoøíme mati i AB 2 C ac,bd v blokovém tvaruAB =

a11B a12B � � � a1bB... ... . . . ...aa1B aa2B � � � aabB (1:18)Jestli¾e tedy uva¾ujeme Hilbertovy prostory Cm , C n a vektory jxi 2 Cm ; jyi 2 C n ,jxi =

x1x2...xm

; jyi =

y1y2...yn; (1:19 a)10

mù¾eme v této reprezenta i øí i jxijyi 2 Cm C n = Cmn ajxijyi =

x1y1...x1ynx2y1...xmy1...xmyn

: (1:19 b)Snadno by hom ukázali, ¾e pokud rozepí¹eme napøíklad výraz (A B)(jxijyi) pro mati eA a B patøièný h rozmìrù pomo í Krone kerova souèinu, získáme (Ajxi) (Bjyi) a podobnì.1.5 Provázané stavyV tomto paragrafu uká¾eme jeden netriviální dùsledek postulátu o slo¾ený h fyzikální hsystéme h.Uva¾ujme fyzikální systém tvoøený dvìma podsystémy, abstraktnì oznaèenými A a B. Pøí-kladem mù¾e být libovolný systém dvou èásti , èi i tyto podsystémy mohou být samy mnohemkomplikovanìj¹í. Ka¾dý z podsystémù má ve smyslu paragrafu 1.1 pøiøazen stavový prostor, kterýoznaèíme HA, resp. HB , a stavovým prostorem elého systému pak je H = HA HB .Stavové vektory j i 2 H mù¾eme rozdìlit do dvou skupin podle kritéria, zda existují takovéj�iA 2 HA a j�iB 2 HB, ¾e j i = j�iA j�iB , èi takovou rovnost není mo¾no splnit. Pronetriviální HA a HB je druhá skupina neprázdná: uva¾ujme napøíklad HA = HB = C 2 aj i = 1p2(j00i+ j11i): (1:20)Zápis takového vektoru v Dira ovì nota i jej i = 1p2 1001: (1:21 a)Pokud by hom v¹ak uva¾ovalij�i = (�1�2 ); j�i = (�1�2 ); (1:21 b)muselo by platit j i =

�1�1�1�2�2�1�2�2; (1:21 ) o¾ je ve sporu s tím, ¾e sloup ové vektory tvoøené první a druhou dvoji í slo¾ek j i jsou lineárnìnezávislé. 11

U vektoru j i tedy nemá smysl øí i, ¾e podsystémy A a B by byly ve stave h popsaný hnìjakými vektory j�i a j�i, pøesto¾e j i je pouze lineární kombina í dvou vektorù ve tvarutenzorového souèinu (produktový h nebo faktorizovatelný h stavù), u který h by taková úvahamo¾ná byla. Stavy, které nejsou faktorizovatelné, se nazývají provázané stavy (entangled states[3℄). Jeji h existen e je nevyhnutelným dùsledkem de�ni e tenzorového souèinu.1.6 Paradox EPRProvázání je také pùvod em známého paradoxu EPR [6℄. Autoøi Einstein, Podolsky a Rosen,jeji h¾ nese jména, se jím sna¾ili ukázat, ¾e pojetí kvantové me haniky pomo í vlnový h funk í7 zapøedpokladu platnosti postulátù uvedený h vý¹e vede ke sporùm, z ni h¾ jeden detailnì popsali.Tento pøíklad zde nebudeme uvádìt,8 proto¾e by bylo nutno detailnì vysvìtlit detaily kvan-tové me haniky na Hilbertový h prostore h nekoneèné dimenze, uká¾eme v¹ak jeho mnohemjednodu¹¹í variantu, kterou se zabýval J. S. Bell. Tento fyzik nejen¾e ukázal obdobu formula eparadoxu pro mnohem jednodu¹¹í fyzikální systémy, které jsou tím blí¾e experimentálním mo¾-nostem, pøedev¹ím v¹ak zformuloval podmínku známou jako Bellova nerovnost, pomo í jejího¾experimentálního ovìøení by bylo mo¾no rozsoudit, zda se systém hová ve sporu s kvantovoume hanikou nebo zda byly hybné pøedpoklady paradoxu. Podívejme se tedy blí¾e na Bellùvpøíklad:Jeden veli e známý provázaný stav, oznaèovaný z histori ký h dùvodù jako spinový sin-glet [3℄, j i = 1p2(j01i � j10i); (1:22)má zajímavou vlastnost: jestli¾e na stavový h prostore h obou podsystémù zvolíme stejnýmzpùsobem novou bázi fj+i; j�ig,j0i = �j+i+ �j�ij1i = �j+i � �j�i }; j�j2 = j�j2 = 1; (1:23)jeho zápis v nové bázi jeji h tenzorového souèinu má opìt tvarj i = 1p2(��j++i � j�j2j+�i+ j�j2j�+i � ��j��i �� ��j++i � j�j2j+�i+ j�j2j�+i+ ��j��i) == 1p2(j�+i � j+�i): (1:24)Poznamenejme, ¾e pro reálná � a � má uvedená transforma e harakter rota e v rovinì urèenévektory j0i a j1i.Jestli¾e provedeme na prvním podsystému mìøení v pùvodní bázi, nastane kolaps vlnovéfunk e buï do stavu j01i nebo j10i. Výsledek si e bude náhodný, ale pøi následném mìøení7 Vlnové funkce jsou stavovými vektory ve Schrödingerově reprezentaci [4]. Původní znění paradoxu

vycházelo z ní, proto v tomto paragrafu budeme používat toto označení.8 Celý text původního článku je k nahlédnutí k dispozici zdarma na stránkách časopisu [6]12

na druhém podsystému s jistotou namìøíme výsledek odpovídají í druhému bázovému vektoru.Jestli¾e by hom vytvoøili sérii dvoji èásti , ka¾dou z ni h v tomto provázaném stavu, a provádìlina ka¾dé mìøení popsaným zpùsobem, pozorovali by hom mezi výstupy korela i.Toté¾ platí, provedeme-li obì mìøení v nové bázi { systém nyní kolabuje buï do stavu j+�inebo j�+i. V tomto okam¾iku v¹ak pøi hází rozumný argument EPR:Dosud jsme provádìli pouze matemati ké úvahy. Pøedstavme si situa i v¹ak z fyzikálního po-hledu, a to na pøíkladì dvou èásti . Dle postulátù kvantové me haniky mohou být v provázanémstavu, a» jsou libovolnì vzdálené, a i tehdy, kdy¾ zabráníme jeji h vzájemné interak i. Aby homzabránili v¹em známým formám interak e, mù¾eme uva¾ovat, ¾e se jedná o dva fotony, které sevzájemnì vzdalují ry hlostí svìtla, jednotlivé báze ne h» pak mají význam natoèení detektorùpolariza e.Jestli¾e provedeme na první èásti i mìøení v bázi fj0i; j1ig, mù¾eme dle výsledku s urèitostíøí i, ¾e druhá èásti e se bude pøi libovolném následném mìøení hovat, jako by byla pøipravenave stavu j0i, resp. j1i. Kdyby hom ale provedli mìøení v nové bázi fj+i; j�ig, mohli by homo stejné èásti i øí i, ¾e je ve stavu j+i nebo j�i.Proto¾e jsme zabránili interak i mezi obìma èásti emi, druhá èásti e se v¹ak nemù¾e þdo-zvìdìtÿ o tom, jaké mìøení jsme se rozhodli provést na první èásti i. Jestli¾e tedy jsme prvníèásti i namìøili napøíklad ve stavu j0i, druhá ji¾ musela nìjakým zpùsobem být na tuto situa ipøipravena ve stavu j1i. Kdyby hom v¹ak první mìøení provedli v nové bázi a namìøili j+i, druháèásti e by souèasnì se v¹emi vlastnostmi stavu j1i musela mít vlastnosti stavu j�i, resp. j+i.Tyto vlastnosti se v¹ak vyluèují { kdyby hom i na druhé èásti i provedli mìøení v pùvodní bázi,stav j1i implikuje nulovou pravdìpodobnost namìøení j0i, zatím o j�i ani j+i ne.EPR tím argumentovali, ¾e popis fyzikální reality pomo í vlnový h funk í není kompletní,proto¾e druhé èásti i není mo¾no po oddìlení ¾ádnou pøiøadit. V¹imnìme si, ¾e kvantová me ha-nika netvrdí, ¾e by takové pøiøazení mìlo být mo¾né { existuje jen stavový vektor elého systémuobou èásti { pak ale pøi hází dùle¾itost otázky, jak by stav druhé èásti e po mìøení první èásti emohl záviset na jeho výsledku, kdy¾ je efektivnì zabránìno pøenosu jakékoliv informa e.Prostorové oddìlení èásti se zdálo být tak silným argumentem, ¾e poèaly snahy kvantovoume haniku pod vlivem tohoto paradoxu nìjak opravit nebo vymyslet novou, pøesnìj¹í teorii.Jednou z uva¾ovaný h mo¾ností9 byla teorie skrytý h promìnný h, která øíká, ¾e vlnové funk etvoøí skuteènì jen èásteèný popis stavu fyzikálního systému a pøedev¹ím, ¾e pro es mìøení jedeterministi ký a jeho statisti ký harakter v kvantové me hani e je jen projevem na¹í neznalostia nes hopnosti ovlivnit dodateènou informa i.J. S. Bell v¹ak navrhl zpùsob, pomo í kterého by bylo mo¾no rozsoudit, zda se fyzikálnísystém hová dle podobný h pøedpokladù, nebo zda se projeví neintuitivní dùsledky kvantovéme haniky. Jeho úvaha je pøedev¹ím znamenitá tím, ¾e neuva¾uje ¾ádné konkrétnì formulovanéteorie { pøedpokládá pouze, ¾e by bylo mo¾no jakkoliv doplnit do nìjaké my¹lené tabulky výsledkymìøení, která jsme ve skuteènosti neprovedli, a jednodu hým zpùsobem vyvodí nerovnost, kterouby pak musely splòovat rùzné míry korela e mezi jednotlivými polo¾kami.9 Další do současnosti uvažovaná řešení, např. přenos informace nazpět v čase, jsou uvedena v [7].13

Bellovy pøedpoklady jsou splnìny u teorie lokální h skrytý h promìnný h, zatím o u kvan-tové me haniky nejsou. Dal¹í analýza pøíkladu s rùznými bázemi C 2 by ukázala, ¾e existují si-tua e, ve který h kvantová me hanika Bellovu nerovnost poru¹uje. Závìrem tedy je jednodu hé,aè mimoøádnì významné tvrzení, známé jako Bellova vìta [8℄:®ádná fyzikální teorie lokální h skrytý h promìnný h nemù¾e dát stejné pøedpovìdi jakokvantová me hanika.S jeho existen í staèilo sestavit odpovídají í experiment, namìøit dostateènou statistiku vý-sledkù a ovìøit na konkrétním pøíkladì platnost Bellovy nerovnosti. Souèasné závìry tì hto ex-perimentù mluví dostateènì pøesvìdèivì ve prospì h kvantové me haniky, i kdy¾ èást fyzikálníhosvìta je stále skepi ká [8℄.Je tøeba poznamenat, ¾e teorie skrytý h promìnný h tímto není zavr¾ena, pouze nemù¾e býtlokální ve smyslu, ¾e by èásti e bylo mo¾no uva¾ovat fyzikálnì z ela izolované, i kdyby s seboumohly nést libovolné mno¾ství informa e libovolného druhu.Celý prùbìh této diskuse s mnoha dal¹ími zajímavými náhledy, dodateènými informa emia úz e souvisejí ími �lozo� kými otázkami je dùslednì popsán v [9℄. Autor uvádí i dal¹í mo¾ná,ví eménì �lozo� ká, vý hodiska, z ni h¾ uvedeme napøíklad tvrzení, ¾e systém èásti tvoøí jedennový nedìlitelný fyzikální objekt, tedy napøíklad, ¾e pár fotonù nelze my¹lenkovì rozdìlit naþpùl-páryÿ stejnì tak, jako se foton v interferometru neroz¹tìpí na þpolo-fotonyÿ.Na závìr tohoto paragrafu se zmiòme o ètyøe h provázaný h stave h z prostoru C 2 C 2 ,které po zmínìný h fyzi í h nesou název Bellovy stavy nebo EPR stavy. Mají v teorii kvantovéinforma e (pøedev¹ím v¹ak mezi kvantovými komunikaèními protokoly) ¹iroké vyu¾ití díky svéjednodu hostí, díky ní¾ jsme se ji¾ i se dvìma z ni h seznámili. Jeji h de�ni e a obvyklé znaèeníjsou j�00i = 1p2(j00i+ j11i);j�01i = 1p2(j01i+ j10i);j�10i = 1p2(j00i � j11i);j�11i = 1p2(j01i � j10i): (1:25)Snadno (napøíklad z mati ového zápisu) by hom se pøesvìdèili, ¾e se zároveò jedná o zajímavouortonormální bázi odpovídají ího prostoru.1.7 Mati e hustotyPojemmati e hustoty10 vzniknul z potøeby popisovat fyzikální systémy, o jeji h¾ stavu mámepouze èásteèné informa e. Je silnìj¹í alternativou ke stavovým vektorùm, uvedeným v para-grafu 1.1, proto¾e po zavedení v analogii s dosavadním formalismem lze roz¹íøit i na otevøenéfyzikální systémy.10 Anglicky density matrix nebo density operator. Místo přímého překladu druhého z názvů se v českéliteratuře můžeme setkat s názvem statistický operátor.14

Mati e hustoty je v øeèi matematiky pozitivním jaderným11 lineárním operátorem na danémprostoru se stopou rovnou jedné. V koneènìdimenzionálním pøípadì této de�ni i odpovídají line-ární operátory, jeji h¾ mati e je hermitovská, pozitivní (odpovídá mati i pozitivnì semide�nitníkvadrati ké formy) a má stopu rovnu 1.Obvykle se zavádí pøi popisu smìsí èásti : pøedstavme si rezervoár stejný h kvantový h sys-témù, které ov¹em mohou být z hlediska kvantové me haniky v rùzný h stave h. Ne h» fjsiigki=1je koneèná12 mno¾ina mo¾ný h stavù a èíslo pi urèuje pomìr zastoupení i-tého stavu pro ka¾déi 2 f1; 2; : : : ; kg. Jestli¾e systém, se kterým budeme pra ovat, odebereme z takové smìsi, budes pravdìpodobností pi ve stavu jsii.Pøi zkoumání èasového vývoje takového systému mù¾eme øe¹ení rozdìlit do k vìtví podletohoto poèáteèního stavu a u ka¾dého výsledku opìt uva¾ovat odpovídají í pravdìpodobnost pi.Mati e hustoty je naproti tomu jediný matemati ký objekt, který kompletnì popí¹e tuto situa ia v¹e hny výsledky dá stejné.Uva¾ovanému systému pøiøadíme mati i hustoty ve tvaru% = k∑

i=1

pijsiihsij: (1:26)Aby ale tento objekt mohl být pou¾itelný, musíme ukázat, jak se vyvíjí s èasem a jaké výsledkypro danou mati i hustoty dá kvantové mìøení. To provedeme ve smyslu pøed hozího odstav e.Pøedpokládejme tedy, ¾e uva¾ovaný systém je v èase t1 s pravdìpodobností pi ve stavu jsii,i = 1; : : : ; n, a zkoumejme jeho stav v èase t2. Podle postulátu 2 existuje taková unitární opera eU , která ka¾dému z uva¾ovaný h poèáteèní h stavù jsii pøiøadí odpovídají í stav U jsii v èase t2.Pøiøaïme tedy tìmto stavùm odpovídají í pravdìpodobnosti a sestavme v èase t2 mati i hustotyv analogii vzor e (1.26):%′ = k∑

i=1

pi (U jsii(U jsii)†) = k∑

i=1

piU jsiihsijU† = U k∑

i=1

pijsiihsijU†: (1:27)Odtud je zøejmé, ¾e samotná opera e U bude udávat pøímý vztah i mezi obìma mati emi hustoty:%′ = U%U†: (1:28)Podobným zpùsobem uká¾eme, s jakou pravdìpodobností mù¾eme oèekávat které výsledkymìøení, známe-li mati i hustoty. Uva¾ujme znaèení dle postulátu 4. Kdyby systém byl ve stavujsii, byla by pravdìpodobnost namìøení výsledku mp(m) = kMmjsiik2 = hsijM†mMmjsii: (1:29 a)

11 Jaderný operátor je operátor, u kterého má smysl obecná definice stopy uvedená v [2]. My se všakopět omezíme na konečněrozměrné prostory, kde každý lineární operátor má stopu rovnou stopě jehomatice v libovolné ortonormální bázi.12 Pro účely tohoto příkladu. Zobecnění samozřejmě použití matice hustoty neznemožňuje, je jen ma-tematicky náročnější. 15

Tuto pravdìpodobnost je ov¹em tøeba je¹tì vynásobit pravdìpodobností pi a pøièíst odpovídají ípøíspìvky od ostatní h mo¾ností. Celkovìp(m) = k∑

i=1

pihsijM†mMmjsii: (1:29 b)Pro podobné zjednodu¹ení tohoto vzor e, jakého jsme dosáhli v minulém odstav i, bude tøebavyu¾ít trik { na toto èíslo pohlédnout jako na stopu mati e 1�1 nebo pøesnìji lineárního operátoruna jednorozmìrném prostoru, tedyp(m) = Tr k

∑

i=1

pihsijM†mMmjsii: (1:29 )Lineární operátor (lineární funk ionál) hsij pak v této stopì mù¾eme pøesunout na poslední místodíky invarian i výsledku vùèi ykli ké zámìnì ve skládání operátorù:p(m) = Tr k

∑

i=1

piM†mMmjsiihsij = TrM†

mMm

k∑

i=1

pijsiihsij; (1:29 d)èím¾ máme opìt mo¾nost ze vzor e vyèlenit mati i hustoty (1.26) jeko elek:p(m) = Tr(M†mMm%): (1:30)Podobnými úvahami by hom dokázali pøevést zbývají í vzor e z postulátù 3 a 4. Tyto vý-sledky dávají tu¹it, ¾e by mati e hustoty mohla být de�nována samostatnì, bez jakékoliv zá-vislosti na pùvodní h postuláte h a úvah o smìsí h. Jestli¾e tedy dosadíme do postulátù 2, 3a 4 odvozené vzor e a postulát 1 nahradíme de�ni í mati e hustoty ze zaèátku paragrafu, zís-káme následují í sadu postulátù [3℄, které skuteènì tvoøí plnou náhradu za postuláty uvedenév paragrafu 1.1.1'. Stavovým prostorem libovolného izolovaného fyzikálního systému je Hilbertùv prostor. Stavsystému je pak plnì popsán pozitivním jaderným lineárním operátorem % na tomto prostoruse stopou rovnou jedné. Jestli¾e je systém s pravdìpodobností pi ve stavu %i, i = 1; : : : k,jeho mati e hustoty je ∑k

i=1 pi%i.2'. Vývoj uzavøeného fyzikálního systému je popsán unitární transforma í, tedy stav systému %v èase t1 je svázán se stavem %′ v èase t2 unitárním operátorem U , který závisí pouze na t1a t2, podle vztahu %′ = U%U†: (1:31)3'. Stavový prostor slo¾eného fyzikálního systému je tenzorovým souèinem stavový h prostorùjednotlivý h komponent. Dále jestli¾e jednotlivé komponenty oèíslujeme èísly 1 a¾ n a pøed-pokládáme, ¾e i-tá komponenta byla pøipravena ve stavu %i, stav slo¾eného systému je%1 : : : %n. 16

4'. Ka¾dé kvantové mìøení je popsáno mno¾inou fMmg lineární h operátorù, zvaný h mìøi íoperátory, na stavovém prostoru mìøeného systému. Indexy m odpovídají rùzným mo¾nýmvýsledkùm mìøení. Jestli¾e stav systému okam¾itì pøed provedením mìøení je %, pravdìpo-dobnost, ¾e namìøíme výsledek m, je rovnap(m) = Tr(M†mMm%); (1:32 a)a stav po mìøení je 1Tr(M†

mMm%)Mm%M†m: (1:32 b)Mìøi í operátory pøitom musí splòovat rovni i úplnosti

∑

m

M†mMm = I: (1:32 )K tìmto postulátùm uveïme opìt nìkolik poznámek:U smìsí jsme se setkali pouze s mati emi hustoty ve tvaru konvexní kombina e projektorùna podprostory dimenze 1 stavového prostoru. Ka¾dá taková kombina e vyhovuje po¾adavkùmpostulátu 1', jak by hom se snadno pøesvìdèili z odpovídají í h de�ni . Dá se v¹ak ukázat, ¾e anide�ni e mati e hustoty jako pozitivního operátoru se stopou rovnou 1 není obe nìj¹í, nejsnázeopìt v pøípadì koneèné dimenze:Proto¾e ka¾dý pozitivní operátor je hermitovský, pro libovolnou mati i hustoty % existujespektrální rozklad % = ∑k

i=1 �iPλi. Jestli¾e ortogonální projektory Pλ rozepí¹eme jako souètyortogonální h projektorù na podprostory dimenze 1 jxihxj, mù¾eme spektrální rozklad psát vetvaru % = l

∑

j=1

�j jxjihxj j: (1:33)Proto¾e fjxjiglj=1 pak tvoøí ortonormální bázi stavového prostoru, nalezli jsme ortonormálníbázi, v ní¾ je % diagonální. Z pozitivity a podmínky na stopu pak ry hle plyne, ¾e v¹e hny vlastníhodnoty �i le¾í v intervalu h0; 1i a jeji h souèet je 1, urèují tedy koe� ienty konvexní kombina eprojektorù fjxjihxj jglj=1 dávají í %.Tato konvexní kombina e v¹ak není urèena mati í hustoty jednoznaènì: volnost je pone hánav rozkladu projektorù Pλ na souèet þjednorozmìrný hÿ projektorù. Napøíklad mati e hustotyna dvourozmìrném prostoru, popsaná v dané ortonormální bázi mati í(

12 00 12

) ; (1:34)lze z ortogonální h projektorù na jednorozmìrné podprostory nakombinovat zpùsoby(

12 00 12

) = 12 ( 1 00 1)+ 12 ( 0 00 1) = 12 ( 12 12

1212

)+ 12 ( 12 �12�12 1

2

) (1:35)a mnoha dal¹ími. Jednoznaènì je mo¾no zapsat pouze projektory samotné, proto¾e tvoøí vr holysvého konvexního obalu. 17

Projektory jsou dle úvodní úvahy mati emi hustoty systémù, u ni h¾ známe stav pøesnì {{ odpovídají výbìru z rezervoáru, ve kterém v¹e hny systémy byly ve stejném stavu. Stav popsanýmati í hustoty, která je ortogonálním projektorem, se odtud nazývá èistým stavem. Ostatní stavyvyhovují í postulátu 1' se nazývají smí¹ené stavy.V tomto místì je¹tì poznamenejme, ¾e formalismus mati e hustoty potøebuje i jinou de�ni iprovázaný h stavù: øekneme, ¾e stav slo¾eného systému tvoøeného n komponentami, popsanýmati í hustoty %, je separovatelný, jestli¾e je konvexní kombina í mati hustoty tvaru %1: : :%n,kde %i je v ka¾dém pøípadì nìjaká mati e hustoty i-tého podsystému pro i = 1; : : : ; n. V opaènémpøípadì øekneme, ¾e daný stav je provázaný.Mati i hustoty má díky své univerzalitì, uvedené na zaèátku tohoto paragrafu, mnohemví e vyu¾ití ne¾ jen pro popis smìsí systémù. V kvantové me hani e má dal¹í významná pou¾itízejména u neizolovaný h systémù, do ni h¾ okolí vná¹í ¹um. Dal¹ím pøíkladem mù¾e být kon-zistentní popis stavu systému, na nìm¾ bylo provedeno mìøení bez zaznamenání výsledku, èím¾nastala velmi podobná situa e jako pøi výbìru ze smìsi. Pro na¹e úèely v¹ak bude nejdùle¾itìj¹íjejí vyu¾ití v pøípadì slo¾ený h fyzikální h systémù, které popisuje následují í paragraf.1.8 Redukovaná mati e hustotyV teorii kvantový h algoritmù budeme èasto potøebovat pra ovat s fyzikálním systémemslo¾eným z nìkolika podsystémù. Pøesto¾e elý systém je izolovaný, jednotlivé podsystémy nejsou.Aèkoli tedy známe jeji h stavové prostory, nelze pro nì nelze zobe nit pojem stavového vektoru,jak ukazuje pøíklad provázaný h stavù. Nad tìmito prostory ov¹em mù¾eme s výhodou uva¾ovatmati e hustoty.Mati e hustoty nad stavovým prostorem jedné komponenty slo¾eného systému se nazýváredukovaná mati e hustoty. Opera e, kterou se z mati e hustoty elého systému získá, se na-zývá par iální stopa. V její de�ni i se pro zjednodu¹ení omezíme na pøípad dvou systémù s ko-neènìdimezionálními stavovými prostory a na bázové vektory mno¾iny lineární h operátorù natenzorovém souèinu tì hto prostorù, pro výpoèet par iální stopy obe né mati e hustoty se dodápo¾adavek linearity. Ne h» tedy systém tvoøený podsystémy A a B je ve stavu popsaném mati íhustoty ja1iha2jjb1ihb2j, kde jaii, resp. jbii jsou nìjaké vektory ze stavový h prostorù HA, resp.HB systémù A, resp. B. Redukovaná mati e hustoty pro systém A je pak urèena výrazem13%A = TrB(ja1iha2j jb1ihb2j) = (Tr jb1ihb2j) ja1iha2j = hb2jb1ija1iha2j: (1:36)Je otázkou, jak dale e souvisí výsledek této matemati ké opera e se skuteèným stavem pod-systému A. Snadno se v¹ak uká¾e, ¾e taková volba redukované mati e hustoty je dobrá { prolibovolné mìøení na systému A dá správný výsledek [3℄.Pøíklad výpoètu redukované mati e hustoty uká¾eme na dvou pøíklade h:{ Ne h» systém je ve smyslu pùvodního formalismu ve faktorizovatelném stavu jaijbi, jai 2HA, jbi 2 HB . Toto odpovídá mati i hustoty èistého stavu % = jaijbi hajhbj = jaihaj 13 Tr za druhým rovnítkem značí již běžnou stopu matice, třetí rovnítko tedy využívá vlastnosti, žestopa součinu matic je invariantní vůči cyklické záměně.18

jbihbj. Redukované mati e pro oba podsystémy mù¾eme urèit okam¾itì dosazením do uvedenéde�ni e par iální stopy: %A = Tr(jbihbj) jaihaj = jaihaj;%B = Tr(jaihaj) jbihbj = jbihbj: (1:37)Jedná se o èisté stavy odpovídají í stavovým vektorùm jai a jbi.{ Ne h» systém je podobnì jako vý¹e v èistém stavu popsaném vektorem j�00i = 1√2(j00i +j11i), a tedy mati í hustoty % = 1

2(j00ih00j+ j00ih11j+ j11ih00j+ j11ih11j). Takový stav jeprovázaný i dle paragrafu 1.5 i v jazy e mati e hustoty. Redukovanou mati i hustoty prosystém A mù¾eme spoèítat po èlene h:%A = 12(h0j0ij0ih0j+ h0j1ij0ih1j+ h1j0ij1ih0j+ h1j1ij1ih1j) = 12(j0ih0j+ j1ih1j) = 12I: (1:38)Stejná redukovaná mati e hustoty vyjde pro systém B a pro libovolný jiný Bellùv stav.Na druhém uvedeném pøíkladì uká¾eme dvì dal¹í vlastnosti mati e hustoty:{ Redukovaná mati e vy¹la ve tvaru násobku jednotkové mati e. Odpovídají í operátor mástejný tvar pøi vyjádøení v libovolné bázi. Ka¾dé úplné mìøení provedené na systému v ta-kovém smí¹eném stavu by mìlo stejnou pravdìpodobnost pro ka¾dý mo¾ný výsledek. Tentostav se tedy vyznaèuje nejvìt¹í mo¾nou neurèitostí.{ Redukované mati e hustoty vyjdou ve stejném tvaru 12I pro oba systémy i v pøípadì kte-réhokoliv jiného Bellova stavu, aèkoliv mati e hustoty elého systému jsou rùzné. Znalostredukovaný h mati hustoty komponent tedy není postaèují í pro rekonstruk i mati e hus-toty slo¾eného systému.Ve smyslu úvodní vìty tohoto paragrafu budeme v rám i této prá e pra ovat s izolovanýmifyzikálními systémy. Vìt¹inou tedy nebudeme potøebovat opou¹tìt formalismus stavový h vek-torù a redukovaná mati e hustoty bude pro mati i hustoty jediným vyu¾itím. U podsystémùbudeme pøíle¾itostnì mezi obìma formalismy pøe házet tím, ¾e místo mati e hustoty èistéhostavu uvedeme nìkterý odpovídají í vektor.

19

Kapitola 2Kvantová me hanika a zpra ování informa ePostuláty kvantové me haniky je mo¾no pou¾ít k simula i matemati ký h výpoètù podobnìjako Booleovu logiku. V této sek i de�nujeme kvantové obdoby její h základù { jednotky bitua logi ký h hradel jako¾to matemati ký h opera í nad bity. De�nujeme kvantové obvody jakoanalogii logi ký h obvodù { pøedpisu prùbìhu digitálního algoritmu. Tato analogie nebude z elajednoznaèná, pøesto na kon i kapitoly uká¾eme, jak jsme s hopni libovolný logi ký obvod nahra-dit kvantovým protìj¹kem. Mezi prvním a druhým paragrafem je vlo¾ena drobná matemati kávsuvka urèená pro seznámení s de�ni í a základními vlastnostmi Pauliho mati .2.1 Dvoudimenzionální prostoryV kvantový h algoritme h se nejèastìji setkáme se stavovým prostorem urèeným tenzorovýmsouèinem dvoudimenzionální h prostorù. Tento po¾adavek vzniknul v analogii s klasi kými poèí-taèovými algoritmy, které vyu¾ívají dvojkovou soustavu: jednotkou informa e v ni h je bit, ka¾dánejmen¹í pamì»ová souèástka mù¾e být ve stavu 0 nebo 1. V kvantový h algoritme h se tedyzavedl pojem kvantového bitu, qubitu, o¾ je vektor v dvoudimenzionálním prostoru, jeho¾ bázioznaèíme fj0i; j1ig.14 Není to jediná pou¾ívaná mo¾nost, nìkteré algoritmy vyu¾ívají i prostoryvy¹¹í h dimenzí { trojdimenzionální prostory jsou napøíklad u¾iteèné pro korek i hyb [3℄, [10℄ èiv analogii tøístavové logiky.V kvantovém poèítaèi mù¾e qubit realizovat napøíklad èásti e s dvìma dobøe de�novanýmienergeti kými hladinami, èásti e se spinem 12 , foton, jeho¾ budeme sledovat polariza i, nebofoton v interferometru, který mù¾e putovat jednou ze dvou vìtví. Není v¹ak smyslem této prá epopisovat jakékoliv detaily realiza e kvantového poèítaèe.V populární literatuøe se setkáme s tvrzením, ¾e qubit mù¾e být ve stave h j0i a j1i þsou-èasnìÿ. Jedná se samozøejmì o vyjádøení my¹lenky superpozi e èi tvrzení, ¾e stavový prostor jevektorovým prostorem: existen e tì hto dvou bázový h stavù implikuje fyzikální smysl libovolnéjeji h nenulové lineární kombina e. Pro laika mù¾e být dále pøekvapivý dùsledek skuteènosti, ¾estavový prostor je komplexní: lineární kombina e, ve který h j0i a j1i jsou zastoupeny stejnì (vesmyslu pravdìpodobnosti namìøení pøi úplném mìøení v této bázi) mohou být j0i+ j1i, j0i� j1i,ale i j0i+ ij1i, èi na místì i mù¾e být libovolná jiná komplexní jednotka, a v¹e hny takto vznikléstavy jsou fyzikálnì odli¹né.V pøípadì jednoho qubitu se èasto uvádí pìkný pøíklad geometri ké reprezenta e projektiv-ního stavového prostoru. V¹e hny fyzikální stavy jednoho qubitu mù¾eme rozmístit na povr hjednotkové sféry (kulové slupky) zvané Blo hova sféra. Taková reprezenta e je výhodná z nìkolikadùvodù:{ v jednom pøedstavitelném obrázku jsou znázornìny v¹e hny paprsky v C 2 , tedy v¹e hnymo¾né þpomìryÿ dvou komplexní h èísel, nulový vektor je efektivnì vyøazen z úvahy,

14 Jedná se zároveň o nejjednodušší netriviální kvantový systém [3].20

{ ka¾dá unitární opera e na C 2 odpovídá a¾ na násobení urèitou komplexní jednotkou (globálnífází obrazu) nìjaké spe iální ortogonální transforma i v prostoru R3 , do kterého je tato sféravnoøena (tedy jen jejímu natáèení),{ prùseèíky libovolné pøímky pro házejí í støedem se sférou odpovídají dvìma kolmým vekto-rùm,{ pøi uva¾ování mati e hustoty místo stavový h vektorù se tato sféra zmìní pouze na kouli,její¾ povr h bude odpovídat mno¾inì èistý h stavù a vnitøek stavùm smí¹eným, støed budereprezentovat nejví e neurèitý stav 12I.Pøesto se Blo hova sféra uplatní spí¹e v jiný h oblaste h teorie kvantový h poèítaèù, napø.v korek i hyb. My ji k výkladu pou¾ívat nebudeme a pøípadné zájem e odká¾eme na [3℄.x y

zj0ij1i1√

2(j0i+ j1i) 1√

2(j0i � j1i)1√2(j0i+ ij1i)1√

2(j0i � ij1i)

Obr. 1: Blochova sféraStavový prostor n qubitù je, jak bylo øeèeno, tenzorovým souèinem stavový h prostorù jed-notlivý h qubitù. Má tedy dimenzi 2n a ka¾dý vektor v nìm by byl popsán 2n komplexními èísly(2n� 2 v projektivním prostoru). Poznamenejme v¹ak, ¾e tento projektivní prostor nemá známu¾ádnou podobnì názornou geometri kou reprezenta i jako Blo hovu sféru.Báze takového stavového prostoru tvoøená tenzorovými souèiny vektorù j0i a j1i se nazývávýpoèetní báze, o její h prv í h budeme mluvit jednodu¹e jako o bázový h vektore h nebo bázo-vý h stave h. Pojem bázové vektory roz¹íøíme i na situa e jiný h tenzorový h souèinù stavový hprostorù, u ni h¾ dopøedu uvedeme nìjakou pra ovní ortonormální bázi nebo budeme uva¾ovatbázi standardní.V následují í h paragrafe h budeme je¹tì pøíle¾itostnì bez upozornìní vyu¾ívat de imální zá-pis: na vnitøek ketu tvaru napø. j0101i, vzniklého ve smyslu paragrafu 1.3 násobným tenzorovýmsouèinem vektorù j0i a j1i, pohlédneme jako na zápis èísla ve dvojkové soustavì a nahradíme jejzápisem v soustavì desítkové: j5i. Toto znaèení je ve shodì se skuteèností, ¾e vektory j0 : : : 00i,j0 : : : 01i, j0 : : : 10i, : : :, j1 : : : 11i = j0i, j1i, j2i, : : :, j2n � 1i tvoøí ortonormální bázi prostoru(C 2)⊗n �= C 2n . 21

2.2 Pauliho mati eV následují ím textu se budeme pøíle¾itostnì setkávat s troji í mati známý h jako Paulihomati e [3℄, [4℄. Zaslou¾í si tedy v této kapitole malou vsuvku.Pauliho mati e jsou sadou tøí jednodu hý h mati 2�2, z ni h¾ ka¾dá je souèasnì hermitovskáa unitární a jako elek mají mnoho dal¹í h spoleèný h vlastností. V kvantové me hani e by homse s nimi setkali nejèastìji u popisu spinu èásti , pozdìji známý h jako þspin-12 èásti eÿ, kdejsou Pauliho mati e pøímo i jeji h lineární kombina e pou¾ívány jako pozorovatelné s pøímýmfyzikálním významem. Díky své elementaritì mají Pauliho mati e v¹ak pou¾ití mnohem ¹ir¹í.Pro nás bude dùle¾itý pøedev¹ím jeji h expli itní tvar�1 = �x = ( 0 11 0)�2 = �y = ( 0 �ii 0)�3 = �z = ( 1 00 �1); (2:1)v textu je budeme nazývat je¹tì jednodu¹eji jako X, Y a Z. Mezi Pauliho mati e se obèas øadíi jednotková mati e druhého øádu �0 = I, my ji v následují í h bode h v¹ak uva¾ovat nebudeme.Mezi nejdùle¾itìj¹í vlastnosti Pauliho mati patøí:{ druhá mo nina ka¾dé z ni h je jednotková mati e,{ ka¾dá má determinant �1, stopu 0 a vlastní èísla 1 a �1,{ ka¾dá hermitovská mati e 2 � 2 je reálnou lineární kombina í Pauliho mati a jednotkovémati ea jeji h komutaèní a antikomutaèní vlastnosti, které zde uvádìt nebude tøeba.Kromì zmínìného pøíle¾itostného pou¾ívání Pauliho mati v následují ím výkladu mají je¹tìdal¹í zajímavé souvislosti s tématem kvantový h algoritmù, pøesnìji s pøed hozím paragrafem:{ Ka¾dá mati e hustoty jednoho qubitu lze vyjádøit ve tvaru% = 12I + 3∑

i=1

ni�i; (2:2)kde (n1; n2; n3) je vektor v R3 se standardním skalárním souèinem mají í délku 1 nebomen¹í. Souøadni e tohoto vektoru pøímo odpovídají poloze v Blo hovì kouli s tím, ¾e èistéstavy jsou popsány právì jednotkovými vektory vyjadøují ími pøesnì polohu odpovídají íhostavového vektoru na pùvodní sféøe.{ Opera e X, Y , resp. Z mají na Blo hovì sféøe geometri ký význam rota e kolem os x, y,resp. z o 180◦. 22

2.3 Kvantová hradlaDal¹ím krokem k pøenesení my¹lenky klasi ký h digitální h algoritmù do kvantového svìtaje poskytnout kvantovou analogii logi ký h hradel15 a dal¹í h prvkù èísli ový h obvodù neboprogramù.Na kvantová hradla budeme pohlí¾et jako na základní stavební prvky, jeji h¾ kombina ímù¾eme sestavit po¾adovaný operátor pro èasový vývoj systému: ka¾dé z ni h bude odpovídatupravenému Hamiltoniánu, podle kterého se uva¾ovaný systém bude vyvíjet po nìjaký omezenýèasový interval.Kvantové algoritmy pak budeme popisovat i zakreslovat podobnì jako klasi ké logi ké ob-vody: stavový prostor systému n qubitù budeme znázoròovat jako n est vedou í h zleva doprava,na ni h¾ se budou provádìt opera e ve formì kvantový h hradel. Poøadí zleva doprava bude od-povídat poøadí, v jakém mají jednotlivá hradla pùsobit. Dále u ka¾dého qubitu musíme stanovitjeho vstupní hodnotu { stav pøed provedením algoritmu, a význam výstupní hodnoty { stavu pojeho provedení.Kvantové hradlo je tedy nìjaká unitární opera e pùsobí í na systém { èasto v¹ak na vìt¹inusystému s výjimkou nìkolika qubitù bude pùsobit triviálnì. Mluvíme pak o jedno-, dvou-, atøíqubitový h hradle h. Znaèky takový h hradel pak budeme v obvodu zakreslovat jen na linká hodpovídají í h pou¾itým qubitùm.Ka¾dému n-qubitovému kvantovému hradlu bude ve výpoèetní bázi stavového prostoru nebodaného podprostoru odpovídat unitární mati e øádu 2n. Podmínka unitarity plyne z postulátùkvantové me haniky uvedený h v první kapitole. Ka¾dá unitární mati e v¹ak naopak odpovídánìjakému myslitelnému èasovému vývoji [3℄.Pøi popisu kvantový h hradel budeme uva¾ovat jeji h pùsobení na bázové vektory stavo-vého prostoru zúèastnìného podsystému. Taková informa e je toti¾ ekvivalentní hledání popsanémati e a díky linearitì je postaèují í pro nalezení obrazu libovolného stavového vektoru.Nejjednodu¹¹í logi ké hradlo, které má pøímou kvantovou analogii, je not (nega e, inver-tor) { v klasi kém obvodu má jeden vstup a jeden výstup. Jestli¾e vstupní hodnotou je 0, jevýstupem 1 a naopak. V kvantovém svìtì by takovému hování odpovídalo jednoqubitové hradlopopsané mati í( 0 11 0) ;tedy Pauliho mati í X. Taková mati e je, jak ji¾ víme, unitární, podobnì jako ka¾dá mati elibovolného øádu, která se li¹í od mati e jednotkové pouze permuta í øádkù. Takové kvantovéhradlo se tedy skuteènì zavádí, nazývá se dle odpovídají í mati e hradlem X (pøípadnì not, n[10℄) a v kvantovém obvodu se znaèí dle obr. 2.X

Obr. 2: Zavedená značka pro hradlo X

15 Termínem logická hradla budeme rozumět hradla klasická.23

Kvantová me hanika v¹ak umo¾òuje de�novat jednoqubitový h hradel mnohem ví e. Mezidal¹í u¾iteèné pøíklady patøí hradla zpùsobují í fázový posun16 amplitudy j1i vùèi j0i:Z ( 1 00 �1)S ( 1 00 i )T ( 1 00 1√2(i+ 1))

Obr. 3: Nejčastější jednoqubitová hradla způsobující fázový posun,jejich označení v obvodu a maticeV¹imnìme si, ¾e mezi tìmito obvyklými hradly platí závislosti17 S = T 2, Z = S2, tatoredundan e v¹ak slou¾í ke zpøehlednìní zápisu. Pøipomeòme také, ¾e Z je dal¹í z Pauliho mati {{ mohli by hom pro úplnost uva¾ovat samozøejmì i jednoqubitové hradlo odpovídají í zbývají ímati i Y , my jej ale potøebovat nebudeme.Ke zmínìným hradlùm S a T se je¹tì setkáme s jeji h sdru¾enými operátory (èili dal¹ímihradly) S† a T †, které zpùsobují fázový posun s opaèným znaménkem (pøipomeòme, ¾e prounitární operátory je sdru¾ený operátor roven operátoru inverznímu).Veli e dùle¾ité je Hadamardovo hradlo, které zobrazuje bázové stavy na superpozi e j+i =

1√2(j0i+ j1i) a j�i = 1√

2(j0i � j1i):H 1p2 ( 1 11 �1)

Obr. 4: Hadamardovo hradlo, jeho označení v obvodu a maticeK Hadamardovu hradlu i oznaèením j+i a j�i se je¹tì mnohokrát vrátíme, nyní v souvislostis jednoqubitovými hradly poznamenejme jen jednu z jeho dùle¾itý h vlastností: H2 = I.Dal¹í logi ká hradla jsou dvouvstupová, výstupem je v¹ak jeden bit. Uvìdomme si, ¾e pøímoukvantovou analogii ¾ádného takového hradla nemù¾eme sestavit, musíme urèit význam obouqubitù po provedení opera e. Nejpøímìj¹í analogii má hradlo xor, jeho¾ pravdivostní tabulka jei1 i2 o0 0 00 1 11 0 11 1 0 .Tab. 1: Pravdivostní tabulka hradla xor.

Sloupce i budou označovat vstupní a o výstupní bity.

16 Řekneme pak, že hradlo mění relativní fázi amplitudy |1〉. Výrok, že dva vektory se liší v relativnífázi, je narozdíl od globální fáze závislý na volbě ortonormální báze, a dva takové vektory jsou fyzikálněrozdílné.17 Uvažované jako algebraické vztahy mezi stejně pojmenovanými maticemi.24

Pokud k výsledku tohoto hradla pone háme jednu ze vstupní h hodnot, získáme pravdivostnítabulku i1 i2 o1 o20 0 0 00 1 0 11 0 1 11 1 1 0 ,Tab. 2: Pravdivostní tabulka hradla cnotodpovídají í ji¾ mati i

1 0 0 00 1 0 00 0 0 10 0 1 0Tato mati e je opìt jako¾to permutaèní mati e jistì unitární, popisuje tedy nìjaké dvouqu-bitové kvantové hradlo. To se v literatuøe nazývá not [3℄ nebo n [10℄ a v kvantovém obvoduse znaèí dle obr. 5. XObr. 5: Různá zavedená značení hradla CNOTPísmeno v názvu hradla je zkratkou za þ ontrolledÿ nebo jednodu¹e þ ontrolÿ. Pokudodhlédneme od pùvodního zámìru zobe nit hradlo xor, v¹imnìme si, ¾e not se pro bázovéstavy skuteènì hová tak, ¾e v závislosti na hodnotì prvního qubitu buï aplikuje na druhý hradlonot nebo ne. Takto mù¾eme þovládatÿ libovolnou jinou opera i (ne nutnì jednoqubitovou):pøidání ovláda ího qubitu k hradlu reprezentovanému mati í U vytvoøí mati i blokového tvaru

( I 00 U ) :Unitarita mati e U se pøi takovém oblo¾ení za hovává.Èasto se setkáme je¹tì s dal¹ími zpùsoby de�ni e kvantový h hradel, které pøedvedeme napøíkladì not: stejnou informa i, která je obsa¾ena v uvedené pravdivostní tabul e nebo mati i,mù¾eme dále zapsat zpùsoby not = j00ih00j+ j01ih01j+ j11ih10j+ j10ih11j == j0ih0j+ j1ih1j+ j3ih2j+ j2ih3j == j0ih0j I + j1ih1j X (2:3)V¹imnìme si dùle¾ité skuteènosti, ¾e problém vykonat nìjakou opera i v závislosti na tom,jestli je øídi í qubit ve stavu j1i, zde neznamená na tomto qubitu provést mìøení. Je-li tedynapøíklad øídi í qubit v superpozi i j0i a j1i (není s øízeným provázán), dostane se druhý qubitpo provedení takové opera e do odpovídají í superpozi e obou výsledkù.25

Ve vztahu k poslednímu odstav i uveïme je¹tì zajímavou skuteènost zmínìnou v [3℄, ¾eþmìøení komutuje s ovládánímÿ. Následují í dva algoritmy jsou tedy ekvivalentní, jak se snadnopøesvìdèíme rozborem jednotlivý h pøípadù a jeji h pravdìpodobností:U U=Obr. 6: Komutace měření s řízenímV pravé èásti obrázku 6 jsou od mìøení dále èáry vytahovány dvojitì { takto budeme znaèitjeden bit klasi ké informa e. Místo øízeného hradla se zde tedy jedná jednodu¹e o provedení èineprovedení hradla U .Pro dvì nejznámìj¹í dvouvstupová logi ká hradla, and a or, stejný postup v¹ak nepomù¾e.Úvahami o tvaru výsledný h mati by hom se snadno ujistili, ¾e ani ¾ádným jiným zpùsobemnemù¾eme v pøípadì tì hto dvou hradel dosáhnout toho, aby na jednom výstupním qubitu bylpøímo výsledek. Kvantové algoritmy zde mají jinou odpovìï: lze navrhnout øízené kvantovéhradlo, kde øídi í qubit bude nahrazen výsledkem takové opera e. Pøíkladem je tøíqubitové Tof-foliho hradlo (viz tab. 3 a obr. 7), které na bázové stavy pùsobí tak, ¾e tøetí qubit zneguje právìtehdy, kdy¾ oba první (øídi í) qubity jsou ve stavu j1i (jeji h stav se v ka¾dém pøípadì za hová).i1 i2 i3 o1 o2 o30 0 0 0 0 00 0 1 0 0 10 1 0 0 1 00 1 1 0 1 11 0 0 1 0 01 0 1 1 0 11 1 0 1 1 11 1 1 1 1 0

Tab. 3: Pravdivostní tabulka Toffoliho hradla

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

Obr. 7: Značení a matice Toffoliho hradlaMù¾eme si v¹imnout, ¾e To�oliho hradlo je ekvivalentní tomu, kdyby hom pøidali k hradlu not je¹tì jeden øídi í bit (nezávisle na tom, ¾e jej ji¾ þobsahujeÿ { na not pohlí¾íme v tomtookam¾iku jako na obe né dvouqubitové hradlo). Proto se v literatuøe, napø. [10℄, setkáme i s ozna-èením n. 26

Tøíqubitová hradla jsou v kvantový h algoritme h, narozdíl od klasi ký h, také veli e roz¹í-øena. Dal¹ím èastým pøíkladem je øízená výmìna, Fredkinovo hradlo:18

1 0 0 0 0 0 0 00 1 0 0 0 0 0 00 0 1 0 0 0 0 00 0 0 1 0 0 0 00 0 0 0 1 0 0 00 0 0 0 0 0 1 00 0 0 0 0 1 0 00 0 0 0 0 0 0 1

Obr. 8: Značení a matice Fredkinova hradlaNakone uveïme obe nì n-qubitové hradlo známé jako Walsh-Hadamardova transforma e19([3℄, [11℄). Jedná se vlastnì o n Hadamardový h hradel pùsobí í h na ka¾dý z qubitù:... H⊗n = ...

HHH

Obr. 9: Walsh-Hadamardova transformaceJednoqubitové opera e provádìné na rùzný h qubite h komutují, nemusíme proto uva¾ovatjeji h poøadí. Obvykle není dùvod nazývat takto utvoøenou opera i novým kvantovým hradlem,ale Walsh-Hadamardova transforma e je tak èastá, ¾e se tento pojem ustálil.Mati e transforma e je, jak bylo øeèeno vý¹e, øádu 2n a její prvky je mo¾no obe nì vyjádøitvzor em Hi,j = 2−n2 (�1)|(i)2·(j)2|; i; j 2 f0; 1; : : : ; 2n � 1g; (2:4)kde exponent u �1 znamená Hammingovu váhu logi kého souèinu èísel i a j po bite h. Ham-mingova váha nezáporného èísla je poèet jednièek v jeho zápisu ve dvojkové soustavì.Mnoho kvantový h algoritmù zaèíná tak, ¾e v¹e hny qubity uva¾ovaného systému se pøedpo-kládají ve stavu j0i a jako první krok se na nì aplikuje právì Walsh-Hadamardova transforma e.Tím se systém dostane do stavu 1p2n

2n−1∑

i=0

jii; (2:5)který budeme nazývat rovno ennou superpozi í v¹e h bázový h stavù.18 Poznamenejme, že T. Toffoli i E. Fredkin pracovali na myšlence reverzibilního programování, nepřímo kvantových počítačů. Tato dvě zmíněná hradla jsou tedy opět kvantovou analogií jejich výsledků.19 Či pouze Hadamardova transformace. 27

2.4 Univerzální mno¾ina hradelDùle¾itá otázka je, jaká je podmno¾ina univerzální h hradel, tedy která hradla postaèí prosestavení elkù funkènì shodný h s libovolným jiným hradlem. Takový fakt je podstatný pøede-v¹ím v otáz e fyzikální realiza e obvodu. Pro logi ké obvody je známo, ¾e univerzální je hradlonand: i1 i2 o0 0 10 1 11 0 11 1 0Tab. 4: Pravdivostní tabulka hradla nandZákladní opera e not, and a or je toti¾ mo¾no sestavit následují ími zpùsoby:

1 =& &

=&

11

=

1

1

&

Obr. 10: Realizace hradel not, and a or pomocí nandUkazuje se, ¾e libovolné kvantové hradlo je mo¾no realizovat pomo í hradla not a jed-noqubitový h opera í [3℄. V [12℄ nebo [3℄ je pøíklad uveden na To�oliho hradle:= H T † T T † TT † H T †

TSObr. 11: Realizace Toffoliho hradla pomocí univerzálních hradelDùle¾itost To�oliho a Fredkinova hradla spoèívá v tom, ¾e kterékoliv z ni h spolu s mo¾nostípøedpokládat existen i pomo ný h qubitù pøipravený h v daný h stave h postaèuje pro simula ilibovolného klasi kého obvodu, jsou tedy univerzální v této oblasti. Výsledkem takové simula eje, ¾e øídi í qubit pro libovolnou opera i bude mo¾no nahradit nejen jednodu hými logi kýmiopera emi na ví e qubite h, ale výsledkem libovolné Booleovské funk e libovolného poètu pro-mìnný h. Takovou konstruk i budeme èasto vyu¾ívat. V následují ím paragrafu naznaèíme jejídetaily za pou¾ití To�oliho hradla.2.5 Simula e klasi ký h obvodù kvantovými hradlyAby hom mohli sestavit kvantový obvod, který by dával stejný výsledek jako daný klasi kýobvod pro ka¾dý bázový stav, je tøeba nahradit kvantovými analogiemi v¹e hny prvky, které28

se mohou v klasi kém pøípadì vyskytovat. Na základì univerzality logi kého hradla nand byse mohlo zdát, ¾e postaèí najít kvantovou analogii pro nìj, ale pov¹imnìme si ji¾ v obr. 10,¾e klasi ký obvod není tvoøen pouze logi kými hradly. V kvantové analogii je tøeba simulovatje¹tì rozdvojení vodièe, triviální není ani pøekøí¾ení dvou vodièù,20 takovou opera i je v¹ak v¾dymo¾no bez újmy vyne hat.Hradlo nand mù¾eme simulovat jediným To�oliho hradlem, pro výsledek budeme potøe-bovat vyu¾ít jeho tøetí (øízený) qubit. Tento qubit budeme uva¾ovat pøipravený ve stavu j1i:jestli¾e ve stave h j1i budou i oba øídi í qubity, To�oliho hradlo na nìm provede opera i not,èím¾ jej zmìní na j0i, v ostatní h tøí uva¾ovaný h bázový h stave h jej pone há ve stavu j1i, o¾je pøesnì po¾adované hování. jxijyij1ijxijyijx nand yi

Obr. 12: Simulace hradla nand pomocí Toffoliho hradlaV pøípadì, ¾e by øízený qubit byl pøipraven ve stavu j0i, stejnou úvahou by hom zjistili, ¾epo prù hodu To�oliho hradlem bude ve stavu jx and yi. Hradlo or mù¾eme sestavit za pomo iji¾ popsaného hradla nand dle obr. 10, kdy¾ místo not pou¾ijeme jednoqubitové hradlo X.Toto hradlo by bylo pro men¹í mno¾inu univerzální h hradel si e také mo¾no nahradit vhodnìpou¾itým To�oliho hradlem, ale pone háme jej v pùvodním stavu { je obe nì jednodu¹¹í pøed-pokládat v¹e hny pomo né qubity v obvodu pøipravené ve stave h j0i a do jiný h pomo ný hstavù je pøípadnì pøevést pomo í jednoqubitový h opera í.To�oliho hradlo s dvìma qubity pou¾itými jako pomo né nám umo¾ní realizovat i obdoburozdvojení vodièe: j1ijxij0ij1ijxijxi

Obr. 13: Simulace odbočky pomocí Toffoliho hradlaOdboèka funguje dle obr. 13 na bázové stavy, uká¾eme ale, ¾e zobe nìní pro obe nou super-pozi i jxi = �j0i+ �j1i neplatí: její pou¾ití v obr. 13 by mìlo za výsledek stav21j1i(�j00i+ �j11i) 6= j1i(�j0i+ �j1i)(�j0i+ �j1i): (2:6)20 V anglické literatuře se pro tyto dvě operace setkáme s označeními fanout a crossover.21 Jako důležitou poznámku uveďme, že se jedná o provázaný stav, přestože výchozí stav nebyl.29

Toto na první pohled nevinné zji¹tìní je dùsledkem obe nì platné vìty, ¾e zálohovat stavqubitu pomo í unitární opera e není mo¾né, vìty o zákazu klonování [3℄. Ve struènosti ji doká-¾eme:Pøedpokládejme, ¾e systém slo¾ený ze dvou komponent je ve stavu jxijsi a hledáme unitárnítransforma i U , která by systém pøevedla do stavu jxijxi pro ka¾dý stav jxi ze stavového prostoruprvního podsystému (jsi pova¾ujme za nìjaký univerzální vý hozí stav). Ne h» takové hováníje splnìno pro dva stavy, j i a j'i: U j ijsi = j ij iU j'ijsi = j'ij'i: (2:7)Z pøedpokladu platnosti obou rovností se musí rovnat i skalární souèiny jeji h levý h a pra-vý h stran. Skalární souèin (U j ijsi; U j'ijsi) je v¹ak díky unitaritì U roven (j ijsi; j'ijsi) =h j'ihsjsi = h j'i, zatím o skalární souèin pravý h stran je (j ij i; j'ij'i) = (h j'i)2. Abymohly platit souèasnì obì rovnosti, musí tak být skalární souèin j i a j'i roven buï 0 nebo 1 aji¾ platnost první rovnosti tak vyluèuje platnost druhé pro libovolné j'i kromì pøípadù j'i = j ia h j'i = 0.Jejím pøímým dùsledkem je opìt nemo¾nost zjistit ví e informa í o kvantovém stavu tak, ¾eby hom jej v¾dy pøed mìøením zálohovali, aby jeho stav bìhem kolapsu nebyl ztra en.Pro kvantovou simula i odboèky má vìta dùsledek, ¾e kdy¾ zálohujeme úspì¹nì stavy j0i aj1i, pro ¾ádnou jeji h netriviální lineární kombina i odboèka ji¾ nemù¾e fungovat, a» je konstru-ována jakkoliv.Upevnìním pouze prvního øídi ího qubitu ve stavu j1i se To�oliho hradlo zredukuje nadal¹í potøebné hradlo not. Pro zjednodu¹ení zápisu pøi pøepisu klasi ký h obvodù do kvantovéanalogie je v¹ak jednodu¹¹í mezi þelementárníÿ hradla zaøadit i not.V¹imìneme si, ¾e v ka¾dé èásti jsme museli zavést pomo né qubity pøipravené v nìjakémkonkrétním stavu. Èím ví e hradel mìl klasi ký obvod, tím obe nì ví e pomo ný h qubitù bybylo potøeba k jeho simula i na kvantovém poèítaèi. To mù¾e být znaèným problémem z hlediskafyzikální realiza e kvantového algoritmu, proto u konkrétní funk e mù¾eme uva¾ovat o jiný hzpùsobe h simula e ne¾ pouze dùsledného pou¾ívání tohoto postupu.Jakmile je simulaèní kvantový obvod sestaven, mù¾eme se ptát, jak se bude hovat, jestli¾emísto bázového stavu vyjdeme z nìjakého obe ného stavu. Celý vývoj stavu bìhem prùbìhu algo-ritmu je popsán jednou unitární opera í, platí tedy prin ip superpozi e a jestli¾e na vstupu bylajistá lineární kombina e bázový h stavù, získáme na výstupu lineární kombina i odpovídají í hvýsledkù (opìt jako¾to bázový h stavù), urèenou stejnými koe� ienty.Simulovaná funk e tak jistým zpùsobem spoèítá výsledky v¹e h pou¾itý h vstupù þnajed-nouÿ: je-li napøíklad kvantový algoritmus navr¾en tak, aby obrazem j0ij0i bylo j0ijf(0)i a obra-zem j1ij0i j1ijf(1)i pro nìjaké zobrazení f : f0; 1g ! f0; 1g, pøi vstupu 1√2(j0i+ j1i)j0i získámevýstup 1√

2(j0ijf(0)i+ j1ijf(1)i). Toto hování se nazývá kvantový paralelismus ([10℄, [3℄).Kvantový paralelismus v¹ak nemù¾eme vyu¾ít ke slibovanému ury hlení výpoètu pøímo.Na uvedeném pøíkladì vidíme, ¾e mìøením nemù¾eme získat obì funkèní hodnoty souèasnì:kdyby hom po algoritmu provedli úplné mìøení stavu, získali by hom pouze jeden z èitatelù, tedy30

pouze jeden z bodù 0 a 1 a funkèní hodnotu v nìm. Prin ip, který poskytuje vìt¹inì kvantový halgoritmù jeji h výhody oproti algoritmùm klasi kým, je interferen e. Detaily jejího vyu¾ití v¹akzávisí na konkrétním algoritmu, na pøíkladì se s ní setkáme v paragrafu 3.4.V minulém odstav i jsme pøedpokládali, ¾e pra ovní prostor je tvoøen jen qubity pøedstavu-jí ími vstup pro funk i a jedním qubitem jako místem pro ulo¾ení výstupu. Pro zaji¹tìní úèelupopsaného na kon i minulého paragrafu a ve smyslu první èásti tohoto v¹ak bude ve skuteènostipotøeba{ n vstupní h qubitù,{ m+ 1 pomo ný h qubitù, pøipravený h ve stavu j0i,{ 1 ílový qubit, na kterém budeme htít provést opera i øízenou výsledkem funk e.Mezi pomo nými qubity jsme zde my¹lenkovì vymezili poslední pro hodnotu funk e. Ne h»tedy poèáteèní bázový stav, zapsaný v rozdìlení na tyto ètyøi èásti, je jxij0ij0ijyi, kde x pøedsta-vuje vstup funk e. Po provedení náhradního kvantového obvodu za obvod poèítají í po¾adova-nou funk i se tento stav zmìní na jxijg(x)ijf(x)ijyi, kde jsme g(x) oznaèili výsledek pomo ný hopera í na první h m pomo ný h qubite h. V tomto okam¾iku mù¾eme provést libovolnou po-¾adovanou jednoqubitovou opera i na posledním qubitu øízenou posledním pomo ným qubitem.Pøedpokládejme, ¾e se jedná o X, výsledným stavem pak je jxijg(x)ijf(x)ijy � f(x)i.Pomo né qubity v¹ak obe nì brání jakékoliv kvantové interferen i výsledkù { aby k ní mohlodojít, musely by se jeji h hodnoty u v¹e h èitatelù shodovat, jinak by tyto èitatele byly nutnìvzájemnì ortogonální. Na poèátku algoritmu tomu tak bylo { v¹e hny pomo né qubity jsmejednotnì uva¾ovali ve stavu j0i. Uká¾eme tedy, ¾e postupem známým jako un omputation [3℄jsme s hopni je do tohoto stavu vrátit za za hování informa e o výsledku funk e.Ka¾dé kvantové hradlo je díky své unitaritì reverzibilní { z jeho výstupu je v¾dy mo¾nozískat zpìtnì a jednoznaènì vstupní stav. Libovolný obvod jsme tedy bìhem simula e nahradiliobvodem reverzibilním. V¹e hna hradla pou¾itá pro simula i klasi ký h obvodù { To�oliho, X apøípadnì not, mají naví vlastnost, ¾e toto pøevrá ení lze provést druhou aplika í tého¾ hradlana výstup (jeji h mati e ve standardní bázi jsou samy sobì inverzními). V¹e hna hradla pou¾itábìhem simula e je tedy mo¾no na stav jxijg(x)ijf(x)ijy�f(x)i pou¾ít znovu, v opaèném poøadí,pro získání koneèného po¾adovaného stavu jxij0ij0ijy � f(x)i.

31

Kapitola 3Kvantové algoritmyMinulá kapitola pøipravila základ, na nìm¾ mù¾eme stavìt kvantové algoritmy jako¾to al-goritmy pra ují í s registry sestavenými z qubitù a vyu¾ívají í prin ipy kvantové me haniky, azabývat se ji¾ jen jeji h spe i� kými vlastnostmi.Teorie kvantový h algoritmù se dìlí na nìkolik logi ký h elkù:{ návrh kvantový h algoritmù jako analogie k digitálním algoritmùm { realiza e výpoètù èialgoritmi ký h úloh za vyu¾ití kvantový h hradel,{ kvantové komunikaèní protokoly a kvantová kryptogra�e { vyu¾ití provázání èi vlastnostíkvantového mìøení pro pøenos informa e,{ kvantové algoritmy pro korek i hyb { bránìní negativního vlivu okolí na prùbìh vý¹e uve-dený h algoritmù v neizolovaný h fyzikální h systéme h,{ matemati ká teorie kvantové informa e a teorie kvantové slo¾itosti,{ úz e souvisejí í problematika experimentální realiza e kvantový h poèítaèù.Ve v¹e h tì hto partií h bylo ji¾ dosa¾eno podstatný h pokrokù. Tím se problematika kvan-tový h algoritmù stala natolik rozsáhlou, ¾e není v mo¾noste h této prá e se zabývat ka¾dýmz tì hto bodù. Ve skuteènosti se ve zbytku textu budeme zabývat pouze prvním z ni h, který jepod pojmem kvantové algoritmy nejèastìji uva¾ován.Kvantové algoritmy zaèaly být detailnì zkoumány poté, o se na nìkolika pøíklade h ukázalo,¾e mají v urèitý h úlohá h oproti digitálním algoritmùm poten iál dojít k výsledku s výraznìkrat¹í èasovou slo¾itostí. Nejdùle¾itìj¹í a nejznámìj¹í z tì hto pøíkladù je Shorùv algoritmus profaktoriza i èísel (1994), øe¹í í tento problém v èase polynomi kém vzhledem k dél e vstupu. Vesvìtì digitální h algoritmù pøitom nejsou známy algoritmy vy¾adují í krat¹í ne¾ exponen iálníèas. Shorovì algoritmu vìnujeme nìkolik krátký h paragrafù, ale s upozornìním, ¾e se nejednáo hlavní èást prá e a tak tyto úseky textu podávají pouze zbì¾ný náhled na klíèové body postupu.Dal¹í milník v kvantový h algoritme h byl Groverùv algoritmus pro vyhledávání v nesetøí-dìné databázi (1996). Ten si e oproti klasi ké obdobì nabízí pouze polynomi ké zkrá ení èasovéslo¾itosti, zde v¹ak je zøejmé, ¾e ¾ádný digitální algoritmus nemù¾e takové ry hlosti dosáhnoutji¾ z prin ipu úlohy. Vyhledáva í algoritmy jsou hlavním ílem této prá e, Groverovì algoritmuse proto vìnuje elá pøí¹tí sek e.Pro úvod kapitoly byl v¹ak zvolen jeden pìkný pøíklad z jiné oblasti, kvantový komunikaèníprotokol známý pod názvem kvantová teleporta e.3.1 Kvantová teleporta eKvantová teleprota e je algoritmus, na nìm¾ pøedvedeme prakti ký pøíklad kvantového ob-vodu a nìkteré mo¾nosti a prin ipy, se kterými se v kvantový h algoritme h setkáváme.32

Uvádìný název je v¹ak bohu¾el také pøíkladem znaèné populariza e terminologie. Tentoalgoritmus je toti¾ urèen k pøenesení libovolné hodnoty jednoho qubitu z jednoho podsystému najiný bez nutnosti pøenosu kvantové informa e mezi tìmito dvìma èástmi zkoumaného systému.Tuto my¹lenku brzy upøesníme, ale uvìdomme si, ¾e se ani vzdálenì nejedná o ¾ádné pøená¹eníobjektù v prostoru.Je jisté, ¾e dle intuitivní pøedstavy by bylo pro rekonstruk i qubitu nutno pøenést nekoneènémno¾ství klasi ké informa e (stav má dva reálné stupnì volnosti), a víme, ¾e naví tuto informa inemáme mo¾nost získat mìøením. Kvantová teleporta e umo¾òuje vyu¾ít provázání tak, ¾e prouskuteènìní pøenosu kvantového stavu postaèí stranám pøedat si pouhé dva klasi ké bity.HX Z

j ij�00i j iObr. 14: Kvantová teleportacePøedstavme si kvantový obvod podle obr. 14. První dvì èásti e jsou umístìny u jednohopozorovatele, který s nimi tak mù¾e provádìt opera e, se kterými jsme se seznámili ve druhések i, tøetí èásti e je umístìna u druhého pozorovatele. První èásti e je v libovolném stavu�j0i + �j1i, který h eme pøenést na tøetí èásti i a pøedat tak druhému z pozorovatelù, tøetí adruhá èásti e jsou spolu pøipraveny v provázaném stavu j�00i = 1√

2(j00i + j11i). Popi¹me, jakse systém vyvíjí, matemati ky: pùvodní stav jej 0i = (�j0i+ �j1i) 1p2(j00i+ j11i) = 1p2(�j000i+ �j011i+ �j100i+ �j111i): (3:1 a)Po první opera i not pakj 1i = 1p2(�j000i+ �j011i+ �j110i+ �j101i): (3:1 b)Hadamardùv operátor pùsobí í na první èásti i má výsledekj 2i = �2 (j000i+ j100i+ j011i+ j111i) + �2 (j010i � j110i+ j001i � j101i): (3:1 )Nyní pouze seskupme èleny se stejnými hodnotami prvního a druhého qubitu:j 2i = 12 (j00i(�j0i+ �j1i) + j01i(�j1i+ �j0i) + j10i(�j0i � �j1i) + j11i(�j1i � �j0i)) : (3:1 d)Jestli¾e tedy jako dal¹í krok provedeme mìøení na podsystému první h dvou èásti , nastanekolaps vlnové funk e do jednoho z èitatelù. Na první h dvou èásti í h namìøíme nìkterou zev¹e h ètyø kombina í 0 a 1, tøetí èásti e se tak dostane do jedné z odpovídají í h kombina í33

j0i a j1i, pøièem¾ tento mezistav, jak by hom okam¾itì ovìøili, poslední dvì opera e na základìvýsledkù obou mìøení v ka¾dém pøípadì þopravíÿ do správného tvaru.Jak uvádí [3℄, kvantová teleporta e nepopírá ani pøedpoklad pøená¹ení informa e ry hlostívìt¹í ne¾ , ani vìtu o nemo¾nosti kopírování kvantového stavu. Ry hlost pøenosu stavu je ome-zena ry hlostí klasi kého komunikaèního kanálu, kterým musíme pøenést ke druhému pozorovatelidva bity informa e { tøetí qubit sám je do té doby z ela nepou¾itelný (je jako¾to jedna stranaprovázané dvoji e ve z ela neurèitém stavu). Odpovìdí na druhou otázku pak je, ¾e po provedeníalgoritmu neexistují dvì kopie pùvodního stavu { první dva qubity skonèí v bázový h stave h.Tento pøíklad mìl v¹ak slou¾it pøedev¹ím jako ukázka, jak málo intuitivní hování kvantovéhoalgoritmu mù¾e být. V¹imnìme si napøíklad, ¾e a¾ na poslední dvì opera e zùstávala tøetí èásti ez ela netknuta a do jednoho ze ètyø stavù vý¹e ji skuteènì dostalo þvytknutí ze závorkyÿ. Dal¹ízajímavá a ménì obvyklá opera e je aplika e Hadamardova hradla tìsnì pøed mìøením, kdy¾ doté doby byl qubit v bázovém stavu.3.2 Shorùv algoritmusShorùv algoritmus [13℄ je bezesporu nejpopulárnìj¹ím kvantovým algoritmem. Jeho úèe-lem je øe¹ení problému faktoriza e èísel (jeji h rozkladu na prvoèíselné èinitele, v jednodu¹¹ípodobì v¹ak pouze nalezení alespoò jednoho netriviálního dìlitele èísla), dùle¾itého pøedev¹ímv mnoha odvìtví h poèítaèového zabezpeèení. Mno¾ství ¹ifrova í h algoritmù toti¾ spoléhá nafakt, ¾e ve¹keré známé klasi ké algoritmy faktoriza e èísel mají exponen iální èasovou slo¾itost(tzn. poèet matemati ký h opera í potøebný k jeji h prùbìhu roste zhruba geometri kou øadouv závislosti na dél e vstupu, která je zde de�nována jako poèet èísli n faktorizovaného èísla N).Takové algoritmy se obe nì nazývají þobtí¾néÿ, proto¾e i s malým zvý¹ením délky vstupu mù¾evzrùst potøebná doba k øe¹ení o nìkolik øádù a tak spolehlivì pøedstihnout pøedpokládaný vývojte hniky a¾ do nedohledné doby. Obe nì ka¾dý algoritmus s exponen iální èasovou slo¾itostíje pova¾ován za nepou¾itelný v pøípade h, kdy délka vstupu není expli itnì omezena nìjakoumalou konstantou, a pro øe¹ení takový h problémù jsou vyhledávány algoritmy s polynomiálníslo¾itostí.V pøípadì faktoriza e èísel do souèasné doby nebyl podán teoreti ký dùkaz o tom, ¾e ¾ádnýnekvantový algoritmus s polynomiální èasovou slo¾itostí nemù¾e existovat [3℄, obe nì je ale takovétvrzení pova¾ováno za veli e pravdìpodobné. Nalezení takového algoritmu dosud alespoò odoláváv¹em pokusùm.Peter W. Shor v¹ak ukázal na pøímém pøíkladu, ¾e polynomiální èasové slo¾itosti je mo¾nodosáhnout pou¾itím kvantový h algoritmù. (V kvantový h algoritme h je èasová slo¾itost de�-nována pomo í potøebného poètu univerzální h kvantový h hradel, uvedený h v paragrafu 2.4.)Taková þhrozbaÿ pro poèítaèovou kryptogra�i zvedla vlnu zájmu o studium kvantový h algo-ritmù, které do té doby byly spí¹e pova¾ovány za okrajovou oblast výzkumu pro men¹í skupinuteoreti ký h fyzikù a informatikù.Do detailù teorie slo¾itosti v rám i této prá e ví e zasahovat nebudeme. Øeknìme jen, ¾einforma e, zda algoritmus má polynomiální èasovou slo¾itost èi nemá, je primární; nejmen¹í dosa-¾itelný stupeò polynomu, pou¾itelného pro horní odhad, je pak a¾ mìøítkem hrubého porovnání34

dvou polynomiálnì slo¾itý h algoritmù, a teprve na dal¹ím místì je pøesnìj¹í spe i�ka e odhadupomo í komplikovanìj¹í h funk í jako log n, pøípadnì pak konstanta úmìrnosti. Ve smyslu tì htopravidel uká¾eme spe i�ka i slo¾itosti Shorova algoritmu a¾ na kon i bez hlub¹ího vysvìtlení apro zajímavost.Shorùv algoritmus vy hází nekvantového algoritmu,22 který pøevádí problém nalezení netri-viální h dìlitelù èísla na problém hledání periody eloèíselné posloupnosti. Hledání periody jeøe¹eno aplika í diskrétní Fourierovy transforma e na vzorek prùbìhu posloupnosti a právì Fou-rierova transforma e je jediným prvkem elého postupu, který zpùsobuje v klasi kém algoritmuexponen iální èasovou slo¾itost. Hlavní pøínos Shorovy prá e je tedy pøedvedení, jak je mo¾no re-alizovat kvantovou obdobu diskrétní Fourierovy transforma e pomo í univerzální h kvantový hhradel, jeji h¾ poèet je polynomi ky závislý na dél e vstupu.Kvantová Fourierova transforma e má pak nìkolik dal¹í h vyu¾ití, které popsal Shor i dal¹ívìd i. Narozdíl od faktoriza e èísel se v¹ak jedná o øe¹ení ví e teoreti ký h matemati ký h pro-blémù, napø. diskrétního logaritmu (odpovídají í algoritmus je popsán rovnì¾ ve [13℄).Ne¾ popí¹eme kvantový algoritmus pro diskrétní Fourierovu transforma i, podívejme se nastruèný pøehled zbytku algoritmu [14℄:Posloupnost fakg+∞k=0, její¾ budeme zkoumat periodu, se konstruuje dle vzoruak = rk mod N; (3:2)kde r je libovolnì zvolené pøirozené èíslo nesoudìlné s N (tedy mají í s ním nejvìt¹í spoleènýdìlitel rovný 1). Snadno by se ukázalo, ¾e je postaèují í èíslo r volit z rozmezí 2 a¾ N�1. Mù¾emejej zvolit náhodnì a podmínku nejmen¹ího spoleèného dìlitele ovìøit. Jestli¾e vyjde jiný ne¾ 1,je netriviálním dìlitelem èísla N a úlohu v jednodu¹¹í formula i, uvedené na zaèátku paragrafu,mù¾eme pova¾ovat za vyøe¹enou.Dal¹ím krokem je nalezení periody posloupnosti fakg. Periodi ita takové posloupnosti plynez faktu, ¾e její zadání lze pøepsat v rekurentním tvaruak = rak−1 mod N; k > 1; (3:3)vyu¾ívají ím pouze jeden pøed hozí èlen, a ¾e obor hodnot posloupnosti je koneèná mno¾ina(pøirozená èísla omezená na interval h1; N � 1i).23 Jak bylo uvedeno vý¹e, pro nalezení periodyse bude vyu¾ívat diskrétní Fourierova transforma e. Uvidíme, ¾e pro realiza i v kvantovém al-goritmu bude vhodné zkoumaný vzorek zvolit jako 2q první h hodnot posloupnosti pro nìjaképøirozené èíslo q. Ukazuje se, ¾e vhodná je taková volba q, aby platiloN2 � 2q < 2N2: (3:4)Nalezenou periodu24 posloupnosti oznaème p. Algoritmus je dále nepou¾itelný, pokud tatoperioda je li hé èíslo { v takovém pøípadì se musí zkusit znovu s jinou volbou r. V pozitivnímpøípadì se budeme zabývat hodnotou ap2. Ta musí splòovat kongruen iap = a0 = 1= (ap

2

)2 mod N (ap2

)2 � 1 mod N: (3:5)22 Tento algoritmus byl v době uvedení Shorova algoritmu již znám ([13], [14]).23 Ještě by bylo třeba provést důkaz, že opakování bude „platitÿ již od prvního členu. Ten uvádětnebudeme, řekneme jen, že v něm se využívá předpokladu nesoudělnosti čísel r a N .24 Pod pojmem perioda budeme zásadně rozumět nejmenší periodu.35

Rovnost ap2= 1 by byla ve sporu s tím, ¾e periodou posloupnosti je p. Dal¹í triviálnípøípad splnìní kongruen e by mohl nastat, pokud ap

2= N � 1. Takový výsledek je v¹ak propokraèování algoritmu nevhodný a znamenal by opìt návrat na zaèátek k jiné volbì r. Budemetedy pøedpokládat, ¾e ap

2nemá ani jednu z tì hto krajní h hodnot.K zakonèení algoritmu se vyu¾ívá kongruen erp � 1 mod Nrp � 1 = (r p

2 � 1) (r p2 + 1) � 0 mod N: (3:6)Z té plyne, ¾e N je dìlitelem uvedeného souèinu. Proto¾e v¹ak nedìlí ani jeden z èinitelù, o¾ jeekvivalentní omezení hodnot ap

2, provedenému v minulém odstav i, musí nutnì mít netriviálníhospoleèného dìlitele s ka¾dým z ni h.Prùbìh algoritmu uká¾eme na pøíkladì: zvolme N = 143 a r = 10. První h nìkolik èlenùposloupnosti fakg+∞k=0 je v tomto pøípadì1; 10; 100; 142; 133; 43; 1; 10; 100; : : : ; (3:7 a)perioda je tedy p = 6. První kontrola, aby p bylo sudé èíslo, probìhne v poøádku, ale ap

2= a3 =142 je rovno nepovolené hodnotì N � 1.Èíslo r bylo tedy zvoleno nevhodnì. Pokusme se proto opakovat výpoèet s jinou náhodnouvolbou, napø. r = 8. S ní jsou poèáteèní èleny posloupnosti1; 8; 64; 83; 92; 21; 25; 57; 27; 73; 12; 96; 53; 138; 103; 109; 14; 112; 38; 18; 1; 8; : : : (3:7 b)a platí p = 20 a a10 = 12. Obì kontroly tedy probìhnou úspì¹nì a díky tomu víme, ¾e 143má netriviální nejmen¹í spoleèné dìlitele s èísly 12� 1. Ty v¹ak ji¾ tvoøí pøímo jeho prvoèíselnýrozklad: 143 = 11 � 13.Je zøejmé, ¾e pokraèování algoritmu od nalezení periody posloupnosti nevy¾aduje ¾ádné po-stupy z kvantový h algoritmù { realiza e Shorova algoritmu tak bude sestávat z kvantové a kla-si ké èásti. Kvantovou èást nebudeme i pøes mo¾nosti simula e libovolného klasi kého algoritmuzbyteènì roz¹iøovat do oblastí, kde klasi ká výpoèetní jednotka poslou¾í lépe.V následují ím paragrafu, který je vyèlenìn pro popis kvantové Fourierovy transforma e,v¹ak uvidíme, ¾e nìkteré èásti výpoètu budeme muset nutnì do kvantového algoritmu zaøadit.3.3 Kvantová Fourierova transforma eKvantová Fourierova transforma e je analogií diskrétní Fourierovy transforma e. Ètenáøbude pravdìpodobnì seznámen s klasi kou Fourierovou transforma í, známou pod vzor em (ménìobvyklá znaménková konven e pøevzata z [15℄)F (!) = 1p2� ∫ +∞−∞

e2πiωtf(t)dt; (3:8)platným pro Lebesgueovsky integrovatelné funk e f , a se skuteèností, ¾e dle tohoto pøedpisu jemo¾no spojitì dode�novat Fourierùv-Plan herelùv operátor, izometri ký na prostoru L2(R;dx)[2℄. 36

Diskrétní Fourierova transforma e je oproti tomu lineární operátor na C n : n-ti i èísel faign−1i=0pøiøazuje n-ti i fAign−1i=0 podle pøedpisuAj = 1pn n−1∑

k=0

e 2πijkn ak (3:9)Mati e takového operátoru ve standardní bázi má prvkyFjk = e 2πijk

n ; j; k = 0; 1; : : : ; n� 1: (3:10)Snadno ovìøíme, ¾e F je unitární: urèeme toti¾ prvky mati ového souèinu(FF †)jk = n−1∑

l=0

FjlFlk = 1n n−1∑

l=0

e 2πijln e− 2πilk

n = 1n n−1∑

l=0

(e 2πi(j−k)n

)l : (3:11 a)Výsledkem poslední úpravy je èásteèný souèet geometri ké øady. Pro pøípad j 6= k lze pou¾ítvzore 1n n−1∑

l=0

(e 2πi(j−k)n

)l = 1� e 2πi(j−k)n nn(1� e 2πi(j−k)

n

) = 0; (3:11 b)proto¾e e2πi(j−k) = 1. Jestli¾e j = k, je koe� ient geometri ké øady e0 = 1 a platí tak(FF †)jj = 1n n−1∑

l=0

1 = 1; (3:11 ) elkovì tedy (FF †)jk = Æjk; (3:11 d) o¾ jsme htìli dokázat.Pro úèely Shorova algoritmu tak mù¾eme uva¾ovat kvantové hradlo F , které bude pùsobitna q qubite h podle odpovídají ího pøedpisuF jki = 1p2q

2q−1∑

j=0

e 2πijk2q jji : (3:12)obraz obe né superpozi e j i =∑2q−1

j=0 �kjki pak budeF j i = 2q−1∑

k=0

�k

1p2q

2q−1∑

j=0

e 2πijk2q jji = 2q−1∑

j=0

1p2q

2q−1∑

k=0

e 2πijk2q ak

jji (3:13)v pøímé analogii s (3.9).Ref. [10℄ ukazuje, jak jsme takovou unitární opera i s hopni realizovat pomo í jedno- advouqubitový h hradel: zavádí se zde hradlo Aj jako Hadamardovo hradlo pùsobí í na j-tý qubita Bjk jako hradlo pùsobí í na j-tý a k-tý qubit tak, ¾e zmìní o π2j−k relativní fázi tì h bázový hstavù, ve který h oba tyto qubity jsou ve stavu j1i. Pro j� k = 1, resp. 2 se tak napøíklad jednáo hradla S, resp. T , zavedená v paragrafu 2.3, pùsobí í na k-tý qubit a øízená j-tým (uvìdommesi v¹ak, ¾e v takovém pøípadì není rozdíl v tom, kdy¾ oznaèení qubitù prohodíme).37

Hradlo F získáme, jestli¾e aplikujeme následují í sérii tì hto opera í:25A1B12B13 : : : B1,qA2B23 : : : B2,qA3 : : : Aq−1Bq−1,qAq (3:14)následovanou výmìnou hodnot prvního a q-tého, druhého a (q� 1)-tého, . . . qubitu. Pokud v¹akbudeme hned po aplika i F htít provést úplné mìøení stavu ve výpoèetní bázi a pokraèovatklasi kým výpoètem, je zbyteèné tyto výmìny zahrnovat do kvantového poèítaèe: postaèí provéstmìøení po zmínìné sérii opera í a namìøené stavy jednotlivý h bitù pøeèíst v opaèném poøadí.Skuteènost, ¾e (3.14) vede k ry hlé Fourierovì transforma i, zde ji¾ nebudeme hloubìji pro-bírat { tento paragraf je my¹len jako skuteènì struèné nahlédnutí na prùbìh Shorova algoritmu.Poznamenejme pouze, ¾e se jedná o z ela pøímou kvantovou interpreta i Cooleyho-Tukeyho im-plementa e ry hlé Fourierovy transforma e (FFT), která je detailnì popsána v [15℄ nebo [16℄.Kvantová me hanika v¹ak klade na takovouto implementa i diskrétní Fourierovy transfor-ma e dvì silné nevýhody:{ neexistuje obe ný zpùsob, jak þulo¾itÿ do poèáteèního stavu analyzovaný prùbìh,{ podobnì není mo¾né zjistit výsledný prùbìh amplitud.Následují í paragraf ukazuje, jak k tìmto dvìma bodùm pøistupuje Shorùv algoritmus.3.4 Fourierova transforma e ve Shorovì algoritmuKvantová èást Shorova algoritmu pùsobí na dvou registre h qubitù { tedy uva¾ujeme stavovýprostor vzniklý tenzorovým souèinem ze stavový h prostorù q a s qubitù, kde q je èíslo de�novanév pøedminulém paragrafu a s je dostateènì velké, aby N < 2s. Poèáteèní stav se pro snaz¹íimplementa i volí tvaru j0ij0i.Fourierova transforma e je ve Shorovì algoritmu aplikována na zvlá¹tním vstupu, který mátvar j0i = 1p2q

2q−1∑

k=0

jkijaki: (3:15)Pøitom transforma e se provádí na první sadì q qubitù, která v této superpozi i reprezentujeindex posloupnosti.Aby se systém dostal do tohoto stavu z poèáteèního stavu j0ih0j, aplikuje se nejprve Walsh--Hadamardova transforma e na prvním registru, který jí pøevedeme do stavuj1i = 1p2q

2q−1∑

k=0

jkij0i: (3:16)Vzhledem k nemo¾nosti do tohoto stavu þdoplnit zvenkuÿ pøedpøipravené hodnoty posloup-nosti je bude tøeba spoèítat v prùbìhu algoritmu pomo í prin ipu kvantové simula e obvodu,kterým by hom je poèítali na klasi ké výpoèetní jednot e. Tato èást je mnohem nároènìj¹í ne¾25 Uvažováno směrem zprava doleva jako skládání operátorů.38

Fourierova transforma e, a to i v èase, i v potøebì pomo ný h qubitù [14℄. Ty musí být v uva-¾ovaném systému tedy také k dispozi i, ale díky pøedpokladu jeji h návratu do pùvodní h stavùj0i po výpoètu je jako souèást stavového prostoru nemusíme uva¾ovat.Pøíklad realiza e výpoètu hodnot posloupnosti potøebné pro Shorùv algoritmus pomo í kvan-tový h hradel je uveden v [17℄.Jestli¾e tedy sestrojíme náhradní kvantový algoritmus, který vstup jkij0i transformuje navýstup jkijaki, staèí pøivést na vstup superpozi i (3.16) a vyu¾ít tak kvantový paralelismus,aby hom na výstupu získali po¾adovanou superpozi i (3.15).Na tuto superpozi i tedy budeme aplikovat kvantový operátor F . Dle rovni e (3.12) se tímstav zmìní na j2i = 12q

2q−1∑

k=0

2q−1∑

j=0

e 2πijk2q jjijaki = 12q

2q−1∑

j=0

2q−1∑

k=0

e 2πijk2q jjijaki: (3:17)Díky tomu, ¾e posloupnost fakg+∞k=0 je periodi ká s periodou p < N a 2q � N2, ka¾dá dosa-¾ená hodnota ak se ve vzorku vyskytne alespoò N -krát. Tato skuteènost nyní umo¾ní kvantovouinterferen i: pravdìpodobnost namìøení stavu jji pøi mìøení na prvním podsystému ve výpoèetníbázi bude

∥

∥

∥

∥

∥

∥

12q

2q−1∑

k=0

e 2πijk2q jaki∥∥∥∥

∥

∥

2; (3:18)kde koe� ienty e 2πijk2q pro taková k, pro která se shodují ak, mohou v závislosti na j interferovatkonstruktivnì i destruktivnì.Ukazuje se, ¾e tato interferen e výraznì potlaèí pravdìpodobnost namìøení v¹e h j kromìtakový h, které le¾í v blízkém okolí26 eloèíselný h násobkù èísla 2qp , kde p je hledaná perioda[10℄, [13℄. Pravdìpodobnost namìøení ¹patného výsledku není nulová, pokud tento zlomek není elé èíslo, ale je dostateènì malá, aby hom opakovaným prùbìhem algoritmu mohli eliminovatmo¾nost hyby.Kvùli vlastnostem kvantového mìøení v¹ak nemù¾eme ovlivnit, který z tì hto násobkù do-staneme. Opakovaným prùbìhem algoritmu v¹ak získáme mno¾ství tì hto èísel ji¾ postaèují íke zji¹tìní konstanty p.V¹imnìme si, ¾e výsledky elého prùbìhu algoritmu mají pravdìpodobnostní harakter. Jakoèasovou slo¾itost v takový h pøípade h musíme uva¾ovat poèet opera í potøebný h k pøekonáníjisté pøedem dané hrani e pravdìpodobnosti úspì hu { v teoreti ké informati e se uva¾uje hra-ni e 23 .Shor ve svém èlánku udává odhady èasové slo¾itosti jednotlivý h èástí postupu. Dùle¾itá jepøedev¹ím informa e, ¾e kvantová Fourierova transforma e má slo¾itost O(q2) = O(n2) (pøipo-meòme, ¾e n je délka vstupu, tedy úmìrná logN), o¾ by hom mohli odhadnout z uvedenéhorozpisu na øetìze jedno- a dvouqubitový h hradel (ta jsou elementární nebo je lze nahradit kon-stantním poètem elementární h hradel, staèí je tedy spoèítat). Tato slo¾itost vynásobená odhady,kolikrát je pro dosa¾ení dostateèné pravdìpodobnosti prùbìh kvantového algoritmu opakovat,dává koneèný odhad O (n2 logn log logn).

26 Největší pravděpodobnost mají celá čísla těmto zlomkům nejbližší, již vzdálenost 1 od této zao-krouhlené hodnoty znamená silný pokles pravděpodobnosti.39

Kapitola 4Groverùv algoritmusV této a následují í sek i popí¹eme dva základní algoritmy pou¾itelné pro øe¹ení zadáníoznaèovaného jako vyhledávání v nesetøídìné databázi.V prvním paragrafu nejprve spe i�kujeme, jak toto zadání bude znít, a shrneme mo¾nostijeho øe¹ení v klasi kém pøípadì. Uvedeme skuteènost, ¾e kvantové algoritmy umo¾òují pøi øe¹enítohoto problému dosáhnout výrazného èasového ury hlení, o¾ uká¾eme v následují í h paragra-fe h na konkrétní h pøíklade h.Ve zbytku kapitoly popí¹eme histori ky první vyhledáva í algoritmus, jeho¾ autorem je LovK. Grover (1996). V jednotlivý h paragrafe h je detailnì matemati ky prozkoumám prùbìh algo-ritmu, diskutovány nìkteré dùle¾ité mezní pøípady a nìkteré od hylky od pùvodního algoritmu,které mohou pomo i k jeho pou¾itelnosti i pøi upraveném zadání nebo zvý¹it jeho efektivitu.4.1 Zadání vyhledáva ího algoritmuJe dána nìjaká koneèná, oèíslovaná mno¾ina prvkù a rozhodova í funk e (orákulum), vázanápodmínkou, ¾e její hodnota je 0 na v¹e h prv í h této mno¾iny kromì jednoho, ve kterém jehodnota funk e 1. Tento prvek budeme nazývat oznaèeným a úkolem je samozøejmì opakovanýmidotazy na funkèní hodnotu najít jeho index. Mno¾ina mù¾e být oboha ena nìjakou dodateènoustrukturu, mù¾e tedy tvoøit napøíklad graf, ale tato struktura neposkytuje ¾ádnou informa iusnadòují í nalezení øe¹ení, napøíklad ve smyslu jeho þblízkostiÿ.Jako názorný pøíklad aplika e tohoto zadání se uvádí (viz napø. [18℄, [19℄) obrá ené hledánív telefonním seznamu: máme dáno telefonní èíslo, o kterém víme, ¾e bude patøit nejvý¹e jednomuèlovìku, a h eme najít tento odpovídají í záznam. Seznam je setøídìn podle abe edy, ale to námnijak nepomù¾e, pokud napøíklad najdeme jméno, jeho¾ èíslo se li¹í jen v jediné èísli i, odhadnout,kde máme hledat dále.V¹imnìme si v¹ak, ¾e vyslovené zadání nepøedpokládá pøítomnost ¾ádného objemného pa-mì»ového média, které by hom oèekávali pod pojmem databáze. Rozhodova í funk e tak musíposkytnout odpovìï pouze na základì indexu prvku a ve¹keré dal¹í informa e musí být ulo¾enyve zpùsobu jejího výpoètu.Bez pou¾ití kvantový h algoritmù tak nezbývá jiná mo¾nost, ne¾ pro házet postupnì v¹e hnypolo¾ky a kontrolovat ka¾dou pro shodu. Vzhledem k harakteru tohoto zadání nepøinese vùbe ¾ádné vylep¹ení ani pou¾ití sto hasti ké metody, tj. náhodného výbìru dal¹ího prvku místopro házení po øadì. Uvìdomme si, ¾e to je ekvivalentní pro házení po øadì po pouhém náhodnémproházení prvkù. Vzhledem k tomu, ¾e algoritmus se zastaví v okam¾iku, kdy náhodnì najdemehledaný prvek, mù¾e mít odhad poètu potøebný h krokù také jen pravdìpodobnostní harakter.V takový h pøípade h se u algoritmù uvádí prùmìrný poèet krokù a poèet krokù v nejhor¹ímpøípadì, které pro tento postup mù¾eme odhadnout i intuitivnì pøibli¾nì na N=2, resp. N (N jepoèet prvkù tvoøí í h databázi). 40

V následují í h paragrafe h této kapitoly a v kapitole následují í uká¾eme, ¾e rùzné kvantovéalgoritmy mají s hopnost za vyu¾ití kvantové interferen e øe¹it tuto úlohu v èase (tedy poètudotazù na orákulum) úmìrném druhé odmo ninì z poètu prvkù N a naví s vlastností, ¾e poèetkrokù bude pro danou velikost seznamu nemìnný.4.2 Popis Groverova algoritmuTento algoritmus je navr¾en k vyhledávání v mno¾inì bez jakékoliv dodateèné struktury,tedy v þnesetøídìné nestrukturované databáziÿ. Jeho jádro tvoøí jednodu há, ale mo ná my¹lenkaposilování amplitudy oznaèeného stavu inverzí podle prùmìru: pøedstavme si situa i, ¾e v¹e hnyprvky kromì oznaèeného mají stejnou reálnou amplitudu a amplituda oznaèeného prvku je jinéreálné èíslo. Jestli¾e nyní spoèítáme aritmeti ký prùmìr v¹e h amplitud a následnì pøevrátímeka¾dou z ni h na druhou stranu od prùmìru, pak za jistý h podmínek se absolutní hodnotaamplitudy oznaèeného prvku zvý¹í na úkor absolutní h hodnot ostatní h amplitud. Z jednodu hégra� ké pøedstavy snadno odvodíme, ¾e touto podmínkou je pouze, aby aritmeti ký prùmìr le¾elmezi nulou a èetnìj¹í z amplitud.Obr. 15: Inverze kolem průměru. Jednotlivé prvky grafu jsou detailně popsány v textu.Velikost databáze, tedy poèet prvkù prohledávané mno¾iny, je omezen na mo niny dvojky:N = 2n. To umo¾òuje sestavit n-qubitový systém, jeho¾ bázové stavy budou odpovídat jed-notlivým prvkùm databáze. Algoritmus bude probíhat tak, ¾e vyjdeme ze stavu, kdy v¹e hnybázové stavy budou mít stejnou amplitudu { o mnoho ví e nemù¾eme obe nì po¾adovat vzhle-dem k faktu, ¾e nemáme ¾ádné dal¹í informa e o funk i ani topologii vstupní h hodnot. Následnìbudeme opakovat itera i sestávají í ze dvou krokù: pøevrá ení znaménka amplitudy oznaèenéhovstupu a popsaného pøeklopení podél prùmìru. Obì tyto opera e jsou jistì lineární, odpovídají íoperátory oznaème U , resp. D. Jeji h dal¹í vlastnosti a realiza i pomo í dostupný h kvantový hhradel uká¾eme pozdìji. Takto utvoøenou itera i v¹ak budeme aplikovat pouze tak dlouho, do-kud se absolutní hodnota amplitudy oznaèeného prvku bude zvy¹ovat { uká¾eme, o by se dìlopøi pøípadný h dal¹í h opakování h. Nakone provedeme úplné mìøení, jeho¾ výsledkem budes dostateènì vysokou pravdìpodobností právì hledaná vstupní hodnota.Optimální poèet itera í je tøeba znát pøed provedením algoritmu { kvantová me hanika ne-umo¾òuje sledovat, jestli u¾ jsme dosáhli dostateèné pravdìpodobnosti. Grover ve svém èlánkudokazuje odhad, ¾e tento poèet je tøídy O (pN), existuje v¹ak jiný zpùsob vedení dùkazu, uve-dený v èlánku [12℄ nebo v [3℄, který umo¾òuje pro poèet itera í najít expli itní vzore . Pøedveïmejej i zde.Poèáteèní stav oznaème jsi = 1√

N

∑N−1i=0 jii, hledaným vr holem ne h» je bez újmy na obe -nosti j0i.27 Difuzní nebo Groverùv operátor D je pak mo¾no zapsat ve tvaruD = 2jsihsj � I (4:1)

27 Takový předpoklad zde mnoho zjednodušení nepřinese, ale ve druhém popisovaném algoritmu budeklíčový, je tedy uveden pro jednotnost. 41

a operátor U jako U = I � 2j0ih0j; (4:2)kde I oznaèuje jednotkový operátor. Ve shodì s Groverovým èlánkem [18℄ uka¾me nejprve uni-tatiru obou opera í. Pro unitární mati i D by muselo platit D†D = I, spoèítejme tedyD†D = (2(jsihsj)† � I†)(2jsihsj � I) = (2jsihsj � I)2 == 4jsihsjsihsj � 2jsihsjI � 2Ijsihsj+ I = 4jsihsj � 2jsihsj � 2jsihsj+ I = I: (4:3)V¹imnìme si, ¾e tento dùkaz nijak nevyu¾íval toho, který konkrétní projektor je pou¾it namístì jsihsj, unitarita U se tedy doká¾e z ela stejnì.Dále si v¹imnìme, ¾e vzhledem k tomu, ¾e poèáteèní stav je jsi, ¾ádným provedeným kro-kem neopustíme reálný lineární obal vektorù jsi a j0i. Díky této skuteènosti mù¾eme pra ovatv takovém podprostoru, který má naví harakter roviny. Pøed pokraèováním odvození v¹ak je¹tìvyøe¹íme mírnì nepøívìtivou skuteènost, ¾e vektory jsi a j0i nejsou ortogonální: jeji h skalárnísouèin je hsj0i = 1√N.Zde mù¾eme efektivnì vyu¾ít Gramùv-S hmidtùv ortonormalizaèní pro es. Máme mo¾nostse rozhodnout, který z vektorù v nové bázi pone háme. Zøejmì nás bude zajímat, jak se budevyvíjet amplituda j0i, nahraïme tedy vektor jsi a výsledek oznaème jui:jui = 1kjsi � h0jsij0ik(jsi � h0jsij0i) = 1

√

N−1N

1pN N−1∑

i=0

jii � 1pN j0i = 1pN � 1 N−1∑

i=1

jii:(4:4)Vektory jui a j0i ji¾ tvoøí ortonormální bázi pra ovního podprostoru. Sestavme tedy izometriipra ovního podprostoru s rovinou, která je identi�kuje s jednotkovými vektory ve smìru oskartézského systému souøadni dle obr. 16.Z lineární algebry víme, ¾e ka¾dá ortogonální mati e druhého øádu má v rovinì buï významrota e kolem poèátku souøadni o libovolný úhel (v pøípadì, ¾e má determinant +1), nebo zr- adlení podle libovolné osy pro házejí í poèátkem, pokud má determinant �1. V¹imnìme si, ¾eopera e D i U (zú¾ené na popsaný podprostor) mají determinant �1 a odpovídají tak zr adlení.Osou bude v obou pøípade h vlastní podprostor odpovídají í vlastnímu èíslu 1, o¾ je [jsi℄λ promati i D a [jui℄λ v pøípadì U . Mati e odpovídají í jedné itera i G = DU má determinant +1 aje tedy tvaru G = ( os' sin'� sin' os') (4:5)pro nìjaký úhel '. Ten staèí urèit z obrazu libovolného vektoru. Vezmìme si tedy pro názornostvektor jui. Proto¾e U jui = jui, je Gjui = Djui a jui se tak zobrazí na vektor, který má dvakrátvìt¹í úhel od kladné poloosy ne¾ jsi. Platí tedy ' = 2'0, kde '0 je úhel mezi vektory jui a jsi.42

juij0i

jsiGjuiGjsiG2jsi'0' = 2'0'

'

Obr. 16: Geometrická reprezentace Groverova algoritmuKa¾dá provedená itera e tedy zvý¹í úhel od kladné poloosy o 2'0 od poèáteèní hodnoty '0a úhel po k itera í h je tak roven (2k + 1)'0. Cílem Groverova algoritmu je itera e opakovat,dokud amplituda j0i v absolutní hodnotì roste. V této geometri ké interpreta i to znamená úhelzvy¹ovat a¾ k hodnotì π2 . Následují í itera e by toti¾ amplitudu zaèaly opìt sni¾ovat, a¾ by sepøiblí¾ila 0 pøi úhlu blízkém �, pøi stále dal¹ím prùbìhu by se elý pro es opakoval.Optimální poèet krokù k0 by tedy mìl splòovat rovni i(2k0 + 1)'0 = �2 ; (4:6 a)kde pro '0 platí sin'0 = os(π

2 � '0) = hsj0i = 1√N. Z ní urèenék0 = 12 ( �2'0 � 1) (4:6 b)v¹ak obe nì nebude pøirozené èíslo, pou¾ijeme tedy alespoò o nejbli¾¹í poèet krokù a tentovýsledek zaokrouhlíme. Oznaèíme-li [x℄ elou èást èísla x, bude výsledek podle bì¾ný h pravidelzaokrouhlování roven k0 = [ �4'0 ] : (4:6 )Vzore mù¾eme je¹tì zjednodu¹it, aproximujeme-li arkussinus ve vzor i '0 = ar sin 1√

Njehoargumentem. Pøi men¹í h hodnotá h N by se taková aproxima e mohla zdát pøíli¹ hrubá, alepøímým výpoètem nìkolika první h odpovídají í h hodnot zjistíme, ¾e nový vzore k0 = [�4pN] (4:7)dává stejný výsledek pro ka¾dé pøirozené N .Toto odvození nám umo¾òuje urèit i spodní hrani i pro pravdìpodobnost namìøení hleda-ného vr holu po tomto optimálním poètu provedený h itera í. Vzhledem k platnosti pøesného(neaproximovaného) vzor e mù¾eme s jistotou prohlásit, ¾e úhel (2k0+1)'0 bude le¾et v rozmezíhπ2 � '0; π

2 + '0i. Pravdìpodobnost namìøení stavu j0i pak budeP = os2 (�2 � (2k0 + 1)'0) = 1� sin2 (�2 � (2k0 + 1)'0) � 1� sin2 '0 = 1� 1N : (4:8)43

4.3 Groverùv algoritmus v krajní h pøípade hZ posledního uvedeného odhadu plyne, ¾e èím vìt¹í je databáze, kterou prohledáváme, tímvìt¹í pravdìpodobnost namìøení hledaného vr holu máme zaruèenu. Cílem tohoto paragrafu jenaopak popsat, jak se Groverùv algoritmus hová pøi veli e malý h hodnotá h n (pøipomìòmeN = 2n).Mati e Groverova operátoru pro pøípad n = 1 (hledání hodnoty jednoho vstupního bitu) jePauliho mati e X. V ka¾dém kroku se tedy zmìní znaménko amplitudy hledané hodnoty, a potése amplitudy stavù j0i a j1i zamìní. Nedo hází tak k ¾ádné interferen i a tedy ani k ¾ádnýmzmìnám pravdìpodobnosti namìøení kterékoliv z hodnot oproti pùvodnímu stavu j+i a Groverùvalgoritmus je zde z ela nepou¾itelný.Pøípad n = 2 je z ela výjimeèný { Groverùv algoritmus umo¾ní namìøit správnou hodnotus jistotou, tedy s nulovou pravdìpodobností nesprávné odpovìdi, a to po pouhé jediné provedenéitera i. Dosazením do vzor ù odvozený h vý¹e toti¾ zjistímesin'0 = 12 ; (4:9)tedy '0 = π6 a po jedné itera i ' = (1 + 2 : 1)π

6 = π2 , o¾ je úhel odpovídají í stavu j0i. Tentopøíklad se èasto uvádí jako ukázka síly kvantový h algoritmù { postaèilo nám jednou þvyhodnotitÿfunk i f , aby hom mezi ètyømi mo¾nými vstupy na¹li jeden oznaèený. To je v pøípadì klasi ký halgoritmù samozøejmì z ela nepøedstavitelné.28Uká¾eme, ¾e pøi ¾ádném vy¹¹ím n ji¾ nemù¾e nastat situa e, ¾e by po optimálním poètu krokùamplitudy v¹e h bázový h stavù kromì hledaného klesly na nuly. Za tímto úèelem si pøedstavmeobr. 16 jako Gaussovu rovinu, tedy sestrojme izomor�smus reálného lineárního obalu vektorù juia j0i s prostorem komplexní h èísel nad R daný vztahy jui 7! 1 a j0i 7! i. Vektor jsi se pøenesena èíslo s = √1� 1N + 1pN i (4:10)a vektor odpovídají í k provedeným itera ím na s2k+1. Aby hom dosáhli stavu j0i, po¾adujme,aby s2k+1 mìlo nulovou reálnou èást. Rozepi¹me jej tedy podle binomi ké vìty:s2k+1 = 2k+1∑

l=0

(2k + 1l )

√1� 1N l pN−(2k+1−l) i2k+1−l (4:11 a)K reálné èásti zøejmì budou pøispívat jen èleny urèené li hými hodnotami l, pone hme tedypouze takové a pøepi¹me l na 2m+ 1, kde m bude novým sèíta ím indexem:Re s2k+1 = k∑

m=0

( 2k + 12m+ 1) √1� 1N 2m+1 pN2m−2k i2k−2m == k∑

m=0

( 2k + 12m+ 1) √1� 1N (1� 1N )m Nm−k (�1)k−m

(4:11 b)28 Kvantové „vyhodnoceníÿ však, jak důsledně upozorňují autoři článku [20], znamená dva průchodyklasickou implementací funkce f ve smyslu paragrafu 2.5, tedy v podstatě dvě vyhodnocení klasická. Tose obvykle nedodává. 44

Pravdivost výroku, ¾e tento výraz je nulový, se jistì nezmìní, vynásobíme-li jej nenulovým èíslemzávislým pouze na N a k. Takovou úpravou mù¾eme získat nutnou podmínkuk∑

m=0

( 2k + 12m+ 1) (N � 1)m (�1)m = 0 (4:11 )V¹e hny èleny dané m vìt¹ími ne¾ 0 jsou násobky nìkteré kladné mo niny N � 1. Aby se elývýraz mohl rovnat 0, musí tedy být i první èlen dìlitelný N � 1. Tímto èlenem je pøitom pouzeèíslo 2k + 1, po¾adujeme tedy N � 1/2k + 1: (4:11 d)Proto¾e v¹ak obì èísla jsou kladná, musí platit 2k+ 1 � N � 1. Tento spodní odhad je v¹ak pron > 2 v rozporu s horním odhadem pro optimální poèet krokù (4.7) (o horní odhad se jednáproto, ¾e [x℄ � x): �4pN � k0�2pN + 1 � 2k0 + 1 � N � 1�2pN � N � 2�2 � pN � 2pN � pN � 1 = 2n2 � 1 (4:12)

Snadno ovìøíme, ¾e pro n > 2 je 2n2 � 1 > π

2 , o¾ je hledaný spor.Pro vy¹¹í n ji¾ tedy ¾ádné zvlá¹tní pøípady nenastávají. Pravdìpodobnost dostateènì blízkoujednot e v¹ak zajistí odhad P � 1� 12n :

Obr. 17: Groverův algoritmus: pravděpodobnost naměření hledaného vrcholupo optimálním počtu iterací. Vpravo je zvětšený výsek s jemnějším měřítkem svislé osy.

Čárkovaně je znázorněn spodní odhad 1− 2−n.4.4 Varia e Groverova algoritmuGroverùv algoritmus je pou¾itelný i v pøípadì, ¾e vyhledáva ímu kritériu vyhovuje ví e ne¾jeden z prvkù databáze, musíme v¹ak vìdìt pøedem, kolik takový h existuje. Oznaème tentopoèet t a mno¾inu v¹e h oznaèený h prvkù T . 45

Odvození provedeme z ela analogi ky jako v pøed hozím paragrafu. Vektor j0i v¹ak nahra-díme vektorem jti = 1pt ∑i∈T

jii: (4:13)Skalární souèin hsjti je roven 1pNtt = √ tN ; (4:14)vektor jui získaný ortonormalizaèním pro esem tedyjui = 1pN � t N−1∑

i=0i6∈T

jii: (4:15)V¹e hny následují í úvahy mohou po této náhradì zùstat nezmìnìny s tím, ¾e sin'0 =hsjti = √

tN , vzore pro optimální poèet krokù se tedy zmìní pouze nak0 = �4√Nt : (4:16)Jiné silné zobe nìní Groverova algoritmu uvádí èlánek [21℄. V nìm autoøi de�nují obe nýalgoritmus pro posilování amplitudy oznaèený h stavù a pozdìji zobe ní i operátory D a U tak,¾e amplituda jsi, resp. jti se mù¾e násobit i jinou komplexní jednotkou ne¾ �1. Operátory po-u¾ívané v Groverovì algoritmu jsou podle této logiky jednotkovému operátoru þnejvzdálenìj¹íÿ,tak¾e takováto úprava mù¾e zvìt¹it poèet potøebný h itera í. Její vhodnou volbou v¹ak mù-¾eme dosáhnout jistoty namìøení hledaného vr holu tak, ¾e þzpomalímeÿ poslední itera i, èím¾v uvedené geometri ké reprezenta i dosáhneme �nálního natoèení o potøebný úhel men¹í ne¾ '.Takovou úpravu uvádí na konkrétním pøíkladì èlánek [22℄: zde se uva¾uje pouze vyhledávánís ví e oznaèenými prvky. Jestli¾e tvoøí právì jednu ètvrtinu ze v¹e h prvkù databáze, namìøímes jistotou jeden z ni h právì po jedné itera i, stejnì jako v pùvodním algoritmu pro N = 4.Jestli¾e je v¹ak oznaèený h prvkù je¹tì ví e, vy hází nezaokrouhlená hodnota k0 men¹í ne¾ 1 aji¾ provedením první itera e by se stavový vektor dostal za optimální hrani i. Zpomalením tétojedné itera e zpùsobem uvedeným v pøed hozím odstav i v¹ak mù¾eme zajistit výsledek stejnýjako v pøípadì t = N

4 .4.5 Realiza e hradel v Groverovì algoritmuPodobnì jako v pøípadì Shorova algoritmu by bylo tøeba je¹tì ukázat, jak je mo¾no operátoryD a U realizovat pomo í jednodu¹¹í h kvantový h hradel.Pøipomeòme, ¾e operátor D je roven 2jsihsj � I, kde jsi je rovno enná superpozi e v¹e hstavù jii2n−1i=0 . Dále dle paragrafu 2.3 je jsi obrazem j0i pøi Walsh-Hadamardovì transforma iH⊗n a platí (H⊗n)2 = I. Pro dosa¾ení ak e operátoru D, fázového posunu slo¾ky odpovídají íortogonální projek i do podprostoru [jsi℄λ vùèi projek i do jeho ortogonálního doplòku, tedy46

staèí ekvivalentnì toté¾ udìlat s ortogonální projek í do podprostoru [j0i℄l a tuto opera i z oboustran oblo¾it operátory H⊗n:D = 2jsihsj � I = H⊗n(2j0ih0j � I)H⊗n (4:17)Dále vyu¾ijeme mo¾nosti zanedbat globální fázi vektoru, díky ní¾ je hradlo 2j0ih0j � I fyzikálnìekvivalentní hradlu I � 2j0ih0j. Tím jsme úlohu pøevedli na problém konstruk e hradla, kteréna v¹e hny bázové vektory kromì j0i pùsobí jako jednotkový operátor a vektoru j0i zmìní zna-ménko. To se veli e podobá jednobitovému hradlu �I øízenému souèasnì nega emi v¹e h qubitù,jak ukazuje obr. 18 a) (pøipomeòme, ¾e pro zmìnu znaménka stavového vektoru postaèí zmì-nit znaménko libovolného èinitele v tenzorovém souèinu), toto hradlo se li¹í potøebou jednohopomo ného qubitu.Øízené hradlo �I je v¹ak stále vzdálené mno¾inì univerzální h hradel. Aby hom se ví epøiblí¾ili hradlùm popsaným v paragrafu 2.3, uká¾eme, ¾e jsme jej s hopni nahradit øízenýmhradlem X, které mù¾eme nazvat zobe nìné To�oliho hradlo. Zmìna znaménka toti¾ nastanepøi pùsobení X na vektor j�i = 1√2(j0i � j1i), proto¾e je vlastním vektorem X pøíslu¹ejí ímvlastnímu èíslu �1. Staèí tedy pomo ný qubit pøedpokládat pøipravený ve stavu j1i a aplikovatna nìj Hadamardovo hradlo (dvakrát kvùli navrá ení do pùvodního stavu).Rozumnou úvahou v¹ak mù¾eme u¹etøit i potøebu pomo ného qubitu. Stejnì jako j�i = Hj1ije vlastním vektorem X pøíslu¹ejí ím vlastnímu èíslu �1, je j+i = Hj0i vlastním vektorempøíslu¹ejí ím vlastnímu èíslu 1. Kdyby hom tedy v obr. 18 b) pøedpokládali pomo ný qubitpøipravený ve stavu j0i, elý zobrazený obvod by pøedstavoval jednotkový operátor. V¹imnìmesi, ¾e místo pomo ného qubitu tak lze pou¾ít kterýkoliv z n pùvodní h qubitù po opera i X:zmìna znaménka nastane pouze tehdy, kdy¾ byl pøed opera í X ve stavu j0i a v¹e hny ostatní,øídi í, qubity také. To je ov¹em pøesné znìní pùvodního zadání. Výsledný náhradní obvod proI � 2j0ih0j tedy ukazuje obr. 18 ).XX...XX �I

XX...XXj0in

a)...XXXXH

XX...XXHj1in

b)

XX...XX H HXX...XX

n )

Obr. 18: Realizace Groverova operátoru pomocí univerzálních hradel –– odvození náhradního obvodu pro pomocný operátor I − 2|0〉〈0|Dále uká¾eme, jak je mo¾no zobe nìné To�oliho hradlo, pou¾ité na obr. 18 ), realizovatpomo í þbì¾néhoÿ To�oliho hradla, které ji¾ budeme pova¾ovat za elementární (jeho pøepis47

pomo í univerzální h kvantový h hradel ukazuje obr. 11 v paragrafu 2.4). Jedná se o opera iøízenou hodnotou (n � 1)-bitové výrokové formy, o¾ jsme s hopni obe nì realizovat postupemnaznaèeným v paragrafu 2.5. Pøedstavíme øe¹ení ukázané v [12℄, které tento postup v podstatìpøesnì sleduje a potøebuje n� 2 pomo ný h qubitù pøipravený h ve stave h j0i. Pro pøehlednostjej výjimeènì popí¹eme slovy.V prvním To�oliho hradle pou¾ijeme 1. a 2. qubit jako øídí í a 1. pomo ný qubit jako ílový. Proto¾e byl ve stavu j0i, jeho stav bude následnì jx1 and x2i, kde jx1i, resp. jx2i jsoustavy 1., resp. 2. qubitu. Nyní pou¾ijeme tento qubit a 3. z pùvodní sady jako øídi í a dal¹ípomo ný jako ílový pro druhé To�oliho hradlo. Stav druhého pomo ného qubitu pak budejx1 and x2 and x3i. K tomuto výsledku opìt þpøidámeÿ 4. qubit a tak dále, a¾ po n � 2kro í h (To�oliho hradle h) bude poslední pomo ný qubit ve stavu odpovídají ímu konjunk iv¹e h pùvodní h hodnot, které jsme htìli pou¾ít jako øídi í. Nyní tedy postaèí tento qubit pou¾ítjako øídi í pro hradlo not a následnì v¹e hny pomo né opera e provést znovu v opaèném poøadípro návrat pomo ný h qubitù do pùvodní h stavù.29Operátor U je v Groverovì algoritmu orákulem. Má opìt harakter výrokové formy, pøi je-jím¾ splnìní po¾adujeme zmìnu znaménka odpovídají ího bázového stavu. Zpùsobem popsanýmv paragrafu 2.5 jsme za pomo i nìjakého poètu pomo ný h qubitù tento problém pøevést a¾ nazmìnu znaménka øízenou jedním qubitem, o které podobnou úvahou jako pøi odvození obr. 18 b)zjistíme, ¾e je ji mo¾no realizovat pomo í hradla not a jednoho pomo ného qubitu. Podobnézjednodu¹ení jako u obr. 18 ) po hopitelnì ji¾ mo¾né není.Z uvedeného postupu je zøejmé, ¾e pro realiza i hradla D budeme potøebovat O(n) univer-zální h kvantový h hradel. De�ni e hradla U nemá n jako parametr, proto pro ni nemá smysltvoøit ¾ádný podobný odhad. Ji¾ toto v¹ak znamená, ¾e ve smyslu poètu provedený h univerzál-ní h hradel nebude èasová slo¾itost Groverova algoritmu O (2n2

), ale O (n2n2

). Èíslo n je v¹akúmìrné pouze logaritmu poètu prvkù databáze N , tak¾e odhad se þpøíli¹ nezhor¹ilÿ. Nový odhadmù¾eme oznaèit ~O (pN), kde ~O(f(n)) znamená O(f(n)p(log f(n))) pro nìjaký polynom p [12℄.4.6 Vztah Groverova algoritmu a problému nerozli¹itelnosti neortogonál-ní h stavùNa závìr sek e o Groverovì algoritmu uveïme následují í drobnou úvahu.Pøi pøemý¹lení o posilování amplitudy vyhledávaného stavu by mohlo nastat podezøení, zdazvy¹ování pravdìpodobnosti namìøení správného výsledku není ve sporu v pouèkou, ¾e ¾ádnémìøení nemù¾e spolehlivì odli¹it blízké stavy. Je v¹ak tøeba si pov¹imnout, ¾e v Groverovì al-goritmu ¾ádný pokus o takové mìøení nepou¾íváme. Pøi hledání oznaèeného vstupu provádímez ela bì¾né projektivní mìøení v bázi fjiigN−1i=0 a ve skuteènosti se sna¾íme rozli¹it mezi máloodli¹nými unitárními opera emi, které k mìøenému stavu vedly od pùvodního stavu jsi.

29 Pozorný čtenář si jistě povšimne, že jeden pomocný qubit je možno ještě ušetřit – poslední pomocnéToffoliho hradlo může působit již na cílový qubit. Postup se zkrátí o použití hradla cnot a opakovánítohoto Toffoliho hradla. 48

Kapitola 5Prohledávání, sítì a náhodné hozeníTato sek e popisuje kvantovou obdobu k zajímavému prin ipu vyu¾ívanému v nìkterý h kla-si ký h algoritme h: náhodnému pro házení. První paragraf shrnuje popis a základní poznatkyo náhodné pro ház e na pøím e, druhá navrhuje kvantovou obdobu tohoto algoritmu. Ukazuje sev¹ak, ¾e výsledky obou pøístupù jsou radikálnì odli¹né. Kvantová náhodná pro házka má pøede-v¹ím vlastnost mnohem ry hlej¹ího dosa¾ení kterékoliv polohy { této vlastnosti je mo¾no vyu¾ítpro jiný pøístup k øe¹ení problému vyhledávání v nesetøídìné databázi. Od tøetího paragrafu dáleje tedy popisován kvantový vyhledávají í algoritmus vyu¾ívají í tento pøístup a nìkteré jehovaria e.5.1 Náhodné pro házeníNáhodná pro házka je postup, pøi kterém sledujeme pohyb objektu po vr hole h nìjakéhografu. Pohyb se dìje po kro í h { v ka¾dém kroku objekt pøejde právì po jedné hranì vy házejí íz vr holu, ve kterém právì stojí, pøièem¾ výbìr z mo¾ný h hran je provádìn náhodnì. Jako pøíkladmù¾e poslou¾it þhraÿ, pøi které þhráèÿ hodí po pøím e tak, ¾e hází min í a podle výsledku hodupostoupí buï jeden krok dopøedu nebo nazpìt.Jestli¾e nasimulujeme mno¾ství takový h náhodný h pro házek po pøím e, vy házejí í h zestejného bodu, a v¾dy po daném poètu krokù N oznaèíme aktuální polohu objektu, získámepravdìpodobnostní rozdìlení. Toto rozdìlení bude omezené na interval h�N;Ni, tyto hrani eodpovídají konstantnímu pohybu v jednom smìru. Dále ka¾dá druhá poloha bude mít nulovoupravdìpodobnost: díky tomu, ¾e v ka¾dém okam¾iku je tøeba udìlat právì jeden krok, po ka¾déitera i se zmìní parita polohy. Po sudém poètu krokù jsou tedy nedosa¾itelné polohy, jeji h¾vzdálenost od poèáteèního místa je li há, a naopak.V obr. 19 jsou tedy vyznaèeny a propojeny jen polohy s nenulovou pravdìpodobností. Totopravdìpodobnostní rozdìlení pøipomíná tvarem Gaussovo rozdìlení, které je jeho limitním pøí-padem (jedná se o tzv. binomi ké rozlo¾ení).

Obr. 19: Pravděpodobnostní rozdělení koncových bodů klasické náhodné procházky po přímce po 100iteracích49

Dobrou mírou otázky, jak daleko se pøi náhodném pro házení objekt dostane po N kro í h,je støední kvadrati ká od hylka tohoto rozdìlení. Ta je v tomto pøípadì pøímo rovna odmo ninìz poètu krokù.5.2 Kvantové náhodné pro házeníKvantovou obdobou tohoto základního pøíkladu se zabývá mnoho pra í, napø. [19℄, [23℄ nebo[24℄. Intuitivnì by hom mohli pøedpokládat, ¾e poloze na pøím e budou odpovídat bázové stavyjii; i 2 Z nekoneènìrozmìrného stavového prostoru, ¾e náhodný výbìr bude mo¾no nahraditutvoøením superpozi e mo¾ný h výsledkù a náhodnost ¾e pone háme pro esu mìøení. Snadno sev¹ak uká¾e, ¾e po¾adavkùm unitarity, symetrie vùèi posunutí po pøím e a tomu, aby obrazemka¾dého bázového stavu byla lineární kombina e pouze dvou pøilehlý h, vyhovují jen triviálnípøípady opera í, které pøedstavují pohyb pouze v jednom smìru. Toto zji¹tìní je v literatuøeoznaèováno jako þNo-Go Lemmaÿ (podrobnìj¹í popis a diskuse mnohem volnìj¹í h pøedpokladùviz [25℄).Øe¹ením tohoto problému je umo¾nit závislost této opera e je¹tì na výsledku pøed hozíhoþhoduÿ.30 To se realizuje tak, ¾e vý¹e uvedený stavový prostor roz¹íøíme tenzorovým souèinemje¹tì o prostor þmin eÿ HC = C 2 . Jedna itera e pak bude tvaruU = SC; (5:1)kde C je nìjaká unitární opera e pùsobí í pouze na prostoru min e HC , C = IC1. C1 budemeuva¾ovat jako mati i z prostoru C 2,2 a dále vektory standardní báze HC oznaèíme j!i a j i.Opera i S de�nujeme pomo í její ak e na bázové vektory elého prostoru H = HS HC :Sjnij!i = jn+ 1ij!iSjnij i = jn� 1ij i (5:2)Jak bylo øeèeno v úvodu prá e, pøesnou korektnost takového vyjádøení a de�ni i unitárníhozobrazení v nekoneènìdimenzionálním prostoru nebudeme diskutovat.Mati e C1 je omezena pouze po¾adavkem unitarity a jejímy rùznými volbami mù¾eme do-sáhnout rùzný h prùbìhù algoritmu. Nejblí¾e analogii s pùvodním, klasi kým pøíkladem se do-staneme v pøípadì, kdy absolutní hodnoty její h prvkù budou stejné, tj. 1√2. Algoritmus by toti¾tehdy na klasi ký pøípad zkolaboval, kdyby hom po ka¾dé itera i provedli úplné mìøení stavu.31Pøíkladem mati e splòují í zmínìné po¾adavky je Hadamardova mati eC1 = H = 1p2 ( 1 11 �1) ; (5:3)podle které se poèáteèní stav j0ij!i bude vyvíjet následovnì:

1√2(j1ij!i+ j�1ij i)

12(j2ij!i+ j0ij i+ j0ij!i � j�2ij i)

12√2(j3ij!i+ j1ij i+ 2j1ij!i � j�1ij!i+ j�3ij i): : : (5:4)

30 Autorem argumentu No-Go je přímo autor zmíněného článku [25], uvedené řešení se připisuje J. Wa-trousovi [26]31 Stejného výsledku můžeme snáze dosáhnout měřením na prostoru HC vždy mezi operacemi C a S.50

Kdyby hom po první nebo druhé itera i provedli mìøení na prostoru HS , nepozorovaliby hom ¾ádný rozdíl vùèi klasi kému pøíkladu. Ve tøetím øádku se v¹ak zaèíná projevovat asyme-trie v pravdìpodobnoste h namìøení j1i a j�1i. Amplitudy ve smìru þod nulyÿ toti¾ v jednompøípadì zinterferovaly konstruktivnì a v jednom destruktivnì. Obr. 20 ukazuje pravdìpodob-nostní rozdìlení po vìt¹ím poètu itera í, jmenovitì 20 a 50.

Obr. 20: Průběh pravděpodobnosti při kvantové náhodné procházce po přímce po 20 a 50 iteracíchNa první pohled je zøejmé, ¾e toto pravdìpodobnostní rozdìlení nijak nepøipomíná klasi kébinomi ké rozlo¾ení, pøedvedené na obr. 19. Za hovává se v¹ak argument s mezemi �N a¾ N ,urèenými N -násobným provedením operátoru S, a podmínka parity polohy. Proto je v obr. 20spojen plnou èarou a¾ ka¾dý druhý bod. V následují í h ilustra í h ji¾ vyne hané body nebudouuva¾ovány. V¹imnìme si v¹ak, ¾e i v hrub¹ím mìøítku je propojují í èára silnì zvlnìna.Pøi odhlédnutí od této nepravidelnosti ukazuje rozdìlení dva výrazné vr holy, které se odsebe navzájem vzdalují s rostou ím poètem itera í zhruba lineární ry hlostí. Tyto vr holy le¾ípøibli¾nì na polohá h � 1√2N (napø. �34 pro N = 50, �702 pro N = 1000). Rozdìlení je naví asymetri ké, vr hol na pravé stranì obr. 20 je mnohem vy¹¹í ne¾ vr hol vlevo. Pravdìpodobnostza hrani í tì hto vr holù je a¾ ke døíve zmínìné hrani i �N nenulová, ale veli e silnì tlumená.Díky tvaru a popsaným vlastnostem rozdìlení roste lineární ry hlostí i støední kvadrati káod hylka. Toto je dùle¾itý rozdíl oproti klasi kému pøípadu, proto¾e daná poloha je s dostateènoupravdìpodobností dosa¾ena v kvadrati ky krat¹ím èase ne¾ u klasi ké náhodné pro házky. V ná-sledují ím paragrafu uká¾eme, jak kvantová náhodná pro házka na jiném grafu vyu¾ije podobnévlastnosti k podobnému ury hlení øe¹ení vyhledáva ího problému, jako poskytuje Groverùv al-goritmus.S poèáteèní podmínkou j0ij i by situa e byla podobná jako s pùvodnì uva¾ovaným po-èáteèním stavem j0ij!i, pravdìpodobnostní rozlo¾ení by bylo jen zr adlovì otoèené vzhledemk poloze odpovídají í j0i. Vzhledem k tomu, ¾e ani jeden pøípad neopustí reálný lineární obalbázový h vektorù H, mù¾eme volbou poèáteèní podmínky1p2(j0ij!i+ ij0ij i) (5:5)51

dosáhnout souèasné existen e obou pozorovaný h jevù s prostým souètem pravdìpodobností, jakukazuje obr. 21.

Obr. 21: Průběh pravděpodobnosti při kvantové náhodné procházce na přímce –– symetrická počáteční podmínka, 50 iteracíVeli e zajímavé je, ¾e elkový harakter výsledku pøíli¹ nezávisí na volbì mati e C1, pokudje splnìna podmínka stejný h absolutní h hodnot její h prvkù: obr. 22 ukazuje pøípadyH = 1p2 ( 1 11 �1) C2 = 1p2 ( 1 ii 1) C3 =

1√212(i+ 1)

−1√212(i+ 1) (5:6)se stejnou volbou poèáteèního stavu 1√

2(j0ij!i+ ij0ij i). V¹imnìme si v¹ak, ¾e na této volbìzávisí, zda daná poèáteèní podmínka povede k symetri kému nebo asymetri kému vývoji.

Obr. 22: Výsledky různé volby matice C po 50 iteracíchPro zajímavost uka¾me je¹tì, jak pravdìpodobnostní rozdìlení vypadá po znaènì velkém52

poètu itera í:

Obr. 23: Průběh pravděpodobnosti pro C1 = H a N = 1000při nesymetrické a symetrické počáteční podmínce5.3 Vyhledávání na hyperkry hliMy¹lenku kvantový h náhodný h pro házek je mo¾no aplikovat ve vyhledáva í h algorit-me h. Dobøe prozkoumán [27℄ je algoritmus urèený k øe¹ení podobného zadání jako Groverùvalgoritmus { vyhledávání v nesetøídìné databázi o velikosti N = 2n. Tentokráte v¹ak budemepøedpokládat, ¾e prvky jsou uspoøádany do vr holù n-rozmìrné hyperkry hle. Jedná se tedyo databázi mají í nìjakou vnitøní strukturu, která ale nalezení oznaèeného vr holu nijak neu-snadòuje.Na vr hole h hyperkry hle, kterým opìt pøiøadíme význam bázový h vektorù fjiigN−1

i=0 sta-vového prostoru n qubitù, nyní v¹ak ve shodì s obr. 24, ne háme probíhat kvantovou náhodnoupro házku. Stejnì jako v pøípadì pøímky vyu¾ijeme pomo ný prostor HC , který v¹ak zde budemít dimenzi n a opera e S bude de�nována vztahySjiijdi = ji� 2dijdi pro ka¾dé i 2 f0; 1; : : : ; N � 1g; d 2 f0; 1; : : : ; ng: (5:7)Znaèka � zde znamená XOR po bite h, pøed hozí øádek má tedy význam nega e d-té èísli e nve dvojkové soustavì èili krok po pøilehlé hranì rovnobì¾né s (d+ 1)-tou souøadnou osou.00 10

1101000 100110010 001 101

1110110000 10001010

11101111011101010001

Obr. 24: Hyperkrychle dimenzí 2, 3 a 4. Vrcholy jsou popsány řetězci n bitů –– dva vrcholy jsou spojeny hranou právě tehdy, když se liší právě v jednom bitu.53

U bázový h vektorù H = HSHC tak budeme mluvit o prostorové a smìrové èásti. Opera eC bude v tomto vyhledáva ím algoritmu nadále pùsobit pouze na smìrovou èást vektoru, alenebude ji¾ tvaru IC1: v rùzný h vr hole h ne háme pùsobit rùzné þmin eÿ. Pro v¹e hny vr holykromì oznaèeného volíme min i, která má stejnou mati i jako difuzní operátor D pro N = n:C1 = 2jsdihsdj � I =

2n � 1 2

n � � � 2n

2n

2n � 1 � � � 2

n... ... . . . ...2n

2n � � � 2

n � 1; (5:8)jsdi = 1pn n−1∑

i=0

jii; (5:9)v oznaèeném vr holu pak pouze C2 = �I. Celkovì tedyC = I C1 � ji0ihi0j (C1 + I) (5:10)Poèáteèní stav algoritmu je rovno enná superpozi e v¹e h bázový h stavù H:j 0i = 1pNn N−1∑

i=0

n−1∑

d=0

jiijdi: (5:11)Na tento stav budeme podobnì jako u Groverova algoritmu aplikovat pøedem daný poèet itera ítvaru U = SC, pøedstavují í h prùbìh kvantové náhodné pro házky. Poté provedeme mìøenína prostoru HS . Ukazuje se, ¾e kvantová náhodná pro házka spolu s vhodnì zvoleným poètemitera í opìt zajistí zvý¹enou pravdìpodobnost namìøení oznaèeného vr holu.Øe¹ení prùbìhu algoritmu se dá, podobnì jako u Groverova algoritmu, znaènì zjednodu¹it.Pøedpokládejme opìt, ¾e hledaným vr holem je j0i { toho mù¾eme v¾dy dosáhnout vhodnýmpøeznaèením vr holù (za dodr¾ení popsaný h pravidel). Jestli¾e pøiøadíme nìjaké oznaèení rov-no enným superpozi ím bázový h stavù H mají í h stejnou Hammingovu váhu prostorové èásti(tedy vzdálenost od hledaného vr holu v poètu krokù po hraná h hyperkry hle) a smìrovou èástodpovídají í pøi opera i S buï zvý¹ení nebo sní¾ení Hammingovy váhy, uká¾eme, ¾e po elýprùbìh algoritmu stavový vektor opìt neopustí (reálný) lineární obal tohoto souboru vektorù.Ve smyslu pøed hozího odstav e tedy oznaèmejx;+i = 1ppx,+

N−1∑

i=0|i|=x

n−1∑

d=0|i⊕2d|=x+1

jiijdi; x = 0; : : : ; n� 1;jx;�i = 1ppx,−

N−1∑

i=0|i|=x

n−1∑

d=0|i⊕2d|=x−1

jiijdi; x = 1; : : : ; n (5:12)Vektory jx;�i jsou jistì vzájemnì kolmé a jeji h normaliza i zajistíme volbou èísel px,±. Taudávají poèet pou¾itý h bázový h vektorù. Urèíme je následovnì: podmínky první sumy v oboupøípade h dávají (nx) mo¾ností pro smìrovou èást vektoru. Poèet mo¾ností d ve druhé ze sumnezávisí na konkrétní hodnotì i, pouze na jij = x, tímto poètem se tedy (nx) bude násobit.54

V prvním pøípadì je roven poètu nul v (i)2, ve druhém poètu jednièek, tedy n� x, resp. x, o¾dává px,+ = (nx)(n� x) = n!x!(n� x� 1)!px,− = (nx)x = n!(x� 1)!(n� x)! = px−1,+ : (5:13)

j0;!i j1; i j1;!i j2; i j2;!i j3; iObr. 25: Náhodná procházka na hyperkrychli: grafické znázornění bázových vektorů H

a jejich vybraných „vrstevÿPøedev¹ím pro poèáteèní stav j 0i platíj 0i = 1pNn N−1∑

i=0

n−1∑

d=0

jiijdi = 1pNn n−1∑

x=0

ppx,+jx;+i+ n∑

x=1

ppx,−jx;+i == 1pNn n−1∑

x=0

ppx,+(jx;+i+ jx+ 1;�i) = 1pN n−1∑

x=0

√(n−1x )(jx;+i+ jx+ 1;�i): (5:14)Podívejme se na ak i operátoru C a S na oznaèené kombina e.Je zøejmé, ¾e pro ka¾dý vektor jiijdi, který je zastoupen v lineární kombina i jx;+i, splòujeSjiijdi podmínky urèené sumami popisují ími jx+ 1;�i a naopak. Z vyjádøení vektorù jx;+i ajx;�i, prostoty S a rovnosti px,+ = px+1,− pak ry hle plyneSjx;+i = jx+ 1;�iSjx;�i = jx� 1;+i (5:15)pro ka¾dé x 2 f0; 1; : : : ; n� 1g.Ne h» x > 0 a jij = x. Proto¾e hledaným vr holem je 0, na vektor jiijdi pùsobí C jako IC1:Cjiijdi = jii(Cjdi) = jii 2n n−1

∑

e=0

jei � jdi (5:16)55

Pøitom pro n� x hodnot èísla e platí ji� 2ej = x+ 1 a pro zbylý h x platí ji� 2ej = x� 1. JetedyCjx;+i = 1ppx,+

N−1∑

i=0|i|=x

n−1∑

d=0|i⊕2d|=x+1

2n n−1∑

e=0

jiijei � jiijdi == 2nppx,+(n� x) N−1

∑

i=0|i|=x

n−1∑

e=0

jiijei � jx;+i == 2(n� x)nppx,+

N−1∑

i=0|i|=x

n−1∑

e=0|i⊕2e|=x+1

jiijei+ 2(n� x)nppx,+

N−1∑

i=0|i|=x

n−1∑

e=0|i⊕2e|=x−1

jiijei � jx;+i == 2(n� x)nppx,+

ppx,+jx;+i+ 2(n� x)nppx,+

ppx,−jx;�i � jx;+i == n� 2xn jx;+i+ 2√x(n� x)n jx;�i(5:17)

Podobným výpoètem by hom odvodiliCjx;�i = 2√x(n� x)n jx;+i+ 2x� nn jx;�i; (5:18)pak zbývá jen triviální pøípad Cj0;+i = �j0;+i.Uva¾me dále, jak jsme s hopni z amplitud vektorù jx;�i urèit zpìtnì pravdìpodobnostivýsledkù mìøení na pùvodním prostoru.Skalární souèin bázového vektoru jiijdi je nulový se v¹emi vektory jx;�i kromì takového,pro který platí x = jij a ji� 2dj = x� 1, s ním¾ je roven 1√px,±

. Bude tedy platitP|i〉|d〉 = 1px,±P|x,±〉; (5:19 a)kde P|x,±〉 znaèí druhou mo ninu absolutní hodnoty amplitudy odpovídají ího vektoru jx;�i.Ví e ne¾ úplné mìøení na H nás v¹ak bude zajímat mìøení na prostoru HS , zkoumejme tedyvýraz P|i〉 = n−1

∑

d=0

P|i〉|d〉 = n� xpx,+P|x,+〉 + xpx,−

P|x,−〉 = 1(nx) (P|x,+〉 + P|x,−〉) : (5:19 b)Pravdìpodobnost namìøení kteréhokoliv bázového stavu tedy závisí jen na Hammingovì vázejxj jeho prostorové èásti. Souèet pravdìpodobností P|x,+〉+P|x,−〉 = Px má pak bezprostøední vý-znam elkové pravdìpodobnosti namìøení nìkterého bázového vektoru s Hammingovou vahou x(který h je elkem (nx)). Vzhledem k tomu, ¾e jsme nede�novali vektor j0;�i, je pravdìpodobnostnamìøení j0i v HS pøímo rovna P|0,+〉.Nejen¾e tedy pøi výpoètu prùbìhu algoritmu postaèí místo nN amplitud bázový h vektorùjiijdi poèítat amplitudy tì hto 2n významný h kombina í, souèasnì se problém pøevedl z kvan-tové náhodné pro házky na hyperkry hli na problém veli e podobný kvantové náhodné pro ház ena pøím e s rùznými min emi v rùzný h polohá h.56

Analogie bude úplná, pokud zavedeme nové Hilbertovy prostory H′S = C n+1 , H′

C = C 2 aH′ = H′S H′

C , kde ortonormální bázi H′S oznaèíme bì¾ným zpùsobem a ortonormální bázi H′

Ckety j i a j!i a mírnì upravíme zú¾ení opera í S a C odvozené vý¹e:S′jiij!i = ji+ 1ij!i; i = 0; : : : ; n� 1;S′jiij i = ji� 1ij i; i = 1; : : : ; n;S′j0ij i = 0; S′jnij!i = 0; (5:20 a)C ′ = n∑

i=1

jiihij ( 2n√x(n� x) 1� 2xn2xn � 1 2

n

√x(n� x))� j0ih0j I: (5:20 b)Jestli¾e identi�kujeme vektory jiij!i s jx;�i a jiij i a jx;+i, snadno se pøesvìdèíme, ¾ejedna itera e U ′ = S′C ′ má v H′ stejný úèinek jako U = SC v H. þKrajníÿ vektory j0ij!i aj0ij i nemají v H protìj¹ky (prostor H′ má dimenzi 2n + 2), ale lineární obal v¹e h ostatní hbázový h vektorù je vùèi U ′ invariantní a touto identi�ka í izometri ký lineárnímu obalu vektorùjx;+i a jx;�i.Upozornìme je¹tì, ¾e lineární operátor S′ není unitární. Prostor H′ je v¹ak pouze pomo námatemati ká konstruk e a od U ′ tak unitaritu nepo¾adujeme.Ani pøes takové zjednodu¹ení není prùbìh algoritmu øe¹itelný analyti ky podobnì jednodu¹ejako v pøípadì Groverova algoritmu. Výpoèet je naopak veli e komplikovaný, vyu¾ívá nìkolikapomo ný h tvrzení a zanedbání a jeho výsledek je pøibli¾ný. Kompletní postup je obsahem vìt¹inyèlánku [27℄. Uvedeme tedy jen jeho výsledky.Pro dostateènì velká n má pravdìpodobnost namìøení hledaného vr holu v poètu itera ípodobnì os ilují í harakter jako u Groverova algoritmu. Délka jedné pùlvlny, tedy optimálnípoèet itera í, je pøibli¾nì k0 = [�2√2n−1] (5:21)(pro nezaokrouhlenou hodnotu platí odhad tf = π

2

p2n−1(1 + O(1=n)), jedná se tedy o spodníodhad tím lep¹í, èím vy¹¹í je n).Pravdìpodobnost dosa¾ená po tomto poètu itera í jep = 12 �O( 1n); (5:22)tedy její limitou pro velká n není 1, ale pouze 12 .Numeri ky aproximovaný prùbìh pravdìpodobností Px bìhem dvou pùlvln je znázornìn naobr. 26. V¹imnìme si nìkolika zajímavostí:{ Pravdìpodobnost, podobnì jako v Groverovì algoritmu, se pøerozdìluje ve prospì h hleda-ného vr holu a po pøekroèení optimálního poètu itera í periodi ky zpìt k pùvodnímu stavu.Tentokrát v¹ak nepøejde do hledaného vr holu v¹e hna, narazí na horní hrani i 12 . Stejnìvýrazný vr hol pravdìpodobnosti je souèasnì v P1, tedy struktura databáze se projeví tak,¾e je znaèná pravdìpodobnost namìøení nìkterého pøilehlého vr holu místo hledaného.{ Na první pohled si jednodu hým zpùsobem vymìòují dominan i dvì pravdìpodobnostní roz-lo¾ení, podobnì jako vektory jui a j0i v Groverovì algoritmu. Pøi bli¾¹ím prozkoumání v¹ak57

zjistíme, ¾e sinusové spojni e v poètu itera í jsou jemnì zvlnìny, prùbìh je tedy kompliko-vanìj¹í. Obr. 27 ukazuje, ¾e v pøípadì malého n jsou od hylky od tohoto pohledu znaèné.K obìma tìmto bodùm se podrobnìji vyjadøuje následují í paragraf.

Obr. 26: Průběh pravděpodobnosti Px v závislosti na Hammingově váze x a počtu provedených iterací,n = 10.

Obr. 27: Obdoba obr. 26 pro menší databázi: n = 5. Obrázek je natočen prosnadnější pohled na průběhy jednotlivých Px.5.4 Dal¹í vlastnosti prohledávání na hyperkry hliPøi detailnìj¹ím pohledu na obr. 27 si mù¾eme pov¹imnout, ¾e ka¾dá z pravdìpodobnostíPx je v¾dy stejná po dvoji í h následují í h krokù. Obr. 28 ukazuje názornì takové hovánípravdìpodobnosti P0 pro n = 10. ®e se nejedná o náhodné pozorování nebo dùsledek volbymalého n, se snadno pøesvìdèíme. Nejprve v¹ak budeme potøebovat nìkolik dodateèný h de�ni :Operátor min e C v zápisu (5.20 b) má tvar jednodu¹¹ího operátoru I C1 s poru hou.Oznaème tedy C0 = I C1 aU0 = SC0: (5:23)58

Okam¾itì by hom ukázali, ¾e j 0i je vlastním vektorem C0 i S pøíslu¹ejí ím vlastnímu èíslu 1.

Obr. 29: Vlevo: průběh pravděpodobnosti P0 v závislosti na počtu provedených iterací.Vpravo: průběh pravděpodobnosti Px v závislosti na Hammingově váze x po optimálním počtu kroků.

V obou případech je voleno n = 10.Oznaème dále Q1 lineární obal mno¾iny v¹e h bázový h vektorù H, jeji h¾ prostorová èástmá sudou Hammingovu váhu, a Q2 jeho ortogonální doplnìk do H. Oznaème dále js1i a js2iortogonální rozklad j 0i do Q1 a Q2.Vzhledem k tomu, ¾e jedno provedení S na libovolném bázovém vektoru zmìní paritu jehoprostorové èásti a C0 ani C ji neovlivní, musí U0 i U zobrazovat Q1 do Q2 a naopak. Proto¾ev¹ak j 0i = js1i+ js2i je vlastním stavem U0 pøíslu¹ejí ím vlastnímu èíslu 1, není jiná mo¾nost,ne¾ ¾e U0js1i = js2i a U0js2i = js1i. Proto¾e v¹ak ak e U0 a U se z bázový h stavù li¹í jen naj0ij!i, který patøí do Q1, platí také U js2i = js1i.Vý hozí stav vyhledáva ího algoritmu j 0i tedy mù¾eme zapsat jako js2i+ U js2i, po k ite-ra í h pøejde na Ukjs2i + Uk+1js2i. Tyto souèty stále ukazují ortogonální rozklad do Q1 a Q2a je zøejmé, ¾e stav po ka¾dé itera i se v jednom èitateli shoduje s pøed hozím a ve druhéms následují ím, èím¾ je dosa¾eno popsaného hování.Toto zji¹tìní má jeden veli e záva¾ný dùsledek: Oznaème P (k)x pravdìpodobnost Px pøiprovedení mìøení po k itera í h. Je souètem druhý h mo nin absolutní h hodnot amplitud jx;+ia jx;�i a tedy vìt¹í nebo rovna ne¾ kterýkoliv z tì hto èitatelù. Podívejme se na vztah P (k−1)1a P (k)0 . Na stav po k � 1 itera í h pùsobí nejprve opera e C. Ta v¹ak nezmìní souèet P (k−1)|1,+〉a P (k−1)|1,−〉 , jak by hom snadno ovìøili z (5.17) a (5.18). Následná opera e S pøenese amplituduj1;�i na j0;+i, kde bude jediným pùvod em pravdìpodobnosti P (k)0 = P (k)|0,+〉 a tedy musí platitP (k)0 � P (k−1)1 .Urèení vztahu mezi P (k)0 a P (k+1)1 je je¹tì jednodu¹¹í: pøi opera i C se u amplitudy j0;+ipouze zmìní znaménko, naèe¾ ji opera e S pøenese na amplitudu j1;�i. Proto¾e v¹ak P k+11 =P (k+1)|1,+〉 + P (k+1)|1,−〉 , bude i P (k+1)1 � P (k+1)|1,−〉 = P (k)|0,+〉.Podle døívìj¹ího odstav e se v¹ak P (k)1 rovná buï P (k−1)1 nebo P (k+1)1 , o¾ znamená, ¾eP (k)1 � P (k)0 nezávisle na k. 59

Proto¾e v¹ak po optimálním poètu itera í je pravdìpodobnost P0 podle (5.22) rovna 12�O( 1n )a pravdìpodobnost P1 mù¾e být jedinì je¹tì vìt¹í nebo rovna, jeji h souèet musí být 1�O( 1n ).To znamená, ¾e pro dostateènì vysoká n máme témìø jistotu, ¾e vr hol, který namìøíme, budebuï pøímo hledaným vr holem nebo s ním bude spojen hranou (bude mít vzdálenost 1). Dùle¾itáje pak ov¹em otázka, jestli je taková informa e k nìèemu u¾iteèná. Uka¾me si sílu tohoto závìruna pøíkladì. Zvolme n = 30. Optimální poèet itera í v tomto pøípadì vy hází asi 36 tisí . Potakto dlouhém experimentu máme pravdìpodobnost pouze 0;482, ¾e vr hol, který namìøíme, jehledaným vr holem. Pokud není, mù¾eme elý výpoèet opakovat a zvý¹it tak pravdìpodobnostnalezení správného výsledku na 0;731 a tak dále. Pokud v¹ak zkusíme ovìøit je¹tì pøilehlé vr holy,za enu pouhý h 30 (v nejhor¹ím pøípadì) dal¹í h dotazù na orákulum nalezneme správný vr hols pravdìpodobností 0;980!Nakone by hom mohli podobnì jako v paragrafu 4.3 diskutovat, jak se hová tento vyhle-dáva í algoritmus pro malá veli e malé hodnoty n. Výsledkem analýzy nìkolika první h itera íje, ¾e selhává pro n = 1, ale je¹tì také pro n = 2, od n = 3 dále se hová oèekávaným, jednotnýmzpùsobem. Podobný zvlá¹tní pøípad jako u Groverova algoritmu zde nenastává. Dal¹ím rozdílemoproti Groverovì algoritmu je, ¾e odhad optimálního poètu itera í (5.21) není pøesný, pro vìt¹íspolehlivost pøi men¹í h n by tedy bylo lep¹í algoritmus nejprve numeri ky simulovat a zjistit,po kolika itera í h je pravdìpodobnost namìøení oznaèeného vr holu nejvy¹¹í.5.5 Podobné vyhledáva í algoritmyV literatuøe jsou popsány dobøe i dal¹í vyhledáva í algoritmy zalo¾ené na kvantovém náhod-ném pro házení po pravidelný h grafe h. V tomto paragrafu se o ni h v¹ak opìt zmíníme pouzevýètem. Obe nì se do hází k výsledku, ¾e za vhodného pou¾ití kvantový h algoritmù je mo¾novyhledat oznaèený prvek v nesetøídìné databázi o velikosti N s èasovou slo¾itostí O(pN) nebo~O(pN).Èlánek [28℄ popisuje vyhledávání na ètver ové møí¾ e o rozmìre h pN � pN a zobe òujevýsledky i na pravoúhlé sítì vy¹¹í h dimenzí.Dále se de�nuje spojitá náhodná pro házka, která neprobíhá po kro í h. Je v klasi kém ob-raze limitním pøípadem situa e, kdy zkra ujeme èasový interval mezi kroky za enu pøidìleníjisté rostou í pravdìpodobnosti, ¾e objekt zùstane na místì. Z tohoto modelu je opìt odvozenakvantová analogie, která nevyu¾ívá kvantový h hradel, ale popisuje vývoj systému pomo í Ha-miltoniánu. Vztahy mezi tímto diskrétním a spojitým modelem nejsou dosud z ela po hopeny[29℄, zajímavé napøíklad je, ¾e spojitá pro házka nepotøebuje pomo ný prostor min e.Analýzou slo¾itosti spojitý h analogií Groverova algoritmu, vyhledávání na hyperkry hli i namøí¾ká h vy¹¹í h dimenzí se zabývá èlánek [30℄.5.6 Pro házení na obe ný h grafe h, opti ké sítìKlasi kou náhodnou pro házku jsme de�novali tak, ¾e jejím pùsobi¹tìm je libovolný graf.32Kvantové analogie jsme naproti tomu dosud diskutovali pouze na grafe h, které se vyznaèovaly32 Obecně se uvažují pro jednoduchost pouze neorientované grafy.60

znaènou strukturální jednodu hostí { pøímka i hyperkry hle jsou grafy regulární, v ka¾dém jeji hvr holu se setkává stejný poèet hran. Pravoúhlé sítì mají takovou vlastnost alespoò ve vìt¹inìsvý h vr holù a v krajní h vr hole h mají hran ménì.Otázkou je, jak by hom mohli roz¹íøit popsanou my¹lenku kvantového náhodného pro házenís min í ( oined quantum random walk, CQRW) jednotným zpùsobem na obe né grafy, o jeji h¾globální h vlastnoste h nemáme podobné informa e. Odpovìï na ni zatím není známa [26℄.33Takovou otázku je s hopen øe¹it poslední algoritmus, který v této prá i popí¹eme, nazývanýobèas v analogii s attering quantum random walk, SQRW [31℄. Jeho základem je (v souèasnédobì my¹lený) experiment, ve kterém ne háváme putovat fotony po opti ké síti, o¾ je zaøízeníprin ipiálnì podobné interferometru. Uká¾eme, ¾e tento algoritmus je v pøípadì regulární h grafùzobe nìním CQRW.Tento algoritmus byl poprvé popsán v [26℄. Jeho te hni kým podkladem jsou lineární opti képrvky zvané multiporty, teoreti ky popsané v prá i [32℄. Jedná se o zobe nìní polopropustnéhozr adla pro n vstupnì-výstupní h est.Polopropustné zr adlo, angli ky pøesnìji zvané beam splitter, je harakterizováno dvìmaparametry, koe� ienty odrazu r a prostupnosti t, jrj2+ jtj2 = 1. Jestli¾e na zr adlo dopadne fotonpøi házejí í z jedné strany, øeknìme zleva, transformuje se jeho stav j!ii na lineární superpozi istavù odpovídají í h prù hodu a odrazu s tìmito koe� ienty:j!ii 7! tj!io + rj io: (5:24 a)Jestli¾e bude foton dopadat z druhé strany, jeho stav bude podle základù kvantové optiky [33℄ortogonální k j!ii, výsledný stav v¹ak oèekáváme opìt v superpozi i stavù j!io a j io. Pro-to¾e od lineární opera e, která na zr adle probíhá, budeme oèekávat unitaritu, musí být tatosuperpozi e ortogonální k (5.24 a). Tak získáme a¾ na volnost ve volbì globální fáze vztahj ii 7! tj io � rj!io: (5:24 b)Multiport má, jak bylo øeèeno vý¹e, n vstupù a výstupù. Oèíslujme pevnì tyto opti ké estyèísly 1 a¾ n a oznaème zatím abstraktním vektorem jiii stav fotonu, který putuje po i-té z ni hsmìrem do multiportu, a jiio smìrem z multiportu ven. Ak i multiportu na vzájemnì ortogonálnívstupní stavy budeme hledat ve tvarujiii 7! rjiio + t n∑

j=1j 6=i

jjio = n∑

j=1

Cij jjio (5:25)Podmínka na unitaritu takového zobrazení, aplikovaná podobnì jako vý¹e, dá tentokrát pod-mínky pro t a r tvaru [26℄ (n� 1)jtj2 + jrj2 = 1(n� 2)jtj2 + 2Re tr = 0: (5:26)Taková podmínka je v¹ak souèasnì podmínkou unitarity mati e s prvky fCijgni,j=1. Na tuto ma-ti i pøedpokládané transformaèní vztahy kladou po¾adavky, aby v¹e hny její diagonální prvky33 Pokud známe maximální stupeň vrcholu v grafu – největší počet hran, který z některého jeho vrcholuvychází, obecné metody jsou známy [19]. 61

mìly hodnotu r a mimodiagonální t. Uvìdomme si, ¾e kromì triviální h pøíkladù násobkù jednot-kové mati e nìjakou globální fází jsme se seznámili je¹tì s jednou mati í, která tìmto po¾adavkùmvyhovuje: viz (5.8).Pro realiza i kvantové náhodné pro házky na obe ném grafu reprezentujeme ka¾dý vr holmultiportem s poètem vstupù rovným stupni vr holu. Ka¾dý výstup multiportu vede do jinéhomultiportu a tyto spojni e odpovídají hranám grafu.Prostor min e v tomto algoritmu nebude potøeba { je nahrazen informa í, po které opti kédráze foton do, resp. z daného multimetru pøi hází, resp. od hází.V algoritmu SQRW pøedpokládáme, ¾e stavový prostor je de�nován svou ortonormální bází,tvoøenou vektory oznaèenými jxyi, kde x a y znaèí dva vr holy uva¾ovaného grafu propojené hra-nou. Pod ka¾dým takovým vektorem budeme rozumìt foton putují í z multiportu odpovídají íhox do multiportu odpovídají ího y.Pøedpokládáme dále, ¾e esta fotonu po libovolné hranì trvá v¾dy stejnou èasovou jednotku.Budeme tedy uva¾ovat, ¾e bìhem této jednotky se stav systému v zavedeném formalismu nemìní,a vstupem do dal¹í takové fáze se zmìní skokovì. Tento vývoj proto nejlépe budeme popisovatoperátorem èasového vývoje U s parametry t1 voleným bìhem první fáze a t2 bìhem následují í.Tento operátor je urèen obrazy bázový h vektorù:U jxyi = n∑

j=1

C(y)ij jyzji; (5:27)kde C(y) je mati e multiportu ve vr holu y, i je èíslo výstupu tohoto multiportu ve smysluoznaèení (5.25), vedou ího k x, a zj je multiport, ke kterém dle stejného oznaèení vede výstupoèíslovaný j.Zkusme, jak by v takto zavedený h podmínká h bylo mo¾no najít analogii vyhledáva ího al-goritmu na hyperkry hli z paragrafu 5.3. Pro hyperkry hli øádu n bude tedy tøeba 2n multiportù,oznaèený h èísly 0 a¾ 2n, ka¾dý s n výstupy. Propojeny budou, stejnì jako vr holy hyperkry hle,multiporty, jeji h¾ èíselná oznaèení se ve dvojkové soustavì li¹í právì v jednom bitu. Jednotlivévýstupy multiportù oèíslujeme tak, ¾e i-tý výstup multiportu x povede k multiportu x � 2i,ne h» i = 0; 1; : : : ; n� 1. V¹imnìme si vlastnosti takového èíslování, ¾e stejná opti ká esta máu multiportù na obou kon í h stejné èíselné oznaèení.V¹em multiportùm kromì jednoho, odpovídají ího oznaèenému vr holu, pøiøaïme mati i(5.8) (jinými slovy r = 2n � 1, t = 2

n), oznaèenému vr holu mati i �I, tedy t = 0 a r = �1.Uká¾eme, ¾e prùbìhy obou algoritmù se stanou ekvivalentními, jestli¾e identi�kujeme vek-tory jxijdi z paragrafu 5.3 s vektory jx; x � 2di, zavedené v tomto paragrafu, pokud itera ipùvodního algoritmu my¹lenkovì pøetvoøíme z U = SC na tvar U = CS.Jedna taková itera e pak toti¾ pùsobí na bázový stavCSjxijdi = C (jx� 2dijdi) = n−1∑

j=0

Cx⊕2ddj jx� 2dijdi; (5:28 a)62

zatím o unitární vývoj pøiøazeného bázového stavu jx; x � 2di v SQRW algoritmu za jednotkuèasu je podle (5.27)U jx; x� 2di = n−1∑

j=0

Cx⊕2ddj jx� 2d; x� 2d � 2di = n−1

∑

j=0

Cx⊕2ddj jx� 2d; xi: (5:28 b)Vektor jx� 2d; xi byl pøitom identi�kován s vektorem jx� 2dijdi.Pro úplnou ekvivalen i algoritmù by bylo je¹tì tøeba udat odpovídají í poèáteèní stavv CQRW. Obe nì se toti¾ uva¾uje, ¾e foton umìle vy¹leme do jedné z opti ký h est, to alev udané identi�ka i rovno enné superpozi i v¹e h bázový h stavù v pùvodním algoritmu neod-povídá. Pøes stejný operátor èasového vývoje by tak oba systémy vykazovaly odli¹ný prùbìhstavu.Je zøejmá jedna okam¾itá výhoda algoritmu CQRW. Experimentální realiza e hradla (5.10)bude veli e snadná díky tomu, ¾e jednotlivým polohám odpovídají fyzi ky rùzné multiporty, amù¾eme tak jednodu¹e ka¾dé poloze pøiøadit, který je potøeba. Tato výhoda je za enu expo-nen iální prostorové nároènosti, která v pøípadì experimentálního sestavení CQRW algoritmupøesnì podle uvedeného návodu umo¾nila jeho vyu¾ití jen v pøípade h drobný h n.

63

ZávìrCílem prá e bylo popsat úvod do problematiky kvantový h algoritmù. Není v¹ak v mo¾nos-te h rozsahu jedné podobné prá e popsat vìt¹í mno¾ství algoritmù tak podrobnì, jak jsem sepokusil alespoò u Groverova algoritmu a vyhledávání na hyperkry hli, pro udr¾ení rozumnéhorozsahu prá e musely být informa e o ostatní h algoritme h podány buï velmi útr¾kovitì, nebozkrá eny na pouhé zmínky o jeji h existen i. Detaily kvantové me haniky by také potøebovalydùslednìj¹í rozbor a uvedení uvedení ví e de�ni í a zákonitostí napø. v paragrafu o kvantovémmìøení. Pøesto doufám, ¾e prá e svùj úèel splnila v rám í h svý h mo¾ností dobøe.

64

PøílohyJako pøílohy uveïme výpisy zdrojový h kódù nìkolika poèítaèový h programù, které byly vy-u¾ívány ke tvorbì grafù v prá i obsa¾ený h. Zdrojové kódy jsou psány v programova ím jazy e Ca pro pøeklad vy¾adují pøekladaè implementují í standard ISO 9899-1990.

65

A.1 Program groverTento jednodu hý program slou¾í k nalezení pravdìpodobnosti namìøení hledaného vr holuv Groverovì algoritmu po optimálním poètu itera í. Vzhledem k tomu, ¾e se jedná pouze o do-sazení do vzor e, mohl být nahrazen pou¾itím libovolného tabulkového pro esoru { program jetedy uvádìn vedle ostatní h dvou spí¹e pro úplnost { ale v této formì byl inspira í ke zkoumáníproblematiky paragrafu 4.3.#in lude <stdio.h>#in lude <math.h> onst int Nm = 20; // Délka tabulkyint main() {int n, N;for(n = 2; n <= Nm; n++) {N = floor(M_PI/4*pow(2.0, n/2.0));printf("%i %.6f %.6f\n", n, pow(sin((2*N+1)*asin(pow(2.0, -n/2.0))), 2),1-pow(2.0, -n));}return 0;}

66

A.2 Program qrw-lineTento program simuluje kvantovou náhodnou pro házku na pøím e. Poèet itera í N musíbýt uveden na poèátku, tomu pak je pøizpùsobena délka pra ovního pole. Výstupem je výèetpravdìpodobností namìøení na ka¾dé poloze po tomto poètu itera í.#in lude <stdio.h>#in lude <math.h>#in lude < omplex.h>#define N 50 // Poèet itera í#define V M_SQRT1_2 // Pøevrá ená hodnota odmo niny ze 2#define C 2 // Výbìr min e z mo¾ností ní¾eint main() {double omplex fld[2*N+1℄[2℄ = {{0}}; // Pra ovní poledouble omplex 2[2℄[2℄ = {{V, V}, {V, -V}}, // Min e pou¾ívané v obr. 22 3[2℄[2℄ = {{V, I*V}, {I*V, V}}, 4[2℄[2℄ = {{V, (I+1)/2.0}, {-V, (I+1)/2.0}};double omplex t;int i, j;fld[N℄[0℄ = I*V; // Poèáteèní stav: amplituda "vlevo"fld[N℄[1℄ = V; // a "vpravo"for(i = 0; i < N; i++) { // Opera e Cfor(j = 1; j < 2*N; j++) {t = C[0℄[0℄*fld[j℄[0℄ + C[0℄[1℄*fld[j℄[1℄;fld[j℄[1℄ = C[1℄[0℄*fld[j℄[0℄ + C[1℄[1℄*fld[j℄[1℄;fld[j℄[0℄ = t;}for(j = 0; j < 2*N; j++) // Opera e Sfld[j℄[0℄ = fld[j+1℄[0℄;for(j = 2*N; j > 0; j--)fld[j℄[1℄ = fld[j-1℄[1℄;}for(j = 0; j < 2*N+1; j++) // Výpis pravdìpodobnostíprintf("%i %.6f\n", j-N, pow( abs(fld[j℄[0℄), 2) +pow( abs(fld[j℄[1℄), 2));return 0;}67

A.3 Program qrw- ubeTento program simuluje algoritmus vyhledávají í na hyperkry hli. Vyu¾ívá k tomu zjed-nodu¹ení zavedené v paragrafu 5.3. Jeho výstupem je tabulka pravdìpodobností pou¾itá provykreslení obr. 26 a 27.#in lude <stdio.h>#in lude <math.h>#define N 10 // Rozmìr hyperkry hledouble binom(int a, int b) { // Binomi ké koefi ientydouble v = 1.0; // Tento výpoèet není pøíli¹ efektivní,int i; // ale funguje i pro velká Nif(b < 0 || b > a) return 0;for(i = 0; i < b; i++)v = v * (a-i) / (b-i);return v;}int main() {double fld[N+1℄[2℄, , s, t; // Pra ovní poleint i, it, m, st, o;for(i = 0; i <= N; i++) { // Vý hozí stavfld[i℄[0℄ = sqrt(binom(N-1, i) / pow(2, N));fld[i℄[1℄ = sqrt(binom(N-1, i-1) / pow(2, N));}m = M_PI/2/M_SQRT2*pow(2, N / 2.0); // Optimální poèet krokùif(m > 1000) // Pokud je pøíli¹ velký, budeme vypisovatst = m / 100; // pouze ka¾dou stou øádkuelsest = 1;for(it = 0; it <= 2*m; it++) { // Délka dvou pùlvlnfld[0℄[0℄ = -fld[0℄[0℄; // Opera e Cfor(i = 0; i <= N; i++) { = 1 - 2.0*i/N;s = 2.0 / N * sqrt(i * (N-i));t = *fld[i℄[0℄ + s*fld[i℄[1℄;fld[i℄[1℄ = s*fld[i℄[0℄ - *fld[i℄[1℄;fld[i℄[0℄ = t;}for(i = 0; i < N; i++) { // Opera e St = fld[i℄[0℄;fld[i℄[0℄ = fld[i+1℄[1℄;fld[i+1℄[1℄ = t; 68

}if(!(it % st)) // Výpis pravdìpodobností P_xfor(i = 0, o = 0; i <= N; i++) { = pow( abs(fld[i℄[0℄), 2) + pow( abs(fld[i℄[1℄), 2);printf("%.6f ", abs( ));}puts("");}return 0;}

69

Pou¾itá literatura[1℄ Pytlíèek, J. Lineární algebra a geometrie. Skripta ÈVUT, Vydavatelství ÈVUT, Praha, 2002.122 s.[2℄ Blank, J., Exner, P., Havlíèek, M. Lineární operátory v kvantové fyzi e. Karolinum, Praha,1993. 678 s.[3℄ Nielsen, M.A., Chuang, I. L. Quantum Computation and Quantum Information. CambridgeUniversity Press, Cambridge, UK, 2000. 676 s.[4℄ Hlavatý, L. Slabikáø kvantové me haniky. Skripta ÈVUT, nevydáno, 2006[5℄ Wikipedia, the free en y lopedia. Tensor produ t. <http://en.wikipedia.org/wiki/Tensorprodu ts> [rev. 17. 4. 2007, it. 6. 5. 2007℄[6℄ Einstein, A., Podolsky, B., Rosen, N. Can Quantum-Me hani al Des ription of Physi alReality Be Considered Complete? Phys. Rev., 47, s. 777{780, 1935, k nahlédnutí bezplatnìna <http://prola.aps.org/abstra t/PR/v47/i10/p777 1> [ it. 11. 7. 2007℄[7℄ Wikipedia, the free en y lopedia. EPR paradox. <http://en.wikipedia.org/wiki/EPRparadox> [rev. 26. 6. 2007, it. 11. 7. 2007℄[8℄ Wikipedia, the free en y lopedia. Bell's Theorem. <http://en.wikipedia.org/wiki/Bell%27stheorem> [rev. 27. 6. 2007, it. 11. 7. 2007℄[9℄ Peres, A.Quantum Theory: Con epts and Methods.Kluwer A ademi Publishers, Dordre ht,NL. 1989. 446 s.[10℄ Berman, G.P., Doolen, G.D., Mainieri, R., Tsifrinovi h, V. I. Introdu tion to QuantumComputers. World S ienti� Publishing, Singapore, 1998. 187 s.[11℄ Wikipedia, the free en y lopedia. Hadamard transform. <http://en.wikipedia.org/wiki//Hadamard transform> [rev. 16. 6. 2007, it. 30. 6. 2007℄[12℄ Lavor, C., Manssur, L.R.U., Portugal, R. Grover's Algorithm: Quantum Database Sear h.arXiv:quant-ph/0301079[13℄ Shor, P.W. Polynomial-Time Algorithms for Prime Fa torization and Dis rete Logarithmson a Quantum Computer. arXiv:quant-ph/9508027v2[14℄ Wikipedia, the free en y lopedia. Shor's algorithm. <http://en.wikipedia.org/wiki/Shorsalgorithm> [rev. 11. 6. 2007, it. 14. 7. 2007℄[15℄ Virius, M. Základy algoritmiza e. ÈVUT, Praha, 1995. 179 s.[16℄ Wikipedia, the free en y lopedia. Cooley-Tukey FFT algorithm. <http://en.wikipedia.org//wiki/Cooley-Tukey FFT algorithm> [rev. 12. 6. 2007, it. 14. 7. 2007℄[17℄ Be kman, D. et al. EÆ ient networks for quantum fa toring. arXiv:quant-ph/9602016v1[18℄ Grover, L.K. A fast quantum me hani al algorithm for database sear h. arXiv:quant-ph//9605043[19℄ Kempe, J. Quantum random walks { an introdu tory overview. Contemporary Physi s, 44,s. 307{327, 2003[20℄ Boyer, M., Brassard, G., H�yer, P., Tapp, A. Tight bounds on quantum sear hing. arXiv::quant-ph/9605034v1 70

[21℄ Brassard, G., H�yer, P., Mos a, M., Tapp, A. Quantum Amplitude Ampli� ation and Esti-mation. arXiv:quant-ph/0005055v1[22℄ Chi, D. P., Kim, J. Quantum Database Sear hing by a Single Query. arXiv:quant-ph//9708005v1[23℄ Ambainis, A. Quantum walks and their algorithmi appli ations. arXiv:quant-ph/0403120[24℄ Nayak, A., Vishvanath, A. Quantum walk on the line. arXiv:quant-ph/0010117[25℄ Meyer, D.A. On the absen e of homogenous s alar unitary ellular automata. arXiv:quant-ph/9604011v2[26℄ Hillery, M., Bergou, J., Feldman, E. Quantum walks based on an interferometri analogy.arXiv:quant-ph/0302161v1[27℄ Shenvi, N., Kempe, J., Whaley, K. Quantum Random Walk Sear h Algorithm. arXiv:quant-ph/0210064[28℄ Ambainis, A., Kempe, J., Rivosh, A. Coins Make Quantum Walks Faster. arXiv:quant-ph//0402107[29℄ Kendon, V. Quantum walks on general graphs. arXiv:quant-ph/0306140[30℄ Childs, A.M., Goldstone, J. Spatial sear h by quantum walk. arXiv:quant-ph/0306054v2[31℄ Ko¹ík, J., Bu¾ek, V. S attering model for quantum random walks on hyper ube. arXiv:quant-ph/0410154v2[32℄ Jex, I., Stenholm, S., Zeilinger, A. Hamiltonian theory of a symmetri multiport. Opt. Com-mun. 117, 95 (1995)[33℄ Paul, H. Introdu tion to Quantum Opti s: From Light Quanta to Quantum Teleportation.Cambridge University Press, Cambridge, UK, 2004. 254 s.

71

Prohlá¹eníProhla¹uji, ¾e jsem svou bakaláøskou prá i vypra oval samostatnì a pou¾il jsem pouze lite-raturu uvedenou v pøilo¾eném seznamu.Nemám záva¾ný dùvod proti u¾ití tohoto skolního díla ve smyslu x 60 Zákona è. 121/2000 Sb.,o právu autorském, o práve h souvisejí í h s právem autorským a o zmìnì nìkterý h zákonù(autorský zákon).V Praze dne . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .podpis

72