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.^[1] Rychlý rozvoj teorie kvantových počítačů a algoritmů nastal v 90. letech dvacátého století po objevení Shorova algoritmu,^[2] 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.^[3]

Historie

Jako jeden z prvních si v roce 1982 možnosti kvantových simulací uvědomil Richard Feynman,^[1] 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^[2] 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),^[4] 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.^[3] Ovšem výpočetní nadřazenost i pomocí klasického světla byla demonstrována v roce 2020.^[5][6]

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 ${\displaystyle \mid 0\rangle }$ a ${\displaystyle \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 ${\displaystyle {\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 ${\displaystyle {\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í ${\displaystyle {\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 ${\displaystyle \alpha |0\rangle +\beta |1\rangle }$ pro dvě komplexní čísla ${\displaystyle \alpha ,\beta }$, pro která navíc platí ${\displaystyle \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 ${\displaystyle {\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á.^[7]

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ř. ${\displaystyle 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 ${\displaystyle {\sqrt {N}}}$ kroků, kde ${\displaystyle 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.^[3] 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).^[4]

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.^[3]

První komerční kvantový počítač s 20 qubity IBM Q System One byl představen v lednu 2019.^[8] Jeho první umístění propagovala poté firma 15. června 2021 ve své centrále v německém Ehningenu.^[9] V listopadu roku 2021 poté představila počítač se 127 qubity.^[10] 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.^[11][12] 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,^[13] avšak v roce 2024 byla jeho realizace odsunuta až po roce 2033.^[14]

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.^[3] Výsledky takového počítače jsou ale dosažitelné klasickým počítačem,^[15] navíc rychleji a méně energeticky náročně.^[16] V prosinci 2024 firma Google ohlásila úspěšnou výrobu kvantového čipu se 105 quibity,^[17] který otestovala pomocí RCS (random circuit sampling), což nepředstavuje praktickou aplikaci.^[18]

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.^[19]

Roku 2024 představila Čína čip s 504 qubity.^[20]

Pochybnosti

Přestože se již objevují komerční zařízení určená na specifické úlohy,^[21] stále panují pochybnosti, zda v tomto případě jde o kvantový výpočet,^[22][23] a nejde o obyčejný analogový počítač,^[24] kde rychlost nebude taková.^[25] Ovšem i analogový počítač může být výhodnější.^[26] Navíc se část fyziků domnívá, že funkční kvantový počítač nebude nikdy sestrojen.^[27] Mají pro to různé důvody.^[28]

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ě.^[29] Navíc pro realizaci je třeba velké množství kvantových hradel^[30] či detektorů.^[31] Například pro faktorizaci 4096bitového čísla je třeba 4947802324992 hradel.^[32] Podle Fujitsu je pro RSA s 2048 bity potřeba zhruba polovina hradel (2,23 bilionu) a k tomu 10 tisíc qubitů.^[33]

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.^[34] Chyby kvantových počítačů tak nejsou náhodné, ale jsou korelované napříč počítačem.^[35] Navrhováno je například stínění olovem či přemístění počítačů hluboko pod zem.^[36] 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.^[37]

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

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.^[39]

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.^[40]

Odkazy

Reference

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

1. FEYNMAN, Richard P. Simulating physics with computers. International Journal of Theoretical Physics. 1982-06-01, roč. 21, čís. 6, s. 467–488. Dostupné online [cit. 2020-01-19]. ISSN 1572-9575. DOI 10.1007/BF02650179. (anglicky) 
2. W, ShorPeter. Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer. SIAM Journal on Computing. 1997-10-01. Dostupné online [cit. 2020-01-19]. DOI 10.1137/s0097539795293172. (EN) 
3. AARONSON, Scott. Opinion | Why Google’s Quantum Supremacy Milestone Matters. The New York Times. 2019-10-30. Dostupné online [cit. 2020-01-19]. ISSN 0362-4331. (anglicky) 
4. Generating hard instances of lattice problems (extended abstract) | Proceedings of the twenty-eighth annual ACM symposium on Theory of Computing. dl.acm.org [online]. [cit. 2020-01-19]. Dostupné online. DOI 10.1145/237814.237838. (EN) 
5. XU, Xiao-Yun; HUANG, Xuan-Lun; LI, Zhan-Ming; GAO, Jun; JIAO, Zhi-Qiang; WANG, Yao; REN, Ruo-Jing. A Scalable Photonic Computer Solving the Subset Sum Problem. S. eaay5853. Science Advances [online]. 2020-01-29. Roč. 6, čís. 5, s. eaay5853. Dostupné online. DOI 10.1126/sciadv.aay5853. (anglicky) 
6. HOUSER, Pavel. Fotonický počítač efektivně řeší NP úplný problém. sciencemag.cz [online]. 2020-05-04 [cit. 2021-12-29]. Dostupné online. 
7. https://phys.org/news/2022-04-side-effects-quantum-error-cope.html - The side effects of quantum error correction and how to cope with them
8. IBM ukázalo svůj kvantový počítač Q System One. Svethardware.cz [online]. 2019-01-11. Dostupné online. 
9. WELLE (WWW.DW.COM), Deutsche. IBM unveils first quantum computer in Germany | DW | 15.06.2021. DW.COM [online]. [cit. 2022-03-28]. Dostupné online. (anglicky) 
10. PALYZA, Jiří. IBM představila nový kvantový čip: díky němu budou výkonné počítače působit zastarale [online]. Chip.cz [cit. 2021-12-23]. Dostupné online. 
11. Efficient tensor network simulation of IBM’s Eagle kicked Ising experiment. arxiv.org [online]. [cit. 2023-07-17]. Dostupné online. 
12. Researchers show classical computers can keep up with, and surpass, their quantum counterparts. phys.org [online]. [cit. 2024-02-09]. Dostupné online. 
13. GAMBETTA, Jay. IBM’s roadmap for scaling quantum technology [online]. IBM [cit. 2021-12-23]. Dostupné online. (anglicky) 
14. IBM Quantum Roadmap Guide — Scaling And Expanding The Usefulness of Quantum Computing. thequantuminsider.com [online]. [cit. 2024-12-15]. Dostupné online. 
15. Ordinary computers can beat Google’s quantum computer after all. www.science.org [online]. [cit. 2023-07-17]. Dostupné online. 
16. Supremacy Surprise: Speedy Supercomputer Surpasses Sycamore. thequantuminsider.com [online]. [cit. 2024-07-07]. Dostupné online. 
17. HUSÁK, Ondřej. Revoluční kvantový čip. Za pět minut spočítal příklad, který by superpočítači trval 10 kvadrilionů let. Novinky.cz [online]. 2024-12-10 [cit. 2024-12-10]. Dostupné online. 
18. Is Google's new Willow quantum computer really such a big deal?. www.newscientist.com [online]. [cit. 2024-12-15]. Dostupné online. 
19. Proč Facebook zvažuje, že zakáže sdílet odkazy na články z médií?. Online Plus [online]. ČRo, 2020-09-05 [cit. 2022-03-28]. Dostupné online. 
20. China Introduces 504-Qubit Superconducting Chip. thequantuminsider.com [online]. [cit. 2024-12-16]. Dostupné online. 
21. JAVŮREK, Karel. Kvantový počítač se utkal s dnešními procesory. Zvítězil? [online]. CN Invest a.s. [cit. 2017-01-29]. Dostupné online. 
22. WOODWARD, Alan. Is It Quantum Computing or Not? [online]. 2013-05-17 [cit. 2017-01-29]. Jde o "přetištěný" blog, lepší zdroj by se hodil... Dostupné online. (anglicky) 
23. YIRKA, Bob. Independent research group testing D-Wave Two finds no quantum speedup [online]. Phys.org, 2014-06-20 [cit. 2017-01-29]. Dostupné online. (anglicky) 
24. BERGAMIN, Fabio. Quantum computing machine under scrutiny [online]. ETH Zürich, 2014-03-17 [cit. 2017-01-29]. Dostupné online. (anglicky) 
25. Team tightens bounds on quantum information 'speed limit'. phys.org [online]. 2015-04-13 [cit. 2021-12-29]. Dostupné online. (anglicky) 
26. BYRNE, Peter. Analog Simulators Could Be Shortcut to Universal Quantum Computers. Scientific American [online]. 2015-05-06 [cit. 2021-12-29]. Dostupné online. (anglicky) 
27. SCHLOSSHAUER, Maximilian; KOFLER, Johannes; ZEILINGER, Anton. A snapshot of foundational attitudes toward quantum mechanics. S. 222–230. Studies in History and Philosophy of Science Part B: Studies in History and Philosophy of Modern Physics [online]. 2013-08. Roč. 44, čís. 3, s. 222–230. Dostupné online. DOI 10.1016/j.shpsb.2013.04.004. (anglicky) 
28. AARONSON, Scott. PHYS771 Lecture 14: Skepticism of Quantum Computing [online]. scottaaronson.com [cit. 2021-12-29]. Dostupné online. (anglicky) 
29. Quantum Error Mitigation May Face Hard Limits. thequantuminsider.com [online]. [cit. 2024-08-04]. Dostupné online. 
30. BECKMAN, David; CHARI, Amalavoyal N.; DEVABHAKTUNI, Srikrishna; PRESKILL, John. Efficient networks for quantum factoring. S. 1034–1063. Physical Review A [online]. 1996-08-01. Roč. 54, čís. 2, s. 1034–1063. Dostupné online. DOI 10.1103/PhysRevA.54.1034. (anglicky) 
31. JOHNSTON, Hamish. Light-based quantum computers will come at a great cost. physicsworld.com [online]. 2015-10-26 [cit. 2021-12-29]. Dostupné online. (anglicky) 
32. SCHNEIER, Bruce. Quantum Computing: Hype vs. Reality. schneier.com [online]. 2008-03-23 [cit. 2021-12-29]. Dostupné online. (anglicky) 
33. Fujitsu quantum simulator assesses vulnerability of RSA cryptosystem to potential quantum computer cryptography threat. www.fujitsu.com [online]. [cit. 2023-07-24]. Dostupné online. 
34. HOUSER, Pavel. Životnost kvantových počítačů omezuje kosmické záření. sciencemag.cz [online]. 2020-08-31 [cit. 2021-12-29]. Dostupné online. 
35. Correlated errors in quantum computers emphasize need for design changes. phys.org [online]. 2021-06-16 [cit. 2021-12-29]. Dostupné online. (anglicky) 
36. HARRIS, Margaret. Cosmic-ray threat to quantum computing greater than previously thought. physicsworld.com [online]. 2021-07-28 [cit. 2021-12-29]. Dostupné online. (anglicky) 
37. JÉGL, Pavel. Dosažen milník ve vývoji kvantových počítačů. Nedd.cz [online]. 2023-02-25 [cit. 2023-02-28]. Dostupné online. 
38. The first exponential quantum advantage for a natural streaming problem. phys.org [online]. [cit. 2024-07-01]. Dostupné online. 
39. KŘELINA, Michal. Blíží se kvantová bouře, která přepíše pravidla šifrování. Připravit se je potřeba už dnes. Lupa.cz [online]. 2024-11-25 [cit. 2024-11-25]. Dostupné online. 
40. NOVÁK, Richard; HUSÁK, Ondřej. Konec bitcoinu? Nový kvantový čip budí obavy. Novinky.cz [online]. 2024-12-10 [cit. 2024-12-10]. Dostupné online. 

Související články

• Kvantová kryptografie
• Kvantová mechanika
• Jozef Gruska

Externí odkazy

• 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