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.[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 považováno za složitý technologický problém.[3] V říjnu 2019 Google AI a NASA publikovaly výsledky demonstrující tzv. kvantovou nadřazenost: to znamená formulaci matematického problému (ne nutně užitečného pro praktické využití), který následně byl 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 dle 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.[4][5]

HistorieEditovat

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. 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[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 ř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)[6] 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ť.[7] Důležitým mezikrokem je demostrace tzv. kvantové nadřazenosti, neboli postavení kvantového počítače, který umí vyřešit alespoň jeden (ne nutně důležitý) problém, jenž neumíme vyřešit na klasických počítačích kvůli vysoké časové náročnosti klasického algoritmu. Dosažení této mety bylo oznámeno 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 sekund, zatímco současným superpočítačům by vyřešení tohoto problému dle jejich odhadu trvalo 10 000 let.[3]

Princip kvantových počítačůEditovat

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   a  . 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  . 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  . 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í  .

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   pro dvě komplexní čísla  , pro která navíc platí  . 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  . 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é algoritmyEditovat

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ř.  ).

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   kroků, kde   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 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).[6]

RealizaceEditovat

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

PochybnostiEditovat

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

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. Navíc pro realizaci je třeba velké množství kvantových hradel[18] či detektorů.[19] Například pro faktorizaci 4096-bitového čísla je třeba 4947802324992 hradel.[20]

ReferenceEditovat

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

  1. a b 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. a b 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. (anglicky) 
  3. a b c d e f 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. https://arxiv.org/abs/2002.05108 - A Scalable Photonic Computer Solving the Subset Sum Problem
  5. https://sciencemag.cz/fotonicky-pocitac-efektivne-resi-np-uplny-problem/ - Fotonický počítač efektivně řeší NP úplný problém
  6. a b 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. (anglicky) 
  7. PRESKILL, John. Quantum Computing in the NISQ era and beyond. Quantum. 2018-08-06, roč. 2, s. 79. Dostupné online [cit. 2020-01-19]. ISSN 2521-327X. DOI:10.22331/q-2018-08-06-79. 
  8. IBM ukázalo svůj kvantový počítač Q System One. Svethardware.cz [online]. 2019-01-11. Dostupné online. 
  9. 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. (čeština) 
  10. 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) 
  11. 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) 
  12. BERGAMIN, Fabio. Quantum computing machine under scrutiny [online]. ETH Zürich, 2014-03-17 [cit. 2017-01-29]. Dostupné online. (anglicky) 
  13. http://phys.org/news/2015-04-team-tightens-bounds-quantum-limit.html - Team tightens bounds on quantum information 'speed limit'
  14. http://www.scientificamerican.com/article/analog-simulators-could-be-shortcut-to-universal-quantum-computers/ - Analog Simulators Could Be Shortcut to Universal Quantum Computers
  15. http://arxiv.org/pdf/1301.1069v1.pdf - A Snapshot of Foundational Attitudes Toward Quantum Mechanics
  16. http://www.scottaaronson.com/democritus/lec14.html - Lecture 14: Skepticism of Quantum Computing
  17. https://rjlipton.wordpress.com/2012/01/30/perpetual-motion-of-the-21st-century/ - Perpetual Motion of The 21st Century?
  18. http://arxiv.org/abs/quant-ph/9602016 - Efficient Networks for Quantum Factoring
  19. http://physicsworld.com/cws/article/news/2015/oct/26/light-based-quantum-computers-will-come-at-a-great-cost - Light-based quantum computers will come at a great cost
  20. https://www.schneier.com/blog/archives/2008/03/quantum_computi_1.html - Bruce Schneier: Quantum Computing: Hype vs. Reality

Související článkyEditovat

Externí odkazyEditovat