Kvantová nadvláda

Aktuální verze stránky ještě nebyla zkontrolována zkušenými přispěvateli a může se výrazně lišit od verze recenzované 8. října 2020; kontroly vyžadují 8 úprav .

Kvantová nadřazenost  je schopnost kvantových výpočetních zařízení řešit problémy, které klasické počítače prakticky řešit neumí. Kvantovou výhodou je schopnost řešit problémy rychleji. Z hlediska teorie výpočetní složitosti to obvykle znamená poskytnout superpolynomiální zrychlení ve srovnání s nejznámějším nebo možným klasickým algoritmem [1] . Termín zpopularizoval John Preskill , ale koncept kvantové výpočetní výhody, zejména při simulaci kvantových systémů, sahá až k návrhu kvantového počítání, který předložil Yuri Manin (1980) [2] aRichard Feynman (1981) [3] .

Shorův algoritmus pro celočíselnou faktorizaci, který běží v polynomiálním čase na kvantovém počítači, poskytuje takové superpolynomiální zrychlení ve srovnání s nejznámějším klasickým algoritmem [4] . Ačkoli to musí být ještě prokázáno, faktorizace je považována za výzvu při použití klasických zdrojů. Obtížnost dokazování toho, co nelze provést klasickým výpočtem, je běžným problémem pro definitivní prokázání kvantové převahy. Ovlivňuje také návrh vzorkování Aaronsonova a Arkhipova bosonu , specializované problémy D-Wave o frustrovaných klastrových smyčkách a vzorkování výstupu pro náhodné kvantové obvody .

Stejně jako faktorizace celého čísla je problém vzorkování výstupních distribucí náhodných kvantových obvodů považován za obtížný pro klasické počítače na základě rozumných předpokladů o složitosti.

Historie

Google již dříve oznámil plány prokázat kvantovou nadvládu do konce roku 2017 pomocí pole 49 supravodivých qubitů [5] . Od začátku ledna 2018 však takový hardware oznámil pouze Intel [6] .

V říjnu 2017 IBM předvedla simulaci 56 qubitů na konvenčním superpočítači, čímž se zvýšil počet qubitů potřebných pro kvantovou nadvládu [7] .

V listopadu 2018 Google oznámil partnerství s NASA , ve kterém bude NASA „analyzovat výsledky z kvantových obvodů běžících na kvantových procesorech Google a... nadřazenosti“ [8] .

Teoretická práce z roku 2018 naznačuje, že kvantové převahy lze dosáhnout na „dvourozměrném poli 7 × 7 qubitů a asi 40 hodinových cyklech“, ale pokud je chybovost dostatečně nízká [9] .

21. června 2019 Scientific American navrhl, že podle Nevenova zákona bude kvantové převahy dosaženo v roce 2019 [10] .

20. září 2019 list Financial Times uvedl, že „Google tvrdí, že dosáhl kvantové převahy na poli 54 qubitů, z nichž 53 bylo funkčních a bylo použito k provádění výpočtů za 200 sekund, což by u konvenčního superpočítače trvalo asi 10 000 let. “ [11] . Zpočátku se zpráva o tom objevila na webu NASA, ale byla krátce po zveřejnění smazána [12] . Později, 23. října, byla oficiálně oznámena kvantová nadvláda [13] . Odborníci z IBM však po analýze prezentovaných dat naznačili, že některé momenty nejsou optimální a že ve skutečnosti takový výpočet na klasickém superpočítači zabere místo deklarovaných 10 000 let jen 2,5 dne. [14] [15] [16]

Dne 3. prosince 2020 čínští vědci oznámili, že jejich kvantový počítač Jiuzhang , poháněný provázanými fotony, dosáhl kvantové převahy. Za 200 sekund úspěšně vypočítali problém, jehož vyřešení by nejrychlejšímu klasickému počítači na světě trvalo více než půl miliardy let [17] .

Výpočetní složitost

Problém složitosti se týká toho, jak se množství zdrojů potřebné k vyřešení problému mění s velikostí vstupu. Jako rozšíření klasické výpočetní teorie složitosti popisuje kvantová teorie složitosti provoz univerzálního kvantového počítače bez zohlednění složitosti jeho vytvoření nebo eliminace efektů dekoherence a šumu [18] . Protože kvantová informace je zobecněním klasické informace , kvantový počítač může simulovat jakýkoli klasický algoritmus .

Třída složitosti problémů s kvantovou polynomiální časově ohraničenou chybou (BQP) je třída rozhodovacích problémů, které lze vyřešit v polynomiálním čase univerzálním kvantovým počítačem . Třída BPQ souvisí s klasickými třídami složitosti hierarchií [19] . Zůstává otevřenou otázkou, zda je některé z těchto vložení přísné.

Na rozdíl od rozhodovacích problémů, které vyžadují odpověď ano nebo ne, vzorkovací problémy vyžadují vzorkování z rozdělení pravděpodobnosti [20] . Pokud existuje klasický algoritmus , který dokáže vzorkovat výstup libovolného kvantového obvodu , posune se polynomiální hierarchie na třetí úroveň, což je považováno za velmi nepravděpodobné. BosonSampling  je specifičtější návrh, jehož klasická složitost závisí na neřešitelnosti problému výpočtu permanentu velké matice s komplexními prvky, což je P#-úplný problém. Argumenty použité k odvození tohoto tvrzení byly také aplikovány na vzorkování IQP [21] , kde je potřeba pouze hypotéza, že průměrná a nejhorší případová složitost problému je stejná.

Superpolynomiální zrychlení

Následující algoritmy poskytují superpolynomiální zrychlení ve srovnání s nejznámějšími klasickými algoritmy [22] :

Shorův algoritmus pro celočíselnou faktorizaci

Tento algoritmus najde prvočíselnou faktorizaci n - bitového celého čísla v čase [4] , nejznámější klasický algoritmus vyžaduje čas a nejlepší horní hranici složitosti tohoto problému . Může také poskytnout zrychlení pro jakýkoli problém, který se scvrkává na faktorizaci celého čísla , včetně problému, zda skupiny matic patří do polí lichého řádu.

Pro kvantové výpočty je tento algoritmus důležitý prakticky i historicky. Stal se prvním polynomiálním kvantovým algoritmem navrženým pro problém, který je pro klasické počítače považován za obtížný [4] . Důvěra v tuto složitost je tak silná, že bezpečnost dnes nejběžnějšího šifrovacího protokolu RSA je založena na faktorizačním algoritmu [23] . Kvantový počítač, který úspěšně a reprodukovatelně spustí tento algoritmus, může prolomit tento šifrovací systém [24] . Toto riziko hackerů se nazývá problém Y2Q, podobně jako problém Y2K , problém Y2K .

Vzorkování bosonů

Toto výpočetní paradigma je založeno na identických fotonech zasílaných lineární optickou sítí a může vyřešit určité problémy se vzorkováním a vyhledáváním, které jsou za předpokladu více hypotéz pro klasické počítače neřešitelné [25] . Přesto se ukázalo, že vzorkování bosonů v systému s dostatečně velkými ztrátami a šumem lze efektivně simulovat [26] .

Dosud největší experimentální implementace bosonového vzorkování má 6 módů, a proto může zpracovávat až 6 fotonů současně [27] . Nejlepší klasický algoritmus pro modelování bosonového vzorkování běží v řádu času pro systém s n fotony a m výstupními režimy [28] . BosonSampling je open source R  implementace algoritmu . Algoritmus dává odhad 50 fotonů , což je nezbytné k prokázání kvantové převahy pomocí bosonového vzorkování.

Vzorkování výstupní distribuce náhodných kvantových obvodů

Nejznámější algoritmus pro simulaci libovolného náhodného kvantového obvodu vyžaduje čas, který se exponenciálně mění s počtem qubitů , na základě čehož jedna skupina výzkumníků odhaduje, že asi 50 qubitů může stačit k prokázání kvantové převahy [9] . Google oznámil svůj záměr demonstrovat kvantovou nadvládu do konce roku 2017 vytvořením a spuštěním 49 -qubitového čipu, který dokáže v rozumném čase vzorkovat distribuce, které nejsou dostupné pro žádné moderní klasické počítače [5] . Ale největší simulace kvantových obvodů úspěšně provedená na superpočítači má 56 qubitů . Proto může být nutné zvýšit počet qubitů požadovaných k prokázání kvantové převahy [7] .

Kritika

Kvantové počítače jsou kvůli dekoherenci a šumu mnohem náchylnější k chybám než klasické počítače . Věta o prahu říká, že hlučný kvantový počítač může použít kvantové kódy opravující chyby [29] [30] k simulaci nehlučného kvantového počítače za předpokladu, že chyba zavedená v každém počítačovém cyklu je menší než určité číslo. Numerické simulace ukazují, že toto číslo může dosáhnout 3 % [31] .

Není však známo, jak se budou zdroje potřebné pro opravu chyb škálovat s počtem qubitů . Skeptici[ co? ] naznačují, že chování šumu je ve škálovatelných kvantových systémech neznámé jako potenciální překážky pro úspěšnou implementaci kvantového počítání a demonstraci kvantové nadřazenosti.

Viz také

Poznámky

  1. ↑ Anargyros; papageorgiou. Measures of quantum computing speedup  (anglicky)  // Physical Review A  : journal. - 2013. - 12. srpna ( roč. 88 , č. 2 ). — S. 022316 . — ISSN 1050-2947 . - doi : 10.1103/PhysRevA.88.022316 . - . - arXiv : 1307,7488 .
  2. ↑ Manin, Yu. I. Vychislimoe i nevychislimoe  (neopr.) . - Sov.Radio, 1980. - S. 13-15.
  3. ↑ Richard P.; Feynman. Simulace fyziky s počítači  // International  Journal of Theoretical Physics : deník. - 1982. - 1. června ( roč. 21 , č. 6-7 ). - str. 467-488 . — ISSN 0020-7748 . - doi : 10.1007/BF02650179 . - .
  4. ↑ 1 2 3 P.; Shor. Polynomiální-časové algoritmy pro primární faktorizaci a diskrétní logaritmy na kvantovém počítači  (anglicky)  // SIAM Review: journal. - 1999. - 1. ledna ( roč. 41 , č. 2 ). - str. 303-332 . — ISSN 0036-1445 . - doi : 10.1137/S0036144598347011 . - . — arXiv : quant-ph/9508027 .
  5. ↑ 1 2 Google plánuje demonstrovat nadřazenost kvantové výpočetní techniky , IEEE Spectrum: Technology, Engineering and Science News . Archivováno z originálu 25. dubna 2021. Staženo 11. ledna 2018.
  6. ↑ CES 2018: 49-Qubitový čip společnosti Intel usiluje o kvantovou nadvládu , IEEE Spectrum: Technology, Engineering and Science News . Archivováno z originálu 23. března 2021. Staženo 22. července 2017.
  7. ↑ 1 2 Plány společnosti Google týkající se kvantových počítačů ohrožené křivkou IBM (20. října 2017). Získáno 22. října 2017. Archivováno z originálu 25. ledna 2021.
  8. ↑ Harris . Google pověřil NASA, aby mu pomohla prokázat kvantovou nadřazenost během měsíců  , MIT Technology Review . Archivováno 10. března 2020. Staženo 30. listopadu 2018.
  9. ↑ 12 Sergio ; Boixo. Charakterizace kvantové nadřazenosti v krátkodobých zařízeních  // Nature Physics  : časopis  . - 2018. - 23. dubna ( roč. 14 , č. 6 ). - S. 595-600 . - doi : 10.1038/s41567-018-0124-x . - arXiv : 1608.00263 .
  10. ↑ https://www.scientificamerican.com/article/a-new-law-suggests-quantum-supremacy-could-happen-this-year/ Archivováno 2. března 2021 na Wayback Machine Nový „zákon“ navrhuje kvantovou nadřazenost Mohlo by se stát tento rok] , Scientific American, Daily Digest, 21. června 2019
  11. ↑ Google tvrdí, že dosáhl kvantové převahy  , The Financial Times  (21. září 2019). Archivováno z originálu 29. dubna 2021. Staženo 23. října 2019.
  12. ↑ Karpukhin, Vladimir The Financial Times: Google oznámil vytvoření nejvýkonnějšího kvantového počítače, ale poté smazal zprávu - Technologies on TJ . TJ (21. 9. 2019). Získáno 23. října 2019. Archivováno z originálu dne 23. října 2019.
  13. ↑ Frank Arute, Kunal Arya, Ryan Babbush, Dave Bacon, Joseph C. Bardin. Kvantová nadvláda pomocí programovatelného supravodivého procesoru   // Nature . - 2019. - říjen ( výr. 7779 , č. 574 ). - S. 505-510 . — ISSN 1476-4687 . - doi : 10.1038/s41586-019-1666-5 . Archivováno z originálu 23. října 2019.
  14. ↑ Co Google vs. Debata IBM o kvantové nadřazenosti znamená | ZDNet . www.zdnet.com . Získáno 12. února 2020. Archivováno z originálu dne 5. března 2020.
  15. ↑ O „Kvantové nadřazenosti“ . IBM Research Blog (22. října 2019). Získáno 24. října 2019. Archivováno z originálu 11. listopadu 2021.
  16. ↑ Google tvrdí, že dosáhne kvantové nadřazenosti – IBM tlačí zpět . NPR.org . Získáno 24. října 2019. Archivováno z originálu dne 23. října 2019.
  17. ↑ Kvantový počítač na bázi světla Jiuzhang dosáhl kvantové převahy | vědecké novinky . Získáno 4. prosince 2020. Archivováno z originálu dne 2. listopadu 2021.
  18. ↑ Watrous, John. Quantum Computational Complexity // Encyclopedia of Complexity and Systems Science  (anglicky) . - Springer New York, 2009. - S. 7174-7201. — ISBN 9780387758886 . - doi : 10.1007/978-0-387-30440-3_428 .
  19. ↑ Umesh; Vazirani. A Survey of Quantum Complexity Theory  (neopr.)  // Proceedings of Symposia in Applied Mathematics.
  20. ↑ AP; Lund. Problémy s kvantovým vzorkováním, BosonSampling a kvantová nadřazenost  //  Npj Quantum Information : deník. - 2017. - 13. dubna ( díl 3 , č. 1 ). - ISSN 2056-6387 . - doi : 10.1038/s41534-017-0018-2 . — . - arXiv : 1702.03061 .
  21. ↑ Michael J.; Bremner. Složitost průměrného případu versus přibližná simulace dojíždění kvantových výpočtů  // Physical Review Letters  : journal  . - 2016. - 18. srpna ( roč. 117 , č. 8 ). — ISSN 0031-9007 . - doi : 10.1103/PhysRevLett.117.080501 . - . - arXiv : 1504,07999 . — PMID 27588839 .
  22. ↑ Jordánsko. Quantum Algorithm Zoo (nedostupný odkaz) . math.nist.gov . Získáno 29. července 2017. Archivováno z originálu dne 29. dubna 2018. 
  23. ↑ RL; Rivest. Metoda získávání digitálních podpisů a kryptosystémů s veřejným klíčem  (anglicky)  // Commun. ACM  : deník. - 1978. - únor ( roč. 21 , č. 2 ). - S. 120-126 . — ISSN 0001-0782 . - doi : 10.1145/359340.359342 .
  24. ↑ Bernstein, Daniel. Post-kvantová kryptografie  (neopr.) .
  25. ↑ Aaronson, Scott. Výpočetní složitost lineární  optiky .
  26. ↑ Saleh; Rahimi-Keshari. Dostatečné podmínky pro efektivní klasickou simulaci kvantové optiky  (anglicky)  // Physical Review X  : journal. - 2016. - 20. června ( roč. 6 , č. 2 ). — S. 021039 . - doi : 10.1103/PhysRevX.6.021039 . - . - arXiv : 1511.06526 .
  27. ↑ Jacques; karolan. Univerzální lineární optika  (anglicky)  // Science. - 2015. - 14. srpna ( roč. 349 , č. 6249 ). - str. 711-716 . — ISSN 0036-8075 . - doi : 10.1126/science.aab3642 . - arXiv : 1505.01182 . — PMID 26160375 .
  28. ↑ Alex; Neville. Žádná bezprostřední kvantová převaha díky bosonovému vzorkování  // Nature Physics  : journal  . - 2017. - 2. října ( roč. 13 , č. 12 ). - S. 1153-1157 . — ISSN 1745-2473 . - doi : 10.1038/nphys4270 . - arXiv : 1705.00686 .
  29. ↑ Peter W.; Shor. Schéma pro snížení dekoherence v paměti kvantového počítače  // Physical Review A  : journal  . - 1995. - 1. října ( roč. 52 , č. 4 ). - P.R2493-R2496 . - doi : 10.1103/PhysRevA.52.R2493 . - .
  30. ↑ AM; Steane. Error Correcting Codes in Quantum Theory  (anglicky)  // Physical Review Letters  : journal. - 1996. - 29. července ( roč. 77 , č. 5 ). - str. 793-797 . - doi : 10.1103/PhysRevLett.77.793 . - . — PMID 10062908 .
  31. ↑ E.; Knill. Kvantové počítání s realisticky hlučnými zařízeními  (anglicky)  // Nature. - 2005. - 3. března ( roč. 434 , č. 7029 ). - str. 39-44 . — ISSN 0028-0836 . - doi : 10.1038/nature03350 . — . — arXiv : quant-ph/0410199 . — PMID 15744292 .