Kvantové počítače: Hrozba pro dnešní úroveň šifrování?

Podle teorie kvantové mechaniky se kvantový objekt může nacházet, a také se nachází v mnoha různých pozicích zároveň. Je to fantastická věc, vždyť koho by aspoň občas nenapadlo, kolik věcí by stihl, kdyby mohl být na více místech současně, aniž by se kvůli tomu musel rozkrájet. Něco podobného napadlo i kvantové fyziky: jak rychle by počítače dospěly k výsledkům, pokud by zvládly výpočty provádět paralelně a ne jako dosud informace zpracovávat postupně jednu po druhé. Nezůstalo však tentokrát jen u myšlenky, oxfordský fyzik David Deutsch následně v r. 1985 navrhl teoretický model kvantového turingova stroje. Převést teorii do praxe však nebylo vůbec snadné, přestože na tomto úkolu pracuje mnoho špičkových vědeckých týmů zejména ve Spojených státech. Vznikla sice řada experimentálních prototypů kvantového počítače, ale teprve v r. 2011 byl společností D-Wave Systems veřejnosti představen první komerční stroj tohoto druhu. Stále to ovšem nebyl plnohodnotný kvantový počítač.

Kvantová logika

Základní princip kvantových výpočtů spočívá v tom, že kvantové vlastnosti částic jsou použity pro reprezentaci a strukturu dat, datovou jednotkou je qubit [kju:bit], a kvantové jevy pak slouží k provádění operací s těmito daty.

Často se uvádí, že hodnotou qubitu je nějaká pravděpodobnost, což je sice pravda, ale je chybou to takto zjednodušovat. Qubit sám o sobě je jenom ekvivalentem bitu, a může tedy nabývat pouze binárních hodnot. Ovšem při výpočtu je jeho hodnota superpozicí obou stavů a jako taková se dá vyjádřit pouze určitou pravděpodobností. Pro ilustraci: za předpokladu, že 30 % qubitů má hodnotu 0 a 70 % qubitů hodnotu 1, tak každý jeden qubit má s pravděpodobností 70 % hodnotu 1. Uvažovat o jednom qubitu však nemá smysl, protože kvantový počítač pracuje naráz s celým kvantem qubitů. Pro efektivitu výpočtů je důležité, aby toto kvantum bylo co největší. Zatímco např. osm qubitů může reprezentovat všechna celá čísla od 0 do 2⁸ (=256), s vyšším počtem qubitů se tato množina exponenciálně (2ⁿ) rozrůstá, takže teoreticky pokaždé odpovídá všem možným kombinacím logických hodnot qubitů. Tím se extrémně zvyšuje výpočetní výkon kvantového počítače, už jen s tím 8qubitovým registrem lze paralelně provést v jednom momentu 28 výpočtů!

Jelikož v kvantové logice existuje kromě stavů 0 a 1 ještě superpoziční stav, rozšiřuje se přirozeně i aparát logických funkcí neboli hradel. Například vedle klasického NOT, které převrací hodnotu (qu)bitu z 0 na 1 a opačně, je potřeba mít ještě hradlo, které invertuje hodnotu qubitu z určitého stavu do superpozice a naopak. Složitějších funkcí se pak dosáhne kombinací hradel. Zvláštností kvantových hradel je to, že jsou ze své podstaty reverzibilní – tedy, že z výstupu lze zpětně dostat vstupy.

I když hradla představují abstraktní matematické operace, musí fungovat na fyzikálních principech – v tomto ohledu stále nezvítězil duch nad hmotou. Práce s kvantovými systémy se děje na subatomární úrovni v podmínkách, které se vymykají běžnému chápání fyzikálních zákonitostí. Vše ještě komplikuje jev zvaný dekoherence, který spočívá v rušivém vlivu okolního prostředí a způsobuje nežádoucí interakce a následně kolaps celého systému. Kvůli těmto technickým obtížím je konstrukce kvantového počítače nevýslovně obtížná, a proto všechna dosud realizovaná řešení byla projektována jako jednoúčelové kvantové logické obvody.

Překonání limitů současných počítačů

Architektura současných počítačových procesorů umožňuje řešit většinu úloh v přijatelném čase, a to i s velkými čísly. Například libovolnou dvojici čísel lze násobit za čas, jenž roste s druhou mocninou počtu číslic v číslech. (Tato doba je měřena počtem základních kroků, které algoritmus potřebuje k dosažení výsledku.) Ovšem opačný postup, tedy rozklad čísla na součin prvočísel neboli faktorizace, je zrovna příkladem, kdy ani ty nejpokročilejší známé metody nezabrání tomu, aby množství času pro výpočet nerostlo exponenciálně s množstvím číslic. Paradoxně má tato indispozice účelné využití: Když se v druhé polovině 20. století začaly počítače využívat i v komerční sféře, komplikoval jejich nasazení pro šifrování citlivé komunikace (bankovních převodů, obchodních jednání apod.) problém bezpečné distribuce klíčů. Ten byl vyřešen také díky vynálezu asymetrických šifer (mají veřejný klíč na zašifrování a soukromý na dešifrování), jejichž princip spočívá právě ve faktorizaci.

Algoritmus představuje sled logických operací, takže to, co je a není vypočítatelné, závisí na tom, které logické operace dokážeme při současné technické úrovni transformovat do fyzikálních procesů. Současné počítače mají potíže zejména s tzv. polynomickými úlohami, jako je úkol obchodního cestujícího najít nejkratší trasu mezi všemi městy, nebo naskládat do svého kufříku krabičky různých rozměrů tak, aby se mu tam všechny vešly. Přestože pro tyto úlohy existují algoritmy o něco lepší než zkoušení každé možné varianty, není znám žádný algoritmus, který by byl výrazně lepší. Kvantový počítač však má širší výpočetní možnosti, umožňuje do algoritmů zařadit v minulosti nemyslitelné operace, a tím řešení takových úloh dramaticky urychlit. Pár příkladů:

• Shorův algoritmus – v roce 1994 sestavil Peter Shor kvantový algoritmus, který umožňuje faktorizovat n-místné číslo v čase, který roste jen s n²
• Groverův algoritmus – v roce 1996 sestavil Lov Grover kvantový algoritmus využitelný k rychlému prohledávání netříděných databází (s přibývajícím počtem vstupních parametrů nebo počtem položek roste časová náročnost zanedbatelně)

Nástup kvantové kryptografie

Bude výpočetní technika založená na kvantové mechanice znamenat novou vědeckotechnickou revoluci? To by asi bylo příliš silné a hlavně předčasné tvrzení, nicméně v oblasti kryptografie se dají očekávat zcela zásadní změny. Už v roce 2001 se podařilo provést první experimentální výpočet pomocí Shorova algoritmu. 7qubitový kvantový počítač na bázi nukleární magnetické rezonance úspěšně rozložil číslo 15 na součin 3 × 5. Přitom bezpečnost nejpoužívanějších asymetrických šifer, jako algoritmus RSA, je podmíněna právě tím, jak náročnou úlohu pro počítače představuje faktorizace velkých čísel.

Obecně je slabina asymetrických šifer v tom, že mezi veřejným a soukromým klíčem existuje matematická vazba a kvantové počítače jsou schopné tuto vazbu rozkrýt. Pokrok ve vývoji kvantových technologií však nemusí nutně vrátit kryptografii o půl století zpátky. Zároveň totiž nabízí nové způsoby ochrany neveřejné komunikace – ty zajišťují vygenerování dokonale náhodného klíče a jeho bezpečnou distribuci bez použití šifer. Místo šifer stačí využít zákony kvantové mechaniky. Z nich vyplývá, že kvantový objekt nelze nezávisle změřit, každé měření má za následek nežádoucí interakci. I kdyby tedy došlo k odposlechu kvantového komunikačního kanálu, byl by tento odposlech spolehlivě detekován, protože přenášené informace by byly proti očekávání změněné; odposlechnutý klíč by pak pochopitelně nebyl použit. Pro samotné tajné sdělení může potom být použita Vernamova šifra.

Zdroje k tématu

Ještě před takovými pěti lety byl člověk, který se chtěl něco dozvědět o kvantových technologiích, odkázán v podstatě jen na cizojazyčné zdroje. Od té doby se situace naštěstí značně zlepšila a česky psaných odborných článků a publikací k této tématice je dostupných mnohem více, např. výborně zpracovaný článek Petra Lukašíka o základních principech kvantového výpočetního systému. Právě proto, že jsou často hodně odborné (a týká se to i některých článků na Wikipedii), bývá jejich prostudování poměrně náročné pro někoho, kdo není zběhlý v informatice a kvantové fyzice. Pro popularizaci kvantových technologií by však bylo potřeba rovněž více takových zdrojů, které by byly nejen dostatečně odborné, ale zároveň i přehledné a srozumitelné pro běžného člověka.