Scienceworld | Cesta ke kvantovému počítači (1) – faktorizace a kvantový Turingův stroj

Cesta ke kvantovému počítači (1) – faktorizace a kvantový Turingův stroj

Fyzika | 19.10.2004

Každý z možných dělitelů, jež mají být testovány, si lze představit jako kvantovou vlnu pravděpodobnosti, kousíček komplexního vlnového balíčku. Počítání je pak ekvivalentní manipulací s celou vlnou pomocí laserové pistole, přičemž všechny možné odpovědi spolu navzájem interferují. Ty nejméně pravděpodobné přitom vymizí, zatímco ty nejpravděpodobnější se navzájem posílí a zvýrazní. Na konci výpočtu vlna zkolabuje a odhalí tím řešení zadaného problému.

Sdílet

Představte si Turingův stroj – ten nám může dobře posloužit jako typický reprezentant kteréhokoli jiného počítače –, jenž je naprogramován na faktorizaci čísla zakódovaného pomocí velice dlouhého řetězce znaků X a znaků O. Jeho čtecí hlava se posouvá podél pásky sem a tam, otrocky čte, zapisuje a přemazává značky dle předem naprogramovaných pravidel. Jednu po druhé zkoumá všechny možnosti, dělí zadané číslo všemi možnými menšími čísly a ty, které nechávají zbytek po dělení, zavrhuje. Mezivýsledky ukládá do políček vyhrazených jako paměť a podle potřeby je vymazává a nahrazuje.
Když jsou všechny operace konečně provedeny, je vstupní páska přeměněna na pásku výstupní: na seznam dělitelů. Abychom ušetřili čas, můžeme nechat pracovat několik Turingových strojů vedle sebe, aby současně testovaly některý ze všech možných dělitelů. Ale jako vždycky, i toto musí být něčím vyváženo: chceme-li analyzovat větší a větší čísla, bude buď čas zpracování, nebo počet Turingových strojů exponenciálně narůstat.
A teď si namísto toho představte kvantový Turingův stroj. Každá značka na jeho pásce může být buď X, O, nebo X a O současně. Stejně jako jeho klasický protějšek může stroj manipulovat s páskou, přesouvat a přeměňovat bity. Ale protože nyní to jsou kvantové bity neboli q-bity, každé číslo, které máme otestovat, bude zakódováno současně na téže pásce v kvantové superpozici. Všechna čísla tak mohou být otestována najednou, během jednoho jediného běhu stroje.
Poněkud realističtější představa takovéto pásky kvantových značek X a O vypadá jako řádka atomů, z nichž každý je obklopen elektronem obíhajícím buď ve směru pohybu hodinových ručiček, nebo proti němu, což reprezentuje buď stav 0, nebo 1. Čtecí a zapisovací hlava může vypadat jako laserová pistole. Osvítí-li atom pulzem o správné frekvenci, donutí ho k rezonanci, takže se atom rozezní jako zvoneček. Když ho zasáhne na tu správnou dobu, změní jeho spin, tedy překlopí ho z 1 na 0 či naopak. Zasáhne-li ho jen na poloviční čas, skončí elektron s padesátiprocentní pravděpodobností ve stavu, kdy se otáčí jedním i druhým směrem. Jinými slovy, bude v superpozici obou možných stavů: tedy 1 i 0 současně.
Pomocí správné sekvence pulzů může laser přeměnit vstupní řetězec – jenž současně kóduje úplně všechna čísla, která mají být otestována – v řetězec výstupní: ten představuje dělitele, tedy řešení naší faktorizační úlohy.
Nejlepší metodou, jak pochopit tuto podivuhodnou novou myšlenku, je útočit na ni stále znovu z různých směrů. Každý z možných dělitelů, jež mají být testovány, si lze představit jako kvantovou vlnu pravděpodobnosti, kousíček komplexního vlnového balíčku. Počítání je pak ekvivalentní manipulací s celou vlnou pomocí laserové pistole, přičemž všechny možné odpovědi spolu navzájem interferují. Ty nejméně pravděpodobné přitom vymizí, zatímco ty nejpravděpodobnější se navzájem posílí a zvýrazní. Na konci výpočtu vlna zkolabuje a odhalí tím řešení zadaného problému.

Anebo, abychom ještě jednou změnili metaforu, si můžete představit foton, který se odráží od středu zrcadla, takže úhel dopadu je roven úhlu odrazu. Podle „mnohodráhové“ představy ale částice zkoušejí současně úplně všechny myslitelné trajektorie. Tyto alternativy navzájem interferují, jedna druhou posiluje anebo oslabuje, což nakonec určí nejpravděpodobnější dráhu. Každá trajektorie představuje jeden z dělitelů, který má být testován. Ta dráha, která se nakonec vynoří, představuje hledanou odpověď.
Ať už si představujete tento kvantový paralelismus jakkoli, dává nám příslib stroje, který by byl imunní vůči exponenciální explozi. Vzpomeňte si, že u klasického počítače způsobí přidání každé další cifry to, že se čas nutný k výpočtu zdvojnásobí. Číslo se 155 dekadickými ciframi je nutno zpracovávat tucty počítačů po celé měsíce; číslo se stovkami cifer by si vyžádalo miliardy let – anebo miliardy Turingových strojů.
Aby kvantový počítač dokázal zpracovat delší čísla, stačí prostě jen přidat pár dalších q-bitů k řádce atomů a pak opět najednou provést všechny výpočty. Čas nutný k řešení úlohy přitom nenaroste skoro vůbec. Anebo se na to můžete podívat ještě jinak: když přidáváte k řádce atomů další a další q-bity, exponenciálně narůstá počet výpočtů, které lze současně provést. Exploze tak pracuje v náš prospěch. Pokud jde o počítání, ukazuje nám kvantová mechanika cestu představující zkratku napříč časem.

Strategie předchozích stránek spočívala v postupném přibližování se k pochopení kvantového počítání pomocí série čím dál lepších karikatur. Obrázek kvantového Turingova stroje, který manipuluje svojí páskou zaplněnou q-bity, se dostal již docela blízko k vystižení samé jeho podstaty. Když se však zadíváme poněkud pečlivěji, objevíme některé problémy.
Klasický Turingův stroj čte políčka a podle seznamu pravidel provádí příslušné operace: může změnit 1 na 0 nebo ji úplně vymazat, čtecí a zapisovací hlava se pak posune podél pásky dopředu nebo dozadu na jiné určené místo. To dobře funguje s klasickými bity. Kvantový Turingův stroj však zpracovává kvantové bity. A nejzákladnější pravidlo kvantové mechaniky přitom zní, že nemůžete změřit hodnotu q-bitu, aniž byste zničili jeho superpozici. Políčko, které říká současně 1 a 0, totiž při čtení náhodným způsobem zkolabuje buď do hodnoty 1, nebo 0. Kvantové eskamotérství, spočívající ve schopnosti provádět více činností najednou, se zhroutí a superponované bity dopadnou jako žonglérské kuličky na zem.
Jednou z možností, jak tuto potíž překonat, je předpokládat, že i sama čtecí a zapisovací hlava je součástí kvantového systému. Je-li přesunuta na políčko s hodnotou , pak i hlava přejde do superponovaného stavu, jenž znamená 1 i 0 současně. Dokud informace neopustí kvantový svět, nedojde k žádnému (klasickému) měření a delikátní superpozice tím nebude porušena. To si ale lze dost těžko představit, neboť hlava musí být kvantově mechanická a nemůže být lokalizována v daném okamžiku na jednom jediném místě. Musela by se nacházet v ještě mnohem složitějším superponovaném stavu, při němž čte všechna políčka současně. Dovedena do těchto důsledků již naše metafora selhává.

Ú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.