Kvanteovermagt

Den aktuelle version af siden er endnu ikke blevet gennemgået af erfarne bidragydere og kan afvige væsentligt fra den version , der blev gennemgået den 8. oktober 2020; checks kræver 8 redigeringer .

Kvanteoverherredømme er kvantecomputerens  evne til at løse problemer, som klassiske computere praktisk talt ikke er i stand til at løse. Kvantefordelen er evnen til at løse problemer hurtigere. Ud fra et beregningsmæssig kompleksitetsteoris synspunkt betyder dette normalt at give en superpolynomial speedup sammenlignet med den mest kendte eller mulige klassiske algoritme [1] . Udtrykket blev populariseret af John Preskill , men begrebet kvanteberegningsfordel, især ved simulering af kvantesystemer, går tilbage til kvanteberegningsforslaget givet af Yuri Manin (1980) [2] ogRichard Feynman (1981) [3] .

Shor 's algoritme til heltalsfaktorisering, som kører i polynomiel tid på en kvantecomputer, giver en sådan superpolynomiel speedup sammenlignet med den bedst kendte klassiske algoritme [4] . Selvom det endnu ikke er bevist, betragtes faktorisering som en udfordring, når man bruger klassiske ressourcer. Vanskeligheden ved at bevise, hvad der ikke kan gøres med klassisk beregning, er et almindeligt problem for definitivt at demonstrere kvanteoverlegenhed. Det påvirker også Aaronson og Arkhipovs bosonsamplingforslag , D-Waves specialiserede problemer med frustrerede klyngesløjfer og outputsampling for tilfældige kvantekredsløb .

Ligesom heltalsfaktorisering anses problemet med at udtage udgangsfordelingerne af tilfældige kvantekredsløb som vanskeligt for klassiske computere baseret på rimelige antagelser om kompleksiteten.

Historie

Google har tidligere annonceret planer om at demonstrere kvanteoverherredømme inden udgangen af ​​2017 ved hjælp af en række af 49 superledende qubits [5] . Fra begyndelsen af ​​januar 2018 var det dog kun Intel, der har annonceret sådan hardware [6] .

I oktober 2017 demonstrerede IBM en simulering af 56 qubits på en konventionel supercomputer, hvilket øgede antallet af qubits , der er nødvendige for kvanteoverherredømme [7] .

I november 2018 annoncerede Google et partnerskab med NASA , hvor NASA vil "analysere resultaterne fra kvantekredsløb kørt på Googles kvanteprocessorer og... overlegenhed" [8] .

Et teoretisk papir fra 2018 antyder, at kvanteoverherredømme kan opnås på "et todimensionelt array på 7 × 7 qubits og omkring 40 clock-cyklusser", men hvis fejlraten er lav nok [9] .

Den 21. juni 2019 foreslog Scientific American , at ifølge Nevens lov vil kvanteoverherredømme blive opnået i 2019 [10] .

Den 20. september 2019 rapporterede Financial Times, at "Google hævder at have opnået kvanteoverherredømme på en række af 54 qubits, hvoraf 53 var funktionelle og brugt til at udføre beregninger på 200 sekunder, hvilket ville tage omkring 10.000 år for en konventionel supercomputer " [11] . I første omgang dukkede en rapport om dette op på NASAs hjemmeside, men blev slettet kort efter offentliggørelsen [12] . Senere, den 23. oktober, blev kvanteoverherredømmet officielt annonceret [13] . Eksperter fra IBM, efter at have analyseret de præsenterede data, indikerede imidlertid, at nogle øjeblikke ikke er optimale, og at en sådan beregning på en klassisk supercomputer faktisk kun vil tage 2,5 dage i stedet for de erklærede 10.000 år. [14] [15] [16]

Den 3. december 2020 rapporterede kinesiske videnskabsmænd, at deres Jiuzhang kvantecomputer , drevet af sammenfiltrede fotoner, havde opnået kvanteoverherredømme. På 200 sekunder beregnede de med succes et problem, der ville tage verdens hurtigste klassiske computer mere end en halv milliard år at løse [17] .

Beregningsmæssig kompleksitet

Spørgsmålet om kompleksitet refererer til, hvordan mængden af ​​ressourcer, der kræves for at løse et problem, skaleres med størrelsen af ​​input. Som en udvidelse af den klassiske beregningsmæssige kompleksitetsteori beskriver kvantekompleksitetsteorien driften af ​​en universel kvantecomputer uden at tage højde for kompleksiteten af ​​dens skabelse eller eliminering af virkningerne af dekohærens og støj [18] . Fordi kvanteinformation er en generalisering af klassisk information , kan en kvantecomputer simulere enhver klassisk algoritme .

Kompleksitetsklassen af ​​kvantepolynomial time bounded error (BQP) problemer er en klasse af beslutningsproblemer, der kan løses i polynomiel tid af en universel kvantecomputer . BPQ-klassen er relateret til de klassiske kompleksitetsklasser af et hierarki [19] . Det er fortsat et åbent spørgsmål, om nogen af ​​disse indlejringer er strenge.

I modsætning til beslutningsproblemer, der kræver et ja eller nej svar, kræver prøvetagningsproblemer prøvetagning fra sandsynlighedsfordelinger [20] . Hvis der er en klassisk algoritme , der kan sample output fra et vilkårligt kvantekredsløb , vil polynomiehierarkiet flytte til det tredje niveau, hvilket anses for meget usandsynligt. BosonSampling  er et mere specifikt forslag, hvis klassiske kompleksitet afhænger af uløseligheden af ​​problemet med at beregne permanenten af ​​en stor matrix med komplekse elementer, hvilket er et P#-komplet problem. Argumenterne brugt til at udlede denne påstand er også blevet anvendt til IQP sampling [21] , hvor kun den hypotese er nødvendig, at den gennemsnitlige og worst case kompleksitet af problemet er den samme.

Superpolynomisk acceleration

Følgende algoritmer giver superpolynomial speedup sammenlignet med de bedst kendte klassiske algoritmer [22] :

Shor's algoritme for heltalsfaktorisering

Denne algoritme finder primfaktoriseringen af ​​et n - bit heltal i tid [4] , den mest berømte klassiske algoritme tager tid og den bedste øvre grænse for kompleksiteten af ​​dette problem . Det kan også give en fremskyndelse for ethvert problem, der koger ned til heltalsfaktorisering , inklusive problemet med, om matrixgrupper tilhører felter af ulige orden.

Til kvanteberegning er denne algoritme vigtig både praktisk og historisk. Det blev den første polynomiske kvantealgoritme , der blev foreslået til et problem, der anses for vanskeligt for klassiske computere [4] . Tilliden til denne kompleksitet er så stærk, at sikkerheden for den mest almindelige krypteringsprotokol RSA i dag er baseret på faktoriseringsalgoritmen [23] . En kvantecomputer, der succesfuldt og reproducerbart kører denne algoritme, kan bryde dette krypteringssystem [24] . Denne hackingrisiko kaldes Y2K-problemet, svarende til Y2K- problemet, Y2K-problemet .

Boson prøvetagning

Dette beregningsparadigme er baseret på identiske fotoner sendt gennem et lineært optisk netværk og kan løse visse prøvetagnings- og søgeproblemer, der, forudsat at der er flere hypoteser, er uløselige for klassiske computere [25] . Ikke desto mindre blev det vist, at bosonsampling i et system med tilstrækkeligt store tab og støj effektivt kan simuleres [26] .

Den største eksperimentelle implementering af bosonprøvetagning til dato har 6 tilstande og kan derfor behandle op til 6 fotoner samtidigt [27] . Den bedste klassiske algoritme til modellering af bosonsampling kører i rækkefølge for et system med n fotoner og m outputtilstande [28] . BosonSampling er en open source R -  implementering af algoritmen . Algoritmen giver et estimat på 50 fotoner , hvilket er nødvendigt for at demonstrere kvanteoverlegenhed ved brug af bosonprøvetagning.

Sampling af outputfordelingen af ​​tilfældige kvantekredsløb

Den bedst kendte algoritme til at simulere et vilkårligt tilfældigt kvantekredsløb kræver tid, der skaleres eksponentielt med antallet af qubits , baseret på hvilket en gruppe forskere vurderer, at omkring 50 qubits kan være nok til at demonstrere kvanteoverlegenhed [9] . Google har annonceret sin hensigt om at demonstrere kvanteoverherredømme inden udgangen af ​​2017 ved at skabe og lancere en 49 -qubit- chip, der kan sample distributioner inden for en rimelig tid, som er utilgængelige for nogen moderne klassiske computere [5] . Men den største simulering af kvantekredsløb med succes udført på en supercomputer har 56 qubits . Derfor kan det være nødvendigt at øge antallet af qubits, der kræves for at demonstrere kvanteoverlegenhed [7] .

Kritik

Kvantecomputere er meget mere fejltilbøjelige end klassiske computere på grund af dekohærens og støj. Tærskelsætningen siger, at en støjende kvantecomputer kan bruge fejlkorrigerende kvantekoder [29] [30] til at simulere en ikke-støjende kvantecomputer, idet det antages, at fejlen introduceret i hver computercyklus er mindre end et vist tal. Numeriske simuleringer viser, at dette tal kan nå 3 % [31] .

Det vides dog ikke, hvordan de ressourcer, der kræves til fejlkorrektion , skaleres med antallet af qubits . Skeptikere[ hvad? ] indikerer, at støjens adfærd er ukendt i skalerbare kvantesystemer som potentielle barrierer for en vellykket implementering af kvanteberegning og demonstration af kvanteoverherredømme.

Se også

Noter

  1. ↑ Anargyros; papageorgiou. Measures of quantum computing speedup  (engelsk)  // Physical Review A  : journal. - 2013. - 12. august ( bind 88 , nr. 2 ). — P. 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. Simulering af fysik med computere  // International  Journal of Theoretical Physics : journal. - 1982. - 1. juni ( bind 21 , nr. 6-7 ). - S. 467-488 . — ISSN 0020-7748 . - doi : 10.1007/BF02650179 . - .
  4. ↑ 1 2 3 P.; Shor. Polynomial-Time Algorithms for Prime Factorization and Discrete Logaritms on a Quantum Computer  (engelsk)  // SIAM Review: journal. - 1999. - 1. januar ( bind 41 , nr. 2 ). - s. 303-332 . — ISSN 0036-1445 . - doi : 10.1137/S0036144598347011 . - . — arXiv : quant-ph/9508027 .
  5. ↑ 1 2 Google planlægger at demonstrere overherredømmet af Quantum Computing , IEEE Spectrum: Technology, Engineering, and Science News . Arkiveret fra originalen den 25. april 2021. Hentet 11. januar 2018.
  6. ↑ CES 2018: Intels 49-Qubit Chip Shoots for Quantum Supremacy , IEEE Spectrum: Technology, Engineering, and Science News . Arkiveret fra originalen den 23. marts 2021. Hentet 22. juli 2017.
  7. ↑ 1 2 Googles kvanteberegningsplaner truet af IBM curveball (20. oktober 2017). Hentet 22. oktober 2017. Arkiveret fra originalen 25. januar 2021.
  8. ↑ Harris . Google har hyret NASA til at hjælpe det med at bevise kvanteherredømmet inden for måneder  , MIT Technology Review . Arkiveret 10. marts 2020. Hentet 30. november 2018.
  9. ↑ 12 Sergio ; Boixo. Karakterisering af kvanteoverherredømme i enheder på kort sigt  // Nature Physics  : tidsskrift  . - 2018. - 23. april ( bind 14 , nr. 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/ Arkiveret 2. marts 2021 på Wayback Machine En ny "lov" foreslår kvanteoverhøjhed Could Happen This Year] , Scientific American, Daily Digest, 21. juni 2019
  11. ↑ Google hævder at have nået kvanteoverherredømme  , The Financial Times  (21. september 2019). Arkiveret fra originalen den 29. april 2021. Hentet 23. oktober 2019.
  12. ↑ Karpukhin, Vladimir The Financial Times: Google annoncerede skabelsen af ​​den mest kraftfulde kvantecomputer, men slettede derefter rapporten - Technologies on TJ . TJ (21. september 2019). Hentet 23. oktober 2019. Arkiveret fra originalen 23. oktober 2019.
  13. ↑ Frank Arute, Kunal Arya, Ryan Babbush, Dave Bacon, Joseph C. Bardin. Kvanteoverlegenhed ved hjælp af en programmerbar superledende processor   // Nature . - 2019. - Oktober ( uds. 7779 , nr. 574 ). - S. 505-510 . — ISSN 1476-4687 . - doi : 10.1038/s41586-019-1666-5 . Arkiveret fra originalen den 23. oktober 2019.
  14. ↑ Hvad Google vs. IBM-debat om kvanteoverherredømme betyder | ZDNet . www.zdnet.com . Hentet 12. februar 2020. Arkiveret fra originalen 5. marts 2020.
  15. ↑ Om "Quantum Supremacy" . IBM Research Blog (22. oktober 2019). Hentet 24. oktober 2019. Arkiveret fra originalen 11. november 2021.
  16. ↑ Google hævder at opnå Quantum Supremacy - IBM skubber tilbage . NPR.org . Hentet 24. oktober 2019. Arkiveret fra originalen 23. oktober 2019.
  17. ↑ Lysbaseret kvantecomputer Jiuzhang opnår kvanteoverlegenhed | videnskabsnyheder . Hentet 4. december 2020. Arkiveret fra originalen 2. november 2021.
  18. ↑ Watrous, John. Quantum Computational Complexity // Encyclopedia of Complexity and Systems Science  (engelsk) . - 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 Symposia in Applied Mathematics.
  20. ↑ AP; Lund. Kvanteprøveudtagningsproblemer, BosonSampling og kvanteoverherredømme  //  Npj Quantum Information : journal. - 2017. - 13. april ( bind 3 , nr. 1 ). - ISSN 2056-6387 . - doi : 10.1038/s41534-017-0018-2 . — . - arXiv : 1702.03061 .
  21. ↑ Michael J.; Bremner. Gennemsnitlig sagskompleksitet versus omtrentlig simulering af pendlende kvanteberegninger  // Physical Review Letters  : journal  . - 2016. - 18. august ( bind 117 , nr. 8 ). — ISSN 0031-9007 . - doi : 10.1103/PhysRevLett.117.080501 . - . - arXiv : 1504.07999 . — PMID 27588839 .
  22. ↑ Jordan. Quantum Algorithm Zoo (utilgængeligt link) . math.nist.gov . Hentet 29. juli 2017. Arkiveret fra originalen 29. april 2018. 
  23. ↑ RL; Rivest. En metode til at opnå digitale signaturer og offentlige nøglekryptosystemer  (engelsk)  // Commun. ACM  : journal. - 1978. - Februar ( bind 21 , nr. 2 ). - S. 120-126 . — ISSN 0001-0782 . - doi : 10.1145/359340.359342 .
  24. ↑ Bernstein, Daniel. Post-  kvantekryptering (neopr.) .
  25. ↑ Aaronson, Scott. Lineær  optiks beregningsmæssige kompleksitet .
  26. ↑ Saleh; Rahimi-Keshari. Tilstrækkelige betingelser for effektiv klassisk simulering af kvanteoptik  (engelsk)  // Physical Review X  : tidsskrift. - 2016. - 20. juni ( bind 6 , nr. 2 ). — S. 021039 . - doi : 10.1103/PhysRevX.6.021039 . - . - arXiv : 1511.06526 .
  27. ↑ Jacques; carolan. Universal lineær optik  (engelsk)  // Videnskab. - 2015. - 14. august ( bd. 349 , nr. 6249 ). - s. 711-716 . — ISSN 0036-8075 . - doi : 10.1126/science.aab3642 . - arXiv : 1505.01182 . — PMID 26160375 .
  28. ↑ Alex; Neville. Ingen forestående kvanteoverherredømme ved bosonprøvetagning  // Nature Physics  : tidsskrift  . - 2017. - 2. oktober ( bind 13 , nr. 12 ). - S. 1153-1157 . — ISSN 1745-2473 . - doi : 10.1038/nphys4270 . - arXiv : 1705.00686 .
  29. ↑ Peter W.; Shor. Ordning til reduktion af dekohærens i kvantecomputerhukommelse  // Physical Review A  : journal  . - 1995. - 1. oktober ( bind 52 , nr. 4 ). - P.R2493-R2496 . - doi : 10.1103/PhysRevA.52.R2493 . - .
  30. ↑ AM; Steane. Fejlkorrigerende koder i kvanteteori  (engelsk)  // Physical Review Letters  : journal. - 1996. - 29. juli ( bd. 77 , nr. 5 ). - s. 793-797 . - doi : 10.1103/PhysRevLett.77.793 . - . — PMID 10062908 .
  31. ↑ E.; Knill. Kvanteberegning med realistisk støjende enheder  (engelsk)  // Nature. - 2005. - 3. marts ( bd. 434 , nr. 7029 ). - S. 39-44 . — ISSN 0028-0836 . - doi : 10.1038/nature03350 . — . — arXiv : quant-ph/0410199 . — PMID 15744292 .