Kvantový počítač

Kvantový počítač je teoretický model pro zařízení na vykonávání výpočtů, které přímo využívá při své činnosti fenomény známé z kvantové mechaniky jako superpozice či interference. V klasickém počítači jsou data reprezentována bity, kde každý bit je buď nula, nebo jedna, zatímco v kvantovém počítači se používají qubity (kvantové bity), které mohou být nula, jedna, nebo i kombinace obou. Výzkum kvantových počítačů započal na počátku 80. let dvacátého století, jedním z prvních proponentů byl známý fyzik Richard Feynman. Rychlý rozvoj teorie kvantových počítačů a algoritmů nastal v 90. letech dvacátého století po objevení Shorova algoritmu, jehož implementace na kvantovém počítači by prolomila většinu dnes používaných kryptosystémů. Sestrojení kvantového počítače je považováno za složitý technologický problém. V říjnu 2019 Google AI a NASA publikovaly výsledky demonstrující tzv. kvantovou nadřazenost, tedy vyřešení jistého problému na kvantovém počítači, které by dle jejich odhadu trvalo současnému superpočítači asi 10 000 let.

Historie

Jako jeden z prvních si v roce 1982 možnosti kvantových simulací uvědomil Richard Feynman, který uvažoval následovně. Je známo, že simulace kvantového systému (například skupiny atomů) na počítači je velmi obtížný problém; časová náročnost všech známých přístupů totiž roste exponenciálně s počtem prvků systému. V konečném důsledku je to příčinou to, že fungování počítačů je založeno na klasické fyzice, která se matematicky liší od kvantové fyziky, již je zapotřebí simulovat. Řešením tohoto problému by bylo sestrojit počítač, jehož součásti by se samy o sobě řídily zákony kvantové mechaniky.

Bouřlivý rozvoj práce na realizaci i teoretickém pochopení kvantových počítačů nastal po roce 1994 v důsledku nalezení tzv. Shorova algoritmu pro faktorizaci velkých čísel na kvantovém počítači. Důležitost tohoto algoritmu spočívá v tom, že je výrazně efektivnější než všechny známé algoritmy řešící tento problém navržené pro klasické počítače. Algoritmus lze modifikovat tak, aby efektivně vyřešil i tzv. problém diskrétního logaritmu. Bezpečnost běžně používaných kryptosystémů s veřejnými klíči jako RSA, Diffie-Hellman, ElGamal či kryptosystémy založené 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. Po sestavení kvantového počítače s dostatečným počtem qubitů by proto velká část používaných kryptosystémů musela být nahrazená jinými systémy, např. těmi založenými na celočíselných mřížkách (jako je např. NTRU) které se zdají být bezpečné i proti útoku kvantovým počítačem.

I přes pokračující pokrok je postavení škálovatelného kvantového počítače stále považováno za běh na dlouhou trať. Důležitým mezikrokem je demostrace tzv. kvantové nadřazenosti, neboli postavení kvantového počítače, který umí vyřešit libovolný (ne nutně důležitý) problém, jenž neumíme vyřešit na klasických počítačích kvůli jeho vysoké časové náročnosti. V říjnu 2019 Google AI a NASA publikovaly výsledky demonstrující vyřešení jistého problému pomocí kvantového počítače během 200 vteřin, zatímco současným superpočítačům by vyřešení tohoto problému dle jejich odhadu trvalo 10 000 let.

Princip kvantových počítačů

Klasické počítače operují s bity, kde každý bit nabývá buď hodnoty nula, nebo jedna. Pro uvedení modelu kvantových počítačů si nejprve představme model klasického počítače, který navíc může dělat náhodná rozhodnutí - například může do daného bitu s poloviční pravděpodobností uložit nula a s poloviční pravděpodobností jedna. V takovém případě již hodnoty bitů, se kterými počítač operuje, nemůžeme reprezentovat jako pouhou nulu, nebo jedničku; vhodnou reprezentací každého bitu je v tomto případě lineární kombinace dvou nezávislých vektorů, jež můžeme nazvat $\mid 0\rangle$ a $\mid 1\rangle$. Jestliže by počítač do daného bitu uložil nula či jedna s poloviční pravděpodobností, můžeme stav tohoto bitu reprezentovat jako ${\frac {1}{2}}\mid 0\rangle +{\frac {1}{2}}\mid 1\rangle$. Koeficienty jsou pravděpodobnosti, tedy nezáporná čísla, jejichž součet je jedna. Jestliže v příštím kroku zkopíruje počítač hodnotu tohoto bitu do jiného, můžeme i nový bit reprezentovat jako ${\frac {1}{2}}\mid 0\rangle +{\frac {1}{2}}\mid 1\rangle$. Tyto dva bity jsou ale nyní provázané - známe-li hodnotu jednoho, známe i hodnotu druhého. Oba bity bychom pak reprezentovali kombinací ${\frac {1}{2}}\mid 00\rangle +{\frac {1}{2}}\mid 11\rangle$.

Model kvantového počítače je podobný modelu klasického pravděpodobnostního počítače. Rozdílem je, že zatímco k popisu pravděpodobnostního počítače používáme přímo pravděpodobnosti, k popisu kvantového počítače se dle zákonů kvantové fyziky používají tzv. amplitudy, což jsou čísla, která mohou být nejen záporná, ale dokonce i komplexní. Změříme-li výstup kvantového počítače, pravděpodobnost daného výstupu se dostane jako druhá mocnina normy amplitudy a jedná se tak speciálně vždy o nezáporné číslo. Jako kvantový bit či qubit tak obecně myslíme dvoudimenzionální vektor $\alpha |0\rangle +\beta |1\rangle$ pro dvě komplexní čísla $\alpha ,\beta$, pro která navíc platí $\alpha ^{2}+\beta ^{2}=1$. Kvantový počítač umí vykonávat podobné instrukce jako klasický počítač a i kvantové bity mohou být provázané. Můžeme tak například dosáhnout stavu ${\sqrt {1/3}}\mid 00\rangle -{\sqrt {2/3}}\mid 11\rangle$. Jestliže v tuto chvíli změříme hodnotu obou qubitů, s pravděpodobností jedna třetina to budou dvě nuly, zatímco s pravděpodobností dvě třetiny se bude jednat o dvě jedničky.

Potenciální výhoda kvantových počítačů oproti těm klasickým je následující. U klasických pravděpodobnostních počítačů platí, že představíme-li si všechny cesty, kterými se pravděpodobnostní výpočet mohl vydat, má každá z nich určitou nezápornou pravděpodobnost. Pravděpodobnost, že algoritmus odpoví špatně, se spočítá jako součet pravděpodobností všech cest vedoucích ke špatnému výsledku. U kvantových počítačů si opět můžeme představit všechny cesty, kterými se výpočet mohl ubrat; v tomto případě má však každá cesta amplitudu, což není nutně kladné číslo. Součet amplitud cest vedoucích ke špatnému výsledku proto může být ve vhodně navrženém kvantovém algoritmu nula. Proto i pravděpodobnost, že algoritmus dá špatný výsledek, může být nula, ačkoli existují cesty vedoucí ke špatnému výsledku. Tento neintuitivní jev se nazývá interference.

Kvantové algoritmy

Jedním z mála známých využití modelu kvantového počítače je využití jevu interference k získání rychlého algoritmu pro Fourierovu transformaci. Na tomto algoritmu je pak založen Shorův algoritmus umožňující efektivně faktorizovat dané číslo (např. $15=3\times 5$).

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 Groverově algoritmu stačí za určitých podmínek udělat řádově jen ${\sqrt {N}}$ kroků, kde $N$ je počet položek seznamu. Pro symetrickou kryptografii to teoreticky znamená potřebu zdvojnásobit délky klíčů. Toto neintuitivní kvadratické zrychlení je způsobeno tím, že kvantové počítače nepopisujeme přímo pomocí pravděpodobností, nýbrž pomocí amplitud, z nichž pravděpodobnost získáme až umocněním na druhou (a toto umocnění na druhou v konečném důsledku umožňuje kvadratické zrychlení).

Typů kvantových algoritmů, pro které dojde k principiálnímu, dramatickému urychlení řešení vzhledem ke klasickým počítačům, je známo velmi málo. Mezi důležité potenciální aplikace kvantového počítače tak v tuto chvíli patří zejména možnost simulovat kvantové systémy, která potenciálně může vést k důležitým aplikacím v medicíně či chemii. Shorův algoritmus pak ukazuje, že sestrojení škálovatelného kvantového počítače vynutí změnu stávajících kryptografických systémů za jiné, např. ty založené na celočíselných mřížkách.

Realizace

Sestrojení netriviálně velkého kvantového počítače se považuje za složitý technologický problém a aplikace jako prolamování současných kryptografických systémů pomocí Shorova algoritmu nejsou v příštích několika letech očekávány. První komerční kvantový počítač s 20 qubity IBM Q System One byl představen v lednu 2019. Když v říjnu 2019 Google AI a NASA publikovaly výsledky demonstrující kvantovou nadřazenost, použily k tomu kvantový počítač s přibližně 50 qubity.

Pochybnosti

Přestože již existují komerční kvantová zařízení určená na specifické úlohy, jakými jsou počítače kanadské firmy D-Wave, panují značné pochybnosti o tom, zda v tomto případě kvantové jevy vyskytující se v zařízení skutečně přináješí výhodu. Někteří vědci se domnívají, že funkční kvantový počítač s netriviálním počtem qubitů nebude nikdy sestrojen.

Reference

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

Související články

• Kvantová kryptografie
• Kvantová mechanika
• Počítač

Externí odkazy

• Obrázky, zvuky či videa k tématu kvantový počítač na Wikimedia Commons

Autoritní data	NKC: ph184827 BNE: XX556504 BNF: cb135068781 (data) GND: 4533372-5 LCCN: sh98002795 NDL: 01072652 NLI: 987007566220005171