Supremația cuantică

Versiunea actuală a paginii nu a fost încă examinată de colaboratori experimentați și poate diferi semnificativ de versiunea revizuită pe 8 octombrie 2020; verificările necesită 8 modificări .

Supremația cuantică  este capacitatea dispozitivelor de calcul cuantic de a rezolva probleme pe care computerele clasice sunt practic incapabile să le rezolve. Avantajul cuantic este capacitatea de a rezolva probleme mai rapid. Din punctul de vedere al teoriei complexității computaționale, aceasta înseamnă de obicei furnizarea unei accelerații superpolinomiale în comparație cu cel mai cunoscut sau posibil algoritm clasic [1] . Termenul a fost popularizat de John Preskill , dar conceptul de avantaj computațional cuantic, în special în simularea sistemelor cuantice, merge înapoi la propunerea de calcul cuantic dată de Yuri Manin (1980) [2] șiRichard Feynman (1981) [3] .

Algoritmul lui Shor pentru factorizarea întregilor, care rulează în timp polinomial pe un computer cuantic, oferă o astfel de accelerare superpolinomială în comparație cu cel mai cunoscut algoritm clasic [4] . Deși nu a fost încă dovedit, factorizarea este considerată o provocare atunci când se utilizează resursele clasice. Dificultatea de a demonstra ceea ce nu se poate face cu calculul clasic este o problemă comună pentru demonstrarea definitivă a superiorității cuantice. De asemenea, influențează propunerea de eșantionare a bosonilor Aaronson și Arkhipov, problemele specializate ale D-Wave despre buclele de cluster frustrate și eșantionarea de ieșire pentru circuite cuantice aleatoare .

La fel ca factorizarea întregi, problema eșantionării distribuțiilor de ieșire ale circuitelor cuantice aleatoare este considerată dificilă pentru calculatoarele clasice, pe baza ipotezelor rezonabile despre complexitate.

Istorie

Google a anunțat anterior planuri de a demonstra supremația cuantică până la sfârșitul anului 2017 folosind o serie de 49 de qubiți supraconductori [5] . Cu toate acestea, de la începutul lunii ianuarie 2018, doar Intel a anunțat un astfel de hardware [6] .

În octombrie 2017, IBM a demonstrat o simulare de 56 de qubiți pe un supercomputer convențional, crescând numărul de qubiți necesari pentru supremația cuantică [7] .

În noiembrie 2018, Google a anunțat un parteneriat cu NASA în care NASA va „analiza rezultatele din circuitele cuantice rulate pe procesoarele cuantice ale Google și... superioritatea” [8] .

O lucrare teoretică din 2018 sugerează că supremația cuantică poate fi atinsă pe „o matrice bidimensională de 7 × 7 qubiți și aproximativ 40 de cicluri de ceas”, dar dacă rata de eroare este suficient de mică [9] .

Pe 21 iunie 2019, Scientific American a sugerat că, conform legii lui Neven , supremația cuantică va fi atinsă în 2019 [10] .

Pe 20 septembrie 2019, Financial Times a raportat că „Google susține că a atins supremația cuantică pe o matrice de 54 de qubiți, dintre care 53 erau funcționali și folosiți pentru a efectua calcule în 200 de secunde, ceea ce ar dura aproximativ 10.000 de ani pentru un supercomputer convențional. „ [11] . Inițial, un raport despre acest lucru a apărut pe site-ul NASA, dar a fost șters la scurt timp după publicare [12] . Ulterior, pe 23 octombrie, supremația cuantică a fost anunțată oficial [13] . Cu toate acestea, experții de la IBM, analizând datele prezentate, au indicat că unele momente nu sunt optime și că de fapt un astfel de calcul pe un supercomputer clasic va dura doar 2,5 zile în loc de cei 10.000 de ani declarați. [14] [15] [16]

Pe 3 decembrie 2020, oamenii de știință chinezi au raportat că computerul lor cuantic Jiuzhang , alimentat de fotoni încâlciți, a atins supremația cuantică. În 200 de secunde, ei au calculat cu succes o problemă care ar fi nevoie de mai mult de jumătate de miliard de ani pentru rezolvarea celui mai rapid computer clasic din lume [17] .

Complexitate computațională

Problema complexității se referă la modul în care cantitatea de resursă necesară pentru a rezolva o problemă se scalează în funcție de dimensiunea intrării. Ca o extensie a teoriei clasice a complexității computaționale , teoria complexității cuantice descrie funcționarea unui computer cuantic universal fără a lua în considerare complexitatea creării sau eliminării efectelor decoerenței și zgomotului [18] . Deoarece informația cuantică este o generalizare a informațiilor clasice , un computer cuantic poate simula orice algoritm clasic .

Clasa de complexitate a problemelor de eroare limitată în timp polinomial cuantic (BQP) este o clasă de probleme de decizie care poate fi rezolvată în timp polinomial de un computer cuantic universal . Clasa BPQ este legată de clasele clasice de complexitate printr-o ierarhie [19] . Rămâne o întrebare deschisă dacă vreuna dintre aceste înglobări este strictă.

Spre deosebire de problemele de decizie care necesită un răspuns da sau nu, problemele de eșantionare necesită eșantionare din distribuții de probabilitate [20] . Dacă există un algoritm clasic care poate eșantiona ieșirea unui circuit cuantic arbitrar , ierarhia polinomială se va muta la al treilea nivel, ceea ce este considerat foarte puțin probabil. BosonSampling  este o propunere mai specifică a cărei complexitate clasică depinde de imposibilitatea de rezolvare a problemei calculării permanentei unei matrice mari cu elemente complexe, care este o problemă P#-completă. Argumentele folosite pentru a deriva această afirmație au fost aplicate și eșantionării IQP [21] , unde este necesară doar ipoteza că complexitatea medie și cel mai rău caz a problemei este aceeași.

Accelerația superpolinomială

Următorii algoritmi oferă o accelerare superpolinomială în comparație cu cei mai cunoscuți algoritmi clasici [22] :

Algoritmul lui Shor pentru factorizarea întregilor

Acest algoritm găsește factorizarea primă a unui număr întreg de n biți în timp [4] , cel mai faimos algoritm clasic necesită timp și cea mai bună limită superioară a complexității acestei probleme . De asemenea, poate oferi o accelerare pentru orice problemă care se reduce la factorizarea întregului , inclusiv problema dacă grupurile de matrice aparțin câmpurilor de ordin impar.

Pentru calculul cuantic, acest algoritm este important atât din punct de vedere practic, cât și din punct de vedere istoric. A devenit primul algoritm cuantic polinomial propus pentru o problemă care este considerată dificilă pentru calculatoarele clasice [4] . Încrederea în această complexitate este atât de puternică încât securitatea celui mai comun protocol de criptare RSA astăzi se bazează pe algoritmul de factorizare [23] . Un computer cuantic care rulează cu succes și reproductibil acest algoritm poate sparge acest sistem de criptare [24] . Acest risc de hacking se numește problema Y2Q, similar cu problema Y2K , problema Y2K .

Eșantionarea bosonilor

Această paradigmă de calcul se bazează pe fotoni identici trimiși printr-o rețea optică liniară și poate rezolva anumite probleme de eșantionare și căutare care, presupunând mai multe ipoteze, sunt de nerezolvat pentru calculatoarele clasice [25] . Cu toate acestea, sa demonstrat că eșantionarea bosonilor într-un sistem cu pierderi și zgomot suficient de mari poate fi simulată eficient [26] .

Cea mai mare implementare experimentală a eșantionării bosonilor de până acum are 6 moduri și, prin urmare, poate procesa până la 6 fotoni simultan [27] . Cel mai bun algoritm clasic pentru modelarea eșantionării bosonilor rulează în timp pentru un sistem cu n fotoni și m moduri de ieșire [28] . BosonSampling este o implementare open source R  a algoritmului . Algoritmul oferă o estimare de 50 de fotoni , ceea ce este necesar pentru a demonstra superioritatea cuantică folosind eșantionarea bosonilor.

Eșantionarea distribuției de ieșire a circuitelor cuantice aleatoare

Cel mai cunoscut algoritm pentru simularea unui circuit cuantic aleatoriu arbitrar necesită timp care se scalează exponențial cu numărul de qubiți , pe baza căruia un grup de cercetători estimează că aproximativ 50 de qubiți ar putea fi suficienți pentru a demonstra superioritatea cuantică [9] . Google și-a anunțat intenția de a demonstra supremația cuantică până la sfârșitul anului 2017 prin crearea și lansarea unui cip de 49 de qubiți care poate eșantiona distribuții într-un timp rezonabil care sunt inaccesibile oricăror computere clasice moderne [5] . Dar cea mai mare simulare de circuite cuantice realizată cu succes pe un supercomputer are 56 de qubiți . Prin urmare, poate fi necesară creșterea numărului de qubiți necesari pentru a demonstra superioritatea cuantică [7] .

Critica

Calculatoarele cuantice sunt mult mai predispuse la erori decât computerele clasice din cauza decoerenței și a zgomotului. Teorema pragului afirmă că un computer cuantic zgomotos poate folosi coduri cuantice de corectare a erorilor [29] [30] pentru a simula un computer cuantic nezgomotos, presupunând că eroarea introdusă în fiecare ciclu de calculator este mai mică decât un anumit număr. Simulările numerice arată că acest număr poate ajunge la 3% [31] .

Cu toate acestea, nu se știe cum se vor scala resursele necesare pentru corectarea erorilor în funcție de numărul de qubiți . Sceptici[ ce? ] indică faptul că comportamentul zgomotului este necunoscut în sistemele cuantice scalabile ca potențiale bariere în calea implementării cu succes a calculului cuantic și a demonstrației supremației cuantice.

Vezi și

Note

  1. ↑ Anargyros; papageorgiou. Măsuri de accelerare a calculului cuantic  (engleză)  // Physical Review A  : jurnal. - 2013. - 12 august ( vol. 88 , nr. 2 ). — P. 022316 . — ISSN 1050-2947 . - doi : 10.1103/PhysRevA.88.022316 . - Cod . - arXiv : 1307,7488 .
  2. ↑ Manin, Yu. I. Vychislimoe i nevychislimoe  (neopr.) . - Sov.Radio, 1980. - S. 13-15.
  3. ↑ Richard P.; Feynman. Simularea fizicii cu calculatoare  //  Jurnalul Internațional de Fizică Teoretică : jurnal. - 1982. - 1 iunie ( vol. 21 , nr. 6-7 ). - P. 467-488 . — ISSN 0020-7748 . - doi : 10.1007/BF02650179 . - Cod biblic .
  4. ↑ 1 2 3 P.; Shor. Algoritmi polinomial-timp pentru factorizarea primului și logaritmii discreti pe un computer cuantic  (engleză)  // SIAM Review : jurnal. - 1999. - 1 ianuarie ( vol. 41 , nr. 2 ). - P. 303-332 . — ISSN 0036-1445 . - doi : 10.1137/S0036144598347011 . - Cod . — arXiv : quant-ph/9508027 .
  5. ↑ 1 2 Google intenționează să demonstreze supremația calculului cuantic , Spectrul IEEE: Știri despre tehnologie, inginerie și știință . Arhivat din original pe 25 aprilie 2021. Preluat la 11 ianuarie 2018.
  6. ↑ CES 2018: Intel 49-Qubit Chip Shoots for Quantum Supremacy , IEEE Spectrum: Technology, Engineering, and Science News . Arhivat din original pe 23 martie 2021. Preluat la 22 iulie 2017.
  7. ↑ 1 2 Planurile de calcul cuantic ale Google amenințate de IBM curveball (20 octombrie 2017). Preluat la 22 octombrie 2017. Arhivat din original la 25 ianuarie 2021.
  8. ↑ Harris . Google a solicitat NASA să o ajute să demonstreze supremația cuantică în câteva luni  , MIT Technology Review . Arhivat 10 martie 2020. Consultat la 30 noiembrie 2018.
  9. ↑ 12 Sergio ; Boixo. Caracterizarea supremației cuantice în dispozitive pe termen scurt  // Nature Physics  : journal  . - 2018. - 23 aprilie ( vol. 14 , nr. 6 ). - 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/ Arhivat 2 martie 2021 la Wayback Machine O nouă „lege” sugerează supremația cuantică Could Happen This Year] , Scientific American, Daily Digest, 21 iunie 2019
  11. ↑ Google pretinde că a atins supremația cuantică  , The Financial Times  (21 septembrie 2019). Arhivat din original pe 29 aprilie 2021. Preluat la 23 octombrie 2019.
  12. ↑ Karpukhin, Vladimir The Financial Times: Google a anunțat crearea celui mai puternic computer cuantic, dar apoi a șters raportul - Technologies on TJ . TJ (21 septembrie 2019). Preluat la 23 octombrie 2019. Arhivat din original la 23 octombrie 2019.
  13. ↑ Frank Arute, Kunal Arya, Ryan Babbush, Dave Bacon, Joseph C. Bardin. Supremația cuantică folosind un procesor supraconductor programabil   // Nature . - 2019. - Octombrie ( red. 7779 , nr. 574 ). - P. 505-510 . — ISSN 1476-4687 . - doi : 10.1038/s41586-019-1666-5 . Arhivat din original pe 23 octombrie 2019.
  14. ↑ Ce este Google vs. Dezbaterea IBM asupra supremației cuantice înseamnă | ZDNet . www.zdnet.com . Preluat la 12 februarie 2020. Arhivat din original la 5 martie 2020.
  15. ↑ Despre „Cuantum Supremacy” . IBM Research Blog (22 octombrie 2019). Preluat la 24 octombrie 2019. Arhivat din original la 11 noiembrie 2021.
  16. ↑ Google pretinde că va atinge supremația cuantică - IBM respinge . NPR.org . Preluat la 24 octombrie 2019. Arhivat din original la 23 octombrie 2019.
  17. ↑ Calculatorul cuantic bazat pe lumină Jiuzhang atinge supremația cuantică | știri științifice . Preluat la 4 decembrie 2020. Arhivat din original la 2 noiembrie 2021.
  18. ↑ Watrous, John. Complexitate computațională cuantică // Enciclopedia complexității și științei sistemelor  (engleză) . - Springer New York, 2009. - P. 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 Symposias in Applied Mathematics.
  20. ↑ AP; Lund. Probleme de eșantionare cuantică, BosonSampling și supremație cuantică  //  Npj Quantum Information : jurnal. - 2017. - 13 aprilie ( vol. 3 , nr. 1 ). - ISSN 2056-6387 . - doi : 10.1038/s41534-017-0018-2 . — Cod biblic . - arXiv : 1702.03061 .
  21. ↑ Michael J.; Bremner. Complexitatea medie a cazului versus simularea aproximativă a calculelor cuantice de navetă  // Physical Review Letters  : journal  . - 2016. - 18 august ( vol. 117 , nr. 8 ). — ISSN 0031-9007 . - doi : 10.1103/PhysRevLett.117.080501 . - Cod . - arXiv : 1504.07999 . — PMID 27588839 .
  22. ↑ Iordania. Quantum Algorithm Zoo (link indisponibil) . math.nist.gov . Consultat la 29 iulie 2017. Arhivat din original la 29 aprilie 2018. 
  23. ↑ RL; Rivest. O metodă pentru obținerea semnăturilor digitale și a criptosistemelor cu cheie publică  (engleză)  // Commun. ACM  : jurnal. - 1978. - Februarie ( vol. 21 , nr. 2 ). - P. 120-126 . — ISSN 0001-0782 . - doi : 10.1145/359340.359342 .
  24. ↑ Bernstein, Daniel. Criptografie post-cuantică  (neopr.) .
  25. ↑ Aaronson, Scott. Complexitatea computațională a opticii  liniare .
  26. ↑ Saleh; Rahimi-Keshari. Condiții suficiente pentru simularea eficientă clasică a opticii cuantice  (engleză)  // Physical Review X  : jurnal. - 2016. - 20 iunie ( vol. 6 , nr. 2 ). — P. 021039 . - doi : 10.1103/PhysRevX.6.021039 . - Cod biblic . - arXiv : 1511.06526 .
  27. ↑ Jacques; carolan. Optică liniară universală  (engleză)  // Știință. - 2015. - 14 august ( vol. 349 , nr. 6249 ). - P. 711-716 . — ISSN 0036-8075 . - doi : 10.1126/science.aab3642 . - arXiv : 1505.01182 . — PMID 26160375 .
  28. ↑ Alex; Neville. Fără supremație cuantică iminentă prin eșantionarea bosonilor  // Nature Physics  : journal  . - 2017. - 2 octombrie ( vol. 13 , nr. 12 ). - P. 1153-1157 . — ISSN 1745-2473 . - doi : 10.1038/nphys4270 . - arXiv : 1705.00686 .
  29. ↑ Peter W.; Shor. Schema pentru reducerea decoerenței în memoria computerului cuantic  // Physical Review A  : journal  . - 1995. - 1 octombrie ( vol. 52 , nr. 4 ). - P.R2493-R2496 . - doi : 10.1103/PhysRevA.52.R2493 . - Cod .
  30. ↑ AM; Steane. Codurile de corectare a erorilor în teoria cuantică  (engleză)  // Physical Review Letters  : jurnal. - 1996. - 29 iulie ( vol. 77 , nr. 5 ). - P. 793-797 . - doi : 10.1103/PhysRevLett.77.793 . - Cod . — PMID 10062908 .
  31. ↑ E.; Knill. Calcul cuantic cu dispozitive realist zgomotoase  (engleză)  // Natura. - 2005. - 3 martie ( vol. 434 , nr. 7029 ). - P. 39-44 . — ISSN 0028-0836 . - doi : 10.1038/nature03350 . — . — arXiv : quant-ph/0410199 . — PMID 15744292 .