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

BAKALÁØSKÁ PRÁCEQuantum Algorithms

2007 Válav Potoèek

PodìkováníRád byh tímto podìkoval vedouímu bakaláøské práe, panu prof. Ing. Igoru Jexovi, DrS.,nejen za podnìtné konzultae 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: Matematiké in¾enýrstvíZamìøení: Matematiká 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 jejih klasikými protìj¹ky.Klíèová slova: kvantové algoritmy, prohledávání databáze, Groverùv algoritmus, kvantové ná-hodné proházeníTitle:Quantum algorithmsAuthor: Válav PotoèekAbstrat: This thesis shows basis of quantum algorithm topis. Its purpose is not to desribe indetail every single known algorithm of some importane. More likely, emphasis is put in explainingthe main onepts and relations of quantum algorithms to their lassial ounterparts.Key words: quantum algorithms, database searh, Grover's algorithm, quantum random walks

ObsahÚvod . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11. Základy kvantové mehaniky . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21.1 Postuláty kvantové mehaniky . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 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 Matie hustoty . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 141.8 Redukovaná matie hustoty . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 182. Kvantová mehanika a zpraování informae . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 202.1 Dvoudimenzionální prostory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 202.2 Pauliho matie . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 222.3 Kvantová hradla . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 232.4 Univerzální mno¾ina hradel . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 282.5 Simulae klasikýh obvodù kvantovými hradly . . . . . . . . . . . . . . . . . . . . . . . . . . . 283. Kvantové algoritmy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 323.1 Kvantová teleportae . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 323.2 Shorùv algoritmus . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 343.3 Kvantová Fourierova transformae . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 363.4 Fourierova transformae 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øípadeh . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 444.4 Variae Groverova algoritmu . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 454.5 Realizae 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é proházení . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 495.2 Kvantové náhodné proházení . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 505.3 Vyhledávání na hyperkryhli . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 535.4 Dal¹í vlastnosti prohledávání na hyperkryhli . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 585.5 Podobné vyhledávaí algoritmy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 605.6 Proházení na obenýh grafeh, optiké 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 klasikýh algoritmù, realizovanýhv elektroniký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 teoretiký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ísteh 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 letehstudia matematiky. Znalost základù kvantové mehaniky je výhodou, ale èásti potøebné propohopení tématu budou shrnuty v první kapitole.V ní jsou uvedeny postuláty kvantové mehaniky v obené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 prinipù, které mají v teoriikvantovýh algoritmù pøímé vyu¾ití.Druhá kapitola je ji¾ zamìøena na vyu¾ití kvantové mehaniky pro nalezení blízké analogielogikýh obvodù. Nejprve se uká¾e zobenìní bitu na kvantový bit, qubit, zavedeme prinipkvantovýh hradel jako obdoby klasikýh digitálníh hradel, a uká¾eme, jak pøes jisté odli¹nostijsme shopni pomoí tìhto nástrojù simulovat libovolný digitální obvod.Ve tøetí kapitole uká¾eme na nìkolika nejznámìj¹íh pøíkladeh mo¾nosti, které poskytujeidea kvantovýh algoritmù jako výhody oproti klasiký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, jejih¾ 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é faktorizae 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éhoproházení do svìta kvantovýh algoritmù a pøedev¹ím jeho vyu¾ití v my¹lene vyhledávaíhalgoritmù, algoritmus vyhledávajíí na hyperkryhli. Struènì je nastínìna problematika realizaekvantovýh vyhledávaíh algoritmù v optiký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í numerikýh øe¹enínìkterýh problémù. Dùle¾itìj¹í vlastní závìry jsou uvedeny v paragrafeh 4.3 a 5.4.1

Kapitola 1Základy kvantové mehanikyKvantová mehanika tvoøí matematiký model, na jeho¾ základì kvantové algoritmy praují.V prvním a druhém paragrafu této kapitoly tak uvedeme postuláty, na nih¾ je kvantová meha-nika zalo¾ena. Ve tøetím a ètvrtém paragrafu zavedeme prvky formalismu, který budeme dálev rámi této práe vyu¾ívat. V posledníh paragrafeh 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é mehanikyKvantová mehanika není podle [3℄ sama fyzikální teorií, pouze matematikým vzorem, najeho¾ základì jsou zalo¾eny jednotlivé teorie nazývané spoleènì kvantovou teorií.Takové oznaèení ov¹em nemusí být zela jednoznaèné { uèebnie [4℄ napøíklad uvádí pod stej-ným názvem jednu z takovýh fyzikálníh teorií, která tvoøí obdobu klasiké mehaniky. V takovépodobì byla kvantová mehanika popsána E. Shrödingerem ve dvaátýh leteh 20. století. Daloby se tedy øíi, ¾e existují rùzné stupnì matematiké abstrake této formulae. V této prái bu-deme pou¾ívat vý¹e naznaèenou matematikou formulai kvantové mehaniky, øízenou sadoupostulátù, ve formì, kterou uvádí [3℄. Jedná se o sjednoení rùznýh smìrù, kterými se kvantovámehanika v dobì svého vzniku vyvíjela { toto sjednoení, známé od pøelomu 20. a 30. let, jepraí P.A.M. Diraa a J. von Neumanna.Uveïme tedy nyní jednotlivé postuláty této formulae, a nìkolik prvníh poznámek ke ka¾-dému z nih.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¹ehnyvzore kvantové mehaniky 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 nih délku ka¾dého pou¾itého vektoruvytknout v nulové moninì.Výjimku v pøedhozímu odstavi tvoøí nulový vektor stavového prostoru. Kdybyhom 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á situae mìla tento dùsledek, nebude moi 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 matematikou 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í hranie pou¾itelnosti lineární algebry (nemá napøíklad de�novány ¾ádné vektorové ope-rae).Nakone v rámi této práe budeme praovat s koneènìdimenzionálními (prehilbertovými)vektorovými prostory, o¾ znaènì usnadní výklad a matematiký formalismus a rovnì¾ zamezívzniku problémù, které je tøeba øe¹it v jinýh aplikaíh kvantové mehaniky [4℄. Ve zela vý-jimeènýh pøípadeh pou¾ijeme v krátkýh úseíh textu i nekoneènìdimenzionální prostor sespoèetnou bází (separabilní). V takovýh pøípadeh 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é informae 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 konovém èase.Tento postulát je tøeba hápat tak, ¾e z konstruke uva¾ovaného fyzikálního systému vyplýváexistene takového unitárního operátoru U na stavovém prostoru, parametrizovaného poèáteè-ním a konový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 koni intervalu bude ve stavupopsaném vektorem U .Dùsledkem linearity unitárního operátoru je prinip superpozie: 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 funkemi 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í podledifereniální rovnie �(t)�t = � i�hH(t)(t); (1:2)kde (t) je stavový vektor systému v èase t, �h redukovaná Plankova konstanta a H(t) hermi-tovský operátor pro libovolné t [3℄.1Operátor H, obenì závislý na èase, má ve Shrödingerovì reprezentai kvantové mehanikypøí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é Plankovy konstanty v rovnii (1.2). V matematiké formulai se konstantauvádí z tohoto historikého dùvodu, jinak by ji bylo mo¾no zahrnout do de�nie operátoru H.Pøi ka¾dé unitární operai se zahová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ì, kdybyhom 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 prinipem superpozie) 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 praovats víeèástiovými systémy. Pøipomeòme napøíklad, ¾e v klasiké mehanie je stavový prostorslo¾eného systému tvoøen direktním souètem stavovýh prostorù jeho komponent.V paragrafeh 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é mehaniky 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émehaniky je rùzným zpùsobem zdùvodòováno, proè by mìøení mìlo systém výraznì ovlivòovat,z matematiké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. rovnii ú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ì deterministiký proes a díky unitaritì èasového vývojedokone 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ámehanika nabízí.Vzhledem k tomu, ¾e o operátoreh Mm nepo¾adujeme, aby byly prosté, mìøení dále neníobenì ani vratným proesem. V dùsledku toho nemù¾eme postupnými mìøeními získávat stáledetailnìj¹í informae o stavu systému. Snadno dokone 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:Neh» a ' jsou dva neortogonální jednotkové vektory, neh»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í informai o stavu kvantového systému bude tvoøitvelkou pøeká¾ku pro vyu¾ívání kvantové mehaniky k realizai výpoètù.Mìøením je ve smyslu pøedhozíh odstavù tedy obenì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 rovnie ú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 rovnii ( ; ) = 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í rovnii úplnosti.Zmiòme, jak by bylo tøeba znìní postulátu upravit, kdybyhom v postulátu 1 nahradilipo¾adavek na pou¾ívání jednotkovýh vektorù pouze zákazem nulového vektoru. De�nie mìøiíh3 Stále zde připomínáme slovo „obecněÿ z důvodu, že definici vyhovuje i měření s jediným měřicím

operátorem I, které dá svůj jediný výsledek s jistotou a stav systému nezmění.5

operátorù Mm ani rovnii ú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 vzorem 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 prostoreh 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. Rovnie ú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 Shrödingerovì reprezentai, 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 rovnie (1.2) se nazývá Shrödingerova rovnie.Problematika kvantového mìøení je mnohem rozsáhlej¹í a projektivní mìøení jsou veliedobø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ìmaformulaemi { mìøení, jejih¾ 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 prostoreh 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, neh» 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 IHj jednotkový 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øedhozíh bodeh a uva¾ujme obenousuperpozii = n∑i=1

�i i: (1:10 a)Délka vektoru je dle de�nie 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 druhoumoninou absolutní hodnoty koe�ientu lineární kombinae u vektoru i, kterou budeme nazývatamplituda vektoru i.Tímto je tedy vymezena sada postulátù, na jejih¾ 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 zelaobené { odpovídají jistým ideálním pøedpokladùm o popisovaném systému a mo¾nosteh na¹íznalosti jeho stavu. V paragrafu 1.7 pøedstavíme alternativní sadu postulátù, která je za stejnýhpøedpokladù matematiky ekvivalentní [3℄, ale univerzálnìj¹í pro praktiké 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 matematikýhobjektù. V tomto textu budeme vyu¾ívat znaèení obvyklé pøedev¹ím v literatuøe k teorii kvantovéinformae, tzv. Diraovu nebo bra-ketovou notai. 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í kombinae vektorù jxi a jyi tak mù¾e být 12 jxi+ ijyi.Diraova notae nám dává mo¾nost vyu¾ívat jako þvnitøekÿ ketu rùzné skupiny symbolù:bì¾ná jsou písmena latinské i øeké abeedy, èíslie i jiné matematiké znaèky (èasto se setkámenapø. s kety j+i a j�i), v dal¹íh oblasteh kvantové fyziky se pou¾ívají i jiné znaèky (j"i, jvai,j~pi apod.)Dùle¾itá poznámka je, ¾e v kvantové mehanie 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 praovat s jedním Hilbertovým prostorem, vektory oznaèené èísly j0i; j1i; : : : budou dáleoznaèovat jeho ortonormální bázi a jejih ortogonality budeme vyu¾ívat bez dal¹ího pøipomínání.Upozornìme v¹ak pøedem, ¾e èasto budeme praovat 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 Diraovy notae jsou bra-vektory. Jestli¾e oznaèíme kety prvky nìjakéhovektorového prostoru, dle nejobenìj¹í de�nie jsou bra vektory z prostoru k nìmu duálního,tedy spojité lineární funkionály [2℄. Je v¹ak známo, ¾e duální prostor k Hilbertovu prostoru jenový Hilbertùv prostor s ním izometriký 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, ¾eake h'j (jako funkioná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 jejih vztah budeme znaèittak, ¾e pro þvnitøekÿ pou¾ijeme stejný symbol: h'j = hyj.První zmìnou zavedenou pou¾itím Diraovy notae je, ¾e v aki funkionálu na vektor vy-nehá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, matematiky øeèeno tedy dode�nujeme operai 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émeh.Ve smyslu pøedhozího paragrafu budeme èasto potøebovat je¹tì oznaèení pro tenzorovýsouèin dvou vektorù (obenì z rùznýh prostorù). I pro ten umo¾òuje Diraova notae zavéstjednoduhé konzistentní oznaèení: ve výrazu jxi jyi vyneháme znaèku tenzorového souèinua budeme psát jxijyi. Pokud naví budou násobené vektory prvky stejného prostoru, mù¾emedokone vynehat vnitøní dvojii 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 Diraovì notai 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 Æ jihdj = jaihbjihdj(�jxi+ �jyi)jzi = �jxijzi+ �jyijzi� � � (1:12)V tomto místì upozornìme na výraz tvaru hxjhyj. Z pøedhozí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 vyneháním v hxjhyj, pak podle de�nie tenzorového souèinu dvou lineárníhzobrazení musí platit hxjhyj(jaijbi) = hxjaihyjbi; (1:13)bli¾¹í smyslu pøedhozího odstave by v¹ak bylo, kdybyhom 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 tutooperai rovnì¾ budeme pøíle¾itostnì potøebovat { neh» 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 Diraovy notaev 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 sloupovýh vektorù. To je elkem obvyklá konvene,i kdy¾ pøíklad [1℄ ukazuje, ¾e ne zela zaruèená.Je tøeba stanovit, jak budeme v tomto prostoru reprezentovat bázové vektory fjiign−1i=0 . Jistìmusíme zahovat 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 byhom mohli zajistit pro libovolnì zvolenou bázi, aby byla ortonormální. Stanovmeproto, ¾e v prostoreh 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)Neh» tedy jxi a jyi jsou prvky C n ,jxi =

x1x2...xn; jyi = y1y2...yn: (1:16 a)Jejih 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 matie(x1 � � � xn ) y1...yn (1:16 )a identi�kujeme výslednou ètverovou matii prvního øádu s jejím jediným prvkem. Operae,kterou jsme pøitom provedli se sloupovým vektorem jxi, braným jako matie typu n � 1, jekombinaí transpozie a komplexního srdu¾ení prvkù, tedy analogií sdru¾ení pro obdélníkovématie.Je tedy mo¾né uva¾ovat duální prostor jako prostor øádkovýh vektorù a obenì 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 asoiativity násobení mati.Tenzorový souèin Hilbertovýh prostorù je, jak byhom 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 reprezentae známá jako Kronekerùv souèin, viz napø. [5℄: z matiA 2 C a,b a B 2 C c,d utvoøíme matii 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 reprezentai øíi jxijyi 2 Cm C n = Cmn ajxijyi =

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

: (1:19 b)Snadno byhom ukázali, ¾e pokud rozepí¹eme napøíklad výraz (A B)(jxijyi) pro matieA a B patøiènýh rozmìrù pomoí Kronekerova 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émeh.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 Diraovì notai jej i = 1p2 1001: (1:21 a)Pokud byhom 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 sloupové 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 staveh 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℄). Jejih existene je nevyhnutelným dùsledkem de�nie tenzorového souèinu.1.6 Paradox EPRProvázání je také pùvodem známého paradoxu EPR [6℄. Autoøi Einstein, Podolsky a Rosen,jejih¾ nese jména, se jím sna¾ili ukázat, ¾e pojetí kvantové mehaniky pomoí vlnovýh funkí7 zapøedpokladu platnosti postulátù uvedenýh vý¹e vede ke sporùm, z nih¾ jeden detailnì popsali.Tento pøíklad zde nebudeme uvádìt,8 proto¾e by bylo nutno detailnì vysvìtlit detaily kvan-tové mehaniky na Hilbertovýh prostoreh nekoneèné dimenze, uká¾eme v¹ak jeho mnohemjednodu¹¹í variantu, kterou se zabýval J. S. Bell. Tento fyzik nejen¾e ukázal obdobu formulaeparadoxu 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 kvantovoumehanikou nebo zda byly hybné pøedpoklady paradoxu. Podívejme se tedy blí¾e na Bellùvpøíklad:Jeden velie známý provázaný stav, oznaèovaný z historikýh dùvodù jako spinový sin-glet [3℄, j i = 1p2(j01i � j10i); (1:22)má zajímavou vlastnost: jestli¾e na stavovýh prostoreh 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 jejih 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á transformae harakter rotae 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éfunke buï do stavu j01i nebo j10i. Výsledek sie 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 byhom vytvoøili sérii dvoji èásti, ka¾dou z nih v tomto provázaném stavu, a provádìlina ka¾dé mìøení popsaným zpùsobem, pozorovali byhom mezi výstupy korelai.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øihází rozumný argument EPR:Dosud jsme provádìli pouze matematiké úvahy. Pøedstavme si situai v¹ak z fyzikálního po-hledu, a to na pøíkladì dvou èásti. Dle postulátù kvantové mehaniky mohou být v provázanémstavu, a» jsou libovolnì vzdálené, a i tehdy, kdy¾ zabráníme jejih vzájemné interaki. Abyhomzabránili v¹em známým formám interake, mù¾eme uva¾ovat, ¾e se jedná o dva fotony, které sevzájemnì vzdalují ryhlostí svìtla, jednotlivé báze neh» pak mají význam natoèení detektorùpolarizae.Jestli¾e provedeme na první èástii mìøení v bázi fj0i; j1ig, mù¾eme dle výsledku s urèitostíøíi, ¾e druhá èástie se bude pøi libovolném následném mìøení hovat, jako by byla pøipravenave stavu j0i, resp. j1i. Kdybyhom ale provedli mìøení v nové bázi fj+i; j�ig, mohli byhomo stejné èástii øíi, ¾e je ve stavu j+i nebo j�i.Proto¾e jsme zabránili interaki mezi obìma èástiemi, druhá èástie se v¹ak nemù¾e þdo-zvìdìtÿ o tom, jaké mìøení jsme se rozhodli provést na první èástii. Jestli¾e tedy jsme prvníèástii namìøili napøíklad ve stavu j0i, druhá ji¾ musela nìjakým zpùsobem být na tuto situaipøipravena ve stavu j1i. Kdybyhom v¹ak první mìøení provedli v nové bázi a namìøili j+i, druháèástie 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í { kdybyhom i na druhé èástii provedli mìøení v pùvodní bázi,stav j1i implikuje nulovou pravdìpodobnost namìøení j0i, zatímo j�i ani j+i ne.EPR tím argumentovali, ¾e popis fyzikální reality pomoí vlnovýh funkí není kompletní,proto¾e druhé èástii není mo¾no po oddìlení ¾ádnou pøiøadit. V¹imnìme si, ¾e kvantová meha-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øihází dùle¾itost otázky, jak by stav druhé èástie po mìøení první èástiemohl záviset na jeho výsledku, kdy¾ je efektivnì zabránìno pøenosu jakékoliv informae.Prostorové oddìlení èásti se zdálo být tak silným argumentem, ¾e poèaly snahy kvantovoumehaniku 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é funketvoøí skuteènì jen èásteèný popis stavu fyzikálního systému a pøedev¹ím, ¾e proes mìøení jedeterministiký a jeho statistiký harakter v kvantové mehanie je jen projevem na¹í neznalostia neshopnosti ovlivnit dodateènou informai.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émehaniky. 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 jednoduhým zpùsobem vyvodí nerovnost, kterouby pak musely splòovat rùzné míry korelae 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ímo u kvan-tové mehaniky nejsou. Dal¹í analýza pøíkladu s rùznými bázemi C 2 by ukázala, ¾e existují si-tuae, ve kterýh kvantová mehanika Bellovu nerovnost poru¹uje. Závìrem tedy je jednoduhé,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á mehanika.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é mehaniky, i kdy¾ èást fyzikálníhosvìta je stále skepiká [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 èástie bylo mo¾no uva¾ovat fyzikálnì zela izolované, i kdyby s seboumohly nést libovolné mno¾ství informae libovolného druhu.Celý prùbìh této diskuse s mnoha dal¹ími zajímavými náhledy, dodateènými informaemia úze 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 nih¾ 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øeh provázanýh staveh 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éinformae (pøedev¹ím v¹ak mezi kvantovými komunikaèními protokoly) ¹iroké vyu¾ití díky svéjednoduhostí, díky ní¾ jsme se ji¾ i se dvìma z nih seznámili. Jejih de�nie 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 matiového zápisu) byhom se pøesvìdèili, ¾e se zároveò jedná o zajímavouortonormální bázi odpovídajíího prostoru.1.7 Matie hustotyPojemmatie hustoty10 vzniknul z potøeby popisovat fyzikální systémy, o jejih¾ stavu mámepouze èásteèné informae. 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

Matie 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�nii odpovídají line-ární operátory, jejih¾ matie je hermitovská, pozitivní (odpovídá matii pozitivnì semide�nitníkvadratiké 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é mehaniky v rùznýh staveh. Neh» 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 praovat, 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.Matie hustoty je naproti tomu jediný matematiký objekt, který kompletnì popí¹e tuto situaia v¹ehny výsledky dá stejné.Uva¾ovanému systému pøiøadíme matii 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 matii hustoty dá kvantové mìøení. To provedeme ve smyslu pøedhozího odstave.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í operaeU , 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 matii hustotyv analogii vzore (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á operae U bude udávat pøímý vztah i mezi obìma matiemi 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 matii 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 vzore, jakého jsme dosáhli v minulém odstavi, bude tøebavyu¾ít trik { na toto èíslo pohlédnout jako na stopu matie 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í funkionál) hsij pak v této stopì mù¾eme pøesunout na poslední místodíky invariani výsledku vùèi ykliké 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 vzore vyèlenit matii hustoty (1.26) jeko elek:p(m) = Tr(M†mMm%): (1:30)Podobnými úvahami byhom dokázali pøevést zbývajíí vzore z postulátù 3 a 4. Tyto vý-sledky dávají tu¹it, ¾e by matie hustoty mohla být de�nována samostatnì, bez jakékoliv zá-vislosti na pùvodníh postuláteh a úvah o smìsíh. Jestli¾e tedy dosadíme do postulátù 2, 3a 4 odvozené vzore a postulát 1 nahradíme de�nií matie 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 matie hustoty je ∑ki=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 rovnii ú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 matiemi hustoty ve tvaru konvexní kombinae projektorùna podprostory dimenze 1 stavového prostoru. Ka¾dá taková kombinae vyhovuje po¾adavkùmpostulátu 1', jak byhom se snadno pøesvìdèili z odpovídajííh de�ni. Dá se v¹ak ukázat, ¾e anide�nie matie hustoty jako pozitivního operátoru se stopou rovnou 1 není obenìj¹í, nejsnázeopìt v pøípadì koneèné dimenze:Proto¾e ka¾dý pozitivní operátor je hermitovský, pro libovolnou matii hustoty % existujespektrální rozklad % = ∑ki=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 ryhle plyne, ¾e v¹ehny vlastníhodnoty �i le¾í v intervalu h0; 1i a jejih souèet je 1, urèují tedy koe�ienty konvexní kombinaeprojektorù fjxjihxj jglj=1 dávajíí %.Tato konvexní kombinae v¹ak není urèena matií hustoty jednoznaènì: volnost je ponehánav rozkladu projektorù Pλ na souèet þjednorozmìrnýhÿ projektorù. Napøíklad matie 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 1212 12 )+ 12 ( 12 �12�12 12 ) (1:35)a mnoha dal¹ími. Jednoznaènì je mo¾no zapsat pouze projektory samotné, proto¾e tvoøí vrholysvého konvexního obalu. 17

Projektory jsou dle úvodní úvahy matiemi hustoty systémù, u nih¾ známe stav pøesnì {{ odpovídají výbìru z rezervoáru, ve kterém v¹ehny 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 matie hustoty potøebuje i jinou de�niiprová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á matie hustoty i-tého podsystému pro i = 1; : : : ; n. V opaènémpøípadì øekneme, ¾e daný stav je provázaný.Matii 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é mehanie má dal¹í významná pou¾itízejména u neizolovanýh systémù, do nih¾ 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á situae 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á matie hustotyV teorii kvantovýh algoritmù budeme èasto potøebovat praovat 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 jejih stavové prostory, nelze pro nì nelze zobenit pojem stavového vektoru,jak ukazuje pøíklad provázanýh stavù. Nad tìmito prostory ov¹em mù¾eme s výhodou uva¾ovatmatie hustoty.Matie hustoty nad stavovým prostorem jedné komponenty slo¾eného systému se nazýváredukovaná matie hustoty. Operae, kterou se z matie hustoty elého systému získá, se na-zývá pariální stopa. V její de�nii 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 pariální stopy obené matie hustoty se dodápo¾adavek linearity. Neh» 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á matie 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 dalee souvisí výsledek této matematiké operae se skuteèným stavem pod-systému A. Snadno se v¹ak uká¾e, ¾e taková volba redukované matie hustoty je dobrá { prolibovolné mìøení na systému A dá správný výsledek [3℄.Pøíklad výpoètu redukované matie hustoty uká¾eme na dvou pøíkladeh:{ Neh» systém je ve smyslu pùvodního formalismu ve faktorizovatelném stavu jaijbi, jai 2HA, jbi 2 HB . Toto odpovídá matii 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é matie pro oba podsystémy mù¾eme urèit okam¾itì dosazením do uvedenéde�nie pariá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.{ Neh» systém je podobnì jako vý¹e v èistém stavu popsaném vektorem j�00i = 1√2(j00i +j11i), a tedy matií hustoty % = 12(j00ih00j+ j00ih11j+ j11ih00j+ j11ih11j). Takový stav jeprovázaný i dle paragrafu 1.5 i v jazye matie hustoty. Redukovanou matii hustoty prosystém A mù¾eme spoèítat po èleneh:%A = 12(h0j0ij0ih0j+ h0j1ij0ih1j+ h1j0ij1ih0j+ h1j1ij1ih1j) = 12(j0ih0j+ j1ih1j) = 12I: (1:38)Stejná redukovaná matie 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 matie hustoty:{ Redukovaná matie vy¹la ve tvaru násobku jednotkové matie. 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é matie hustoty vyjdou ve stejném tvaru 12I pro oba systémy i v pøípadì kte-réhokoliv jiného Bellova stavu, aèkoliv matie hustoty elého systému jsou rùzné. Znalostredukovanýh mati hustoty komponent tedy není postaèujíí pro rekonstruki matie hus-toty slo¾eného systému.Ve smyslu úvodní vìty tohoto paragrafu budeme v rámi této práe praovat s izolovanýmifyzikálními systémy. Vìt¹inou tedy nebudeme potøebovat opou¹tìt formalismus stavovýh vek-torù a redukovaná matie hustoty bude pro matii hustoty jediným vyu¾itím. U podsystémùbudeme pøíle¾itostnì mezi obìma formalismy pøeházet tím, ¾e místo matie hustoty èistéhostavu uvedeme nìkterý odpovídajíí vektor.

19

Kapitola 2Kvantová mehanika a zpraování informaePostuláty kvantové mehaniky je mo¾no pou¾ít k simulai matematikýh výpoètù podobnìjako Booleovu logiku. V této seki de�nujeme kvantové obdoby jejíh základù { jednotky bitua logikýh hradel jako¾to matematikýh operaí nad bity. De�nujeme kvantové obvody jakoanalogii logikýh obvodù { pøedpisu prùbìhu digitálního algoritmu. Tato analogie nebude zelajednoznaèná, pøesto na koni kapitoly uká¾eme, jak jsme shopni libovolný logiký obvod nahra-dit kvantovým protìj¹kem. Mezi prvním a druhým paragrafem je vlo¾ena drobná matematikávsuvka urèená pro seznámení s de�nií a základními vlastnostmi Pauliho mati.2.1 Dvoudimenzionální prostoryV kvantovýh algoritmeh 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 klasikými poèí-taèovými algoritmy, které vyu¾ívají dvojkovou soustavu: jednotkou informae v nih je bit, ka¾dánejmen¹í pamì»ová souèástka mù¾e být ve stavu 0 nebo 1. V kvantovýh algoritmeh 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 koreki hyb [3℄, [10℄ èiv analogii tøístavové logiky.V kvantovém poèítaèi mù¾e qubit realizovat napøíklad èástie s dvìma dobøe de�novanýmienergetikými hladinami, èástie se spinem 12 , foton, jeho¾ budeme sledovat polarizai, nebofoton v interferometru, který mù¾e putovat jednou ze dvou vìtví. Není v¹ak smyslem této práepopisovat jakékoliv detaily realizae kvantového poèítaèe.V populární literatuøe se setkáme s tvrzením, ¾e qubit mù¾e být ve staveh j0i a j1i þsou-èasnìÿ. Jedná se samozøejmì o vyjádøení my¹lenky superpozie èi tvrzení, ¾e stavový prostor jevektorovým prostorem: existene tìhto dvou bázovýh stavù implikuje fyzikální smysl libovolnéjejih nenulové lineární kombinae. Pro laika mù¾e být dále pøekvapivý dùsledek skuteènosti, ¾estavový prostor je komplexní: lineární kombinae, 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¹ehny takto vznikléstavy jsou fyzikálnì odli¹né.V pøípadì jednoho qubitu se èasto uvádí pìkný pøíklad geometriké reprezentae projektiv-ního stavového prostoru. V¹ehny fyzikální stavy jednoho qubitu mù¾eme rozmístit na povrhjednotkové sféry (kulové slupky) zvané Blohova sféra. Taková reprezentae je výhodná z nìkolikadùvodù:{ v jednom pøedstavitelném obrázku jsou znázornìny v¹ehny paprsky v C 2 , tedy v¹ehnymo¾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í operae na C 2 odpovídá a¾ na násobení urèitou komplexní jednotkou (globálnífází obrazu) nìjaké speiální ortogonální transformai v prostoru R3 , do kterého je tato sféravnoøena (tedy jen jejímu natáèení),{ prùseèíky libovolné pøímky proházejíí støedem se sférou odpovídají dvìma kolmým vekto-rùm,{ pøi uva¾ování matie hustoty místo stavovýh vektorù se tato sféra zmìní pouze na kouli,její¾ povrh 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 Blohova sféra uplatní spí¹e v jinýh oblasteh teorie kvantovýh poèítaèù, napø.v koreki hyb. My ji k výkladu pou¾ívat nebudeme a pøípadné zájeme 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 geometrikou reprezentai jako Blohovu 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 vektoreh nebo bázo-výh staveh. Pojem bázové vektory roz¹íøíme i na situae jinýh tenzorovýh souèinù stavovýhprostorù, u nih¾ dopøedu uvedeme nìjakou praovní ortonormální bázi nebo budeme uva¾ovatbázi standardní.V následujííh paragrafeh budeme je¹tì pøíle¾itostnì bez upozornìní vyu¾ívat deimá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 matieV následujíím textu se budeme pøíle¾itostnì setkávat s trojií mati známýh jako Paulihomatie [3℄, [4℄. Zaslou¾í si tedy v této kapitole malou vsuvku.Pauliho matie jsou sadou tøí jednoduhýh mati 2�2, z nih¾ ka¾dá je souèasnì hermitovskáa unitární a jako elek mají mnoho dal¹íh spoleènýh vlastností. V kvantové mehanie byhomse s nimi setkali nejèastìji u popisu spinu èásti, pozdìji známýh jako þspin-12 èástieÿ, kdejsou Pauliho matie pøímo i jejih lineární kombinae pou¾ívány jako pozorovatelné s pøímýmfyzikálním významem. Díky své elementaritì mají Pauliho matie v¹ak pou¾ití mnohem ¹ir¹í.Pro nás bude dùle¾itý pøedev¹ím jejih expliitní 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 matie se obèas øadíi jednotková matie druhého øádu �0 = I, my ji v následujííh bodeh v¹ak uva¾ovat nebudeme.Mezi nejdùle¾itìj¹í vlastnosti Pauliho mati patøí:{ druhá monina ka¾dé z nih je jednotková matie,{ ka¾dá má determinant �1, stopu 0 a vlastní èísla 1 a �1,{ ka¾dá hermitovská matie 2 � 2 je reálnou lineární kombinaí Pauliho mati a jednotkovématiea jejih 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øedhozím paragrafem:{ Ka¾dá matie 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øadnie tohoto vektoru pøímo odpovídají poloze v Blohovì 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.{ Operae X, Y , resp. Z mají na Blohovì sféøe geometriký význam rotae kolem os x, y,resp. z o 180◦. 22

2.3 Kvantová hradlaDal¹ím krokem k pøenesení my¹lenky klasikýh digitálníh algoritmù do kvantového svìtaje poskytnout kvantovou analogii logikýh hradel15 a dal¹íh prvkù èísliovýh obvodù neboprogramù.Na kvantová hradla budeme pohlí¾et jako na základní stavební prvky, jejih¾ kombinaímù¾eme sestavit po¾adovaný operátor pro èasový vývoj systému: ka¾dé z nih 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 klasiké logiké ob-vody: stavový prostor systému n qubitù budeme znázoròovat jako n est vedouíh zleva doprava,na nih¾ se budou provádìt operae 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í operae 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 hradleh. 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í matie øádu 2n. Podmínka unitarity plyne z postulátùkvantové mehaniky uvedenýh v první kapitole. Ka¾dá unitární matie v¹ak naopak odpovídánìjakému myslitelnému èasovému vývoji [3℄.Pøi popisu kvantovýh hradel budeme uva¾ovat jejih pùsobení na bázové vektory stavo-vého prostoru zúèastnìného podsystému. Taková informae je toti¾ ekvivalentní hledání popsanématie a díky linearitì je postaèujíí pro nalezení obrazu libovolného stavového vektoru.Nejjednodu¹¹í logiké hradlo, které má pøímou kvantovou analogii, je not (negae, inver-tor) { v klasiké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á matie je, jak ji¾ víme, unitární, podobnì jako ka¾dá matielibovolného øádu, která se li¹í od matie jednotkové pouze permutaí øádkù. Takové kvantovéhradlo se tedy skuteènì zavádí, nazývá se dle odpovídajíí matie 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á mehanika 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, tatoredundane v¹ak slou¾í ke zpøehlednìní zápisu. Pøipomeòme také, ¾e Z je dal¹í z Pauliho mati {{ mohli byhom pro úplnost uva¾ovat samozøejmì i jednoqubitové hradlo odpovídajíí zbývajíímatii Y , my jej ale potøebovat nebudeme.Ke zmínìným hradlùm S a T se je¹tì setkáme s jejih 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).Velie dùle¾ité je Hadamardovo hradlo, které zobrazuje bázové stavy na superpozie 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¹í logiká 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í operae. 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 ponehá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¾ matii

1 0 0 00 1 0 00 0 0 10 0 1 0Tato matie je opìt jako¾to permutaèní matie 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 zobenit 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 operai (ne nutnì jednoqubitovou):pøidání ovládaího qubitu k hradlu reprezentovanému matií U vytvoøí matii blokového tvaru

( I 00 U ) :Unitarita matie U se pøi takovém oblo¾ení zahovává.Èasto se setkáme je¹tì s dal¹ími zpùsoby de�nie kvantovýh hradel, které pøedvedeme napøíkladì not: stejnou informai, která je obsa¾ena v uvedené pravdivostní tabule nebo matii,mù¾eme dále zapsat zpùsobynot = 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 operai 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 superpozii j0i a j1i (není s øízeným provázán), dostane se druhý qubitpo provedení takové operae do odpovídajíí superpozie obou výsledkù.25

Ve vztahu k poslednímu odstavi 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 jejih 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 klasiké informae. Místo øízeného hradla se zde tedy jedná jednodu¹e o provedení èineprovedení hradla U .Pro dvì nejznámìj¹í dvouvstupová logiká hradla, and a or, stejný postup v¹ak nepomù¾e.Úvahami o tvaru výslednýh mati byhom 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é operae. 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 (jejih stav se v ka¾dém pøípadì zahová).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, kdybyhom pøidali k hradlunot je¹tì jeden øídií bit (nezávisle na tom, ¾e jej ji¾ þobsahujeÿ { na not pohlí¾íme v tomtookam¾iku jako na obené 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 algoritmeh, narozdíl od klasikýh, také velie 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 obenì n-qubitové hradlo známé jako Walsh-Hadamardova transformae19([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é operae provádìné na rùznýh qubiteh komutují, nemusíme proto uva¾ovatjejih poøadí. Obvykle není dùvod nazývat takto utvoøenou operai novým kvantovým hradlem,ale Walsh-Hadamardova transformae je tak èastá, ¾e se tento pojem ustálil.Matie transformae je, jak bylo øeèeno vý¹e, øádu 2n a její prvky je mo¾no obenì vyjádøitvzorem 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 logikého souèinu èísel i a j po biteh. 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¹ehny 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 transformae.Tím se systém dostane do stavu 1p2n 2n−1∑i=0

jii; (2:5)který budeme nazývat rovnoennou superpozií v¹eh 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áze fyzikální realizae obvodu. Pro logiké 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í operae 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 nih spolu s mo¾nostípøedpokládat existeni pomonýh qubitù pøipravenýh v danýh staveh postaèuje pro simulailibovolného klasikého obvodu, jsou tedy univerzální v této oblasti. Výsledkem takové simulaeje, ¾e øídií qubit pro libovolnou operai bude mo¾no nahradit nejen jednoduhými logikýmioperaemi na víe qubiteh, ale výsledkem libovolné Booleovské funke libovolného poètu pro-mìnnýh. Takovou konstruki budeme èasto vyu¾ívat. V následujíím paragrafu naznaèíme jejídetaily za pou¾ití To�oliho hradla.2.5 Simulae klasikýh obvodù kvantovými hradlyAbyhom mohli sestavit kvantový obvod, který by dával stejný výsledek jako daný klasikýobvod pro ka¾dý bázový stav, je tøeba nahradit kvantovými analogiemi v¹ehny prvky, které28

se mohou v klasikém pøípadì vyskytovat. Na základì univerzality logiké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 klasiký obvod není tvoøen pouze logikými hradly. V kvantové analogii je tøeba simulovatje¹tì rozdvojení vodièe, triviální není ani pøekøí¾ení dvou vodièù,20 takovou operai je v¹ak v¾dymo¾no bez újmy vynehat.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 staveh j1i budou i oba øídií qubity, To�oliho hradlo na nìm provede operai not,èím¾ jej zmìní na j0i, v ostatníh tøí uva¾ovanýh bázovýh staveh jej ponehá 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 byhom zjistili, ¾epo prùhodu To�oliho hradlem bude ve stavu jx and yi. Hradlo or mù¾eme sestavit za pomoiji¾ 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 sie také mo¾no nahradit vhodnìpou¾itým To�oliho hradlem, ale poneháme jej v pùvodním stavu { je obenì jednodu¹¹í pøed-pokládat v¹ehny pomoné qubity v obvodu pøipravené ve staveh j0i a do jinýh pomonýhstavù je pøípadnì pøevést pomoí jednoqubitovýh operaí.To�oliho hradlo s dvìma qubity pou¾itými jako pomoné 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 zobenìní pro obenou super-pozii 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 obenì platné vìty, ¾e zálohovat stavqubitu pomoí unitární operae 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ítransformai 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). Neh» 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 jejih 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ímo 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, ¾ebyhom jej v¾dy pøed mìøením zálohovali, aby jeho stav bìhem kolapsu nebyl ztraen.Pro kvantovou simulai odboèky má vìta dùsledek, ¾e kdy¾ zálohujeme úspì¹nì stavy j0i aj1i, pro ¾ádnou jejih netriviální lineární kombinai 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 klasiký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 pomoné qubity pøipravené v nìjakémkonkrétním stavu. Èím víe hradel mìl klasiký obvod, tím obenì víe pomonýh qubitù bybylo potøeba k jeho simulai na kvantovém poèítaèi. To mù¾e být znaèným problémem z hlediskafyzikální realizae kvantového algoritmu, proto u konkrétní funke mù¾eme uva¾ovat o jinýhzpùsobeh simulae 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 obeného stavu. Celý vývoj stavu bìhem prùbìhu algo-ritmu je popsán jednou unitární operaí, platí tedy prinip superpozie a jestli¾e na vstupu bylajistá lineární kombinae bázovýh stavù, získáme na výstupu lineární kombinai odpovídajííhvýsledkù (opìt jako¾to bázovýh stavù), urèenou stejnými koe�ienty.Simulovaná funke tak jistým zpùsobem spoèítá výsledky v¹eh 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 uryhlení 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ì:kdybyhom po algoritmu provedli úplné mìøení stavu, získali byhom pouze jeden z èitatelù, tedy30

pouze jeden z bodù 0 a 1 a funkèní hodnotu v nìm. Prinip, který poskytuje vìt¹inì kvantovýhalgoritmù jejih výhody oproti algoritmùm klasikým, je interferene. 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 odstavi jsme pøedpokládali, ¾e praovní prostor je tvoøen jen qubity pøedstavu-jíími vstup pro funki a jedním qubitem jako místem pro ulo¾ení výstupu. Pro zaji¹tìní úèelupopsaného na koni minulého paragrafu a ve smyslu první èásti tohoto v¹ak bude ve skuteènostipotøeba{ n vstupníh qubitù,{ m+ 1 pomonýh qubitù, pøipravenýh ve stavu j0i,{ 1 ílový qubit, na kterém budeme htít provést operai øízenou výsledkem funke.Mezi pomonými qubity jsme zde my¹lenkovì vymezili poslední pro hodnotu funke. Neh»tedy poèáteèní bázový stav, zapsaný v rozdìlení na tyto ètyøi èásti, je jxij0ij0ijyi, kde x pøedsta-vuje vstup funke. Po provedení náhradního kvantového obvodu za obvod poèítajíí po¾adova-nou funki se tento stav zmìní na jxijg(x)ijf(x)ijyi, kde jsme g(x) oznaèili výsledek pomonýhoperaí na prvníh m pomonýh qubiteh. V tomto okam¾iku mù¾eme provést libovolnou po-¾adovanou jednoqubitovou operai na posledním qubitu øízenou posledním pomoným qubitem.Pøedpokládejme, ¾e se jedná o X, výsledným stavem pak je jxijg(x)ijf(x)ijy � f(x)i.Pomoné qubity v¹ak obenì brání jakékoliv kvantové interfereni výsledkù { aby k ní mohlodojít, musely by se jejih hodnoty u v¹eh èitatelù shodovat, jinak by tyto èitatele byly nutnìvzájemnì ortogonální. Na poèátku algoritmu tomu tak bylo { v¹ehny pomoné qubity jsmejednotnì uva¾ovali ve stavu j0i. Uká¾eme tedy, ¾e postupem známým jako unomputation [3℄jsme shopni je do tohoto stavu vrátit za zahování informae o výsledku funke.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 simulae nahradiliobvodem reverzibilním. V¹ehna hradla pou¾itá pro simulai klasiký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 (jejih matie ve standardní bázi jsou samy sobì inverzními). V¹ehna hradla pou¾itábìhem simulae 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 praujíí s registry sestavenými z qubitù a vyu¾ívajíí prinipy kvantové mehaniky, azabývat se ji¾ jen jejih spei�kými vlastnostmi.Teorie kvantovýh algoritmù se dìlí na nìkolik logikýh elkù:{ návrh kvantovýh algoritmù jako analogie k digitálním algoritmùm { realizae výpoètù èialgoritmiký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 informae,{ kvantové algoritmy pro koreki 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émeh,{ matematiká teorie kvantové informae a teorie kvantové slo¾itosti,{ úze souvisejíí problematika experimentální realizae kvantovýh poèítaèù.Ve v¹eh 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¾nosteh 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 nih, 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øíkladeh ukázalo,¾e mají v urèitýh úloháh oproti digitálním algoritmùm poteniá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 profaktorizai èísel (1994), øe¹íí tento problém v èase polynomikém vzhledem k déle vstupu. Vesvìtì digitálníh algoritmù pøitom nejsou známy algoritmy vy¾adujíí krat¹í ne¾ exponeniá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 algoritmeh byl Groverùv algoritmus pro vyhledávání v nesetøí-dìné databázi (1996). Ten sie oproti klasiké obdobì nabízí pouze polynomiké zkráení èasovéslo¾itosti, zde v¹ak je zøejmé, ¾e ¾ádný digitální algoritmus nemù¾e takové ryhlosti dosáhnoutji¾ z prinipu úlohy. Vyhledávaí algoritmy jsou hlavním ílem této práe, Groverovì algoritmuse proto vìnuje elá pøí¹tí seke.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á teleportae.3.1 Kvantová teleportaeKvantová teleprotae je algoritmus, na nìm¾ pøedvedeme praktiký pøíklad kvantového ob-vodu a nìkteré mo¾nosti a prinipy, se kterými se v kvantovýh algoritmeh setkáváme.32

Uvádìný název je v¹ak bohu¾el také pøíkladem znaèné popularizae terminologie. Tentoalgoritmus je toti¾ urèen k pøenesení libovolné hodnoty jednoho qubitu z jednoho podsystému najiný bez nutnosti pøenosu kvantové informae mezi tìmito dvìma èástmi zkoumaného systému.Tuto my¹lenku brzy upøesníme, ale uvìdomme si, ¾e