Kvantový počítač

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

Kvantový počítač je 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í částic, 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ého počítání 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]

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

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í.[12]

Reference[editovat | editovat zdroj]

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

  1. https://arxiv.org/pdf/quant-ph/0002077v3.pdf - David P. DiVincenzo: The Physical Implementation of Quantum Computation
  2. http://vtm.e15.cz/kyužívvantovy-pocitac-se-utkal-s-dnesnimi-procesory-zvitezil - Kvantový počítač se utkal s dnešními procesory. Zvítězil?
  3. http://news.yahoo.com/quantum-computing-not-140100223.html - Is It Quantum Computing or Not?
  4. http://phys.org/news/2014-06-independent-group-d-wave-quantum-speedup.html - Independent research group testing D-Wave Two finds no quantum speedup
  5. http://phys.org/news/2014-03-quantum-machine-scrutiny.html - Quantum computing machine under scrutiny
  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://arxiv.org/abs/quant-ph/9602016 - Efficient Networks for Quantum Factoring
  10. 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
  11. https://www.schneier.com/blog/archives/2008/03/quantum_computi_1.html - Bruce Schneier: Quantum Computing: Hype vs. Reality
  12. https://web.eecs.umich.edu/~imarkov/pubs/jour/cise05-grov.pdf - IS QUANTUM SEARCH PRACTICAL?

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

Externí odkazy[editovat | editovat zdroj]