Kvantový počítač

Datum 28.02.2016

Foto:

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žnosti 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šemu 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ž dnes[kdy?] 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 logaritmu 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 N1/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, simulací 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 (nelze je například využít k realizaci Shorova algoritmu), 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.

Přestože se již objevují komerční zařízení určená na specifické úlohy,[1] stále panují pochybnosti, zda v tomto případě jde o kvantový výpočet,[2][3] a nejde o obyčejný analogový počítač,[4]kde rychlost nebude taková.[5] Navíc část fyziků se domnívá, že funkční kvantový počítač nebude nikdy sestrojen.[6]

Poznamenejme, že k realizaci Shorova algoritmu je potřeba řádově statisíce až miliony v zásadě provázaných qubitů, což je nesrovnatelné i se stovkou qubitů počítačů D-Wave. Miliony qubitů jsou potřebné zejména proto, že kvantový počítač tráví drtivou většinu času opravami chyb. Navíc pro realizaci je třeba velké množství kvantových hradel[7] či detektorů.[8] Například pro faktorizaci 4096-bitového čísla je třeba 4947802324992 hradel.[9]

Základní požadavky na kvantový hardware jsou shrnuty z tzv. DiVincenceho kritériích.

Existují také jisté druhy algoritmů (například NTRU), u kterých kvantový počítač nepřináší zlepšení. Proto se v případě šifer mluví o postkvantové kryptografii (post-quantum cryptography). Z uvedeného vyplývá, že pro dešifrování jsou kvantové počítače nevhodné, protože volené velikosti klíče či algoritmu je snadno dělají složitě realizovatelné a neúčinné.

 

Zdroj: Wikipedie
EPM 700 x 200 px

Napsat komentář