I hvilke spesifikke tilfeller overgår kvantedatamaskiner sine klassiske motstykker? Det er et vanskelig spørsmål å svare på, delvis fordi dagens kvantedatamaskiner er pirkete ting, plaget med feil som kan hope seg opp og ødelegge beregningene deres.
På en måte har de selvfølgelig allerede gjort det. I 2019, fysikere hos Google annonsert som de brukte en 53-qubit-maskin for å oppnå kvanteoverlegenhet, en symbolsk milepæl som markerer punktet der en kvantedatamaskin gjør noe utenfor rekkevidden til enhver praktisk klassisk algoritme. Lignende demonstrasjoner av fysikere ved University of Science and Technology i Kina fulgte snart.
Men i stedet for å fokusere på et eksperimentelt resultat for én bestemt maskin, ønsker informatikere å vite om klassiske algoritmer vil være i stand til å henge med etter hvert som kvantedatamaskiner blir større og større. "Håpet er at til slutt trekker kvantesiden seg helt bort til det ikke er noen konkurranse lenger," sa Scott Aaronson, en informatiker ved University of Texas, Austin.
Det generelle spørsmålet er fortsatt vanskelig å svare på, igjen delvis på grunn av de irriterende feilene. (Fremtidige kvantemaskiner vil kompensere for ufullkommenhetene deres ved å bruke en teknikk som kalles kvantefeilkorreksjon, men den evnen er fortsatt et stykke unna.) Er det mulig å få den håpede kvantefordelen selv med ukorrigerte feil?
De fleste forskere mistenkte at svaret var nei, men de kunne ikke bevise det for alle tilfeller. Nå, i en papir postet til preprint-serveren arxiv.org, har et team av informatikere tatt et stort skritt mot omfattende bevis på at feilretting er nødvendig for en varig kvantefordel i tilfeldig kretsprøvetaking – det skreddersydde problemet som Google brukte for å vise kvanteoverlegenhet. De gjorde det ved å utvikle en klassisk algoritme som kan simulere tilfeldige kretsprøveeksperimenter når feil er tilstede.
"Det er et vakkert teoretisk resultat," sa Aaronson mens han understreket at den nye algoritmen ikke er praktisk nyttig for å simulere ekte eksperimenter som Googles.
I tilfeldige kretsprøveeksperimenter starter forskere med en rekke qubits, eller kvantebiter. De manipulerer deretter tilfeldig disse qubitene med operasjoner kalt kvanteporter. Noen porter fører til at par av qubits blir viklet inn, noe som betyr at de deler en kvantetilstand og ikke kan beskrives separat. Gjentatte lag med porter bringer qubitene inn i en mer komplisert sammenfiltret tilstand.
For å lære om den kvantetilstanden måler forskerne alle qubitene i matrisen. Dette får deres kollektive kvantetilstand til å kollapse til en tilfeldig streng med vanlige biter - 0-er og 1-er. Antallet mulige utfall vokser raskt med antall qubits i matrisen: Med 53 qubits, som i Googles eksperiment, er det nesten 10 kvadrillioner. Og ikke alle strenger er like sannsynlige. Sampling fra en tilfeldig krets betyr å gjenta slike målinger mange ganger for å bygge opp et bilde av sannsynlighetsfordelingen som ligger til grunn for utfallene.
Spørsmålet om kvantefordel er ganske enkelt dette: Er det vanskelig å etterligne den sannsynlighetsfordelingen med en klassisk algoritme som ikke bruker noen sammenfiltring?
I 2019, forskere beviste at svaret er ja for feilfrie kvantekretser: Det er faktisk vanskelig å klassisk simulere et tilfeldig kretsprøveeksperiment når det ikke er noen feil. Forskerne jobbet innenfor rammen av beregningskompleksitetsteori, som klassifiserer den relative vanskeligheten til ulike problemer. På dette feltet behandler ikke forskere antall qubits som et fast tall, for eksempel 53. «Tenk på det som n, som er et tall som kommer til å øke," sa Aram Harrow, en fysiker ved Massachusetts Institute of Technology. «Da vil du spørre: Gjør vi ting der innsatsen er eksponentiell n eller polynom i n?” Dette er den foretrukne måten å klassifisere en algoritmes kjøretid - når n vokser seg stor nok, en algoritme som er eksponentiell i n ligger langt bak enhver algoritme som er polynom i n. Når teoretikere snakker om et problem som er vanskelig for klassiske datamaskiner, men enkelt for kvantedatamaskiner, refererer de til denne forskjellen: Den beste klassiske algoritmen tar eksponentiell tid, mens en kvantedatamaskin kan løse problemet i polynomtid.
Likevel ignorerte avisen fra 2019 effekten av feil forårsaket av ufullkomne porter. Dette forlot saken om en kvantefordel for tilfeldig kretsprøvetaking uten feilkorreksjon.
Hvis du forestiller deg kontinuerlig å øke antallet qubits slik kompleksitetsteoretikere gjør, og du også vil ta hensyn til feil, må du bestemme om du også skal fortsette å legge til flere lag med porter - øke kretsdybden, som forskere sier. Anta at du holder kretsdybden konstant på, for eksempel, relativt grunne tre lag, når du øker antallet qubits. Du vil ikke få mye sammenfiltring, og utgangen vil fortsatt være mottagelig for klassisk simulering. På den annen side, hvis du øker kretsdybden for å holde tritt med det økende antallet qubits, vil de kumulative effektene av portfeil vaske ut sammenfiltringen, og utgangen vil igjen bli lett å simulere klassisk.
Men i mellom ligger en Gulllokk-sone. Før det nye papiret var det fortsatt en mulighet for at kvantefordelen kunne overleve her, selv om antallet qubits økte. I dette tilfellet med middels dybde øker du kretsdybden ekstremt sakte etter hvert som antallet qubits vokser: Selv om utgangen stadig vil bli forringet av feil, kan det fortsatt være vanskelig å simulere klassisk ved hvert trinn.
Det nye papiret lukker dette smutthullet. Forfatterne utledet en klassisk algoritme for å simulere tilfeldig kretsprøvetaking og beviste at kjøretiden er en polynomfunksjon av tiden som kreves for å kjøre det tilsvarende kvanteeksperimentet. Resultatet gir en tett teoretisk forbindelse mellom hastigheten til klassiske og kvantetilnærminger til tilfeldig kretsprøvetaking.
Den nye algoritmen fungerer for en stor klasse av kretser med middels dybde, men dens underliggende forutsetninger bryter sammen for visse grunnere, og etterlater et lite gap der effektive klassiske simuleringsmetoder er ukjente. Men få forskere har håp om at tilfeldig kretsprøvetaking vil vise seg å være vanskelig å simulere klassisk i dette gjenværende slanke vinduet. "Jeg gir det ganske små odds," sa Bill Fefferman, en informatiker ved University of Chicago og en av forfatterne av teorioppgaven fra 2019.
Resultatet antyder at tilfeldig kretsprøvetaking ikke vil gi en kvantefordel av de strenge standardene for beregningskompleksitetsteori. Samtidig illustrerer det det faktum at polynomiske algoritmer, som kompleksitetsteoretikere tilfeldig kaller effektive, ikke nødvendigvis er raske i praksis. Den nye klassiske algoritmen blir gradvis tregere etter hvert som feilraten avtar, og med de lave feilratene som oppnås i kvanteoverlegenhetseksperimenter, er det altfor sakte til å være praktisk. Uten feil brytes den helt ned, så dette resultatet motsier ikke noe forskerne visste om hvor vanskelig det er å klassisk simulere tilfeldig kretsprøvetaking i det ideelle, feilfrie tilfellet. Sergio Boixo, fysikeren som leder Googles forskning om kvanteoverherredømme, sier at han ser på oppgaven "mer som en fin bekreftelse på tilfeldig kretsprøvetaking enn noe annet."
På ett punkt er alle forskere enige: Den nye algoritmen understreker hvor avgjørende kvantefeilkorreksjon vil være for den langsiktige suksessen til kvanteberegning. "Det er løsningen på slutten av dagen," sa Fefferman.
