Podrobně a populárně o tom jak se věci skutečně mají s kvantovými počítači

10.2.2014

Napsal: Dark Side
Přeložil Hamilbar, převzato odtud.

V jedné z Lemových povídek o velkých robotech-inženýrech Trurlovi a Klapaciovi se píše, že jednou zkonstruovali počítací stroj, který sice uměl pouze násobit dva krát dva, ale zato měl jankovitou povahu a dokonce ani tuto jednoduchou věc nedělal vždy správně. Současné kvantové počítače jsou do jisté míry tomuto Lemovu stroji podobné. Jeden z nich vstoupil před několika lety do historie tím, že rozložil na činitele číslo 15. Což je podstatně těžší než vzájemné násobení dvojek, ovšem užitek je z toho zhruba stejný.

Nehledě na skromné výsledky, diskuse o kvantovém počítání probíhá již téměř třicet let a zájem o něj neklesá. Naopak, v poslední době se o něm hovoří mimořádně často. O kvantových počítačích se stále častěji hovoří i ve zprávách, které nemají přímý vztah k vědě.

Analytická společnost Gartner je zařadila do seznamu perspektivních technologií, které „vystřelí“ v následujících deseti letech. Zakladatelé společnosti Parallels, jak se zdá, sdílejí tento názor, protože před několika měsíci založili fond, který bude investovat do rozvoje kvantových technologií. Současně Google a Lockheed Martin utrácí miliony za zařízení využívající k činnosti kvantové efekty. Jak říkával medvídek Pů, to „n-n-není“ jen tak!

***

Nemožné stroje

Jak kvantové, tak klasické počítače zpracovávají data zakódovaná do jedniček a nul. Rozdíl je v tom, že zatímco v klasickém počítači je hodnota každého bitu známa, tak hodnota qubitů (nebo též kvantových bitů), které slouží k uchovávání informací v kvantovém počítači, může být neurčitou a odpovídat zároveň jedničce i nule, přitom s různou pravděpodobností toho či onoho.

V průběhu práce kvantového počítače jsou jednotlivé qubity spojeny efektem kvantové provázanosti (entanglement). Několik propojených qubitů s neurčitou hodnotou obsahuje ne jedno číslo, ale všechna možná čísla, která se vejdou do buňky příslušné délky (s odpovídajícím počtem pozic). Jinými slovy, kvantový počítač současně posuzuje všechna řešení úlohy, jak správná, tak chybná.

Problém spočívá v tom, že při čtení (snímání) informace neurčitost mizí. Místo nesčetného množství řešení, které ještě před chvilkou obsahoval kvantový počítač, zbude pouze jedno, přičemž ne to nejsprávnější, ale to, které „první přišlo pod ruku“. Aby byl od kvantového počítače nějaký užitek, je třeba nepotřebné varianty předem nějak odfiltrovat.

To se provádí pomocí kvantových algoritmů, jež sestávají ze specielních operaci působících na qubity. Asociace s počítačovými programy, kterou může vyvolat slovo „algoritmus“ není úplně přesná. Kvantové algoritmy se programům příliš nepodobají. Podstatně více mají společného s logickými schématy skládajícími se z ventilů A, NEBO, NE, jenom místo Booleovy algebry používají kvantovou logiku.

***

Kvantové programování

V roce 1994 matematik Peter Shor vymyslel první kvantový algoritmus mající potenciál praktického použití. Shorův algoritmus je určen k faktorizaci čísel, tedy k jejich rozkladu na prvočinitele. Právě jeho funkční způsobilost prověřoval kvantový počítač, rozkládající na jednotlivé činitele číslo 15.

***

Půl království za koně: Google, Qualcomm a další hledají velké vynálezce

Velcí vynálezci se jen málokdy objevují bez vnějšího stimulu. Za úspěchy v dobývání kosmu vděčíme závodům ve zbrojení mezi SSSR a USA. Počítače přišly na svět počátkem Druhé světové války kvůli balistickým výpočtům a prolomení německých šifer. Ale stejně tak často bývá stimulem ne válka, ale velká odměna, lákající k řešení důležitého problému.

***

Nejlepší mozky lidstva

Faktorizace čísel – to je jeden z těch úkolů, který tradiční počítače zvládají jen s velkým úsilím. Čím je číslo větší, tím více času je třeba na jeho rozložení na součin prvočísel. A ne o něco více; počet kroků, který je zapotřebí k faktorizaci čísla pomocí známých algoritmů, exponenciálně roste s každým dalším řádem a rychle se tak dostává za rámec možného.

Na tom je založena kryptografie s veřejným klíčem, používaná k ochraně finančních operací na internetu nebo v elektronické valutě Bitcoin. K prolomení, například, šifry RSA, je nutné znát prvočinitele součinu tvořící veřejný klíč. A protože jako klíč slouží dostatečně velké číslo, jeho faktorizace pomocí obyčejného počítače bude trvat roky.

Pokud je tentýž úkol řešen pomocí Shorova algoritmu na kvantovém počítači, doba výpočtu neroste exponenciálně, ale podstatně pomaleji. Velká čísla se faktorizují i v tomto případě déle než čísla malá, ale ne o tolik, aby nestálo za to, to zkoušet.

Kvantový počítač umožňuje faktorizovat číslo mající N řádů za N na druhou operací. Což znamená že objevení se dostatečně výkonných kvantových počítačů znehodnotí mnohé dnes populární kryptoalgoritmy.

Druhý zajímavý příklad – Grooverův algoritmus, umožňující najít hledaný prvek v nesetříděném seznamu N prvků a provést pouhých N1/2 porovnání. Na obyčejném počítači by k tomu bylo zapotřebí N porovnání.

Pro názornost předpokládejme, že seznam má milion prvků. Obyčejný počítač k nalezení jednoho z nich musí provést milion porovnání. Kvantovému počítači používajícímu Grooverův algoritmus jich bude stačit tisíc. Není to sice exponenciální zrychlení, jako v případě Shorova algoritmu, ale přírůstek je i tak citelný.

***

Krutá realita

Tři atomy beryllia, používané jako qubity.

Kvantové algoritmy potřebují podstatně méně kroků k nalezení řešení, než jejich analogy pracující na tradičních počítačích. Někteří se domnívají, že pomocí kvantových počítačů bude možné efektivně řešit dokonce i NP-úplné problémy, i když tento názor není velmi populární. Mimochodem, dokonce i bez NP-úplných problémů jsou přednosti kvantových počítačů očividné. Tak kde to tedy vázne?

Slovo „počítač“ je ošidné. Vrtošivá a drahá kvantová zařízení, která staví v laboratořích, nemají s počítači nic společného. Nejsou to programovatelné počítací stroje. Slovo „stroj“ se příliš nehodí k jejich označení – minimálně v současné etapě jejich vývoje.

Jelikož se kvantové efekty projevují pouze na mikroúrovni, jsou experimentátoři nuceni pracovat s jednotlivými atomy nebo elementárními částicemi, což, eufemicky řečeno, není až tak jednoduché. Jako qubity mohou například sloužit ionty zavěšené v elektromagnetickém poli.

Ionty ovšem nezačnou faktorizovat čísla jenom proto, že je nazveme qubity. Jednoduše nemají čím to dělat. K provádění kvantových operací je nutný vnější stimul. Stimulovat qubity lze například laserem nebo pomocí mikrovln. Je celkem pochopitelné, že malý počet qubitů se tímto způsobem dá ještě zvládnout, ale dál začínají problémy.

Věc se komplikuje ještě i tím, že jakákoliv interakce mezi qubity a okolním prostředím může způsobit dekoherenci, která znemožní další pokračování v činnosti. Kvůli odstranění vnějšího rušení, velmi často umísťují kvantové počítače do vakua a ochlazují téměř k absolutní nule, ale moc to nepomáhá.

***

Renegáti a šarlatáni

V roce 2007 kanadský startup D-Wave oznámil záměr vyrobit první komerční kvantový počítač. Záměr podpořili demonstrací stroje, majícího podle ujištění jeho tvůrců šestnáct qubitů.

Před očima diváků řešil sudoku, propočítal ideální kombinaci hostů hypotetické svatby a zpracoval příkaz SQL ve speciální verzi MySQL. Tyto úkoly by zvládl i obyčejný počítač, ale úkolem prezentace nebylo ohromit něčí představivost.

Ohromujícím bylo něco jiného: napoleonské plány D-Wawe. Ke konci roku společnost plánovala zvýšit počet qubitů na 32, a k polovině roku 2008 vyrobit kvantový počítač s 1024 qubity.

Sliby D-Wave se od kruté reality, dobře známé všem zabývajícím se výzkumem v oblasti kvantových výpočtů, lišily jako nebe a dudy. Skok této úrovně by se rovnal zázraku a zázraky, jak je známo, se nedějí.

Skepticismus výzkumníků narazil na absolutní nezájem D-Wave objasnit, jakým že to způsobem bylo dosaženo těchto úspěchů. Logicky vyvstala otázka: a existoval skutečně ten hoch? Jedná se v případě přístroje, kterým se společnost chlubí, skutečně o kvantový počítač? Žádné důkazy pro to neexistovaly. Rozptýlit pochybnosti by mohly například publikace pracovníků D-Wave ve vědeckých časopisech, ale žádné nebyly.

Na D-Wave nalepili nálepku „šarlatáni“, ale společnost pokračovala v práci. Přehnaně optimistický plán bylo nutno zkorigovat. Stroj, používající, jestli věřit D-Wave, 128 qubitů, se objevil ne v roce 2008, ale až v roce 2011. Před několika měsíci to dotáhli na 512.

V roce 2009 provedli D-Wave a Google společnou prezentaci. Na ní známý odborník z oblasti rozpoznávání tváří Hertmut Neven vyprávěl o testování samoučícího se algoritmu k identifikaci automobilů na fotografiích Street Wiev. Podle jeho slov, zvládal kvantový stroj D-Wave úlohu lépe než tradiční počítače v datových centrech Google.

Tento vývoj událostí skeptiky poněkud překvapil. Výsledky, které prezentoval Neven, nedokazovaly sice, že D-Wave sestrojili skutečný kvantový počítač, ale nebrat je v úvahu také nebylo možné. Jestliže jsou D-Wave podvodníci, tak jak se jim podařilo dostat na svou stranu rozhodně ne hloupé lidi z Google?

V roce 2011 korporace Lockheed Martin, gigant vojenskoprůmyslového komplexu USA, oznámila nákup 128 qubitového stroje D-Wave za 10 milionů dolarů. Dalo se předpokládat, že důvodem nákupu nebyla pouhá zvědavost, ale tím to neskončilo.

V březnu 2013 se Lockheed Martin rozhodli koupit následující model kvantového počítače D-Wave. První nákup nejen uspokojil zájem společností, ale dokázal svoji užitečnost. Dá se tedy říci, že na prohlášeních D-Wave přeci jenom něco bude?

***

Pravda o D-Wave

Nakonec v D-Wave přeci jenom hodili zpátečku a publikovali pár vědeckých prací o svém stroji. Při té příležitosti se vyjasnilo, že za prvé nejde o kvantový počítač v nejčastěji chápaném smyslu tohoto slova, a za druhé qubity, o kterých se mluví v reklamních materiálech společnosti, upřímně řečeno, nejsou tak zcela qubity.

Jádrem stroje D-Wave je do -273 stupňů Celsia ochlazený čip s mřížkou tvořenou supravodivými kvantovými interferometry. A právě ty společnost nazývá qubity. Hodnota qubitů D-Wave, stejně jako hodnota qubitů v opravdovém kvantovém počítači, může být neurčitá, jenomže nejsou svázány efektem kvantové provázanosti.

Stroj D-Wave není vhodný pro algoritmy využívající kvantové ventily. Ani Shorův, ani Grooverův algoritmus na něm nebudou fungovat. Místo toho používá ke své činnosti úplně jiný princip – takzvané adiabatické kvantové výpočty. Což podstatně omezuje jeho možnosti, ale z druhé strany umožňuje nestarat se o dekoherenci a podobné problémy.

Adiabatické kvantové počítače jsou specializovaná zařízení, určená k řešení jediné úlohy: hledání optimálního řešení funkce, definované celkovým energetickým stavem všech qubitů. Nejsou sice schopny provádět operace nad jednotlivými qubity, ale v daném případě to ani není zapotřebí.

Tato optimalizační úloha má až překvapivě mnoho praktických aplikací. V D-Wave použili zařízení pro skládání proteinů, v Google ho učili rozeznávat obrazce, a v Locheed Martin používají stroj k verifikaci kriticky důležitého software.

Současná zařízení D-Wave nedělají nic, co by nezvládly současné počítače, ale zdá se, že je to jen otázkou času: následující modely, jestli věřit slibům technického ředitele společnosti, budou dostatečně výkonné, aby rozptýlily pochybnosti skeptiků. Mimochodem, nezávisle na tom jak to nakonec dopadne, stojí za to D-Wave sledovat. Ta společnost razí cestu, po které jednou půjdou další.

Napsáno Janika Rubriky: Zajímavosti Tagged with Autor: Hamilbar