Kvantové omyly

Často kladené otázky na téma "kvantové počítače" V Computerworldu 27/2003 jsme publikovali článek vysvětlující pri...


Často kladené otázky na téma "kvantové počítače"
V Computerworldu 27/2003 jsme publikovali článek vysvětlující principy
fungování kvantových počítačů. Následovala řada čtenářských dotazů. Několik
otázek jsme proto položili autorovi původního článku Pavlu Cejnarovi, který se
na pražské MFF UK zabývá fyzikou kvantového chaosu a fázovými přechody v
atomových jádrech.
Cílem tohoto minirozhovoru je uvést na pravou míru několik z mnoha mýtů,
polopravd i nepravd, jež jsou s kvantovým počítáním spojeny. Jedná se o téma,
které bývá dezinterpretacemi zatíženo velmi často. Čtenáře následujícího textu
odkazujeme v případě nejasností na původní článek v CW 27/2003.

Často se uvádí, že kvantový počítač je schopný řešit exponenciálně složité (NP
úplné) problémy v polynomiálním čase prostě proto, že s růstem q-bitů roste
exponenciálně také počet jeho stavů. Počítač dokáže díky tomu zrychlovat stejně
snadno, jako roste výpočetní náročnost úlohy. Je takové chápání oprávněné?
To se takto říct vůbec nedá. Na kvantovém počítači musíte nejprve vymyslet
konkrétní algoritmus pro řešení určitého problému. Algoritmem zde míním
posloupnost elementárních jedno a dvou q-bitových operací. Tato posloupnost
může ale nemusí mít onu kýženou vlastnost, že její délka roste s velikostí
vstupu jen polynomiálně na rozdíl od exponenciálního růstu délky odpovídajícího
algoritmu pro klasický počítač. Právě to se podařilo Shorovi u té často
zmiňované faktorizace.

Dobře. Mohl byste tedy uvést příklad nějakého algoritmu pro kvantový počítač,
třeba právě ten Shorův nebo Groverův (určený pro hledání v neseřazených
databázích)?
Srozumitelnější by mohl být algoritmus, který má zjistit, jaký je v daném
souboru celých čísel podíl těch lichých. V tomto případě prostě připravíte
kvantový stav, v němž budou přítomna v superpozici se stejnými váhovými faktory
"všechna čísla souboru". Lichost či sudost jednoho daného čísla samozřejmě
závisí pouze na jeho poslední binární číslici, takže stačí odečíst "změřit"
hodnotu na q-bitu, který odpovídá této poslední číslici.
I v případě kvantové superpozice všech čísel bude výsledek takového měření vždy
buď nula, nebo jedna, ale již nelze předem určit, která z těchto hodnot to
doopravdy bude. Známe však pravděpodobnosti obou výsledků a ty jsou rovny právě
zastoupení sudých a lichých čísel v celém souboru. Proto stačí celý postup,
včetně přípravy počátečního stavu, dostatečně mnohokrát zopakovat a statistika
jednotlivých výsledků již určí podíl lichých čísel na požadované přesnosti.

V tomto případě ale není algoritmus vlastně zvlášť odlišný od algoritmu
klasického? Kde je výhoda?
Samozřejmě, uvádím to jen jako příklad snadno pochopitelného algoritmu, který
využívá kvantového paralelismu. V tomto případě by kvantový počítač opravdu
nepředstavoval žádnou zvláštní výhodu. Tedy snad až na jednu věc: Když budete
vybírat čísla "klasickým" způsobem, může se stát, že váš výběr nebude tak
docela náhodný, narazíte na nějakou třeba skrytou uspořádanost původního
souboru. Pro kvantový výpočet je náhodnost zaručena tím, že vstupním stavem je
zmíněná superpozice opravdu všech číselných hodnot souboru.

Jak vlastně vypadá odečítání výsledků z kvantového počítače? Systém tedy
vždycky zkolabuje a my musíme vše opakovat znovu? Kolikrát?
Záleží na okolnostech. Při měření/odečtení výsledku můžete opravdu získat pouze
jedinou hodnotu a kvůli kolapsu stavu počítače nezbývá, než celý výpočet znovu
a znovu opakovat. Přece jen tady však je několik zjednodušujících možností.
Jednotlivé výsledky se např. mohou soustředit do relativně úzkých oblastí a
určení požadovaného údaje může být dílem relativně malého počtu opakování.
Dá se využít i to, že řada úloh není výpočetně stejně složitá oběma směry.
Pokud při faktorizaci získáte nějaký výsledek, můžete ho zkontrolovat řádově
lehčím procesem násobením obou prvočísel. Nedá se ale vyloučit ani to, že v
některých případech najdete veličinu, která systém z vašeho hlediska dokonale
charakterizuje, i když jde o jeden jediný údaj. Když třeba zkoumáte eventuální
rovnost veličin-čísel, můžete ji potvrdit (nebo vyvrátit) v jediném kroku a
přitom se neptat na vlastní hodnoty. Jako byste se třeba jenom po očku mrkli,
zda jsou jazýčky vah v rovnováze...

Rád bych se zastavil u vratnosti kvantového počítání. Kvantový počítač je,
podobně jako celá kvantová fyzika, principiálně vratný, nehraje zde roli nárůst
entropie, který se u klasických počítačů projevuje vznikem odpadního tepla. Jak
se to projeví na počítání? A jak si takovou vratnost konkrétně představit?
Uvedu vám příklad související s hledáním hodnoty určité funkce. Pokud tato
funkce není prostá, dostanete se od X k Y, ale tomuto Y nemůžete zpětně
přiřadit jedinou hodnotu X. Proces tedy není vratný a na kvantovém počítači jej
v takto jednoduché podobě nelze uskutečnit.
Existuje naštěstí způsob, jak tento problém vyřešit: Vstupní a výstupní hodnoty
X a Y jsou neseny dvěma odlišnými skupinami q-bitů. Na vstupu vytvoříte na
první skupině X a na druhé nulu, na výstupu zůstává na první skupině X a na
druhé se objevuje Y. Tím je vše opět v souladu s vratnou kvantovou mechanikou.
Kolaps počítače při měření ale samozřejmě vratným procesem není.

Pokud se podaří realizovat kvantové počítače, ovlivní to nějak hledání správné
interpretace kvantové fyziky? Mám tím na mysli především úvahy řady
popularizátorů o tom, že kvantový výpočet probíhá ve "více světech" současně.
Podpořila by existence kvantových počítačů hypotézy více světů?
Podle mého názoru nikoliv. V současnosti jsou různé interpretace kvantové
fyziky spíše záležitostí metafyziky než vědy. Prostě nevíme, co přesně obnáší
kolaps vlnové funkce. Existence kvantových počítačů nám k řešení tohoto
problému ale asi nijak nepomůže.

text ON-LINE
Kompletní podobu tohoto textu naleznete na portálu Science World
(www.scienceworld.cz) s datem 5. 9. 2003.









Komentáře
K tomuto článku není připojena žádná diskuze, nebo byla zakázána.