Student World

Vědci našli i další způsob, jak dosud úzký repertoár kvantových algoritmů rozšířit. V roce 1996 ukázal Lov Grover, opět výzkumník z Bellových laboratoří, že kvantová mechanika se dá využít ke zrychlení určitého typu masivního vyhledávání, který omezují možnosti počítačů klasického světa.6 Vyhledávání je skutečnou podstatou výpočetních procesů, ať již představuje hledání stránky na webu, jména v databázi anebo nejlepšího šachového tahu. Aby počítač mohl soupeřit s lidským protihráčem, musí prohlédnout šachovnici a analyzovat ohromné množství možností. Jestliže se pěšák přesune sem, jak bude protihráč reagovat a jaká bude nejlepší reakce na tuto reakci – a reakce na reakci na reakci? Rychlý nárůst možností může být zakreslen do herního stromu – diagramu, který připomíná složitý labyrint.

V čase mezi tahy zkoumá počítač tuto houštinu do takové šířky a hloubky, jak je to pro něj možné, a porovnáním jednotlivých výsledků se snaží vybrat tah, který vychází jako nejvýhodnější. Čím jsou počítače rychlejší, tím více úrovní bludiště mohou projít. Ale i tak musejí nechávat skoro celou jeho rozlohu až na nepatrný zlomek neprozkoumanou. Claude Shannon, matematik, který zformuloval teorii informace, v roce 1950 odhadl, že v typické šachové partii existuje nějakých 10^120 možností – mnohem více, než je atomů ve vesmíru. Technologický pokrok od doby Shannonova výpočtu skýtá jen malou útěchu. I kdybychom předpokládali, že počítač může projít bilion možností za vteřinu, stále by mu trvalo skoro 10100 let, než by zcela analyzoval celou hru. Vesmír existuje jen zanedbatelný zlomeček této doby.
Znovu zde narážíme na problém, že i těm nejrychlejším klasickým počítačům vadí jejich sériová povaha, nutnost zabývat se v jednom okamžiku vždy jen jedním kouskem dat. Nejsilnější šachové stroje, jako Deep Blue firmy IBM, využívají v určité skromné míře i paralelismu a vykonávají několik operací současně. Když tento počítač v roce 1997 porazil šachového šampiona Garry Kasparova, měl 256 tandemově pracujících procesorů a zkoušel 60 miliard možností během tří minut povolených mezi tahy. Představte si 256 myší vybíhajících prozkoumat bludiště. Je to jistě více než myš jedna, ale stále bylo zapotřebí také ohromujícího množství sériových, krok po kroku jdoucích operací a rozlehlé oblasti prohledávaného prostoru musely být z výpočtu vyloučeny.
Co kdyby počítač mohl labyrint zkoumat pomocí myších regimentů, které probíhají každou jednotlivou větví a hledají cestu paralelně, v kvantové superpozici? To je právě možnost, kterou otevřel Groverův algoritmus. Ve hře s Kasparovem zpracoval každý z procesorů Deep Blue kolem 25 milionů pozic před každým tahem, uvažoval a vylučoval postupně jednu po druhé. Díky výkonu vyplývajícímu z kvantové mechaniky by kvantový počítač o stejné rychlosti byl za stejný čas schopen prohledat
25 milionů na druhou pozic, čili 6,25 × 10^14. Dejte dohromady 256 takových zařízení a výsledkem bude kvantový Deep Blue procházející více než 10^17 pozic za tři minuty – to je 10milionkrát více než může projít jeho klasický protějšek.
Aplikace vysokorychlostního kvantového prohledávacího stroje by byly neomezené. Předpokládejme, že máme abecední seznam všech lidí na světě s telefonním číslem u každého jména. Najít číslo podle jména je snadné, ale pokud máte jenom číslo a chcete znát, komu patří, pak vy – nebo váš počítač – musíte pročesávat seznam položku po položce. Máte-li štěstí, narazíte na správný řádek hned na začátku. Když ne, musíte hledat až do hořkého konce.
Pro nalezení dané položky je potřeba projít v průměru polovinou seznamu: položka má stejnou šanci být nahoře i dole. Se dvěma procesory můžete začít na obou koncích a hledání dvakrát urychlit. Se čtyřmi procesory budete pracovat čtyřikrát rychleji. Ale s kvantovým počítačem vybaveným Groverovým algoritmem lze prověřovat všechna čísla najednou, v superpozici.
Podstata této nové metody, která by mohla výrazně urychlit třídění stohů neuspořádaných informací, tkví v kvantovém paralelismu. Při použití dlouhého řetězce
q-bitů by se každá jednotlivá položka seznamu dala držet v superpozici. Zpracujte tuto konfiguraci správnou sekvencí laserových pulzů – Groverovým algoritmem – a všechna data budou analyzována jedním rázem. Groverův objev, podobně jako Shorova faktorizační technika, však nabádá k podrobnějšímu pohledu. Z černé skříňky můžeme sloupnout několik obalových vrstev. Detaily jsou fascinující a opět nevyžadují nic než jednoduchou aritmetiku a vůli sledovat kroky algoritmického receptu. Přitom se rodí hlubší pochopení výpočetní síly kvantové mechaniky.

V tomto textu jsme se ideu kvantové superpozice dosud snažili popsat metaforicky, s trochou umělecké licence – jako komplex vlnek, z nichž každá představuje jeden z výstupů nějaké události. Ale ve skutečnosti je to trochu složitější. Pro elektron obíhající kolem jádra reprezentuje každá
vlnka jednu z mnoha poloh, kterou by částice mohla zaujmout, kdybychom ji měřili. Každá z těchto možností je popsána číslem, jež charakterizuje výšku vlnky neboli „amplitudu“. Představujme si ji jako hlasitost zvuku. Mohlo by se zdát přirozené předpokládat, že amplituda udává pravděpodobnost – například jedna ze sta –, že se elektron objeví na daném místě. Ale ve skutečnosti amplituda vyjadřuje jinou veličinu, totiž odmocninu z pravděpodobnosti. Abychom dostali pravděpodobnost, amplitudu musíme vynásobit samu se sebou. Takže je-li výška vlnky třeba 1/10, je pravděpodobnost odpovídající události dána jejím čtvercem: 1/10 krát 1/10 rovná se 1/100 – šance jedna ze sta, čili 1 procento.
Tato relace mezi amplitudami a pravděpodobnostmi je zajímavější, než by se mohlo zdát. Zatímco pravděpodobnosti jsou vždycky kladná čísla (bylo by nesmyslem, kdyby šance, že něco nastane, byla menší než nula), amplitudy mohou být kladné i záporné. Vrchol vlny zvedající se nad obzorem má kladnou amplitudu. Ale vlna může také padat pod horizont, vytvářejíc údolí nebo koryto s negativní amplitudou. Jestliže je na škále od jedné do deseti pravděpodobnost události 9, amplituda vlny, která to popisuje, může být 3 nebo –3. Druhá mocnina obou těchto čísel dává stejný výsledek.
Zásadním důsledkem – a od něho se právě odvíjí velká část podivnosti kvantové mechaniky – je, že kladné a záporné amplitudy se mohou dostat k sobě, vrcholy překrývající se s údolími, a navzájem se vyrušit. Přesně to se děje, když superpozice – tento komplex mnoha možností – kolabuje do jednoho výsledku. Když částice, kvantový balíček potencionalit, narazí do bariéry nebo je jinak vyrušena, záporné vlnky se zkombinují s kladnými a v sebedestrukci zanechávají jen jedinou vlnku popisující možnost, která se realizuje v pozorovaném světě.
Groverův algoritmus využívá tento jev k rychlému vyhledávání zasuté informace. Nejprve jsou všechny položky převedeny na jedničky a nuly a společně umístěny v kvantové superpozici. Aniž bychom se teď trápili s detaily, připomeňme, že toho lze dosáhnout působením laserových pulzů převracejících spiny atomů sem a tam. Výsledkem je svazek vln reprezentujících jednotlivé položky. Pak systém ovlivněte tak, aby se vlnky pozitivních amplitud vyrušily s vlnkami negativních amplitud. Nakonec zbude jen vlnka reprezentující hledanou položku databáze.
Toto je jádro myšlenky, kterou teď podrobněji ilustrujeme pomocí jednoduchého příkladu. Začněme krátkým seznamem cyklistů s jejich pořadím v silničním závodu (zadaným pochopitelně binárně). Vítěz, Gina, je 00001. Šesté místo (číslo 00110) obsadil Pavel, poslední místo (číslo 16 čili 10000) Lolla.

Amy 00010 Ian 00101
Betty 00111 John 01000
Carrie 00100 Kateřina 01110
David 00011 Lolla 10000
Ely 01101 Marianna 01100
Frank 01010 Nina 01001
Gina 00001 Oliver 01011
Harry 01111 Pavel 00110

Je snadné se podívat na seznam a ověřit, že Marianna byla dvanáctá (01100) a Nina devátá (01001). Jména jsou seřazena podle abecedy. Ale pokud chcete vyhledat, který cyklista skončil řekněme čtrnáctý, musíte se snažit trochu víc – ne o moc, protože tohle je krátký seznam, ale představte si, že byste se museli prodírat stem nebo tisícem jmen.
V Groverově algoritmu nám v urychlení hledání pomáhá kvantová mechanika. S pouhými několika q-bity, každým v superpozici hodnot 1 a 0, můžeme vyjádřit všechna pořadí od 00001 až po 10000 současně. Několik dalších q-bitů umožní přiřadit pořadím jména. Zde stačí použít jen iniciály: A00010 Amy, B00111 Betty… (písmena by samozřejmě byla zakódována numericky). Jinými slovy, seznam cyklistů a jejich pořadí se dá popsat svazkem utkaným ze 16 vlnek o stejné amplitudě. V tuto chvíli by měření na složené vlně způsobilo její kolaps do jakékoliv z 16 možností. Pravděpodobnost objevení se libovolného členu je tedy 1 proti 15, čili 1/16, a amplituda každé vlnky se rovná odmocnině z této hodnoty, což je 1/4 nebo –1/4.
Zatím jsme popsali jen další generátor náhodných čísel. Nemáme žádnou kontrolu nad tím, jaká hodnota by z něho vyšla. Ale předpokládejme, že seznam prohledáváme kvůli jedné konkrétní položce, třeba cyklistovi, který skončil devátý, číslo 01001. Proto ještě před uskutečněním měření vyzkouší Groverova procedura souběžně všech 16 vstupů (může odečíst 01001 z části reprezentující pořadí a zjistit, kde se objevilo číslo 00000). Jakmile najde hledanou shodu, zesílí její vlnku, zatímco ostatní vlnky k ní přidá vždy vrcholem proti údolí, takže se vzájemně zruší. Nová vlna, která vzešla z této kvantové manipulace, teď může být proměřena. A s vysokou pravděpodobností dá položku, kterou hledáme: N01001. Deváté místo obsadila Nina.
Možná se vám to pořád zdá trochu vágní. Jak jsou ony komplementární vlnky přesně míchány a porovnávány, aby vyrobily správnou odpověď? Bez hlubší matematiky je trocha neurčitého mávání rukama nevyhnutelná. Ale i s jednoduchou aritmetikou je možné sloupnout ještě jednu vrstvu. Abychom omezili detaily na minimum, uvažujme databázi o pouhých 4 položkách, 00, 01, 10 a 11. Dejte je do superpozice (vše, co potřebujete, jsou dva atomy se spiny nahoru a dolů). Teď má každá položka šanci na vytažení rovnu jedné čtvrtině, takže amplituda jednotlivých vlnek je odmocnina z 1/4, to je 1/2 nebo –1/2. Nejdřív budou všechny amplitudy (jedna pro každou položku) kladné:
Předpokládejme, že hledáme položku 10. Odesláním správné sekvence pulzů (budeme pokládat za dokázané, že taková sekvence existuje) bude počítač manipulovat s vlnkami a současně v nich zkoušet najít hledaný vzor. (Opět lze prostě odečíst 10 od všech položek a dívat se, kde se objeví 00.) Jakmile jej najde, spustí se sekvence pulzů, která obrátí fázi vlnky tak, že z vrcholu se stane údolí a amplituda se změní na –1/2:

Poznámka: Úryvek je, přepokládáme, srozumitelný i bez obrázků, které najdete v tištěné knize.

Tato operace nezpůsobí kolaps kvantové superpozice. Ať se amplituda rovná 1/2 či –1/2, pravděpodobnost je po-řád 1/4. Takže z hlediska vnějšího pozorovatele se nic nezměnilo. Žádná informace neprosákla ven z kvantové sféry a delikátní superpozice zůstala nedotčena.
Dále počítač vygeneruje sekvenci pulzů, jež způsobí zprůměrování všech amplitud. To se nijak neliší od výpočtu aritmetického průměru libovolného seznamu čísel. Nejprve čísla sečteme: 1/2 + 1/2 + (–1/2) + 1/2. Dva členy se vzájemně odečtou (jejich vlnky se překryjí) a dostaneme
1/2 + 1/2 čili 1. Pak vydělíme 1 počtem položek, tj. 4, a dostaneme průměr: 1/4.
Nakonec je provedena operace zvaná „inverze kolem střední hodnoty“. Ta je trochu obtížnější, ale stále je to jen pouhá aritmetika. Nejprve se použije algoritmus, který určí, jak daleko nad nebo pod průměrem každá z vlnek je. Pak dojde k jejímu převrácení o stejnou hodnotu na opačnou stranu. Nejsnadněji to pochopíme tak, že to prostě provedeme: vlny s amplitudou 1/2 jsou o 1/4 větší než průměr (1/4 + 1/4 = 1/2), takže je uděláme o stejnou hodnotu menší než průměr: 1/4 – 1/4 je 0. Tyto vlny jsou tedy vyhlazeny. Teď si všimněme, že vlna s amplitudou –1/2 je o 3/4 pod průměrem, takže ji vytáhneme nad průměr o stejnou hodnotu: 1/4 + 3/4 = 1. Tato vlna tak zdvojnásobí svou výšku a dotkne se maxima osy. Po ukončení operace jsou amplitudy 0, 0, 1, 0.

Teď už zbývá jen dostat informaci ven ze systému. Připomeňme, že amplituda – výška – je odmocnina z pravděpodobnosti odpovídající události. Takže pravděpodobnost toho, že by měření vedlo ke kolapsu vlny do libovolného z nesprávných členů, se zjistí umocněním jejich amplitud: 0 × 0 = 0. Pravděpodobnost výběru správného členu je 1 × 1 = 1. Šance jedna ku nule je ta nejlepší možná. Superpozice se tedy vyvinula do správné odpovědi. Hledání ve větších databázích by vyžadovalo opakování jednotlivých kroků algoritmu znovu a znovu. V každém kole by se hledaná vlnka zesilovala, zatímco ostatní by se zmenšovaly k nule.
Podobně jako Shorův faktorizační algoritmus se i Groverova metoda vyhledávání zdá být dost zamotaná. Ale existuje za to lákavá odměna. Místo abychom se propracovávali polovinou všech položek databáze, jak to obecně musí dělat klasický počítač, kvantovému zařízení by stačilo pročesat jen odmocninu z počtu položek. Pro velikost 16 to znamená zpracovat 4 položky místo 8, abychom dostali výsledek. Rozdíl se nezdá velký, ale pro 1 000 000 položek by se klasický počítač musel v průměru podívat na 500 000 z nich, zatímco kvantový počítač s Groverovým algoritmem jen na 1000. Kolik hardwaru by k tomu bylo zapotřebí? Milion je přibližně dvě na dvacátou, takže základní výpočet by se dal udělat s řadou 20 q-bitů – objektem hluboko pod hranicí viditelnosti.
Groverův algoritmus sice neposkytuje exponenciální urychlení jako ten Shorův, ale i tak nabízí obrovskou výhodu. Představte si šachový stroj, který by porazil nejen Kasparova, ale i každého možného potomka počítače Deep Blue.

Úryvek z knihy
Geogre Johnson: Zkratka napříč časem – cesta ke kvantovému počítači, přeložili Pavel Cejnar a Jiří Podolský, Argo a Dokořán, Praha, 2004.

Předešlé díly:
1. Faktorizace a kvantový Turingův stroj
http://www.scienceworld.cz/sw.nsf/ID/87C5E59169CF6DF9C1256F2D004F9E1B?OpenDocument&cast=1

2. Kvantový celulární automat
http://www.scienceworld.cz/sw.nsf/ID/BEB82A3388A8DD5CC1256F2D0050F51E?OpenDocument&cast=1

3. Shorův algoritmus
http://www.scienceworld.cz/sw.nsf/ID/74F58DA3A12D8BA1C1256F2D0051E961?OpenDocument&cast=1

autor