Jak fungují kvantové počítače

Kvantový počítač dokáže provést matematickou operaci třeba na na miliardách čísel naráz. Říká se tomu kvantový paralelismus. Jak to ale dělá?

Pojem kvantové počítače je poněkud nešťastný, protože vyvolává představu přístroje podobného tomu, ze kterého teď čtete tento článek. Termín již vstoupil do širšího povědomí, ví se, že je to cosi pekelně rychlého, probleskují články o komerčních řešeních, a tak se zdá, že co nevidět zasedneme k notebooku s nějakými Windows quantum, které nebudou zpomalovat práci. Což je z mnoha důvodů pošetilé.

Ten fyzikální důvod, proč se to nestane, je v samotném principu. Dnes si již málokdo vzpomene, že počítače kdysi byly rychlejší. Nedokázaly třídit data, sloužily k řešení matematických problémů. Byly to tak zvané analogové počítače. Rychlé byly proto, že doopravdy nic nepočítaly, využívaly skutečnosti, že příroda úlohu spočítá sama. Stačilo pospojovat elektrické součástky tak, aby matematický popis jejich chování odpovídal řešeným rovnicím a pak na zvolených místech změřit napětí, proud nebo jejich průběh, podle toho, které neznámé bylo třeba určit.

Když všechno fungovalo, bylo řešení k dispozici okamžitě. Na druhou stranu se jednalo o specializované nástroje určené pouze k řešení matematických úloh. V tomto směru se dají připodobnit ke kvantovým počítačům. Algoritmy kvantových počítačů se týkají pouze některých typů úloh, naštěstí z oboru těch, které by klasický počítač nezvládl v rozumném čase. Navíc je takových algoritmů známo zoufale málo. Možná jsme špatní kvantoví programátoři, možná příroda více nenabízí.

Odhlédneme-li od technických detailů, které dokážou nadělat vrásky nejlepším konstruktérům světa, stojí kvantový výpočet na třech pilířích. Jednak je to vlastní algoritmus a pak dvě nepochopitelnosti kvantového světa - EPR paradox a superpozice stavů.

Zkusme hodit elektron mezi dva protony. Aby se nám nepletly, očíslujeme si je pořadovými čísly 0 a 1. Výsledek pokusu nás nepřekvapí. Elektron se přitáhne k jednomu z protonů a vytvoří s ním atom vodíku. Nestarejme se o další chování atomu a chápejme proton jen jako past na elektron, abychom ho dostali do jedné ze dvou poloh. Do polohy 0, nebo do polohy 1.

Asi není těžké domyslet se, že jsme právě vymysleli součástku schopnou zaznamenat informaci o délce jednoho bitu. Když na jeden z protonů posvítíme laserem, elektron vybudíme a přeskočí k druhému protonu. Když posvítíme na druhý proton, elektron přeskočí zpět. Máme tedy i nástroj, jak bit nastavit na požadovanou hodnotu. Takových bitů můžeme zkonstruovat libovolné množství a jsme na cestě postavit počítač. Jenomže na takovém počítači není nic kvantového.

Ještě jsme si neřekli, co se stane, když posvítíme na oba protony. Elektron se vybudí a zase přitáhne k jednomu z protonů, buď do polohy 0, nebo do polohy 1, zdá se logická odpověď. Nicméně takhle kvantový svět nefunguje. V minulém dílu jsme si ukázali, že dokud neprovedeme měření, ztrácí se pojem polohy v neurčitosti. Můžeme snad mluvit o pravděpodobnosti, kde elektron nalezneme, až ho budeme hledat, ale do té doby o něm nevíme nic. Přesto o něm chceme uvažovat, a proto fyzici přišli se zvláštním nástrojem, který takovou situaci popisuje.

Podle současné interpretace kvantové mechaniky (která nabízí tolik ověřitelných předpovědí, že bychom ji měli brát vážně) se elektron nachází v tak zvané superpozici stavů. Nedá se říci, že je v poloze 0, nebo v poloze 1. Správná teze zní, že je v poloze 0 i v poloze 1. To je šokující poznatek, naprosto popírající všechno, co známe z makrosvěta, ve kterém se nacházíme vždy na jediném místě, jakkoli se nám to ne vždy hodí.

Co s takovým kvantovým bitem (říká se mu qubit), který může mít nedefinovanou hodnotu? To je špatně položená otázka, nemá nedefinovanou hodnotu. On má obě hodnoty. Číslo sestavené ze dvou qubitů bude mít současně čtyři hodnoty (00, 01, 10 a 11), při třech qubitech již osm hodnot, N qubitů uchová v jeden okamžik 2^N hodnot.

Teď se ocitáme zpět na základní škole, kdy jsme se dozvěděli, že se dají sčítat nejen čísla, ale i písmenka. Chvíli trvalo, než jsme si zvykli na myšlenku, že operace neděláme nad konkrétními hodnotami, ale jen jaksi ve vzduchu žonglujeme s písmenky, abychom do nich až ve finále dosadili konkrétní hodnoty. Ale tady jsme přece jen trochu dál. Zatímco ve škole jsme museli u výrazu A + B skončit, protože až do chvíle dosazení s tím nic dalšího nešlo, qubity mohou jít dále. Obsahují přece všechny možné hodnoty čísel A a B. Po provedení příslušného algoritmu by ve výsledku měly být obsaženy všechny jejich součty. Teď jen, jak této skutečnosti využít.

Vyšli jsme z těžko představitelného faktu, že kvantový stav může nabývat zároveň všech svých hodnot. Matematici mají v rukávu několik triků, jak takovou podivnost uchopit. Jeden z nich se nazývá vlnová funkce. Ve jménu tradic evropského humanismu nebudeme zabředat do detailů tohoto úžasného nástroje, jen se spokojíme s vědomím, že něco takového existuje a uchováme název v hlavě pro pozdější použití. Kdykoli se bude mluvit o vlnové funkci, je zřejmo, že popisujeme něco, co jsme ještě nezměřili a máme jen povšechnou představu, co všechno může vlna natropit. Je to jako opravdová vodní vlna, která se také nachází v mnoha bodech najednou a teprve, když nás zmáčí, můžeme říci kde k tomu došlo.

Tím se dostáváme k rozčarování, které tu číhá. Kdo se těšil, že spatří elektron, jak se nachází ve dvou místech najednou, bude zklamán. Ve chvíli, kdy provedeme měření, elektron se již nemůže schovávat za oponou neurčitosti a musí se někde zhmotnit. Nalezneme ho buď v poloze 0, anebo v poloze 1, ale nikdy nebude v obou polohách současně. Říkáme, že v okamžiku měření dochází ke kolapsu vlnové funkce.

To je závažný technický problém. Zatím jsme si mohli představovat qubitovou kalkulačku, na které zadáme třeba funkci sinus a v jediném okamžiku budou ve výstupním registru všechny její hodnoty. V jediném okamžiku to bude proto, že procesor vykoná algoritmus výpočtu sinu vlastně jen jednou, nad qubitovým číslem. Ale tady je ta potíž. Aby mohl algoritmus provést, musel by nejprve qubitové číslo přečíst. Přečíst qubit, to vlastně znamená provést na něm měření. Procesor tak provede výpočet nad náhodným číslem, do kterého zkolabovaly vlnové funkce qubitů.

Při hlubším zamyšlení uvidíme, že je to pouze komplikace, nikoli principiálně neřešitelný problém. Procesor nemůže načítat data do svých registrů, protože by zkolabovala vlnová funkce? Dobrá, tak ho tedy rozdělíme. Registry budou mimo procesor a procesor nechť jim pouze posílá řídící impulsy, co mají dělat.

Jeden typ řídicího impulsu už jsme si ukázali. Je to nastavení hodnoty qubitu na hodnotu 0, 1, nebo na superpozici těchto hodnot. Ale logické operace mezi jednotlivými qubity? To je obtížnější problém, protože vyžaduje, aby jednotlivé qubity o sobě věděly. Je nezbytné, aby nějak viděly hodnoty svých sousedů, aby mohly svou hodnotu změnit podle stavu některého souseda. Potřebujeme, aby byly qubity nějakým způsobem provázané.

Slovo "provázané" jsme již použili v povídání o teleportaci, při objasňování EPR paradoxu. Ve stručnosti připomeneme, že částice, které se spolu někdy setkaly, mají mezi sebou stále jakési informační pouto. Je sice velice křehké, mizí ve chvíli, kdy provedeme na jedné z nich měření, ale do té doby se navzájem ovlivňují.

Změní-li jedna částice stav, změní ho i ta provázaná. Dnes se již daří provázanost nastavovat tak, že můžeme realizovat ekvivalenty základních logických operací jako NOT, AND nebo OR.

Tím máme vlastně kvantový počítač postavený. Zopakujme, jak funguje: proces začíná přípravou vlastních qubitů a jejich kvantovým provázáním. Potom laserem nastavíme qubity na vstupní hodnoty. Nastavováním hodnot jejich kvantové provázání nepoškodíme, nejedná se o měření. Celý kvantový systém je stále popsatelný vlnovou funkcí. Dalšími laserovými pulsy spustíme provedení kvantového programu a to je vlastně všechno. Příslušné qubity obsahují hledanou informaci.

Takhle zhruba si můžeme představit kvantový počítač. Ve skutečnosti nejsou qubity realizovány tímto způsobem, který je sice jednoduchý na představu, ale technicky by byl problematický. Laboratorní qubity skrývají svou informaci v kvantovém čísle nazývaném spin. Jeho hodnota se pak nastavuje délkou laserového impulsu. V principu je to však jedno. Jde jen o to mít kvantovou součástku, která umí být ve dvou stejně pravděpodobných stavech naráz a kterou můžeme kvantově provázat s jinými.

Kvantové počítače by patrně vznikaly mnohem pomaleji, nebýt Petera Shora, který před dvaadvaceti lety připadl na algoritmus rozkladu čísel na prvočísla pomocí kvantového počítače. Rozložit velké číslo na dělitele je matematická úloha, na jejíž náročnosti stojí celá filosofie bezpečnosti šifrování důležitých dat. Není divu, že se rychle našly finanční prostředky na výzkum, když se ukázalo, že úlohu, kterou klasické superpočítače nejsou s to zvládnout do doby srovnatelné se stářím vesmíru, může Shorův algoritmus vyřešit na počkání.

Rozložit číslo X na prvočíselné dělitele je úloha, na jejíž řešení připadne asi každý. Stačí poctivě projít všechna čísla od jedničky až po X, zkoušet dělitelnost a pokud operace proběhla beze zbytku, našli jsme dělitele. Dokonce není třeba procházet všechna čísla až do X, stačí jen do hodnoty jeho odmocniny. Přesto je rozklad několika set ciferného čísla nad naše možnosti.

Existuje i jiný způsob. Princip není zcela průhledný, postup má navíc nějaké podmínky a větvení, ukážeme si ho proto na speciálním příkladu, nalezení dělitelů čísla 15.

Nejprve si vybereme libovolné číslo menší než 15, třeba 7, a vypíšeme si pár hodnot číselné řady, která vznikne z předpisu: (7^k)mod 15. Jakkoli tento zápis vypadá magicky, není na něm nic obtížného. 7^k znamená k-tá mocnina čísla 7, tedy: 1, 7, 49, 343, 2401, 16807, ... a operace mod 15 znamená zbytek po dělení číslem 15. Např. 17 mod 15 je 2 (17/15 = 1x15 + 2)

Řada pak vypadá následovně: 1, 7, 4, 13, 1, 7, 4, ... Vidíme, že řada se po čtvrtém členu začíná opakovat. Délka periody (čtyři členy) je to, co nás na řadě zajímá. Vydělíme čtyři dvěma, to je dva. Na toto číslo umocníme 7, tedy 7^2, získáme 49 a zapamatujeme si dvě sousední hodnoty, tedy 48 a 50. Zjistíme zbytek po dělení číslem 15, a tím získáme hledané dělitele, čísla 3 a 5.

Krkolomné a neuvěřitelné? Určitě, přesto se tímto způsobem dobereme výsledku rychleji, než postupným procházením. Bohužel stále ne tak rychle, abychom to stihli v rozumném čase. Největší práci nám dá zjistit onu opakující se řadu. A to je právě ta část, kterou můžeme realizovat kvantovým počítačem.

Pro kvantový počítač je to hračka. Vložíme číslo 7, necháme umocnit na hodnotu, která je v qubitovém registru a vydělíme číslem 15, abychom dostali zbytek po dělení. To jsou jen dvě matematické operace, ale získáme tím celou řadu, protože v registru jsou superponována všechna celá čísla. Smutnou skutečností je, že my se tahle čísla nikdy nedozvíme, právě proto, že jsou rozplizlá v oblaku neurčitosti.

Řekli jsme si, že přečtením informace kolabuje vlnová funkce a hodnoty se materializují v jedné náhodné kombinaci. Dejme tomu, že to bude hodnota 13. Z toho o řadě asi nic moc nezjistíme. Zapomněli jsme však na jednu skutečnost. V našem kvantovém počítači je výstupní registr provázaný se vstupním (zvláštním rysem uzavřeného kvantového systému je, že výpočet musí fungovat obousměrně). Původní hodnota vstupního registru byla všechna celá čísla (exponenty, na které bylo umocňováno číslo 7). Po kolapsu výstupního registru zkolaboval i vstupní, ale jen částečně. Nastavil se na superpozici všech indexů, které porodily číslo 13. Tedy 3 (7^3 mod 15), 7 (7^7 mod 15), 11 (7^11 mod 15), 15 (7^15 mod 15),...

Tato řada je jednoduchá aritmetická posloupnost. Rozdíl mezi sousedními čísly je vždy 4, což je perioda číselné řady 1, 7, 4, 13, 1, 4, 7... Ve skutečnosti nám toto číslo stačí (viz popis algoritmu - následuje vydělení dvěma, umocnění sedmi na toto číslo, výběr sousedů...).

Vstupní registr je stále superponován, pro získání hodnoty periody tedy musíme znovu spustit kvantový výpočet. To je ale to poslední, co po kvantovém počítači chceme, zbytek dopočítá bez problémů klasický počítač.

Shorův algoritmus není to jediné, co kvantový počítač nabízí řešit. Výčet možností však není velký. Za zmínku stojí Groverův algoritmus pro vyhledávání v netříděném seznamu a Hadamardova transformace pro Fourierovu transformaci v n-rozměrném prostoru.

A jak jsme na tom s realizací, dočkáme se někdy kvantových počítačů? Kanadská firma D-Wave nabízí kvantový počítač pracující s 2048 qubity. Qubity jsou založeny na supravodivém Josephsonově jevu (procesor obsahuje 128 tisíc Josephsonových tunelových přechodů), což u odborníků vzbuzuje pochyby, zda se jedná o plnokrevný kvantový počítač, nebo jen kvantový simulátor.

Máme se obávat o zašifrovaná data? Dnes ještě ne. Počítač firmy D-Wave je malý zázrak techniky, nicméně se nejedná o univerzální stroj. Úlohy jako Shorův algoritmus řešit neumí. Přesto větší firmy i organisace začínají přemýšlet o jiných algoritmech šifrování, na které není znám ani kvantový protialgoritmus. Možná jednou D-Wave nebo někdo jiný přijde se strojem schopným rozlomit kód a pak bude možné rozšifrovat záznamy i zpětně. 
video:

Co vše může zahrnovat kvantová superpozice? Animace.