I vilka specifika fall överträffar kvantdatorer sina klassiska motsvarigheter? Det är en svår fråga att svara på, delvis för att dagens kvantdatorer är petiga saker, plågade av fel som kan hopa sig och förstöra deras beräkningar.

På ett sätt har de förstås redan gjort det. 2019, fysiker på Google meddelade som de använde en 53-qubit-maskin för att uppnå kvantöverlägsenhet, en symbolisk milstolpe som markerar punkten då en kvantdator gör något utom räckhåll för någon praktisk klassisk algoritm. Liknande demonstrationer av fysiker vid University of Science and Technology i Kina följde snart.

 

Men istället för att fokusera på ett experimentellt resultat för en viss maskin, vill datavetare veta om klassiska algoritmer kommer att kunna hänga med när kvantdatorerna blir större och större. "Förhoppningen är att kvantsidan så småningom bara drar sig helt bort tills det inte finns någon konkurrens längre," sa Scott aaronson, en datavetare vid University of Texas, Austin.

 

Den allmänna frågan är fortfarande svår att besvara, återigen delvis på grund av dessa irriterande fel. (Framtida kvantmaskiner kommer att kompensera för sina ofullkomligheter med en teknik som kallas kvantfelkorrigering, men den förmågan är fortfarande långt borta.) Är det möjligt att få den efterlängtade kvantfördelen även med okorrigerade fel?

 

De flesta forskare misstänkte att svaret var nej, men de kunde inte bevisa det för alla fall. Nu, i en papper publicerat på preprint-servern arxiv.org, har ett team av datavetare tagit ett stort steg mot omfattande bevis på att felkorrigering är nödvändig för en bestående kvantfördel vid slumpmässig kretssampling – det skräddarsydda problem som Google använde för att visa kvantöverlägsenhet. De gjorde det genom att utveckla en klassisk algoritm som kan simulera slumpmässiga kretssamplingsexperiment när fel finns.

"Det är ett vackert teoretiskt resultat," sa Aaronson samtidigt som han betonade att den nya algoritmen inte är praktiskt användbar för att simulera verkliga experiment som Googles.

 

I slumpmässiga kretssamplingsexperiment börjar forskare med en uppsättning qubits, eller kvantbitar. De manipulerar sedan slumpmässigt dessa qubits med operationer som kallas kvantgrindar. Vissa grindar gör att par av qubits blir intrasslade, vilket betyder att de delar ett kvanttillstånd och inte kan beskrivas separat. Upprepade lager av grindar för qubits till ett mer komplicerat intrasslat tillstånd.

 

För att lära sig om det kvanttillståndet mäter forskare sedan alla kvantbitar i arrayen. Detta får deras kollektiva kvanttillstånd att kollapsa till en slumpmässig sträng av vanliga bitar - 0:or och 1:or. Antalet möjliga utfall växer snabbt med antalet qubits i arrayen: Med 53 qubits, som i Googles experiment, är det nästan 10 quadrillions. Och alla strängar är inte lika troliga. Sampling från en slumpmässig krets innebär att man upprepar sådana mätningar många gånger för att bygga upp en bild av sannolikhetsfördelningen som ligger till grund för utfallen.

 

Frågan om kvantfördelar är helt enkelt denna: Är det svårt att efterlikna den sannolikhetsfördelningen med en klassisk algoritm som inte använder någon intrassling?

 

I 2019, forskare visat att svaret är ja för felfria kvantkretsar: Det är verkligen svårt att klassiskt simulera ett slumpmässigt kretssamplingsexperiment när det inte finns några fel. Forskarna arbetade inom ramen för beräkningskomplexitetsteorin, som klassificerar den relativa svårigheten för olika problem. Inom detta område behandlar forskare inte antalet qubits som ett fast antal, till exempel 53. "Tänk på det som n, vilket är ett antal som kommer att öka”, sa Aram Harrow, fysiker vid Massachusetts Institute of Technology. "Då vill du fråga: Gör vi saker där ansträngningen är exponentiell n eller polynom i n?” Detta är det föredragna sättet att klassificera en algoritms körtid - när n växer tillräckligt stor, en algoritm som är exponentiell i n ligger långt efter alla algoritmer som är polynomer n. När teoretiker talar om ett problem som är svårt för klassiska datorer men lätt för kvantdatorer, syftar de på denna distinktion: Den bästa klassiska algoritmen tar exponentiell tid, medan en kvantdator kan lösa problemet i polynomtid.

Ändå ignorerade denna tidning från 2019 effekterna av fel orsakade av ofullkomliga grindar. Detta lämnade öppet fallet med en kvantfördel för slumpmässig kretssampling utan felkorrigering.

 

Om du föreställer dig att kontinuerligt öka antalet qubits som komplexitetsteoretiker gör, och du också vill ta hänsyn till fel, måste du bestämma dig för om du också kommer att fortsätta lägga till fler lager av grindar – öka kretsdjupet, som forskare säger. Anta att du håller kretsdjupet konstant vid, säg, relativt grunda tre lager, när du ökar antalet qubits. Du kommer inte att få mycket intrassling, och utgången kommer fortfarande att vara mottaglig för klassisk simulering. Å andra sidan, om du ökar kretsdjupet för att hålla jämna steg med det växande antalet qubits, kommer de kumulativa effekterna av grindfel att tvätta bort intrasslingen, och utsignalen kommer återigen att bli lätt att simulera klassiskt.

 

Men däremellan ligger en Guldlockszon. Innan den nya tidningen var det fortfarande en möjlighet att kvantfördelar kunde överleva här, även när antalet qubits ökade. I det här fallet med mellandjup ökar du kretsdjupet extremt långsamt när antalet qubits växer: Även om utsignalen stadigt kommer att försämras av fel, kan det fortfarande vara svårt att simulera klassiskt vid varje steg.

Den nya tidningen täpper till detta kryphål. Författarna härledde en klassisk algoritm för att simulera slumpmässig kretssampling och bevisade att dess körtid är en polynomfunktion av den tid som krävs för att köra motsvarande kvantexperiment. Resultatet skapar en snäv teoretisk koppling mellan hastigheten hos klassiska och kvantmetoder för slumpmässig kretssampling.

 

Den nya algoritmen fungerar för en stor klass av medeldjupa kretsar, men dess underliggande antaganden bryts ner för vissa grundare, vilket lämnar ett litet gap där effektiva klassiska simuleringsmetoder är okända. Men få forskare har hopp om att slumpmässig kretssampling kommer att visa sig vara svår att simulera klassiskt i detta kvarvarande smala fönster. "Jag ger det ganska små odds," sa Bill Fefferman, en datavetare vid University of Chicago och en av författarna till 2019 års teoriuppsats.

 

Resultatet tyder på att slumpmässig kretssampling inte kommer att ge en kvantfördel genom de rigorösa standarderna för beräkningskomplexitetsteorin. Samtidigt illustrerar det faktumet att polynomalgoritmer, som komplexitetsteoretiker urskillningslöst kallar effektiva, inte nödvändigtvis är snabba i praktiken. Den nya klassiska algoritmen blir gradvis långsammare när felfrekvensen minskar, och med de låga felfrekvenser som uppnås i kvantöverlägsenhetsexperiment är det alldeles för långsamt för att vara praktiskt. Utan fel går det sönder helt, så detta resultat motsäger inte något som forskare visste om hur svårt det är att klassiskt simulera slumpmässig kretssampling i det ideala, felfria fallet. Sergio Boixo, fysikern som leder Googles kvantöverlägsenhetsforskning, säger att han ser uppsatsen "mer som en trevlig bekräftelse på slumpmässig kretssampling än något annat."

 

På en punkt är alla forskare överens: Den nya algoritmen understryker hur avgörande kvantfelskorrigering kommer att vara för den långsiktiga framgången med kvantberäkning. "Det är lösningen, i slutet av dagen," sa Fefferman.

Översätt "