Kvantové počítání

 

Kvantové algoritmy nabízejí úžasnou rychlost výpočtu, ale jejich uvedení do praxe nebude snadné

 

Pavel Cejnar

 

Výpočetní úlohy, jejichž řešení svěřujeme počítačům, můžeme rozdělit na jednoduché a složité. K těm jednoduchým náleží všechny úkony standardní aritmetiky, jako je sčítání, násobení apod., k těm složitým naopak problémy typu šachové hry nebo faktorizace čísel. Složité úlohy vyžadují ohromné množství elementárních binárních operací - přesněji:  množství, které roste exponenciálně s velikostí souboru vstupních dat -, což v praxi  znamená dlouhé čekání na výsledek. V některých případech opravdu velmi dlouhé – např. faktorizaci čísla o řádově stovkách cifer by současný PC podle dosud známých algoritmů prováděl několik miliard let! O tom, že postupné zvyšování rychlosti stávajícího typu počítačů není tou nejlepší strategií k řešení složitých úloh, se nás snaží přesvědčit odborníci zabývající se zdánlivě nepraktickou vědní disciplínou – kvantovou fyzikou. Mladý obor slibující kvalitativní změnu řešení výpočetně složitých úloh se nazývá kvantové počítání.

 

S ideou kvantového počítání přišel na začátku osmdesátých let jako jeden z prvních Richard Feynman. Tehdejší úvaha tohoto nositele Nobelovy ceny za fyziku, tvůrce kvantové elektrodynamiky, byla až zázračně jednoduchá: jestliže časová náročnost numerické simulace vývoje nějakého kvantového systému roste exponenciálně rychle s počtem stupňů volnosti tohoto systému (např. počtem vzájemně interagujících částic), nemohla by naopak spontánní dynamika vhodně sestavených kvantových soustav realizovat a podstatně urychlit určité numerické výpočty? Ano, mohla!

 

Dlužno dodat, že Feynmanovu poznání předcházel několikaletý rozvoj oboru, který se zabýval fyzikou elementárních výpočetních procesů. Bylo zjištěno, že každá elementární operace typu logického AND nebo XOR provedená nevratným způsobem nevyhnutelně produkuje určité množství entropie, tedy také tepla. To se samozřejmě musí odvádět, což brání zmenšování  procesorů a zvyšování jejich rychlosti. Kdyby se však počítání svěřilo vratným fyzikálním dějům, např. elementárním procesům na úrovni atomů, mohl by tento problém odpadnout. Děje v mikrosvětě popisuje kvantová fyzika, odtud tedy označení „kvantové počítače.“

 

Principiálním důvodem, proč kvantové počítání může být tak odlišné od počítání klasického (tj. od výpočtů prováděných na počítačích, jež pracují podle zákonů klasické fyziky), jsou dvě nezvyklé vlastnosti kvantového světa. Podle první z nich se kvantové částice dokáží vyskytovat ve zvláštních stavech, ve kterých jakoby vykazují dvě či více klasických vlastností současně, např. nacházet se zároveň „tady“ i „tam“ (dokud ovšem neprovedeme měření!). Elementární kvantové bity tedy nejsou jen nuly a jedničky, ale jakési kombinace, tzv. superpozice těchto stavů. Druhou kvantovou vlastností stojící za vysokou efektivitou kvantového počítání je možnost vzájemné provázanosti (anglicky entanglement, čili doslova propletenost), matematické neoddělitelnosti stavů dvou různých fyzikálních objektů, např. dvou elementů kvantového počítače. Obě tyto vlastnosti jsou známy již od prvních dnů kvantové mechaniky, a byly také předmětem mnoha filozofických diskusí o zásadní odlišnosti klasického a kvantového světa. Dnes, kdy úžas nad podivností kvantových zákonů máme už pomalu za sebou, se začínáme více věnovat také jejich praktické využitelnosti.

 

Protože v kvantovém světě nelze uplatnit běžnou zkušenost, jsme zde plně odkázáni na abstraktní jazyk matematiky. Víme, že element nesoucí jeden bit „klasické“ informace musí mít dva odlišené fyzikální stavy, totiž stavy odpovídající logické nule a logické jedničce. Tyto stavy označíme jako ψ0 a ψ1. Kvantový bit (Q-bit) se však podle principu superpozice může nacházet také ve výše zmíněných stavech „mezi nulou a jedničkou,“ které se dají vyjádřit  jako ψ=aψ0+bψ1, kde a a b jsou libovolné číselné koeficienty (amplitudy) udávající „míru mísení“ obou zúčastněných stavů (přesněji, jde o komplexní čísla, splňující podmínku |a|2+|b|2=1). Možným klasickým logickým stavům dvojice bitů – tj. kombinacím „nula-nula,“ „jedna-jedna,“ „nula-jedna“ a „jedna-nula“ - odpovídají fyzikální stavy ψ0ψ0´, ψ1ψ1´, ψ0ψ1´ a ψ1ψ0´ (kde apostrof odlišuje stavy druhého bitu od stavů prvního). Dvojice Q-bitů se však může nacházet také v libovolné superpozici Y těchto čtyř stavů. Obdobně bychom již snadno zkonstruovali možné kvantové stavy i pro každou větší soustavu Q-bitů.

 

Možnost vytvářet kvantové stavy namíchané ze všech „nula-jedničkových“ kombinací dané soustavy Q-bitů je jedním z klíčů k porozumění kvantovému počítání. Chápeme-li čtyři logické stavy dvojice Q-bitů jako binární zápis čísel nula až tři, tj. 00=0, 01=1, 10=2 a 11=3, představuje kvantový stav Y superpozici všech těchto číselných hodnot. Připravit na vstupu počítače takový stav znamená tedy provádět výpočet se všemi hodnotami najednou! Této podivuhodné vlastnosti kvantového počítání se říká kvantový paralelismus.

 

Druhým klíčem ke kvantovému počítání je již zmíněná existence propletených stavů soustav Q-bitů. U klasických počítačů můžeme tvrdit, že každý jednotlivý bit se za všech okolností nachází ve svém vlastním stavu (klasicém stavu nula nebo jedna). Podobné tvrzení ale nelze vyslovit pro počítače kvantové. Např. celkový stav superpozice Y dvojice Q-bitů se obecně nedá rozepsat jako Y= ψψ´, kde by ψ a ψ´ představovaly libovolné stavy jednotlivých Q-bitů (toto není možné ani se započtení všech sperpozic ψ=aψ0+bψ1 a ψ´= a´ψ0´+b´ψ1´). Znamená to, že pro kvantový systém v obecném případě nelze oddělit dílčí stavy jeho součástí - opět vlastnost z hlediska klasické zkušenosti zcela nepochopitelná! Právě díky ní se však všechny paralelně (podle principu superpozice) uskutečňované větve kvantového výpočtu dají kdykoliv v průběhu výpočtu přiřadit jednotlivým vstupním hodnotám.

 

Kvantový počítač jako takový je soustava určitého počtu Q-bitů, tedy elementárních kvantových soustav (např. atomů, elektronů, fotonů apod.), které se zvolenou posloupností fyzikálních operací dostávají do superponovaných a propletených kvantových stavů. Právě posloupnost operací, navržená se zřetelem ke sledovanému cíli, je hlavní součástí kvantového algoritmu. Celý tento fyzikální děj chápeme jako výpočet, na jehož konci stav počítače obsahuje informaci o řešení zadaného problému. Bylo ukázáno, že všechny kvantové algoritmy lze - podobně jako algoritmy klasické – rozložit na určité elementární operace. Ty ovlivňující stav vždy jen jednoho nebo dvou Q-bitů (viz tabulky 1 a 2) a definují jakýsi základní programovací jazyk, umožňující realizaci libovolného výpočtu nezávisle na tom, jakou konkrétní fyzikální podobu má daný počítač.

 

 

vstup

Výstup

ψ0

(ψ0+ψ1)/Ö2

ψ1

(ψ0-ψ1)/Ö2

 

Tabulka 1: Hademardova transformace - příklad elementární jednobitové kvantové operace. Vstupní logické stavy 0 a 1 jsou převáděny na příslušné výstupní superponované stavy (superpozice vstupních stavů ψ=aψ0+bψ1  by dala odpovídající superpozici příslušných výstupních stavů). Provedení Hademardovy transformace na soustavě Q-bitů, všech ve vstupním stavu 0, vede k výstupu tvaru superpozice obsahující se stejnými amplitudami všechny možné kombinace nul a jedniček. Tak lze při kvantovém výpočtu dosáhnout rovnoměrného a paralelního zpracování všech číselných hodnot. 

 

vstup

výstup

ψ0ψ0´

ψ0ψ0´

ψ0ψ1´

ψ1ψ1´

ψ1ψ0´

ψ1ψ0´

ψ1ψ1´

ψ0ψ1´

 

Tabulka 2: Elementární operace na dvou Q-bitech – kvantové XOR. Vstupní hodnota na druhém Q-bitu – 0 či 1 - rozhoduje o tom, zda se hodnota prvního Q-bitu při transformaci změní, či ne; samotná hodnota druhého Q-bitu zůstává při transformaci zachována. Výstupní hodnotu na prvním Q-bitu můžeme chápat jako klasické XOR obou vstupních hodnot. Tato operace může vytvořit kvantový propletený stav. Např. je-li vstupním stavem prvního Q-bitu logická 0 a současně na druhém Q-bitu vstupuje libovolná superpozice 0 a 1, na výstupu se již dílčí stavy obou Q-bitů z celkového stavu Y nedají oddělit.

 

Přečtení výsledku libovolného kvantového výpočtu se nemůže uskutečnit jinak, než formou měření. I to je součástí algoritmu. Jakékoliv měření však odhalí pouze nepatrnou část kvantové informace, zakódované ve stavu počítače, a navíc tento stav nevratným způsobem zničí. Např. měření provedené na jednom Q-bitu může vést jen k výsledkům „ano“ nebo „ne“ ohledně nějaké kvantové vlastnosti, tedy opět jen k jednomu bitu klasické informace - navzdory mnohosti všech možných kvantových superpozic, ve kterých se daný Q-bit mohl předtím nacházet. Toto jsou nevyhnutelné vlastnosti každé intervence vnějšího (makroskopického) pozorovatele do průběhu kvantových dějů. Výsledky kvantových měření se navíc nedají přesně předvídat – kvantová mechanika určuje pouze jejich pravděpodobnosti. Právě z tohoto důvodu je celý výpočet zpravidla třeba několikrát opakovat. Při každém běhu sice závěrečné měření dopadne nějak jinak (samozřejmě v souladu se stanovenými pravděpodobnostmi), ale hledaný výsledek lze získat z celkové statistiky většího počtu běhů. I tak ale kvantové algoritmy v některých případech výrazně předčí algoritmy klasické.

 

S dosud nejznámějším kvantovým algoritmem přišel v roce 1994 Peter Shor. Do té doby byly úvahy „kvantových informatiků“ přece jen poněkud vzdáleny praktickým problémům. Shorův článek zato způsobil doslova explozi zájmu o kvantové počítání i mimo skupinu fyziků. Jedná se totiž o slavnou faktorizační úlohu, která je základem dnes nejpoužívanějších metod šifrování: Je-li dáno číslo N, které je součinem dvou prvočísel P a Q, najdi P a Q. Na klasické úrovni je tato úloha řazena do třídy velmi náročných problémů - délka výpočtu pro všechny dostupné klasické algoritmy roste přibližně exponenciálně s počtem cifer čísla N (každý sice jistě umí víceméně rychle vynásobit např. čísla P=127 a Q=229, ale dostane-li naopak za úkol rozložit na prvočinitele zadané číslo N=29083, jejich součin, bude to asi trvat o dost déle…).  Shor ukázal, že zapojení zákonů kvantové mechaniky do procesu výpočtu by umožnilo řešení zcela zásadně urychlit. Navrhl proceduru, kdy sled určitých elementárních jedno a dvoubitových operací (tento sled, čítající jak Hademardovy transformace, tak kvantová XOR - viz tabulky-, obsahuje vstupní informaci o čísle N) vede ke kvantovému stavu soustavy Q-bitů, z něhož lze pomocí vhodného měření s vysokou pravděpodobností (tj. s relativně nízkým počtem nutných opakování výpočtu) vyčíst hodnoty P a Q. To vše (včetně opakování výpočtu) v časech, které rostou jen polynomiálně s počtem cifer faktorizovaného čísla N, tedy opravdu dramaticky kratších než pro známé klasické algoritmy faktorizace!

 

To je sice pěkné, říkáte si možná, ale jak to prakticky provést? To opravdu je - a asi ještě dlouho zůstane - hlavním kamenem úrazu kvantového počítání. Je samozřejmě docela dobře možné činnost kvantového počítače simulovat na počítači klasickém, ale tím se veškeré výpočetní výhody ztrácí. Skutečný kvantový počítač musí být opravdový kvantový objekt! Známých systémů potenciálně vhodných k uskutečnění kvantového počítání je sice hned několik, všechny praktické pokusy ale zatím narážejí na problémy způsobené naší ne příliš velkou „zručností“ v manipulaci se stavy kvantových částic. Např. v roce 1995 byla teoreticky popsána možnost kvantových výpočtů na soustavě nabitých atomů, které by v silně ochlazeném stavu byly pomocí intenzivního elektromagnetického pole drženy na vzdálenostech pouhých několika mikronů od sebe. Každý atom by reprezentoval jeden Q-bit. Působením laserových impulsů o vhodně nastavených parametrech by bylo možné libovolný z atomů selektivně excitovat a de-excitovat (čili měnit stavy Q-bitů), přičemž sekvence těchto impulsů by realizovala daný kvantový algoritmus. Laboratorní pokusy s takovými systémy jsou však stále v zárodečném stadiu.

 

Jednou z hlavních překážek kvantového počítání je nutnost udržet kvantový počítač po celou dobu výpočtu v naprosté izolaci od ze všech stran jej obklopujícího „oceánu“ okolního prostředí – jak od blízkých kvantových částic, tak od vnitřních stupňů volnosti počítače samotného (např. excitačních módů atomu, které nejsou využity k zápisu kvantové informace). Přitom velmi rychlé provazování stavů naprosté většiny kvantových systémů se stavy prostředí (ve smyslu výše zmíněné kvantové propletenosti) je známým jevem, kterému se dá jen stěží zabránit. Jeho důsledkem je nemožnost připsat nějaký samostatný kvantový stav systému, jenž po určitou dobu volně interagoval s okolím. „Kvantovost“ počítače by tak pravděpodobně zanikla ještě před tím, než bychom stihli provést první operaci daného algoritmu.

 

Naštěstí jsou již známy strategie, jak tomuto jevu, odborně nazývanému dekoherence, čelit. Jednu z nich opět poprvé popsal Peter Shor. Jedná se v podstatě o periodické provádění jistých transformací stavu počítače, které při dostatečné frekvenci opakování škody způsobené interakcí s prostředím opravují – alespoň na vysoké hladině pravděpodobnosti. Jiná technika potlačení dekoherence spočívá ve využití speciálních stavů mnohočásticových soustav, které se z jistých důvodů (souvisejících s principy symetrie) s prostředím „zaplétat“ prostě nemohou.

 

Velký rozruch vyvolala zpráva skupiny vedené Isaacem Chuangem z prosince 2001. Bylo oznámeno první experimentální provedení výpočtu podle Shorova faktorizačního algoritmu pomocí kvantového počítače na bázi nukleární magnetické rezonance (NMR). Na významu tohoto úspěchu nic nemění ani skutečnost, že výpočet byl realizován v tak jednoduchém případě, že o nějaké praktické použitelnosti se zatím nedá vůbec mluvit – „kvantový počítač“ čítající sedm Q-bitů v tomto případě dokázal za téměř půl minuty rozložit číslo 15 na součin 3×5. Počítání pomocí NMR využívá manipulace s jádry atomů ve velkých organických molekulách pomocí radiofrekvenčních pulsů magnetického pole. Jednotlivé Q-bity jsou v tomto případě reprezentovány jadernými spiny (vnitřní kvantové točivé momenty jader), které v některých případech mají jen dvě možné prostorové orientace („nahoru“ a „dolů“), plus samozřejmě všechny možné superpozice ψ=a­+b¯. Kvantovým počítačem je celá molekula, přičemž každý makroskopický vzorek sloučeniny obsahuje obrovské množství jeho replik. Tím sice odpadá nutnost opakování výpočtu, typická pro jiné druhy kvantových počítačů (výpočet běží na všech replikách, tedy dostatečně mnohokrát), naopak však vznikají značné potíže s uvedením počítače do specifického počátečního kvantového stavu.

 

Problémem všech dosavadních pokusů s kvantovým počítáním je jen velmi malý počet kvantových bitů, které jsme schopni do výpočtu zapojit. I pro počítače na bázi jaderné magnetické rezonance platí striktní omezení, daná velikostí použitelných molekul a fyzikálními limity měřitelnosti. Ty nedovolují překročit horní mez několika desítek provázaných Q-bitů.  Použití Shorova algoritmu k faktorizaci tak vysokých čísel, jaká se v současné době používají k šifrování zpráv, proto zůstává zcela za obzorem fyzikální představivosti. V nedávné době se však objevily nadějné signály, že i kvantové výpočty na podstatně menším počtu bitů mohou být prakticky užitečné. Několik teoretiků v oblasti fyziky chaosu přišlo s ideou, že kvantové počítače realistických rozměrů by mohly pomoci při simulaci chování některých systémů vykazujících tzv. kvantový chaos. Nutno poznamenat, že právě úlohy související s chaotickými systémy jsou těmi numericky nejobtížnějšími. Do jisté míry to můžeme chápat jako uzavření kruhu, na jehož počátku kdysi stál Richard Feynman – kvantové počítače možná nejvíce využijí právě ti, z jejichž dílny tato idea vzešla...

 

Webové odkazy:

 

 

Slovníček pojmů:

Faktorizace: Rozklad daného čísla na součin dvou prvočísel, např. 15=3×5 nebo 29083=127×229. (Samozřejmě ne všechna čísla takový rozklad připouštějí.)

Q-bit: Kvantový bit, element kvantového počítače. Od klasického se liší možností připravit na něm superpozice nuly a jedničky, tj. ψ=aψ0+bψ1, kde ψ0  a ψ1 odpovídají logickým stavům 0 a 1, zatímco a a b udávají „komplexní amplitudy“ jejich mísení.

Superpozice: Kvantový stav, kdy se popisovaný systém jakoby nachází v několika klasických stavech najednou, např. Q-bit zároveň ve stavech 0 a 1. Superpozice nemají obdobu ve světě naší zkušenosti, takže matematika je jediným jazykem jejich popisu.

Entanglement: Propletenost, či provázanost soustavy dvou či více kvantových objektů, kdy z celkového kvantového stavu soustavy není možné vydělit dílčí stavy jednotlivých objektů.

Kvantové měření: Interakce kvantového systému s makroskopickým měřicím přístrojem. Měření nevratným způsobem mění stav kvantového systému a jeho výsledek má statistický charakter.

Kvantový výpočet: Posloupnost elementárních kvantových transformací podle daného algoritmu, zakončená měřením. Protože výsledek jednoho měření nemůže obsáhnout celou kvantovou informaci nesenou počítačem, výpočet je většinou  potřeba vícekrát opakovat.

Kvantový paralelismus: Současné zpracování několika vstupních hodnot při kvantovém výpočtu s využitím superponovaných a propletených stavů dané soustavy Q-bitů.

Dekoherence: Ztráta čistoty kvantového stavu v důsledku interakce daného kvantového objektu s prostředím. Nepřítel číslo 1 všech druhů kvantového počítání.

Spin: Vnitřní moment hybnosti kvantových částic. Jeho průmět do libovolného směru může nabývat jen některých hodnot, např. hodnot +1/2 a –1/2 („spin nahoru“ a „dolů“).

NMR: Jaderná magnetická rezonance – metoda manipulace se spiny atomových jader. Technika dosud používaná především v medicíně a analytické chemii,  podle nejnovějších výsledků též nadějný kandidát na realizaci kvantového počítání.