Kvantöverlägsenhet

Den aktuella versionen av sidan har ännu inte granskats av erfarna bidragsgivare och kan skilja sig väsentligt från versionen som granskades den 8 oktober 2020; kontroller kräver 8 redigeringar .

Quantum supremacy  är förmågan hos kvantdatorenheter att lösa problem som klassiska datorer praktiskt taget inte kan lösa. Kvantfördelen är förmågan att lösa problem snabbare. Ur beräkningskomplexitetsteoris synvinkel innebär detta vanligtvis att man tillhandahåller en superpolynomisk hastighet jämfört med den mest kända eller möjliga klassiska algoritmen [1] . Termen populariserades av John Preskill , men konceptet med kvantberäkningsfördelar, särskilt vid simulering av kvantsystem, går tillbaka till kvantberäkningsförslaget från Yuri Manin (1980) [2] ochRichard Feynman (1981) [3] .

Shors algoritm för heltalsfaktorisering, som körs i polynomtid på en kvantdator, ger en sådan superpolynomisk hastighet jämfört med den mest kända klassiska algoritmen [4] . Även om det ännu inte har bevisats anses faktorisering vara en utmaning när man använder klassiska resurser. Svårigheten att bevisa vad som inte kan göras med klassisk beräkning är ett vanligt problem för att definitivt demonstrera kvantöverlägsenhet. Det påverkar också Aaronsons och Arkhipovs bosonsamplingsförslag , D-Waves specialiserade problem med frustrerade klusterslingor och utgångssampling för slumpmässiga kvantkretsar .

Liksom heltalsfaktorisering anses problemet med att sampla utgångsfördelningarna från slumpmässiga kvantkretsar vara svårt för klassiska datorer baserat på rimliga antaganden om komplexiteten.

Historik

Google tillkännagav tidigare planer på att demonstrera kvantöverlägsenhet i slutet av 2017 med en uppsättning av 49 supraledande kvantbitar [5] . Men i början av januari 2018 är det bara Intel som har annonserat sådan hårdvara [6] .

I oktober 2017 demonstrerade IBM en simulering av 56 qubits på en konventionell superdator, vilket ökade antalet qubits som behövs för kvantöverhöghet [7] .

I november 2018 tillkännagav Google ett partnerskap med NASA där NASA kommer att "analysera resultaten från kvantkretsar som körs på Googles kvantprocessorer och... överlägsenhet" [8] .

En teoretisk artikel från 2018 antyder att kvantöverlägsenhet kan uppnås på "en tvådimensionell array på 7 × 7 qubits och cirka 40 klockcykler", men om felfrekvensen är tillräckligt låg [9] .

Den 21 juni 2019 föreslog Scientific American att, enligt Nevens lag , kommer kvantöverhöghet att uppnås 2019 [10] .

Den 20 september 2019 rapporterade Financial Times att "Google påstår sig ha uppnått kvantöverlägsenhet på en uppsättning av 54 qubits, varav 53 var funktionella och användes för att utföra beräkningar på 200 sekunder, vilket skulle ta cirka 10 000 år för en konventionell superdator " [11] . Inledningsvis dök en rapport om detta upp på NASA:s webbplats, men raderades kort efter publiceringen [12] . Senare, den 23 oktober, tillkännagavs kvantöverhöghet officiellt [13] . Experter från IBM, efter att ha analyserat de presenterade uppgifterna, indikerade dock att vissa ögonblick inte är optimala och att en sådan beräkning på en klassisk superdator faktiskt bara tar 2,5 dagar istället för de deklarerade 10 000 åren. [14] [15] [16]

Den 3 december 2020 rapporterade kinesiska forskare att deras Jiuzhang kvantdator , som drivs av intrasslade fotoner, hade uppnått kvantöverlägsenhet. På 200 sekunder beräknade de framgångsrikt ett problem som skulle ta världens snabbaste klassiska dator mer än en halv miljard år att lösa [17] .

Beräkningskomplexitet

Frågan om komplexitet hänvisar till hur mängden resurser som krävs för att lösa ett problem skalar med storleken på insatsen. Som en förlängning av den klassiska beräkningskomplexitetsteorin beskriver kvantkomplexitetsteorin driften av en universell kvantdator utan att ta hänsyn till komplexiteten i dess skapelse eller eliminering av effekterna av dekoherens och brus [18] . Eftersom kvantinformation är en generalisering av klassisk information , kan en kvantdator simulera vilken klassisk algoritm som helst .

Komplexitetsklassen för quantum polynomial time bounded error (BQP) problem är en klass av beslutsproblem som kan lösas i polynomtid av en universell kvantdator . BPQ-klassen är relaterad till de klassiska komplexitetsklasserna genom en hierarki [19] . Det är fortfarande en öppen fråga om någon av dessa inbäddningar är strikta.

Till skillnad från beslutsproblem som kräver ett ja eller nej svar, kräver provtagningsproblem sampling från sannolikhetsfördelningar [20] . Om det finns en klassisk algoritm som kan sampla utdata från en godtycklig kvantkrets , kommer polynomhierarkin att flyttas till den tredje nivån, vilket anses vara mycket osannolikt. BosonSampling  är ett mer specifikt förslag vars klassiska komplexitet beror på olösbarheten av problemet med att beräkna permanenten för en stor matris med komplexa element, vilket är ett P#-komplett problem. Argumenten som används för att härleda detta påstående har också tillämpats på IQP-sampling [21] , där endast hypotesen behövs att den genomsnittliga och värsta fallets komplexitet för problemet är densamma.

Superpolynomacceleration

Följande algoritmer ger superpolynomisk hastighet jämfört med de mest kända klassiska algoritmerna [22] :

Shors algoritm för heltalsfaktorisering

Denna algoritm hittar primfaktoriseringen av ett n -bitars heltal i tid [4] , den mest kända klassiska algoritmen tar tid och den bästa övre gränsen för komplexiteten i detta problem . Det kan också ge en snabbare för alla problem som kokar ner till heltalsfaktorisering , inklusive problemet om matrisgrupper tillhör fält av udda ordning.

För kvantberäkning är denna algoritm viktig både praktiskt och historiskt. Det blev den första polynomkvantalgoritmen som föreslagits för ett problem som anses vara svårt för klassiska datorer [4] . Förtroendet för denna komplexitet är så starkt att säkerheten för det vanligaste krypteringsprotokollet RSA idag baseras på faktoriseringsalgoritmen [23] . En kvantdator som framgångsrikt och reproducerbart kör denna algoritm kan bryta detta krypteringssystem [24] . Denna hackerisk kallas Y2K-problemet, liknande Y2K- problemet, Y2K-problemet .

Bosonsampling

Detta beräkningsparadigm är baserat på identiska fotoner som skickas genom ett linjärt optiskt nätverk och kan lösa vissa provtagnings- och sökproblem som, om man antar flera hypoteser, är olösliga för klassiska datorer [25] . Ändå visades det att bosonsampling i ett system med tillräckligt stora förluster och buller effektivt kan simuleras [26] .

Den största experimentella implementeringen av bosonsampling hittills har 6 lägen och kan därför behandla upp till 6 fotoner samtidigt [27] . Den bästa klassiska algoritmen för modellering av bosonsampling körs i ordningstid för ett system med n fotoner och m utgångslägen [28] . BosonSampling är en öppen källkod R -  implementering av algoritmen . Algoritmen ger en uppskattning av 50 fotoner , vilket är nödvändigt för att demonstrera kvantöverlägsenhet med hjälp av bosonsampling.

Sampling av utgångsfördelningen för slumpmässiga kvantkretsar

Den mest kända algoritmen för att simulera en godtycklig slumpmässig kvantkrets kräver tid som skalar exponentiellt med antalet kvantbitar , baserat på vilket en grupp forskare uppskattar att cirka 50 kvantbitar kan vara tillräckligt för att visa kvantöverlägsenhet [9] . Google har meddelat sin avsikt att demonstrera kvantöverlägsenhet i slutet av 2017 genom att skapa och lansera ett 49 -qubit- chip som kan sampla distributioner inom rimlig tid som är otillgängliga för alla moderna klassiska datorer [5] . Men den största simuleringen av kvantkretsar som framgångsrikt utförts på en superdator har 56 qubits . Därför kan det vara nödvändigt att öka antalet qubits som krävs för att visa kvantöverlägsenhet [7] .

Kritik

Kvantdatorer är mycket mer felbenägna än klassiska datorer på grund av dekoherens och brus. Tröskelsatsen säger att en brusig kvantdator kan använda felkorrigerande kvantkoder [29] [30] för att simulera en icke-brusig kvantdator, förutsatt att felet som introduceras i varje datorcykel är mindre än ett visst antal. Numeriska simuleringar visar att denna siffra kan nå 3 % [31] .

Det är dock inte känt hur de resurser som krävs för felkorrigering kommer att skalas med antalet qubits . Skeptiker[ vad? ] indikerar att brusets beteende är okänt i skalbara kvantsystem som potentiella hinder för framgångsrik implementering av kvantberäkning och demonstration av kvantöverhöghet.

Se även

Anteckningar

  1. ↑ Anargyros; papageorgiou. Measures of quantum computing speedup  (engelska)  // Physical Review A  : journal. - 2013. - 12 augusti ( vol. 88 , nr 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. Simulering av fysik med datorer  // International  Journal of Theoretical Physics : journal. - 1982. - 1 juni ( vol. 21 , nr 6-7 ). - s. 467-488 . — ISSN 0020-7748 . - doi : 10.1007/BF02650179 . - .
  4. ↑ 1 2 3 P.; Shor. Polynom-tidsalgoritmer för primfaktorisering och diskreta logaritmer på en kvantdator  (engelska)  // SIAM Review: journal. - 1999. - 1 januari ( vol. 41 , nr 2 ). - s. 303-332 . — ISSN 0036-1445 . - doi : 10.1137/S0036144598347011 . - . — arXiv : quant-ph/9508027 .
  5. ↑ 1 2 Google planerar att demonstrera överlägsenheten av Quantum Computing , IEEE Spectrum: Technology, Engineering, and Science News . Arkiverad från originalet den 25 april 2021. Hämtad 11 januari 2018.
  6. ↑ CES 2018: Intels 49-Qubit Chip Shoots for Quantum Supremacy , IEEE Spectrum: Technology, Engineering, and Science News . Arkiverad från originalet den 23 mars 2021. Hämtad 22 juli 2017.
  7. ↑ 1 2 Googles kvantberäkningsplaner hotas av IBM Curveball (20 oktober 2017). Hämtad 22 oktober 2017. Arkiverad från originalet 25 januari 2021.
  8. ↑ Harris . Google har anlitat NASA för att hjälpa den att bevisa kvantöverhöghet inom några månader  , MIT Technology Review . Arkiverad 10 mars 2020. Hämtad 30 november 2018.
  9. ↑ 12 Sergio ; Boixo. Karakteriserande kvantöverlägsenhet i enheter på kort sikt  // Nature Physics  : journal  . - 2018. - 23 april ( 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/ Arkiverad 2 mars 2021 på Wayback Machine En ny "lag" föreslår kvantöverlägsenhet Could Happen This Year] , Scientific American, Daily Digest, 21 juni 2019
  11. ↑ Google påstår sig ha nått kvantöverhöghet  , The Financial Times  (21 september 2019). Arkiverad från originalet den 29 april 2021. Hämtad 23 oktober 2019.
  12. ↑ Karpukhin, Vladimir The Financial Times: Google tillkännagav skapandet av den mest kraftfulla kvantdatorn, men raderade sedan rapporten - Technologies on TJ . TJ (21 september 2019). Hämtad 23 oktober 2019. Arkiverad från originalet 23 oktober 2019.
  13. ↑ Frank Arute, Kunal Arya, Ryan Babbush, Dave Bacon, Joseph C. Bardin. Quantum supremacy med en programmerbar supraledande processor   // Nature . - 2019. - Oktober ( iss. 7779 , nr 574 ). - S. 505-510 . — ISSN 1476-4687 . - doi : 10.1038/s41586-019-1666-5 . Arkiverad från originalet den 23 oktober 2019.
  14. ↑ Vad Google vs. IBM-debatt om kvantöverhöghet betyder | ZDNet . www.zdnet.com . Hämtad 12 februari 2020. Arkiverad från originalet 5 mars 2020.
  15. ↑ Om "Quantum Supremacy" . IBM Research Blog (22 oktober 2019). Hämtad 24 oktober 2019. Arkiverad från originalet 11 november 2021.
  16. ↑ Google hävdar att man uppnår kvantöverlägsenhet - IBM skjuter tillbaka . NPR.org . Hämtad 24 oktober 2019. Arkiverad från originalet 23 oktober 2019.
  17. ↑ Ljusbaserad kvantdator Jiuzhang uppnår kvantöverlägsenhet | vetenskapsnyheter . Hämtad 4 december 2020. Arkiverad från originalet 2 november 2021.
  18. ↑ Watrous, John. Quantum Computational Complexity // Encyclopedia of Complexity and Systems Science  (engelska) . - 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. Quantumsampling problem, BosonSampling and quantum supremacy  //  Npj Quantum Information : journal. - 2017. - 13 april ( vol. 3 , nr 1 ). - ISSN 2056-6387 . - doi : 10.1038/s41534-017-0018-2 . — . - arXiv : 1702.03061 .
  21. ↑ Michael J.; Bremner. Genomsnittlig fallkomplexitet kontra ungefärlig simulering av pendlingskvantberäkningar  // Physical Review Letters  : journal  . - 2016. - 18 augusti ( vol. 117 , nr 8 ). — ISSN 0031-9007 . - doi : 10.1103/PhysRevLett.117.080501 . - . - arXiv : 1504.07999 . — PMID 27588839 .
  22. ↑ Jordanien. Quantum Algorithm Zoo (inte tillgänglig länk) . math.nist.gov . Hämtad 29 juli 2017. Arkiverad från originalet 29 april 2018. 
  23. ↑ RL; Rivest. En metod för att erhålla digitala signaturer och kryptosystem med offentliga nyckel  (engelska)  // Commun. ACM  : journal. - 1978. - Februari ( vol. 21 , nr 2 ). - S. 120-126 . — ISSN 0001-0782 . - doi : 10.1145/359340.359342 .
  24. ↑ Bernstein, Daniel. Postkvantkryptering  (neopr.) .
  25. ↑ Aaronson, Scott. Linjäroptikens  beräkningskomplexitet .
  26. ↑ Saleh; Rahimi-Keshari. Tillräckliga villkor för effektiv klassisk simulering av kvantoptik  (engelska)  // Physical Review X  : journal. - 2016. - 20 juni ( vol. 6 , nr 2 ). — S. 021039 . - doi : 10.1103/PhysRevX.6.021039 . - . - arXiv : 1511.06526 .
  27. ↑ Jacques; carolan. Universell linjär optik  (engelska)  // Science. - 2015. - 14 augusti ( vol. 349 , nr 6249 ). - s. 711-716 . — ISSN 0036-8075 . - doi : 10.1126/science.aab3642 . - arXiv : 1505.01182 . — PMID 26160375 .
  28. ↑ Alex; Neville. Ingen överhängande kvantöverhöghet genom bosonsampling  // Nature Physics  : journal  . - 2017. - 2 oktober ( vol. 13 , nr 12 ). - P. 1153-1157 . — ISSN 1745-2473 . - doi : 10.1038/nphys4270 . - arXiv : 1705.00686 .
  29. ↑ Peter W.; Shor. Schema för att minska dekoherensen i kvantdatorminne  // Physical Review A  : journal  . - 1995. - 1 oktober ( vol. 52 , nr 4 ). - P.R2493-R2496 . - doi : 10.1103/PhysRevA.52.R2493 . - .
  30. ↑ AM; Steane. Error Correcting Codes in Quantum Theory  (engelska)  // Physical Review Letters  : journal. - 1996. - 29 juli ( vol. 77 , nr 5 ). - s. 793-797 . - doi : 10.1103/PhysRevLett.77.793 . - . — PMID 10062908 .
  31. ↑ E.; Knill. Kvantberäkning med realistiskt bullriga enheter  (engelska)  // Nature. - 2005. - 3 mars ( vol. 434 , nr 7029 ). - S. 39-44 . — ISSN 0028-0836 . - doi : 10.1038/nature03350 . — . — arXiv : quant-ph/0410199 . — PMID 15744292 .