Kvantovým počítačům patří budoucnost

Tento článek vyšel v časopise Computer 4/01 dne 8. března 2001

Robert Batůšek: Kvantové počítače začínají získávat pozornost médií. Jednou se tak o nich dočtete to, jindy zase ono. V jednom se ale všechny články shodují – tyto počítače zásadním způsobem změní některé naše činnosti. Jak a proč?

Výkon počítačů se stále zvyšuje. Podle tzv. Moorova zákona se zhruba každých 18 měsíců zdvojnásobí počet tranzistorů na jednom čipu. I když mu kritici několikrát předpovídali konec platnosti, zdá se, že bude platit i v nejbližších letech. Jenže: zdvojnásobování počtu tranzistorů zároveň znamená nutnost jejich zmenšování. A tak, pokud tempo vydrží, bychom kolem roku 2020 měli mít čipy ze součástí velikosti atomu. To však asi nebude možné, protože v těchto rozměrech už nemusí platit některé zákony, na které jsme zvyklí z klasické fyziky. To je jeden z důvodů, proč se vědci dnes intenzivně zabývají tzv. kvantovými počítači.

Není to ovšem důvod jediný. Pro praxi je důležité, že tento pohled na počítání může vést ke konstrukci velmi rychlých počítačů. Zejména možnost souběžného zpracování (paralelismus), které je u kvantových počítačů extrémní, z nich dělá nástroje, jež jsou v některých aplikacích řádově výkonnější než klasické počítače.

Kvantový počítač současnosti si ovšem nesmíme představovat jako klasický počítač. Většina dosud známých výsledků existuje pouze v teoretické rovině. V podstatě říkají, že pokud se někdy podaří kvantový počítač sestrojit, bude mít určité vlastnosti a bude možné s ním provádět určité výpočty.

Naštěstí se už objevují také výsledky praktické. I ony však mají ke klasickému počítači daleko. Jednak se jejich kapacita pohybuje v jednotkách tzv. kvantových bitů, jednak mají podobu např. iontové pasti, nebo nádoby s tekutinou plné speciálních molekul. Zkrátka, Quake na tom prostě „nezapaříte“.

Sestrojení kvantového počítače tedy ještě neznamená zánik klasického počítače. Naopak: oba druhy počítačů budou delší dobu existovat vedle sebe a doplňovat se. Velmi důležitým krokem každého kvantového výpočtu je totiž měření. Jelikož svět člověka není kvantový, ale „klasický“, je třeba výsledek každého kvantového výpočtu nějakým způsobem prezentovat. V tom jsou zatím klasické počítače nepřekonatelné. Počítač budoucnosti tedy může vypadat jako klasický počítač, který bude sloužit jako terminál. Ten bude vykonávat běžné operace, jako třeba práce s textovým editorem, ovšem bude nějakým způsobem spojen s kvantovým počítačem určeným pro vykonávání náročnějších úloh.

Jednotkou klasické informace je 1 bit, který může nabývat hodnot 0 nebo 1. Jednotkou kvantové informace je jeden kvantový bit (qubit). Na rozdíl od toho klasického může nabývat nekonečně mnoha hodnot. Stejně jako v běžném případě nezáleží na tom, jestli logickou hodnotu 0 nebo 1 vyjadřujeme pomocí dřevěného počitadla nebo elektronického obvodu, tak i hodnota kvantového bitu může být vyjádřena různým způsobem. Obvykle se používají vhodné rysy elementárních částic, jako například energetické úrovně atomu nebo polarizace fotonu.

Normální situace. Přijdete do práce a přihlásíte se do sítě. Napíšete jméno a heslo a za chvíli se objeví vaše virtuální pracovní plocha. Jenomže mezitím se stala strašná spousta věcí. Jednou z nich je i to, že se vaše jméno a heslo poslalo po síťovém kabelu příslušnému serveru a ten ověřil, zda odpovídají údajům, které má o vás uloženy. Jenomže co když někdo „poslouchal“ zrovna ve chvíli, kdy heslo putovalo mezi vaší stanicí a serverem, a přečetl si ho? To by znamenalo, že od této chvíle se může kdykoliv přihlásit do sítě vydávaje se za vás.

Ne, nebojte se, nemusíte hned volat správce sítě, nikdo si vaše heslo nepřečetl, po síti se totiž posílá zašifrované. (I když, po pravdě řečeno, programy jako například telnet posílají klidně heslo po síti v nezašifrované podobě. Takže pozor na to!) Nicméně ani zašifrování citlivých informací – jako například heslo – neznamená, že se je nikomu nepodaří přečíst. Pokud vyvine dostatečné úsilí, může se mu podařit šifru rozluštit.

Dnešní šifry (teď samozřejmě mluvíme o klasických počítačích), které se používají v síťové komunikaci, informačních systémech nebo třeba v bankovnictví, jsou založeny na existenci speciálních matematických funkcí. Tyto funkce je velmi snadné vypočítat jedním směrem, opačně je to však značně obtížné. Proto se pro ně používá pojem jednocestné funkce.

Například je jednoduché vypočítat číslo, které je součinem dvou prvočísel. Známe-li ovšem pouze výsledek součinu, je dosti těžké zjistit, z jakých prvočísel bylo vytvořeno. Pokud tedy zvolíme dvě dostatečně velká a vhodná prvočísla, bude případnému luštiteli trvat rozluštění šifry za použití současných počítačů třeba několik milionů let. Výkon počítačů se ale neustále zvyšuje, proto je v současných šifrovacích systémech nutno pracovat se stále většími čísly. Navíc zatím není matematicky dokázáno, zda neexistuje nějaký efektivní algoritmus pro rozklad daného čísla na prvočísla.

V kvantových počítačích už je ovšem jasno. Efektivní algoritmus pro rozklad čísla na prvočísla existuje! To tedy znamená, že po sestrojení dostatečně výkonného kvantového počítače bude možné s jeho pomocí hravě rozluštit všechny klasické šifry. Následky pro oblast elektronických informačních systémů je lepší nedomýšlet. Proto je potřeba už teď vymyslet nové formy komunikace, které by odolaly i útoku vedenému pomocí kvantových počítačů. Využívá se k tomu vlastnosti kvantové informace, kterou jsem již zmínil: žádnou kvantovou informaci nelze zkopírovat ani přečíst bez toho, že by se nepoškodila.

Klasické kryptografii je nutno přiznat, že vyvinula jednu metodu, která je absolutně bezpečná, tzv. Vernamovu šifru. Je velmi jednoduchá: náhodně vygenerujeme tajný šifrovací klíč a ten bezpečným kanálem (např. osobní setkání) doručíme ke svému partnerovi. Pomocí tohoto klíče potom můžeme kdykoli zašifrovat zprávu, přenést ji a náš partner si ji pomocí stejného klíče rozšifruje. Protože klíč byl naprosto náhodný, nikdo nemůže ze zašifrované zprávy nic usoudit. Má to ale několik háčků. Klíč musí být stejně dlouhý jako vlastní zpráva a můžeme jej použít pouze jednou. Navíc ani vygenerování naprosto náhodné posloupnosti bitů není pro klasické počítače jednoduché, i když řešitelné to je. Vzhledem k tomu, že stejně musíme mít k dispozici bezpečný kanál, po kterém je nutno přenášet klíče, je jednodušší takovým kanálem přenášet rovnou zprávy. To je důvod, proč se v klasické kryptografii tato metoda příliš neujala.

Kvantové počítače nabízejí řešení. Místo toho, abychom klíč posílali z jednoho místa na druhé, vygenerujeme na obou místech současně stejný náhodný klíč. Metod řešení existuje víc. My si popíšeme jednu z nich (v zájmu zjednodušení se dopustíme jistých nepřesností).

Řekněme, že spolu chtějí komunikovat dva lidé, Alice a Bob. Alice pošle Bobovi náhodnou posloupnost kvantových bitů, přičemž u každého z nich zná správný způsob měření. Bob tuto posloupnost změří. U každého bitu náhodně volí mezi dvěma různými typy měření, z nichž jedno je správné (on ovšem zatím neví, které). Potom pošle Alici seznam, ve kterém uvede, kdy který typ měření použil. Alice mu pošle zpět pořadí těch kvantových bitů, kdy Bob měřil správně a tedy spolehlivě zjistil, které bity Alice posílala. Bob potom pošle opět Alici pořadí těch bitů, ve kterých se jejich náhodné posloupnosti shodují.

Všimněte si, že ani jednou nejde po komunikačním kanálu posloupnost nul a jedniček. Nejdříve se posílá posloupnost kvantových bitů, které mohou být jak 0, tak 1 v závislosti na typu měření. Pak se posílá seznam typů měření a potom jenom pořadí kvantových bitů, které mohou být použity jako náhodný tajný klíč.

Pokud by se případný záškodník pokusil přenos narušit nebo komunikaci přečíst, změní se původní posloupnost kvantových bitů. K tomu, aby se podobná snaha odhalila, Bob a Alice obvykle „obětují“ několik sdílených bitů k tomu, aby si zkontrolovali, že skutečně sdílejí stejnou informaci. Současný výzkum v oblasti kvantové kryptografie směřuje například k tomu, aby obětovaných bitů bylo co nejméně a aby se přitom podařilo odlišit útok narušitele od běžného šumu na komunikačním kanálu.

Výzkumu v oblasti kvantových počítačů se v současné době ve světě věnuje velká pozornost. „Divácky nejatraktivnější“ je přirozeně sestavení funkčního kvantového počítače, ale jak jsme viděli na příkladu šifrování, i teoretičtěji zaměřený výzkum může nést praktické ovoce.

V České republice se výzkumu v oblasti kvantové kryptografie věnují na katedře optiky Přírodovědecké fakulty univerzity Palackého v Olomouci a ve společné laboratoři optiky UP a FzÚ AV ČR v Olomouci, kde se v nedávné době zdařil experiment s bezpečnou kvantovou komunikací popsaný výše. Kvantové bity byly kódovány do fázového posunu fotonů. V Brně na fakultě informatiky Masarykovy university se kvantovými počítači zabývá náš přední a světově uznávaný odborník na teoretickou informatiku prof. J. Gruska, který v roce 1999 vydal knihu Quantum Computing.

Na prakticky použitelné kvantové počítače si tedy ještě pár let počkáme. Již dnes je však možné hledat oblasti jejich použití a pokusit se zkoumat meze této technologie. Výzkum v oblasti kvantové informatiky zahrnuje nepřeberné množství témat, kterými se dnešní počítačový nadšenec může zabývat, a slibuje možnosti zatím spíše jen tušené. Kvantové počítače jsou počítači budoucnosti. Nabízí se vám velká šance. Tak na co ještě čekáte?

Kopírování informace. Zatímco klasickou informaci je možné libovolně beze změny kopírovat, u kvantové informace to možné není. Každý pokus o kopírování vede ke změně původní informace. Toho se využívá např. v kvantové kryptografii (kryptografie je věda o šifrování) při zabezpečení přenosu citlivých informací – přenos nemůže nikdo odposlouchávat tak, aby si toho jeho účastníci nevšimli.

Entanglement. Pojem, který zatím nemá český ekvivalent. Snad by se dal přeložit jako „provázání“. Klasické bity jsou vzájemně nezávislé. Pokud změníme hodnotu jednoho bitu, nemá to vliv na hodnotu jiného. U kvantových bitů to nemusí nutně platit. Pokud jsou dva kvantové bity provázané (entanglované), změna hodnoty jednoho bitu vyvolá změnu hodnoty bitu druhého. Provázání je možné i mezi větším počtem kvantových bitů než mezi dvěma, což způsobuje značné problémy při konstrukci kvantových počítačů.

Teleportace. Tohoto jevu lze velmi dobře využít. Změna hodnoty provázaného kvantového bitu totiž probíhá okamžitě, a co je důležité – nezávisí na vzdálenosti mezi elementárními částicemi nesoucími informaci o hodnotě příslušných kvantových bitů. Pokud tedy vezmeme dvě provázané částice a umístíme je na dvě různé planety v různých slunečních soustavách (jak prosté), změna stavu jedné částice se okamžitě projeví změnou stavu částice druhé. Dokonce nemusíme ani znát polohu provázané částice. K úspěšnému provedení teleportace je ale nutné přenést alespoň dva klasické bity. Pokusy s kvantovou teleportací na vzdálenost několika kilometrů už byly provedeny.

Paralelismus. Klasické procesory jsou schopny zpracovávat v jednom okamžiku pouze jeden program. (To, že například ve Windows se zdá, že běží několik programů současně, je iluze vyvolaná velmi rychlým přepínáním mezi jednotlivými úlohami.) Oproti tomu kvantový procesor může provést v jednom okamžiku operací mnoho.

Výpočetní výkon. Díky paralelismu mohou kvantové počítače vykonávat některé úlohy mnohem efektivněji než klasické počítače. Jako příklad může sloužit vyhledávání prvku v nesetříděné databázi. Můžeme si představit třeba vyhledání jména v telefonním seznamu podle telefonního čísla. Zatímco na klasickém počítači musíme probírat jednu položku po druhé a porovnávat ji s námi hledaným prvkem, na kvantovém počítači prostě vypočteme všechna porovnání najednou a vybereme si z nich to, které bylo úspěšné.

Samozřejmě to není tak úplně jednoduché. Také na kvantovém počítači je třeba pro vyhledání prvku v databázi velikosti n provést přibližně odmocninu z n operací. I tak to ovšem znamená, že správného majitele telefonního čísla v seznamu obsahujícím 10 000 účastníků najdeme už po 100 krocích. To není špatné, co říkáte?

Vernamova šifra

m	i	l	u	j	i	t	ě	Zpráva
4	0	11	25	3	7	33	19	Náhodný tajný klíč
p	i	t	o	m	o	s	t	Zašifrovaná zpráva
4	0	11	25	3	7	33	19	Náhodný tajný klíč (odečítáme)
m	i	l	u	j	i	t	ě	Zpráva

Generování náhodného tajného čísla*

1	2	3	4	5	6	7	8	9	Pořadí
1	0	0	0	1	1	0	1	1	Náhodná sekvence Alice
A	B	A	A	B	A	B	B	B	Alicin typ měření
0	1	1	0	1	0	0	1	1	Náhodná sekvence Boba
A	A	B	A	B	B	A	A	B	Bobův typ měření
X	x	x	0	1	x	x	x	1	Shodné bity měřené stejně

* Bity číslo 4, 5 a 9 tvoří tajný klíč.

Právě vyšlo
nové číslo
časopisu Computer.