Kvantový počítač

Z Wikipedie, otevřené encyklopedie
Skočit na: Navigace, Hledání

Kvantový počítač je v informatice 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í , 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.

Historie[editovat | editovat zdroj]

Jako jeden z prvních si v roce 1982 možnosti kvantových simulací uvědomil Richard 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 pro univerzální kvantové počítače je již 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 po roce 1994 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).

Použití[editovat | editovat zdroj]

Vysoká efektivnost některých kvantových algoritmů má být 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. kvantové 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 teoreticky 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í.

Realizace[editovat | editovat zdroj]

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 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, 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.

Základní požadavky na kvantový hardware jsou shrnuty v tzv. DiVincenzeho kritériích.[1]

Pochybnosti[editovat | editovat zdroj]

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

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[11] či detektorů.[12] Například pro faktorizaci 4096-bitového čísla je třeba 4947802324992 hradel.[13]

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é. Ovšem i praktičnost Groverova algoritmu je diskutabilní.[14]

Kvantové počítače v praxi[editovat | editovat zdroj]

Kvantové počítače kanadské firmy D-Wave jsou dosud jedinými systémy, které se již prakticky využívají (respektive to bylo oficiálně oznámeno). Zákazníky D-Wave jsou Google, NASA, Lockheed Martin a od verze D-Wave 2000Q (s 2048 qubity) také TDS. Kvantové počítače D-Wave jsou jednoúčelové stroje určené pro kvantové žíhání (annealing), nejsou např. schopné provádět Shorův algoritmus.[15]

Reference[editovat | editovat zdroj]

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

  1. DIVINCENZO, David P.. The Physical Implementation of Quantum Computation [online]. 2000-02-25, [cit. 2017-01-29]. Kapitola REALIZING QUANTUM COMPUTATION, s. 2-6. Dostupné online. (anglicky) 
  2. 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) 
  3. 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) 
  4. 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) 
  5. BERGAMIN, Fabio. Quantum computing machine under scrutiny [online]. ETH Zürich, 2014-03-17, [cit. 2017-01-29]. Dostupné online. (anglicky) 
  6. http://phys.org/news/2015-04-team-tightens-bounds-quantum-limit.html - Team tightens bounds on quantum information 'speed limit'
  7. http://www.scientificamerican.com/article/analog-simulators-could-be-shortcut-to-universal-quantum-computers/ - Analog Simulators Could Be Shortcut to Universal Quantum Computers
  8. http://arxiv.org/pdf/1301.1069v1.pdf - A Snapshot of Foundational Attitudes Toward Quantum Mechanics
  9. http://www.scottaaronson.com/democritus/lec14.html - Lecture 14: Skepticism of Quantum Computing
  10. https://rjlipton.wordpress.com/2012/01/30/perpetual-motion-of-the-21st-century/ - Perpetual Motion of The 21st Century?
  11. http://arxiv.org/abs/quant-ph/9602016 - Efficient Networks for Quantum Factoring
  12. 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
  13. https://www.schneier.com/blog/archives/2008/03/quantum_computi_1.html - Bruce Schneier: Quantum Computing: Hype vs. Reality
  14. https://web.eecs.umich.edu/~imarkov/pubs/jour/cise05-grov.pdf - IS QUANTUM SEARCH PRACTICAL?
  15. HOUSER, Pavel. D-Wave 2000Q, nová verze kvantového počítače. Sciencemag.cz [online]. 2017-01-29 [cit. 2017-01-29]. Dostupné online.  

Související články[editovat | editovat zdroj]

Externí odkazy[editovat | editovat zdroj]