Po kvantech jde počítání rychleji

Co jsou to vlastně kvantové počítače? Při pokusu o srozumitelný výklad ihned narazíme na velký kámen úrazu: Jakou ...


Co jsou to vlastně kvantové počítače? Při pokusu o srozumitelný výklad ihned
narazíme na velký kámen úrazu: Jakou roli má v našem popisu hrát matematika?
Jen málo popularizátorů "nové" fyziky (teorie relativity a kvantová fyzika) je
nadáno takovým talentem, který jim umožní podat výklad bez složitých
doprovodných rovnic. Tento článek by měl být pochopitelný i bez matematického
doprovodu, několik zde zmíněných základních pojmů slouží spíše k pochopení typů
příkladů, v nichž by použití kvantových počítačů představovalo výhodu oproti
těm klasickým. Pokud řešíte nějaký problém, ať už jde o formalizovaný
matematický příklad nebo třeba o šachovou úlohu, máte v zásadě dvě možnosti:
buď se snažíte postupovat analyticky/logicky, nebo prostřednictvím metody hrubé
síly (brute force). Hrubá síla znamená, že z množiny možností vybíráte vlastně
náhodným způsobem jednu po druhé, kontrolujete, zda vyhovuje podmínkám řešení,
a v případě neúspěchu přejdete k dalšímu řešení. Obě možnosti lze v praxi
samozřejmě různě kombinovat.
V případě řady úloh není žádný "inteligentní" algoritmus pro jejich řešení znám
(buď jsme ho ještě neobjevili, nebo nemůže existovat principiálně), a musíme
tedy postupovat výčtem prvků. Z našeho hlediska je v tuto chvíli klíčová
především rychlost řešení, tedy to, aby výpočet vůbec stihl doběhnout ke svému
konci v reálném čase.
Pojďme dále. Máte např. najít nejkratší cestu mezi několika body (a musíte
navštívit každý z nich právě jednou jedná se o tzv. problém obchodního
cestujícího, kterým jsme se podrobněji zabývali v Computerworldu číslo 6/2001 v
článku o DNA počítačích), nebo vyřešit šifru s klíčem o určité bitové délce.
Přichází důležitá otázka: Pokud zdvojnásobíte počet bodů v grafu nebo délku
šifrovacího klíče, co se stane s časem potřebným k řešení problému? Zdvojnásobí
se? Tak jednoduché to samozřejmě není a např. šifrování je založeno právě na
skutečnosti, že s růstem složitosti roste čas potřebný k řešení prakticky nade
všechny meze.
Jaká je matematická závislost mezi složitostí úlohy a časem potřebným k jejímu
řešení? V zásadě rozlišujeme úlohy polynomiální a nepolynomiální, tzv. NP
problémy. Jestliže čas potřebný k řešení úlohy roste např. jako kubická rovnice
(y = ax3 + bx2 + cx + d), můžeme růst složitosti alespoň teoreticky kompenzovat
tím, že k řešení použijeme vždy větší počítač (objem, respektive výpočetní
výkon poroste tedy řekněme také s mocninou třetího stupně). Čas potřebný k
řešení NP problémů však s růstem složitosti roste exponenciálně (y = ax) a zde
je každá rada drahá. V této souvislosti je dobré si uvědomit, že exponenciální
závislost je řádově vyšší než polynomiální.
Právě v souvislosti s NP problémy naleznou uplatnění kvantové počítače. Jak se
dočtete v hlavním článku, kvantový počítač se v jednom okamžiku může současně
nacházet v 2n stavech, kde n je počet základních stavebních jednotek systému
qbitů. S růstem jednotek roste tudíž výkonnost kvantového počítače opět
exponenciálně, a tím jaksi "vyrovnává" růst NP problémů. Kvantový počítač tedy
"snižuje úroveň složitosti výpočtu". O kolik? Nutno přiznat, že v tom není
zcela jasno. Algoritmus navržený pro luštění v některých případech nepřevede
exponenciální závislost na polynomiální, ale "schová" ji pod odmocninu [y =
+(ax)]. O určitých nejasnostech v tomto ohledu svědčí např. článek ve vědecké
sekci Neviditelného psa (http://pes.internet.cz/clanky/9794_0_0_0.html) a
zejména následující diskuze.
Jiným příkladem je tzv. Groverův algoritmus, což je způsob, jakým se prohledává
netříděná databáze. Postupujeme prostě tak, že každou položku zkoušíme. Pokud
můžeme neúspěšné po-kusy z databáze vyřadit, pak k řešení dojdeme v průměru po
(n + 1)/2 otázkách. Díky kvantovému algoritmu, se kterým přišel v roce 1996 L.
K. Grover, však k nalezení řešení potřebujeme v průměru pouze +(n) pokusů
kvantový algoritmus nám tedy složitost výpočtu opět snížil přidáním odmocniny.
Podrobnosti hledejte např. na
http://www.kolej.mff.cuni.cz/~lmotm275/RUZE/19/node18.html.


TAM, Kde ZDRAVÝ rozum NEPLATÍ aPři sečtení dvou rychlostí náhle neplatí, že
jedna plus jedna jsou dvě. Daná částice současně někde je i není. Kvantová
fyzika i teorie relativity se vydávají do sfér, kde spíše než "zdravý rozum"
platí jakési složité paradoxy podepřené nepochopitelnou matematikou ostatně už
vizualizace příslušných funkcí v našich obrázcích svědčí o tom, že před sebou
nemáme právě jednoduché vztahy. Paradoxně se v této oblasti přitom rodí něco,
co fyzikové k nelibosti ostatních vědců označují jako "velké sjednocení" či
"teorie všeho". Z našeho hlediska je ale namístě i podstatně prozaičtější
otázka: Může krabice fungující na podobných "mlžných" principech stát v blízké
budoucnosti na vašem zcela reálném stole?
Odpověď je podle všeho záporná. Kvantové počítače či zařízení pracující třeba
na molekulárních principech (viz CW 6/2001) mají smysl pouze pro určitou
kategorii úloh, tj. tam, kde počítače nijak neskrývají původní význam svého
označení, tedy kde počítají úlohy jinak neřešitelné. Rozhodně nemají smysl pro
běžné kancelářské aplikace a vzhledem ke své citlivosti na vnější vlivy
vyžadují speciální, velmi komorní prostředí. Na stole by se tedy kvantový
počítač mohl objevit snad jen v tom smyslu, že bychom naše vlastní PC použili
pro terminálový přístup.

Historie
Richard Feynmann je díky svým popularizačním knihám jedním z mála fyziků tohoto
století, kteří jsou známi širší veřejnosti. Snad právě z tohoto důvodu tedy
začíná líčení historie kvantových počítačů obvykle právě u něj. Vlastní
definice kvantového počítače se pak přičítá Davidu Deutschovi a datuje se do
roku 1985. Zvýšený zájem o celou problematiku nastal kolem roku 1994, kde Peter
Short z Bellových laboratoří přišel s kvantovými algoritmy pro faktorizaci
velkých čísel i prohledávání netříděné databáze (viz náš vložený článek o
matematických základech kvantových počítačů). Faktorizace velkých čísel (tedy
jejich rozklad na dvě prvočísla, které dají po vynásobení původní číslo) se
dosud pokládala za principiálně neřešitelnou a právě na této neřešitelnosti
stály moderní kryptografické technologie.
Pokud se přeneseme naopak k aktuálním událostem, posledních úspěchů dosáhli v
létě roku 2000 výzkumníci IBM ve spolupráci s týmem kalifornské Stanfordovy
univerzity, když se jim podařilo sestrojit kvantový počítač složený z pěti
částic (qbitů, viz dále). Do dvou let by se podle experimentátorů mohlo podařit
spojit do jednoho bloku až desítku atomů.
V lednu tohoto roku byla navíc objevena možnost zpomalení a zastavení světla,
přičemž celá technologie by mohla přispět nejen k vytvoření krátkodobé paměti
kvantového počítače, ale především k realizaci bezpečné kvantové komunikace.

Principy
Jak už vyplývá z názvu, kvantový počítač stojí na aplikaci zákonitostí kvantové
fyziky. Klíčovým pojmem v rámci tohoto oboru je tzv. vlnová funkce, což je
matematický předpis určující možné stavy částice a jejich pravděpodobnosti.
Pokud je nějaké částice ponechána sama sobě, nachází se ve všech stavech
umožněných vlnovou funkcí najednou. Teprve ve chvíli, kdy se vlastnosti objektu
nějak pokusíme změřit, dojde k tzv. kolapsu vlnové funkce a my změříme jednu
konkrétní hodnotu.
Jinak řečeno: Měření zásadním způsobem ovlivňuje vlastnosti zkoumaného,
neexistuje žádné nezávislé pozorování. Pokud se někdo pokusí odposlouchávat
vaši kvantovou komunikaci, jistě na to přijdete. Jak ale poznáte, zda šlo o
nějakého narušitele, nebo jen o neškodnou interakci s neživým zařízením? Kdy
přesně vlnová funkce zkolabuje? Dobrá otázka. Pokud se zamyslíte nad vloženým
článkem o proslulé SchrÖdingerově kočce, objevíte mezi oběma problémy jistě
řadu analogií. Současná kvantová fyzika není každopádně ve výkladu tohoto
problému zcela jednotná.
Ještě zajímavější jsou však důsledky vlnové funkce pro vlastní sílu kvantového
počítače. Zatímco základní jednotka klasického počítače může existovat v jednom
ze dvou stavů, tzv. qbit u počítače kvantového (nejčastěji jde částici ve stavu
"nezkolabované" vlnové funkce) se nachází ve dvou stavech současně. Stavy n
částic pak můžeme skládat (tento jev se označuje jako superpozice), a celý
systém se tak v jednom okamžiku může nacházet ve 2n stavech. Např. pro kvantový
systém 3 qbitů dostáváme celkem 23 = 8 kombinací: 000, 001, 010, 011, 100, 101,
110 a 111. Superpozice stavů je klíčovým momentem celého kvantového počítání,
bohužel se ale poněkud vzpírá zdravému rozumu. Jesliže však tuto možnost
připustíme, máme před sebou masivně paralelní zařízení, jehož výkon roste s
přidáváním dalších stavebních kamenů exponenciálně a exponenciální závislost je
velmi strmá. Pokud se podaří spojit v kvantovém počítači společně stovky atomů,
bude zařízení schopno provádět miliardy operací současně.
Vratné a nevratné počítání
S jakými dalšími pojmy se můžeme v oblasti kvantového počítání setkat? Soubor
qbitů je pak nazýván kvantový registr. Jsou definovány logické (booleanovské)
operace, které je možné s qbity provádět, přičemž qbit zahrnující v sobě více
možností se při těchto operacích reprezentuje ani ne tak klasickým číslem, ale
spíše prostřednictvím matice.
Je to trochu komplikované, že? Jak takový kvantový počítač (respektive nesmělé
pokusy o něj, protože teorie výrazně předběhla praxi) vypadá? Např. prozatím
největší stroj od IBM funguje na základě tzv. nukleární magnetické rezonance
(NMR), což byla původně metoda používaná v analytické chemii. To, v čem je
ukryta informace, je spin, tedy v podstatě číslo, které udává směr rotace
elektronu. Jeho hodnoty se udávají prostřednictvím 1 nebo -1 (jde vlastně o
průměty vektorů charakterizujících rotaci na kartézské souřadnice). Tyto dvě
hodnoty jsou právě dvěma stavy kvantového počítače, obdoba nabito-nenabito v
počítači klasickém.
To nejzajímavější však teprve přichází. Kvantové počítače se díky superpozici
stavů řadí do kategorie tzv. nedeterministických strojů. Zde se dostáváme na
zvlášť křehkou půdu. Nedeterministický stroj pracuje v principu vratně. Zatímco
klasické počítání je obecně operace podléhající druhému zákonu termodynamiky, a
tudíž nevratná (dle Barrowovy knihy "Teorie všeho" z toho nakonec vyplývá i
naše subjektivní vnímání šipky času: lidský mozek je v podstatě počítač a jeho
operace jsou proto z hlediska času orientované jednosměrně), existuje kategorie
tzv. Fredkinových strojů, jejichž operace jsou naopak vratné (neboli časově
invariantní).
Není úplně jasné, co všechno za důsledky může z této vlastnosti kvantových
počítačů nakonec vyplynout. Znamená to např., že náš počítač se v průběhu
operace může obrátit a dospět zpátky k zadání bez zjištění výsledku? Nebo
naopak to, že pokud je dobře proveditelný výpočet jedním směrem, zvládne naše
zařízení stejně snadno i složitější obrácený proces? Příklad: Vynásobit dvě
prvočísla je jednoduché, opačný proces, tedy rozklad výsledku na dvě prvočísla
(výše zmíněná faktorizace) je podstatně složitější. A jsou zde samozřejmě ještě
obecnější otázky: protože se druhý termodynamický zákon o růstu entropie/chaosu
pokládá za univerzálně platný, přinese existence kvantových počítačů v tomto
ohledu nějaký spor?

Problémy
Vlnová funkce při kontaktu s vnějším světem obvykle zkolabuje. Kvantový počítač
je tedy jakousi černou skřínkou, v níž výpočetní proces probíhá bez naší
účasti. Zatímco ale DNA počítače je možno s trochou nadsázky charakterizovat
slovy "něco nasypete do zkumavky, třepete s tím a řešení vám vyplave na
hladinu", na kvantový počítač se během procesu ještě navíc nesmíte ani podívat.
Částice, které tvoří kvantový počítač, bývají proto od okolí maximálně
izolovány. Např. může jít o ionty, které se nechají kmitat v tzv.
potenciálových jámách (díky účinkům nějakého silového pole je pak "vyskočení"
částice velmi nepravděpodobné vzhledem k množství energie k tomu potřebné).
Extrémní závislost kvantových počítačů na vnějších vlivech je jednak problémem
při jejich konstrukci, jednak působí problémy při zápisu dat a jejich čtení.
Vlastně: vstup i výstup dat jsou nesporně destruktivními interakcemi. Proces
výpočtu musíte tedy nechat proběhnout celý najednou a až pak odečíst výsledek a
přitom nutně způsobit kolaps procesu. Poté kvantový počítač opět spustíte. A
navíc: Protože v kvantovém počítači dříve či později dojde k destruktivní
interakci s okolím, musí příslušný výpočet proběhnout dostatečně rychle.
Frekvence kvantového počítače, potřebná k tomu, aby ještě před kolapsem vlnové
funkce stihl dokončit nějaký prakticky použitelný výpočet (konkrétně
faktorizaci tisícimístného čísla), by byla kolem 1015 Hz
(http://psaci.misto.cz/_MAIL_/fyzika/kvant/ckvantovepoci tace.html). Prakticky
použitelný kvantový počítač by tedy musel pracovat na podstatně vyšší frekvenci
než dnešní stroje.

Závěr
Pokud po přečtení tohoto textu máte stále dojem, že si kvantový počítač
nedovedete nějak názorně představit, souvisí to jednak s principiálními
problémy (jistá nekompatibilita "nové fyziky" s naším přirozeným světem),
jednak s tím, že o kvantové fyzice píše obvykle pouze úzká skupina odborníků
materiály určené opět těmto několika zasvěcencům. Na druhé straně se z pojmu
"kvantový počítač" stává jakési zaklínadlo, používané zhusta i bez základních
znalostí příslušné fyzikální problematiky. Pokud se tomuto článku podařilo
uvést na scénu alespoň základní pojmy, zařadit je do určitých souvislostí a
ukázat i některé komplikace a spojené s tématem, pak splnil svůj účel.
Kam pro další informace? Značná nesrozumitelnost je bohužel problémem celé řady
internetových odkazů. Poměrně kompletním zdrojem informací, minimálně však
nepřehledně uspořádaných, jsou stránky Luboše Motla na adrese
http://come.to/lumo. Autor, který v minulosti spolupracoval i s
Computerworldem, zde nabízí řadu informací nejen o kvantových počítačích, ale
např. i výklad populární teorie superstrun.
Pokud se neobáváte i trochu složitějších matematických vztahů, doporučuji
zejména článek Marka Biskupa, Pavla Cejnara a Romana Kopeckého, který vyšel v
časopise Vesmír, dostupný však v tuto chvíli není na serveru tohoto časopisu,
ale na adrese http://psaci.misto.cz/_MAIL_/fyzi ka/kvant/ckvantovepocitace.html.

Kočka pana SchrÖdingera
SchrÖdingerova kočka je zřejmě nejznámějším příkladem, na němž se demonstrují
paradoxy kvantové fyziky. Realizace experimentu je jednoduchá. Do krabice
uzavřete kočku a svážete její život s nějakým náhodně probíhajícím dějem, jehož
pravděpodobnost je např. 50 %. Pokud děj proběhne, kočku ve svých důsledcích
zahubí, v opačném případě zůstane kočka naživu. Dokud do krabice nenahlédnete,
je kočka vlastně s příslušnými pravděpodobnostmi současně živá i mrtvá.
Zbývá samozřejmě upozornit, že se jedná o značnou nadsázku, která pro ilustraci
přenáší vlastnosti platné v mikrosvětě do světa "lidské zkušenosti". Kočka sama
o sobě je dostatečně makroskopickým objektem, aby svou přítomností způsobila
kolaps vlnové funkce a přechod systému do jednoho zcela určitého stavu.
1 0594 / pah









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