Scienceworld | Cesta ke kvantovému počítači (2)

Cesta ke kvantovému počítači (2) – kvantový celulární automat

Fyzika | 21.10.2004

Na rozdíl od čtecí hlavy Turingova stroje, laser kvantového celulárního automatu ve skutečnosti nečte informaci zaznamenanou „na pásce“. Prostě jen vysílá příkazy, které se mají provést. Q-bity vlastně čtou sebe navzájem. Informace zůstává uvnitř kvantové říše, a nedochází tak k žádnému předčasnému kolapsu.

Sdílet

Chceme-li provést ještě další krůček směrem k tomu, jak by reálný kvantový počítač mohl opravdu vypadat, vyžaduje to opět změnit náš úhel pohledu a podívat se na počítání v malinko jiném světle. Představte si Turingův stroj, model počítání pomocí klasického počítače, ale zcela odstraňte jeho čtecí a zapisovací hlavu, takže zůstane jen samotná páska.
Dostanete tak cosi, co matematikové nazývají celulární automat, zkráceně CA, napohled jednoduché zařízení, jež ovšem může vykazovat překvapivě komplikované chování. Obarvěte na počátku pásku obrazcem černých a bílých políček, které představují jedničky a nuly. Nechejte pak každé políčko interagovat s jeho sousedy podle jednoduchých pravidel typu: „Jestliže jsou obě políčka bezprostředně nalevo od tebe černá a obě políčka bezprostředně napravo bílá, pak se také musíš přebarvit nabílo.“ Nebo: „Je-li obrazec nalevo od tebe typu bílá–černá–bílá a současně napravo od tebe černá–černá–bílá, pak se musíš změnit na černou barvu.“ Můžete si vymyslet spoustu takových pravidel. Jakmile je zařízení spuštěno, políčka interagují jedno s druhým a s každým dalším tikem hodin se začne vytvářet kaleidoskopický obrazec, fascinující vzor utkaný z černých a bílých buněk.
Když budete sledovat jedinou řádku políček, které neustále blikají, po chvilce se vám z toho budou dělat mžitky před očima. Aby celý děj lépe pochopili, tak ti, kdo praktikují tento druh tajemného umění, programují své počítače, aby se každý nově vytvořený řádek zobrazil pod svým předchůdcem. Zvolte pravidla, podle nichž se má systém chovat, vložte počáteční sekvenci políček a před vašima očima se na obrazovce krok za krokem rozvine příslušný obraz. (Můžete si to sami vyzkoušet pomocí simulátorů dostupných na několika webových stránkách.) Některé konfigurace se velmi rychle zaseknou do vyjetých kolejí nudných a stále se opakujících cyklů.

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

Jiné automaty naopak vyprodukují příjemné symetrické obrazce. A některé vytvoří jen zmatek. Ale pár se jich bude donekonečna vyvíjet podle jakéhosi skrytého plánu a vytvářet spletité motivy, které vznikají z napětí mezi řádem a chaosem, jež označujeme slovem „složitost“.

Připomeňme si znova, že počítání lze chápat jako přeměnu vstupní řádky políček do výstupní, do obrazce, který představuje odpověď na daný problém. Proto může být celulární automat naprogramován k počítání, stačí jen správně stanovit pravidla jeho chování.4 Představme si například, že chceme vyrobit stroj na sčítání. Jako svůj vstup vezme řádku políček vybarvených buď černě, nebo bíle, což reprezentuje buď 1, nebo 0. Může to vypadat třeba takto: 0000000000110111, což znamená 2 + 3. Pak se přetransformuje do obrazce, který znamená 5, tedy 0000000000011111. (Nepoužili jsme tu dvojkový zápis čísel, jenom příslušný počet jedniček.) A jiný, mnohem složitější systém pravidel může pro změnu vzít za svůj vstup nějaké číslo a přeměnit ho po mnoha složitých krocích na jeho prvočíselné dělitele, které se objeví na výstupu jako sekvence černých a bílých políček. Jinými slovy, zařízení se bude chovat jako Turingův stroj, ale nebude k tomu potřebovat čtecí a zapisovací hlavu.
Inženýr dokáže vymyslet řadu způsobů, jak takové abstraktní zařízení realizovat. Políčka se mohou skládat ze řady kartiček obarvených černě na jedné straně a bíle na druhé. V zákulisí jsou spolu propojeny důmyslným systémem ozubených koleček a převodů, které představují příslušné souvislosti: kartička bude otočená bílou stranou, když všechny tři nalevo od ní budou černé a současně dvě napravo od ní obě bílé. Jestliže se však kartička úplně napravo převrátí, pak se musí změnit i kartička uprostřed i zcela nalevo. A tak dále. Uvedli jsme tu jen jeden konkrétní případ, počet možností je ovšem neomezený. V elektronické verzi celulárního automatu by každé políčko mohlo být reprezentováno žárovkou, která by stejně jako u Geniacu byla propojena elektrickými dráty s ostatními skrze předivo logických obvodů – hradel AND, OR a NOT. A nejspíše by existovala i možnost sestrojit ho ze součástek stavebnice Tinkertoy.
Abychom tuto představu přenesli do kvantového světa, musíme provést nám již známý krok: zařídit, aby každé políčko mohlo být černé, bílé anebo černé a bílé současně. Stejně jako u kvantového Turingova stroje může být každé políčko představováno atomem, jehož elektrony se otáčejí buď ve směru hodinových ručiček, proti němu, anebo v obou směrech najednou.
Předpokládejme opět, že máme za úkol rozložit nějaké číslo na jeho prvočíselné dělitele. Nejprve zasáhneme každý atom laserem a nastavíme tak řádek q-bitů do stavu superpozice, jenž představuje všechny možné dělitele, které máme otestovat. Když jsme takto vložili data, lze provést samu proceduru – tedy vydělení zadaného čísla příslušným menším číslem a zjištění, zdali zanechalo zbytek – a to prostřednictvím další, mnohem složitější sekvence laserových impulzů, jež jsou ekvivalentem počítačového programu.
Označme atomy písmenky A, B, C, D, E a tak dále a představme si, že jsou jistým způsobem propojeny. Jestliže je atom C zasažen pulzem správné délky a frekvence, změní svůj stav a překlopí se z 1 do 0 nebo naopak, avšak jen v tom případě, pokud jeho sousedé B a D jsou také ve stavu 1. Je to atomová verze pravidla chování celulárního automatu. Anebo se může D překlopit jenom tehdy, když jeho sousedé, tedy C a E, jsou ve stavech právě opačných. Algoritmus může také nařídit zasáhnout atom E pulzem poloviční délky, čímž ho uvede do stavu superpozice 1 a 0. Když správně vymyslíte a aplikujete takováto pravidla, dostanete na konci posloupnosti transformací řádek otáčejících se atomů, jejichž stav bude reprezentovat odpověď na zadaný problém.
Na rozdíl od čtecí hlavy Turingova stroje, laser kvantového celulárního automatu ve skutečnosti nečte informaci zaznamenanou „na pásce“. Prostě jen vysílá příkazy, které se mají provést. Q-bity vlastně čtou sebe navzájem. Informace zůstává uvnitř kvantové říše, a nedochází tak k žádnému předčasnému kolapsu.
Netrapme se prozatím detaily atomové fyziky, které stojí v pozadí. Důležité je pochopit především podstatu celé ideje. Jak ukazuje Einsteinův myšlenkový experiment (právě ten, kterým se spolu s Rosenem a Podolskym snažil prokázat chybnost kvantové teorie), mohou se subatomární částice „proplést“, jejich osudy se navzájem nerozlučitelně svážou. Když se elektron atomu A otáčí v jednom směru, pak se elektron v atomu B musí otáčet ve směru opačném. Anebo spolu mohou být propojeny tak, že se oba otáčejí stejným směrem. Záleží na tom, jaký typ atomů si vyberete. Dokonce ani nemusí být svými bezprostředními sousedy. Atom A může být například propleten s atomem D anebo atom E s B. V klasickém celulárním automatu jsou políčka řízena vnější tabulkou pravidel. V kvantovém CA jsou pravidla vnitřní, jsou důsledkem způsobu, jakým spolu q-bity interagují.
Výsledkem toho je nástroj na provádění logických operací, kvantových ekvivalentů hradel AND, OR a NOT. Oproti klasickému počítači neobsahuje žádné dráty, jen vazby mezi atomy. Problém, jenž máme vyřešit, je zakódován do vstupního obrazce q-bitů, poté je aplikován příslušný program skládající se z laserových pulzů a systém se sám vyvine do stavu vyjadřujícího odpověď, a to ve spokojené izolaci od vnějšího světa.
A zde přichází ke slovu poslední krok. Když je výpočet proveden, všechna řešení – tedy dělitelé analyzovaného čísla – se nacházejí v superponovaném stavu. Vložte do programu číslo 15 a výsledkem bude řádek q-bitů, které budou současně říkat 3 a 5. Změřte nyní systém a donuťte tím stav superpozice zkolabovat. Se stejnou pravděpodobností bude říkat 3 nebo 5. Úloha je vyřešena. Vydělením zadaného čísla kterýmkoli dělitelem, který jste získali (pomocí obyčejné kalkulačky nebo i zpaměti), dostanete druhého dělitele. Pokud existují více než dva dělitelé, stačí výpočet zopakovat. Systém vždy skončí v tomtéž stavu superpozice a jeho změření náhodně vybere jeden z dělitelů, který obsahuje. Dostatečný počet opakovaných výpočtů je všechny vyslídí.

Uvedený obrázek kvantového CA stále ještě dává jen hrubou představu ideje kvantového počítání. Je to abstraktní hračka, kde detaily byly smazány proto, aby čtenáři poskytla intuitivní pomůcku. V roce 1994 však Peter Shor, výzkumný pracovník Bellových laboratoří, tuto éterickou představu kvantové faktorizace postavil na pevné základy. Nesnažil se ovšem postavit kvantový počítač z otáčejících se atomů. Je to matematik, nikoli fyzik. Ukázal však, že kdyby takový stroj mohl být zkonstruován – a připomeňme, že žádný fyzikální zákon to nezakazuje –, pak by opravdu mohl být naprogramován tak, aby hledal dělitele čísel. A co je ještě důležitější: dokázal, že takový stroj by překonal problém exponenciální exploze. Jak roste délka čísel, která máme faktorizovat, bude čas nutný k výpočtu narůstat mnohem pomaleji než v jakémkoli myslitelném klasickém počítači. I čísla, která by jinak bylo prakticky nemožné rozložit, neboť by to zabralo více času, než je stáří vesmíru, by bylo možné snadno zpracovat.

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