Kvantový počítač

Blochova koule je znázornění qubitu, základní stavební jednotky kvantových počítačů.

Kvantový počítač je zařízení, které podobně jako klasický počítač slouží k provádění výpočetních úloh, liší se však v tom, že pro zpracování vstupních dat využívá jevů známých z kvantové fyziky, jako jsou například interference, kvantová superpozice, kvantové provázání či redukce vlnové funkce kvantovým měřením. Data jsou místo klasických bitů reprezentována qubity (kvantovými bity), které mohou nabývat nejen klasických hodnot 0 či 1, ale mohou se nacházet také v superpozici obou hodnot.

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í plně funkčního kvantového počítače je však považováno za složitý technologický problém.

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. Příčinou je jistě 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 tohoto druhu 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 nahrazena jinými systémy (postkvantová kryptografie), 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.

V říjnu 2019 Google AI a NASA publikovaly výsledky demonstrující tzv. kvantovou nadřazenost, tedy formulaci matematického problému (ne nutně užitečného pro praktické využití), který byl následně vyřešen pomocí kvantového počítače, zatímco vyřešení tohoto problému pomocí současného klasického superpočítače by podle jejich odhadu trvalo asi 10 000 let. Ovšem výpočetní nadřazenost i pomocí klasického světla byla demonstrována v roce 2020.

Princip kvantových počítačů

Vysvětlení principu kvantového počítače

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 podle 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 vychází 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 ubírat; 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.

Reálně dochází k chybám. K opravám slouží kvantová oprava chyb. Ale i ta není bezchybná.

Kvantové algoritmy

Na tuto kapitolu je přesměrováno heslo Kvantový algoritmus. Pomozte Wikipedii tím, že pro něj vytvoříte samostatný článek.

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ě rozložit dané celé číslo na prvočísla (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 asi nejdůležitější potenciální aplikace kvantového počítače tak v tuto chvíli^[kdy?] 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 (postkvantová kryptografie).

Realizace kvantového počítače

IBM Q System One

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. Jeho první umístění propagovala poté firma 15. června 2021 ve své centrále v německém Ehningenu. V listopadu roku 2021 poté představila počítač se 127 qubity. V názvosloví procesorů se objevuje IBM Eagle. V roce 2023 bylo ukázáno, že speciální klasický počítač dosáhne lepších výsledků než tento kvantový počítač se 127 qubity. Podle plánu z roku 2020 mělo IBM v roce 2023 předvést první kvantový počítač s více než 1000 qubity, avšak v roce 2024 byla jeho realizace odsunuta až po roce 2033.

Když v říjnu 2019 Google AI a NASA publikovaly výsledky údajně demonstrující kvantovou nadřazenost, použily k tomu kvantový počítač s přibližně 50 qubity. Výsledky takového počítače jsou ale dosažitelné klasickým počítačem, navíc rychleji a méně energeticky náročně. V prosinci 2024 firma Google ohlásila úspěšnou výrobu kvantového čipu se 105 quibity, který otestovala pomocí RCS (random circuit sampling), což nepředstavuje praktickou aplikaci.

Na území Evropské unie projevilo iniciativu v kvantovém počítání Spojené království, realizací prvního komerčně dostupného kvantového počítače ve firmě ORCA Computing v Londýně v roce 2020, v ceně 13 mil. eur.

Roku 2024 představila Čína čip s 504 qubity.

Pochybnosti

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č, kde rychlost nebude taková. Ovšem i analogový počítač může být výhodnější. Navíc se část fyziků domnívá, že funkční kvantový počítač nebude nikdy sestrojen. Mají pro to různé důvody.

Je třeba podotknout, ž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. Pro větší systémy limity rostou exponenciálně. Navíc pro realizaci je třeba velké množství kvantových hradel či detektorů. Například pro faktorizaci 4096bitového čísla je třeba 4947802324992 hradel. Podle Fujitsu je pro RSA s 2048 bity potřeba zhruba polovina hradel (2,23 bilionu) a k tomu 10 tisíc qubitů.

Stavy, se kterými teorie kvantových počítačů počítá, nejsou ideální a ani ideálně izolované od okolí. Jejich dobu života, po kterou jsou koherentní, může limitovat ionizující záření, které je běžné v okolí a proniká do počítače. Chyby kvantových počítačů tak nejsou náhodné, ale jsou korelované napříč počítačem. Navrhováno je například stínění olovem či přemístění počítačů hluboko pod zem. Druhou možností je použít na jeden logický qubit více fyzických qubitů. Dříve se používalo 17 qubitů, nověji bylo použito 49 qubitů a zároveň se podařilo chybovost snížit. Přesto je chybovost stále poměrně vysoká na to, aby bylo možné kvantové počítače rutinně používat.

Kvantový počítač nemusí být vůbec rychlejší než klasický, jen má výhodu v paměti.

Rizika pro šifrování

Podrobnější informace naleznete v článku Postkvantová kryptografie.

Po sestrojení dostatečně výkonného kvantového počítače by byly ohroženy klasické moderní asymetrické šifry (např. RSA), oslabeny by byly symetrické šifry (např. AES). Proto je vyvíjena postkvantová kryptografie, která by měla kvantovým počítačům odolat.

Bitcoin by mohlo ohrozit úspěšné vytvoření kvantového počítače, který by však musel mít odhadem 13 miliónů qubitů. V prosinci 2024 jsou však k dispozici kvantové čipy se 105 qubity.

Odkazy

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
• Jozef Gruska

Externí odkazy

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

• Roadmapa kvantového vývoje v IBM (anglicky)
• První kvantový počítač v Německu

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