Kvantové počítání

Kvantové algoritmy nabízejí úžasnou rychlost výpočtu, ale jejich praktická realizace nebude snadná Výpočetní úlo...


Kvantové algoritmy nabízejí úžasnou rychlost výpočtu, ale jejich praktická
realizace nebude snadná
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říslušné číslo roste často s
velikostí souboru vstupních dat exponenciálně. V praxi to znamená dlouhé čekání
na výsledek např. faktorizaci čísla o řádově stovkách cifer by současné PC
podle dosud známých algoritmů provádělo několik miliard let! 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 jako jeden z prvních na počátku 80. let
Richard Feynman. Úvaha tohoto nositele Nobelovy ceny za fyziku 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 (tedy například 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. Tyto
děje v mikrosvětě popisuje kvantová fyzika odtud tedy pochází i samotné
označení "kvantové počítače."

Propletené superpozice
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), tedy 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í 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 y0 a y1.
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
y=ay0+by1, 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 y0y0, y1y1, y0y1 a y1y0 (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ů.

Skutečně paralelně
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 (klasické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 = yy,
kde by y a y představovaly libovolné stavy jednotlivých Q-bitů (toto není
možné ani se započtení všech superpozic y = ay0+by1 a y= ay0+by1).
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.

Realizace výpočtu
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í stav vždy jen jednoho nebo dvou Q-bitů (viz tabulky) 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č.
Přečtení výsledku libovolného kvantového výpočtu se nemůže uskutečnit jinak než
formou měření. I tato procedura je přitom 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é.

Slavná faktorizace
S dosud nejznámějším kvantovým algoritmem přišel v roce 1994 Peter Shor z
Bellových laboratoří. Do té doby byly úvahy "kvantových informatiků" přece jen
poněkud vzdáleny praktickým problémům, Shorův článek však naopak způsobil
doslova explozi zájmu o kvantové počítání i mimo skupinu fyziků.
Shorův algoritmus se vztahuje ke známé faktorizační úloze, 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 číslo N=29 083, bude to asi trvat o
dost déle...).
Shor však 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!

Fyzikální realizace
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
impulzů 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 impulzů 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.

Šance do budoucna
Velký rozruch vyvolala zpráva skupiny vedené Isaacem Chuangem z prosince 2001.
Vědcům z IBM se podařilo první experimentální provedení výpočtu podle Shorova
faktorizačního algoritmu pomocí kvantového počítače. Systém pracoval na bázi
jaderné 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 x 5.
Počítání pomocí NMR využívá manipulace s jádry atomů ve velkých organických
molekulách pomocí radiofrekvenčních pulzů 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ů"), k čemuž se samozřejmě připočítávají všechny
možné superpozice y=a". 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 molekuly, proběhne tedy
dostatečněkrá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 v tuto chvíli 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 stál kdysi Richard Feynman kvantové
počítače nakonec možná dokáží nejlépe využít právě ti, z jejichž dílny tato
idea původně vzešla...

Jednobitová operace
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ů y=ay0+by1 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.

Kvantové XOR
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.

Slovníček kvantového počítání
Faktorizace: Rozklad daného čísla na součin dvou prvočísel (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 bitu se liší
možností připravit na něm superpozice nuly a jedničky, tj. y=ay0+by1, kde y0 a
y1 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 představuje jediný
jazyk pro jejich popis.
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í.

Výklad a přehled novinek na webu
http://www.informatics.bangor.ac.uk/~schmuel/comp/comp.html výklad základních
pojmů kvantového počítání lze najít na výukových stránkách prof. S. Braunsteina
http://xxx.lanl.gov/archive/quant-ph zde se průběžně objevují preprinty článků
přinášejících nové výsledky v oblasti kvantové informatiky









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