O.S.E.L. - Jak porozumět kvantovým počítačům
 Jak porozumět kvantovým počítačům
Poněkud nesouvislý rozklad (nikoliv výklad) jako reakce na situaci, kdy se kvantové počítání dostává (opět?) do módy a do oboru tečou peníze nejen z akademické sféry.

Když se člověk chce v něčem aspoň trochu vyznat, měl by si říct, na co se vykašlat. Genetik nepotřebuje znát vzorečky bází v DNA ani jejich chemii, programátor nepájí obvody. Evoluční biolog zkoumající výhodnost určitého znaku prakticky vůbec nemusí vědět, jak daný znak vzniká (pardon, ukradená a navíc omletá metafora: vlčí zuby nejsou otázkou vápníku, ale Karkulky).
Nešlo by kvantové počítače brát podobě? Samozřejmě – přístup black box má jak výhody, tak i nevýhody. Zde však dle vlastních zkušeností soudím, že nemá rozumnou alternativu. Následující text vůbec není nějaké blahosklonné vysvětlování typu „řeknu vám to jednoduše, i když sám tomu rozumím“; kdepak, nerozumím – vezměte si poučení z 15 let mého intelektuálního zápolení, pochopte rychle, co lze, a zbytečně se neobtěžujte zbytkem; programování začalo lidi bavit ve chvíli, kdy při tom nemuseli pracovat s pájkou, eventuálně dostali Basic. Omluvte též jistou nesoustavnost následujícího textu.

Procesor D-Wave: Vyžaduje stínění, které musí snížit magnetické pole Země 50 000 x. Vyžaduje vysoké vakuum. Tlak je 10 miliard krát nižší, než atmosférický tlak.
Procesor D-Wave
Vyžaduje stínění, které musí snížit magnetické pole Země 50 000 x. Vyžaduje vysoké vakuum. Pracuje v tlaku 10 miliard krát nižším, než atmosférický tlak.

Takže teze na úvod

 

Má-li se normální člověk trochu vyznat v kvantových počítačích, nejlepší je prostě si hned říct, že všechny vzorečky, řeči o propletení a kresby vlnových funkcí pochopení spíš zatemňují. Dokonce nemá smysl ani moc přemýšlet o základní logice, totiž povaze kvantových bitů. V kvantovém počítači se možná v daný okamžik kombinují všechny možné stavy propletených částic, takže se zde skrývá i řešení úlohy, ale na tom sotva záleží, když tento výsledek je před námi skrytý.
Příklad: řešíme úlohu obchodního cestujícího, tj. nalezení nejkratší trasy. Propletené bity (možná) obsahují všechny kombinace, to je nám ale čerta platné. K řešení se nedostaneme, vlnová funkce prostě náhodně zkolabuje. Na rozdíl od DNA počítače, kde se nám molekuly skutečně nakombinují vedle sebe a ta nejkratší třeba jako nejlehčí vyplave nahoru. (Programování DNA počítačů pro každého).

 

Poučení číslo 1: Na to, jak to funguje uvnitř, zapomeňte.

Počítače používáme k počítání. Kvantové počítače nabízejí proti těm normálním výpočetní výkon, který s počtem qubitů roste exponenciálně, jenže to je zase jen takové přiblížení, málem jen metafora. Skutečné zrychlení záleží na konkrétním algoritmu. Pak zjistíte, že známý Shorův algoritmus – rozklad složeného čísla na prvočísla – snižuje výpočetní složitost nějak, algoritmus pro hledání v databázích (Groverův) zase jinak. Jde o vlastnost konkrétního algoritmu. Navíc se k tomu přidružují různé kontroly výpočtů, kvůli kolapsu vlnové funkce mají výsledky spíš statistický charakter. Jak konkrétně se šťouchá třeba laserovým paprskem do jednotlivých částic při realizaci algoritmu, z toho zase spíš rozbolí hlava. (Nakonec qubity mohou být reprezentovány fotony, kousky supravodivého materiálu, elektrony, ale i dírami. Skutečně bude manipulace laserem fungovat nějak univerzálně? A tak dále.)

 

Poučení číslo 2: Na to, jak funguje uvnitř konkrétní kvantový algoritmus, spíš zapomeňte.
Z toho, jak je konkrétní kvantový algoritmus rychlý oproti klasickému (respektive jak roste jeho výpočetní složitost, tj. čas na generování výstupu s objemem vstupu) si lze ale udělat hrubou představu, kolik qubitů potřebujeme, aby to vše z hlediska výpočetního výkonu mělo smysl. Zatím z toho kvantové počítače moc triumfálně nevycházejí (pochopitelně, jinak by už nešlo o experimentální technologii). Ale zrovna tohle se dá počítat. Specialisté IBM odhadují, že mezi 50–100 qubity už kvantový počítač přinese výsledky, které jsou na současných klasických počítačích nedosažitelné (Sciencemag.cz). Dodávám – ale stále jen pro určité typy úloh. Samozřejmě asi ty, které v sobě kvantovou mechaniku obsahují už samy o sobě, tj. spíše chemii a fyziku než problémy informatické/matematické.

Úkol: Zjistit nejnižší bod v krajině. Klasické počítače se systémem klasických algoritmů mohu jen "chodit po povrchu krajiny". Kvantový počítač může krajinu tunelovat a tím najít nejnižší bod rychleji. Procesor D-Wave bere v úvahu všechny možnosti současně. Zvládá 10 000 odpovědí během jedné sekundy.
Úkol: Zjistit nejnižší bod v krajině. Klasické počítače se systémem klasických algoritmů mohu jen "chodit po povrchu krajiny". Kvantový počítač může krajinu tunelovat a tím najít nejnižší bod rychleji. Procesor D-Wave bere v úvahu všechny možnosti současně. Zvládá 10 000 odpovědí během jedné sekundy.

Jednoúčelové, nebo univerzální?

 

Zajímavé v této souvislosti je, zda vůbec stojíme o obecný kvantový počítač, když známe stejně jen několik efektivních algoritmů, kde nám kvantové počítání přináší výhodu. Existují v zásadě dva přístupy: první, který uplatňuje firma D-Wave, prozatím nabízí systémy pro kvantové žíhání. Tyto kvantové počítače jsou jako jediné zatím nasazeny v produkčním prostředí (NASA, Google, Lockheed Martin), alespoň pokud víme. (Ne že bych tedy věřil, že na utajených vojenských základnách mají dnes kvantové počítače louskající šifry.)Tyto počítače provádějí jedinou operaci, kvantové žíhání. Jak si zase tohle představit? Snad nějak následujícím způsobem. Řešíme optimalizační úlohu, hledáme minima či maxima na křivce, prohledáváme stavový prostor. Algoritmus při tom může snadno uvíznout v lokálním extrému, viz známý příklad kuličky kutálející se adaptivní krajinou. Biologická evoluce nezamrzne, protože adaptivní krajina se neustále mění. Všemožné evoluční/genetické algoritmy analogicky přicházejí s tzv. žíháním, kdy se s výsledkem/krajinou jakoby třese a máme tak větší šanci najít globální, nikoliv nejbližší lokální extrém. Kvantové žíhání znamená prostě to, že k tomuto procesu „dopočítání“ používáme nějaké kvantové triky. Člověka napadne, že v kvantové fyzice existuje tunelování, kdy se překážka (ať už jde o dveře nebo nepohodlnou část křivky) překoná přímo, podleze. Souvisí to nějak s kvantovým žíháním? Možná.

Ještě v téhle souvislosti trochu úsměvná perlička. Když firma D-Wave svůj systém představila, hádali se všichni, zda se vlastně vůbec jedná o kvantový počítač a mnozí vědci to zpochybňovali. Muselo vyjít několik článků v časopisech typu Nature, než se odborníci cca shodli, že nejde o marketingový trik a uvnitř systému ve skutečnosti manipulaci s daty neprovádějí permoníci. Jak bychom tomu pak měli porozumět my ostatní?

Na počítači D-Wave údajně vůbec nejde lámat šifry, ať už se konstruují jakoukoliv asymetrickou operací, kdy výpočet jedním směrem je obtížný, ověření výsledku ale snadné (nejen faktorizace, ale např. i eliptické křivky). A to proto, že D-Wave při kvantovém žíhání stejně nehledá nejlepší řešení, ale nejlepší řešení objevitelné dostatečně rychle, tj. de facto zase jen lokální extrém. Tady zase nevím, dá se v tom vyznat? Snad jo, ale je to záležitost běžné matematiky, informatiky, ne kvantové fyziky. Samotné kvantové žíhání představuje zase black box.

Keith Devlin na World Science Festival 2011. (Kredit: Richard Ressman) 
Keith Devlin na World Science Festival 2011. (Kredit: Richard Ressman)


Poučení číslo 3, pro zopakování:

 

To, že kvantové počítače něco zvládnou rychleji než klasické, vůbec neznamená, že to platí univerzálně. Jedním z nejpopulárnějších problémů současné matematiky je otázka výpočetní složitosti, tzv. problém P vs. NP. I když se někdy tvrdí opak, žádný kvantový počítač/algoritmus dnes NP problémy v polynomiálním čase řešit neumí. Slavná faktorizace není NP úplný problém (respektive nikdo nedokázal, že by byla, a většinou se o tom pochybuje).(Problém P vs. NP je mimochodem tak populární možná ne kvůli praktickým aplikacím, ale hlavně proto, že i my nematematici dokážeme vůbec pochopit zadání. Na rozdíl od řady dalších největších matematických hádanek, jak je sestavil Clayúv ústav.)

Důvodné je naproti tomu přesvědčení, že i když určité sporné problémy nikdo exaktně nezařadí do nějaké třídy výpočetní složitosti a nezkonstruuje účinný kvantový algoritmus, při samotném zkoumání získá takový vhled do problému, který mu umožní přijít s různými heuristikami a triky. I to je asi jedna z příčin, proč se to zkoumá (doufá se v jakýsi by-product; což může být i smysluplná motivace pro provoz celé vědy, ale to už bychom se dostali někam úplně jinam). 
Alespoň matematik a autor popularizačních knih Keith Devlin se domnívá, že v tomto pochopení je právě riziko pro současné šifrovací technologie – i když přímo nezmiňuje kvantové algoritmy, ale spíše řešení úlohy P vs. NP a Riemannovu hypotézu popisující rozložení prvočísel.

Zpět k otázce, zda budoucností jsou spíše jednoúčelové systémy. V IBM si myslí opak než v D-Wave (Sciencemag.cz). Je to divné. Ačkoliv známe omezené množství efektivních kvantových algoritmů, výzkumy/publikace se soustředí spíše na univerzální systémy. Logičtější by mi přišel opak, jenže já tomu nerozumím. (Nicméně – na tuhle otázku by se odpověď asi našla. Znovu: Cílem tohoto textu není odrazovat od kladení otázek a přemýšlení nad problémy kvantových počítačů; spíše rozdělit problémy do dvou kategorií: někde to smysl má, jinde ne.)

Poučení číslo 4:

Kvantový počítač je jen rychlejší, nedokáže vyřešit nic víc než obecný Turingův stroj. Tudíž lze – patřičně pomalu – každý kvantový algoritmus simulovat na klasickém počítači. Zajímavé v této souvislosti je, že IBM nabízí zájemcům přístup ke svým kvantovým počítačům. Jakou to má výhodu proti simulátoru, který ostatně IBM nabízí rovněž? Nevím, ale toto bych opět zařadil do kategorie otázek, kde by odpovědi mohly být pochopitelné.

George Johnson.  Kredit: Girona7, en.wikipedia
George Johnson. Kredit: Girona7, en.wikipedia


Bod zlomu

 

Co je zajímavé, kvantové počítače se dnes zdají být v kurzu. Těžko říct, co tak zásadního se stalo za posledních třeba 12 let, dnes se však tato podivná technologie považuje ne za akademickou hračku nebo vizi autorů sci-fi, ale za významný průmyslový trend. Vnímání technologie se změnilo tak někdy v roce 2013-14. Dnes sem míří investice firem typu Intelu (loňská investice) a IBM, i v jiných největších IT firmách všichni pokyvují, že toto je budoucnost. Dělá se to prostě proto, že se to líbí akcionářům, v jiných případech se na to dobře shání rizikový kapitál apod.? Google dokonce nedávno avizoval, že do prohlížeče Chrome zahrne šifrování odolné proti kvantovým počítačům, tzv. post kvantovou kryptografii (Sciencemag.cz) Takové sdělení samozřejmě média zaujme, ale má Google takový marketing zapotřebí, když sám je dnes vlastně hlavním médiem? S nástupem kvantových počítačů zřejmě všichni opravdu počítají, nebo se tak alespoň tváří.

Vedlejší prvky

A ještě jeden zcela subjektivní pohled: na co se teď všichni primárně soustředí, nejsou algoritmy a ani to, jak pospojovat co nejvíce qubitů. Počítačová architektura má spoustu prvků a cílem je teď vyvinout kvantovou obdobu maxima z nich – nebo alespoň klasickou obdobu, která by umožnila propojit prvky kvantové. Takže se vyvíjejí třeba systémy kontrolních bitů nebo sběrnice, která by umožňovala informaci přenášet. Hlavním cílem je přitom škálovatelnost, tedy přijít s bloky, které by šlo rutinně skládat vedle sebe. Objevilo se už pár oznámení, že meta byla pokořena a dostali jsme se do „fáze stavebnice“, ale moc věrohodně to nepůsobí –  protože obvykle následuje douška ve stylu, že „už jde jen o inženýrský, nikoliv zásadní problém“.

Knihy o kvantových počítačích

Už v roce 2004 u nás vyšla kniha Zkratka napříč časem od George Johnsona. Je to dílo jistěže starší a subjektivně ne úplně vydařené, ale zato česky a v kvalitním překladu lidí, kteří problematice rozumí. Bylo by hezké, kdyby se nějaký vydavatel dnes odvážil risknout a vydat knižně modernější titul. Nicméně kdo by chtěl přece jen zkusit pochopit Shorův algoritmus, ve Zkratce napříč časem je výkladu věnována celá kapitola a trochu pochopitelné to je.


Autor: Pavel Houser
Datum:26.08.2016