Kvantumfölény

Az oldal jelenlegi verzióját még nem ellenőrizték tapasztalt közreműködők, és jelentősen eltérhet a 2020. október 8-án felülvizsgált verziótól ; az ellenőrzések 8 szerkesztést igényelnek .

A kvantumfölény a kvantumszámítógépek  azon képessége, hogy olyan problémákat oldjanak meg, amelyeket a klasszikus számítógépek gyakorlatilag nem képesek megoldani. A kvantum előnye a gyorsabb problémamegoldás képessége. Ez a számítási komplexitáselmélet szempontjából általában szuperpolinomiális gyorsítást jelent a legismertebb vagy lehetséges klasszikus algoritmushoz képest [1] . A kifejezést John Preskill népszerűsítette, de a kvantumszámítási előny fogalma, különösen a kvantumrendszerek szimulációjában, egészen a Yuri Manin (1980) [ 2] és Richard Feynman (1981) kvantumszámítási javaslatáig nyúlik vissza. ] .

A kvantumszámítógépen polinomiális időben futó Shor -algoritmus egész számok faktorizálására ilyen szuperpolinomiális gyorsulást biztosít a legismertebb klasszikus algoritmushoz képest [4] . Bár még nem bizonyított, a faktorizáció kihívásnak számít a klasszikus erőforrások használatakor. A kvantumfölény végleges kimutatásának gyakori problémája annak bizonyítása, hogy mit nem lehet a klasszikus számításokkal megtenni. Ez hatással van az Aaronson és Arkhipov bozon mintavételi javaslatára, a D-Wave speciális problémáira a frusztrált klaszter hurkokra és a véletlenszerű kvantumáramkörök kimeneti mintavételére .

Az egész számok faktorizálásához hasonlóan a véletlenszerű kvantumáramkörök kimeneti eloszlásának mintavételezésének problémája is nehéznek tűnik a klasszikus számítógépek számára a bonyolultságra vonatkozó ésszerű feltételezések alapján.

Történelem

A Google korábban bejelentette, hogy 2017 végére 49 szupravezető qubitből álló tömb segítségével demonstrálja a kvantumfölényt [5] . 2018 január elejétől azonban csak az Intel jelentett be ilyen hardvert [6] .

2017 októberében az IBM egy 56 qubit szimulációját mutatta be egy hagyományos szuperszámítógépen, ami megnövelte a kvantumfölényhez szükséges qubitek számát [7] .

2018 novemberében a Google bejelentette, hogy partnerséget köt a NASA -val, amelyben a NASA "elemzi a Google kvantumprocesszorain és... felsőbbrendűségén futó kvantumáramkörök eredményeit" [8] .

Egy 2018-as elméleti tanulmány azt sugallja, hogy a kvantumfölény elérhető „egy 7 × 7 qubites és körülbelül 40 órajeles kétdimenziós tömbön”, de ha a hibaarány elég alacsony [9] .

2019. június 21-én a Scientific American azt javasolta, hogy a Neven-törvény szerint a kvantumfölény 2019-ben valósul meg [10] .

2019. szeptember 20-án a Financial Times arról számolt be, hogy "a Google azt állítja, hogy kvantumfölényt ért el egy 54 qubitből álló tömbön, amelyből 53 volt működőképes, és 200 másodperc alatt végeztek számításokat, ami körülbelül 10 000 évbe telne egy hagyományos szuperszámítógépnek. " [11] . Erről kezdetben a NASA honlapján jelent meg egy jelentés, de a megjelenés után nem sokkal törölték [12] . Később, október 23-án hivatalosan is bejelentették a kvantumfölényt [13] . Az IBM szakértői azonban a bemutatott adatok elemzése után jelezték, hogy bizonyos pillanatok nem optimálisak, és valójában egy ilyen számítás egy klasszikus szuperszámítógépen csak 2,5 napot vesz igénybe a bejelentett 10 000 év helyett. [14] [15] [16]

2020. december 3-án kínai tudósok arról számoltak be, hogy az összegabalyodott fotonokkal működő Jiuzhang kvantumszámítógépük kvantumfölényt ért el. 200 másodperc alatt sikeresen kiszámítottak egy problémát, amelynek megoldása a világ leggyorsabb klasszikus számítógépének több mint félmilliárd évbe telne [17] .

Számítási összetettség

A komplexitás kérdése arra utal, hogy a probléma megoldásához szükséges erőforrás mennyisége hogyan skálázódik a bemenet méretével. A klasszikus számítási komplexitáselmélet kiterjesztéseként a kvantumkomplexitáselmélet egy univerzális kvantumszámítógép működését írja le anélkül, hogy figyelembe venné létrehozásának bonyolultságát vagy a dekoherencia és a zaj hatásainak kiküszöbölését [18] . Mivel a kvantuminformáció a klasszikus információ általánosítása , a kvantumszámítógép bármilyen klasszikus algoritmust képes szimulálni .

A kvantumpolinomiális időkorlátos hiba (BQP) problémák összetettségi osztálya olyan döntési problémák osztálya, amelyek polinomiális időben megoldhatók univerzális kvantumszámítógéppel . A BPQ osztály hierarchiával kapcsolódik a klasszikus komplexitási osztályokhoz [19] . Továbbra is nyitott kérdés, hogy szigorúak-e ezek a beágyazások.

Ellentétben az igen vagy nem választ igénylő döntési problémákkal, a mintavételi problémák valószínűségi eloszlásból való mintavételt igényelnek [20] . Ha létezik egy klasszikus algoritmus , amely képes mintát venni egy tetszőleges kvantumáramkör kimenetéből , akkor a polinomiális hierarchia a harmadik szintre kerül, amit nagyon valószínűtlennek tartanak. A BosonSampling egy specifikusabb javaslat, amelynek klasszikus összetettsége a komplex elemekből álló nagy mátrix állandójának  kiszámításának problémájának megoldhatatlanságától függ , ami P#-teljes probléma. Az állítás levezetéséhez használt érveket az IQP mintavételnél is alkalmazták [21] , ahol csak az a hipotézis szükséges, hogy a probléma átlagos és legrosszabb eset komplexitása megegyezik.

Szuperpolinomiális gyorsulás

A következő algoritmusok szuperpolinomiális gyorsítást biztosítanak a legismertebb klasszikus algoritmusokhoz képest [22] :

Shor algoritmusa egész számok faktorizálásához

Ez az algoritmus megtalálja egy n bites egész szám prímtényezősségét időben [4] , a leghíresebb klasszikus algoritmushoz idő kell, és a probléma összetettségének legjobb felső korlátja . Ezenkívül felgyorsíthat minden olyan problémát, amely az egész számok faktorizálására vezethető vissza , beleértve azt a problémát is, hogy a mátrixcsoportok páratlan sorrendű mezőkhöz tartoznak -e .

A kvantumszámításhoz ez az algoritmus gyakorlatilag és történetileg egyaránt fontos. Ez lett az első polinomiális kvantumalgoritmus , amelyet a klasszikus számítógépek számára nehéznek tartott probléma megoldására javasoltak [4] . Az ebbe az összetettségbe vetett bizalom olyan erős, hogy a manapság legelterjedtebb RSA titkosítási protokoll biztonsága a faktorizációs algoritmuson alapul [23] . Az ezt az algoritmust sikeresen és reprodukálhatóan futtató kvantumszámítógép feltörheti ezt a titkosítási rendszert [24] . Ezt a hackelési kockázatot Y2Q problémának nevezik, hasonlóan az Y2K problémához, az Y2K problémához .

Bozon mintavétel

Ez a számítási paradigma egy lineáris optikai hálózaton keresztül küldött azonos fotonokon alapul, és meg tud oldani bizonyos mintavételi és keresési problémákat, amelyek több hipotézist feltételezve a klasszikus számítógépek számára megoldhatatlanok [25] . Ennek ellenére bebizonyosodott, hogy a bozon mintavételezése egy kellően nagy veszteséggel és zajjal rendelkező rendszerben hatékonyan szimulálható [26] .

A bozon-mintavétel eddigi legnagyobb kísérleti megvalósítása 6 üzemmóddal rendelkezik, ezért akár 6 fotont is képes feldolgozni egyidejűleg [27] . A legjobb klasszikus algoritmus a bozon-mintavételezés modellezésére egy n fotonnal és m kimeneti móddal rendelkező rendszer esetén sorrendben fut [28] . A BosonSampling az algoritmus nyílt forráskódú R  implementációja . Az algoritmus 50 fotonra ad becslést , ami szükséges a kvantumfölény bozonmintavétellel történő demonstrálásához.

Véletlenszerű kvantumáramkörök kimeneti eloszlásának mintavételezése

Egy tetszőleges véletlenszerű kvantumáramkör szimulálására szolgáló legismertebb algoritmushoz olyan időre van szükség, amely exponenciálisan skálázódik a qubitek számával , ami alapján a kutatók egy csoportja úgy becsüli, hogy körülbelül 50 qubit elegendő lehet a kvantumfölény kimutatásához [9] . A Google bejelentette szándékát, hogy 2017 végéig demonstrálja a kvantumfölényt egy 49 qubit-es chip létrehozásával és elindításával, amely ésszerű időn belül képes mintát venni olyan disztribúciókból, amelyekhez egyetlen modern klasszikus számítógép sem fér hozzá [5] . De a szuperszámítógépen sikeresen végrehajtott kvantumáramkörök legnagyobb szimulációja 56 qubittel rendelkezik . Ezért szükség lehet a kvantumfölény kimutatásához szükséges qubitek számának növelésére [7] .

Kritika

A kvantumszámítógépek a dekoherencia és a zaj miatt sokkal hibásabbak, mint a klasszikus számítógépek . A küszöbtétel kimondja, hogy egy zajos kvantumszámítógép hibajavító kvantumkódokkal [29] [30] képes szimulálni egy nem zajos kvantumszámítógépet, feltételezve, hogy az egyes számítógépes ciklusokban fellépő hiba kisebb egy bizonyos számnál. Numerikus szimulációk azt mutatják, hogy ez a szám elérheti a 3%-ot [31] .

Nem ismert azonban, hogy a hibajavításhoz szükséges erőforrások hogyan skálázódnak a qubitek számával . Szkeptikusok[ mi? ] azt mutatják, hogy a zaj viselkedése ismeretlen a skálázható kvantumrendszerekben, mint potenciális akadálya a kvantumszámítástechnika sikeres megvalósításának és a kvantumfölény kimutatásának.

Lásd még

Jegyzetek

  1. ↑ Anargyros; papageorgiou. Measures of quantum computing speedup  (angol)  // Physical Review A  : Journal. - 2013. - augusztus 12. ( 88. évf. , 2. sz.). — P. 022316 . — ISSN 1050-2947 . - doi : 10.1103/PhysRevA.88.022316 . - . - arXiv : 1307.7488 .
  2. ↑ Manin, Yu. I. Vychislimoe i nevychislimoe  (neopr.) . - Szov.Rádió, 1980. - S. 13-15.
  3. ↑ Richard P.; Feynman. Fizika szimulációja számítógépekkel  // International  Journal of Theoretical Physics : folyóirat. - 1982. - június 1. ( 21. évf. , 6-7. sz. ). - P. 467-488 . — ISSN 0020-7748 . - doi : 10.1007/BF02650179 . - Iránykód .
  4. ↑ 1 2 3 P.; Shor. Polinom-idő algoritmusok prímfaktorizáláshoz és diszkrét logaritmusokhoz kvantumszámítógépen  (angol)  // SIAM Review : folyóirat. - 1999. - január 1. ( 41. köt. , 2. sz.). - P. 303-332 . — ISSN 0036-1445 . - doi : 10.1137/S0036144598347011 . - . — arXiv : quant-ph/9508027 .
  5. ↑ 1 2 A Google azt tervezi, hogy demonstrálja a kvantumszámítástechnika felsőbbrendűségét , IEEE Spectrum: Technology, Engineering and Science News . Archiválva az eredetiből 2021. április 25-én. Letöltve: 2018. január 11.
  6. ↑ CES 2018: Az Intel 49 Qubit chipes felvételei a kvantumfölényhez , IEEE Spectrum: technológiai, mérnöki és tudományos hírek . Archiválva az eredetiből 2021. március 23-án. Letöltve: 2017. július 22.
  7. ↑ 1 2 A Google kvantumszámítási terveit az IBM Curveball fenyegeti (2017. október 20.). Letöltve: 2017. október 22. Az eredetiből archiválva : 2021. január 25.
  8. ↑ Harris . A Google felkérte a NASA-t, hogy hónapokon belül bebizonyítsa a kvantumfölényt  ( MIT Technology Review ). Archiválva : 2020. március 10. Letöltve: 2018. november 30.
  9. ↑ 12 Sergio ; Boixo. A kvantumfölény jellemzése rövid távú eszközökben  // Nature Physics  : Journal  . - 2018. - április 23. ( 14. évf. , 6. sz.). - P. 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/ Archiválva : 2021. március 2. a Wayback Machine -nél Egy új „törvény” a kvantumfölényt javasolja Megtörténhet ebben az évben] , Scientific American, Daily Digest, 2019. június 21.
  11. ↑ A Google azt állítja, hogy elérte a kvantumfölényt  , The Financial Times  (2019. szeptember 21.). Archiválva az eredetiből 2021. április 29-én. Letöltve: 2019. október 23.
  12. ↑ Karpukhin, Vladimir The Financial Times: A Google bejelentette a legerősebb kvantumszámítógép megalkotását, de aztán törölte a jelentést – Technologies on TJ . TJ (2019. szeptember 21.). Letöltve: 2019. október 23. Az eredetiből archiválva : 2019. október 23.
  13. ↑ Frank Arute, Kunal Arya, Ryan Babbush, Dave Bacon, Joseph C. Bardin. Kvantumfölény programozható szupravezető processzor  segítségével  // Természet . - 2019. - október ( 7779. sz. , 574. sz.). - P. 505-510 . — ISSN 1476-4687 . - doi : 10.1038/s41586-019-1666-5 . Archiválva az eredetiből: 2019. október 23.
  14. ↑ Mi a Google vs. Az IBM vita a kvantumfölényről azt jelenti, | ZDNet . www.zdnet.com . Letöltve: 2020. február 12. Az eredetiből archiválva : 2020. március 5.
  15. ↑ A "Kvantum felsőbbségről" . IBM Research Blog (2019. október 22.). Letöltve: 2019. október 24. Az eredetiből archiválva : 2021. november 11.
  16. ↑ A Google azt állítja, hogy el akarja érni a kvantumfölényt – az IBM visszalép . NPR.org . Letöltve: 2019. október 24. Az eredetiből archiválva : 2019. október 23.
  17. ↑ A fényalapú kvantumszámítógép, a Jiuzhang eléri a kvantumfölényt | tudományos hírek . Letöltve: 2020. december 4. Az eredetiből archiválva : 2021. november 2.
  18. ↑ Vizes, John. Kvantumszámítási komplexitás // Encyclopedia of Complexity and Systems Science  (angol) . - Springer New York, 2009. - P. 7174-7201. — ISBN 9780387758886 . - doi : 10.1007/978-0-387-30440-3_428 .
  19. ↑ Umesh; Vazirani. A Quantum Complexity Theory felmérése  (neopr.)  // Proceedings of Symposia in Applied Mathematics.
  20. ↑ AP; Lund. Kvantummintavételi problémák, BosonMintavétel és kvantumfölény  //  Npj Quantum Information : folyóirat. - 2017. - április 13. ( 3. köt. , 1. sz.). - ISSN 2056-6387 . - doi : 10.1038/s41534-017-0018-2 . — Iránykód . - arXiv : 1702.03061 .
  21. ↑ Michael J.; Bremner. Az esetek átlagos összetettsége versus ingázási kvantumszámítások hozzávetőleges szimulációja  // Physical Review Letters  : folyóirat  . - 2016. - augusztus 18. ( 117. évf. , 8. sz.). — ISSN 0031-9007 . - doi : 10.1103/PhysRevLett.117.080501 . - . - arXiv : 1504.07999 . — PMID 27588839 .
  22. ↑ Jordánia. Quantum Algorithm Zoo (nem elérhető link) . math.nist.gov . Letöltve: 2017. július 29. Az eredetiből archiválva : 2018. április 29. 
  23. ↑ RL; Rivest. Módszer digitális aláírások és nyilvános kulcsú kriptorendszerek megszerzésére  (angol)  // Commun. ACM  : folyóirat. - 1978. - február ( 21. évf. , 2. sz.). - 120-126 . o . — ISSN 0001-0782 . - doi : 10.1145/359340.359342 .
  24. ↑ Bernstein, Daniel. Post-kvantum kriptográfia  (neopr.) .
  25. ↑ Aaronson, Scott. A lineáris  optika számítási összetettsége .
  26. ↑ Száleh; Rahimi-Keshari. Elegendő feltételek a kvantumoptika hatékony klasszikus szimulációjához  (angol)  // Physical Review X  : folyóirat. - 2016. - június 20. ( 6. évf. , 2. sz.). — P. 021039 . - doi : 10.1103/PhysRevX.6.021039 . - Iránykód . - arXiv : 1511.06526 .
  27. ↑ Jacques; carolan. Univerzális lineáris optika  (angol)  // Tudomány. - 2015. - augusztus 14. ( 349. évf. , 6249. sz.). - P. 711-716 . — ISSN 0036-8075 . - doi : 10.1126/science.aab3642 . - arXiv : 1505.01182 . — PMID 26160375 .
  28. ↑ Alex; Neville. Nincs küszöbön álló kvantumfölény a bozon mintavételével  // Nature Physics  : Journal  . - 2017. - október 2. ( 13. évf. , 12. sz.). - P. 1153-1157 . — ISSN 1745-2473 . - doi : 10.1038/nphys4270 . - arXiv : 1705.00686 .
  29. ↑ Peter W.; Shor. Sém a dekoherencia csökkentésére a kvantumszámítógép memóriájában  // Physical Review A  : Journal  . - 1995. - október 1. ( 52. évf. , 4. sz.). - P.R2493-R2496 . - doi : 10.1103/PhysRevA.52.R2493 . - .
  30. ↑ AM; Steane. Error Correcting Codes in Quantum Theory  (angol)  // Physical Review Letters  : Journal. - 1996. - július 29. ( 77. köt. , 5. sz.). - P. 793-797 . - doi : 10.1103/PhysRevLett.77.793 . - . — PMID 10062908 .
  31. ↑ E.; Knill. Kvantumszámítás valósághűen zajos eszközökkel  (angol)  // Természet. - 2005. - március 3. ( 434. köt. , 7029. sz.). - P. 39-44 . — ISSN 0028-0836 . - doi : 10.1038/nature03350 . — . — arXiv : quant-ph/0410199 . — PMID 15744292 .