Kvantový počítač

Kvantový počítač je oproti klasickému počítači, kde jsou data reprezentována bity, přičemž každý bit je buď 0, nebo 1, tak v kvantovém počítači se používají qubity (kvantové bity), které mohou být nula, jedna, nebo i kombinace obou. Kvantový počítač vykonává výpočty na základě fenoménů známých z kvantové mechaniky jako superpozice či interference.

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. +more 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 považováno za složitý technologický problém.

Mezi nejvýznamnější české akademiky na poli kvantového počítání patří prof. Jozef Gruska, doktor věd, jenž působí na Fakultě informatiky Masarykovy univerzity.

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. V konečném důsledku je 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. +more Ř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. +more 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 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, to znamená 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 dle jejich odhadu trvalo asi 10 000 let. +more Ovšem výpočetní nadřazenost i pomocí klasického světla byla demonstrována v roce 2020.

Princip kvantových počítačů

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. +more 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 \frac12\mid0\rangle + \frac12 \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 \frac12\mid0\rangle + \frac12 \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í \frac12\mid00\rangle + \frac12 \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 dle zákonů kvantové fyziky používají tzv. +more 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}\mid00\rangle - \sqrt{2/3}\mid11\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. +more 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

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ř. +more 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. +more 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 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. +more 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

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 +more_červen'>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 má IBM v plánu předvést první kvantový počítač s více než 1000 qubity.

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.

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.

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ší. +more Navíc část fyziků se 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. +more 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.

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. +more 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.

Odkazy

Reference

Související články

Kvantová kryptografie * Kvantová mechanika * Jozef Gruska

Externí odkazy

[url=https://research. ibm. +morecom/blog/ibm-quantum-roadmap]Roadmapa kvantového vývoje v IBM[/url] (anglicky) * P[url=https://www. dw. com/en/ibm-unveils-first-quantum-computer-in-germany/a-57909494]rvní kvantový počítač v Německu[/url].

Kategorie:Třídy počítačů Kategorie:Kvantová fyzika