Kvantový počítač

Kvantový počítač je zařízení na vykonávání výpočtů, které přímo využívá při svojí činnosti fenomény známé z kvantové mechaniky, jako je například superpozice nebo kvantové provázání částic, na vykonávání operací s daty. V klasickém počítači jsou data určena bity, v kvantovém počítači se používají qubity (kvantové bity). Základním principem kvantových výpočtů je to, že kvantové vlastnosti částic jsou využity pro reprezentaci a strukturu dat a kvantové jevy se mohou použít k vykonávaní operací s těmito daty.

Jako první si možnost kvantového počítání pravděpodobně uvědomil Richard Philips Feynman. Uvažoval zhruba takto: Víme, že složitost popisu kvantového systému roste exponenciálně s počtem jeho částí (ve smyslu přidávání zhruba stejných částí). Proto počítače založené na klasické fyzice při snaze o detailní popis kvantových systémů selhávají už pro velmi jednoduché struktury. Představme si ale, že můžeme experimentálně zkoumat kvantový systém, jehož dynamika (struktura Hamiltoniánu) je obdobná jako u jiného kvantového systému, který pro nás experimentálně dostupný není. Pak systém dostupný našemi zkoumání pro nás simuluje chování systému, který nás sice primárně zajímá, ale našemu zkoumání dostupný není.

Kvantový simulátor ale není tzv univerzální kvantový počítač. Není například schopen řešit všechny úlohy, které je schopen řešit klasický počítač. Teorie univerzálních kvantových počítačů je již nes velmi dobře rozpracována. Používá pojmy jako qubit, kvantové hradlo, univerzální sada hradel, kvantový obvod a podobně.

Bouřlivý rozvoj prací na realizaci kvantových počítačů nastal v důsledku zveřejnění tzv Shorova algoritmu pro faktorizaci velkých čísel v kubickém čase. Navíc lze tento algoritmus jednoduše modifikovat tak, že v kubickém čase řeší i problém diskrétního logarimu a to jak nad číselným tělesem tak i nad Eliptickou křivkou. Bezpečnost běžně používaných kryptosystémů s veřejnými klíči (hlavní užití k ustanovení klíčů a k digitálnímu podpisu) jako RSA, Diffie-Hellman, ElGamal, kryptosystémy na eliptických křivkách závisí na praktické neřešitelnosti právě problému diskrétního logaritmu a faktorizace velkých čísel. Pro řešení těchto problémů pomocí klasických počítačů jsou známy pouze algoritmy se superpolynomiální časovou náročností (výpočetní čas roste s velikostí vstupů rychleji než libovolný polynom).

Neuvěřitelná efektivnost některých kvantových algoritmů je dána tím, že díky zákonitostem kvantové fyziky jsou kvantové počítače schopny provádět některé operace pro všechny vstupy (z dané rozsáhlé množiny) najednou. Tato možnost paralelizace je důsledkem tzv principu superpozice. Takže například periodu funkce, která se jinak chová "náhodně", lze pomocí kvantového algoritmu najít tak, že kvantovým paralelismem spočítáme hodnoty této funkce pro všechny hodnoty vstupů a pak na tyto hodnoty aplikujeme tzv kvantovou Fourierovu transformaci. Možnost efektivní implementace kvantové verze Fourierovy transformace je důsledkem jiné podstatné vlastnosti, jimiž se kvantové systémy odlišují od klasických, a to tzv provázání - entanglement.

Další potenciální aplikací kvantových počítačů v kryptoanalýze je urychlení hledání v nestrukturovaném seznamu. Typickým příkladem je hledání v telefonním seznamu, kdy známe číslo a chceme znát jeho majitele. Klasický počítač musí projít v průměru polovinu seznamu, zatímco kvantovému stačí udělat řádově jen N^1/2 kroků, kde N je počet položek seznamu (Groverův algoritmus). Pro symetrickou kryptografii (bez veřejných klíčů) to znamená zdvojnásobit délky klíčů.

Typů kvantových algoritmů, pro které dojde k principiálnímu dramatickému urychlení řešení úlohy vzhledem ke klasickým počítačům, je známo velmi málo (kromě Shorova a Groverova algoritmu, suïmulací kvantových systémů, jen kvantové náhodné procházky a snad pár dalších). Zatím se neví, zda je to v podstatě věci, nebo jen nejsme dost nápadití.

Pokud jde o možnost realizace kvantového počítače využitelného k lámání současných šifer s veřejnými klíči (například RSA s 2048 bity), panuje velká skepse. Před pár lety byl maximální počet provázaných qubitů (kvantová analogie bitu) řádově 10. Situace se podstatně změnila realizací kvantových počítačů nazývaných D-Wave, které, jak se zatím zdá, obsahují stovky provázaných qubitů. D-Wave jsou kvantové počítače, jejichž qubity jsou na bázi Josephsonových přechodů v obvodech se supravodivostí. Nejsou to univerzální počítače, ale kvantové simulátory, i když univerzálnější, než by plynulo z výše uvedeného principu prvoplánových simulátorů. Jde o adiabatické kvantové počítače, které využívají adiabatické změny Hamiltoniánu, při kterých systém setrvává ve svém základním stavu. Počáteční Hamiltonián se volí tak, abychom znali a uměli realizovat jeho základní stav. Poté se Hamiltonián mění adiabaticky tak, aby výsledný základní stav obsahoval netriviální informaci o řešení úlohy (viz níže).

Přestože se již objevují komerční zařízení určená na specifické úlohy, stále panují pochybnosti, zda v tomto případě jde o kvantový výpočet, a nejde o obyčejný analogový počítač.

Poměrně populární, ale i perspektivní možností implementace univerzálního kvantového počítače je využití tzv iontových pastí. Jde o soustavy iontů uvězněných v proměnných elektrických polích. K realizaci netriviálních (alespoň dvou-qubitových) kvantových hradel se

Existují také jisté druhy algoritmů, u kterých kvantový počítač nepřináší zlepšení. Proto se v případě šifer mluví o post-quantum cryptography.

Související články

• Galerie kvantový počítač na Wikimedia Commons
• Kvantová kryptografie
• Kvantová mechanika
• Počítač

V tomto článku byl použit překlad textu z článku Kvantový počítač na slovenské Wikipedii.