Et slående nytt bevis i kvanteberegningskompleksitet kan best forstås med et lekent tankeeksperiment. Kjør et bad, og dump deretter en haug med flytende stangmagneter i vannet. Hver magnet vil vende sin orientering frem og tilbake, og prøve å justere med naboene. Den vil presse og trekke på de andre magnetene og bli dyttet og trukket i retur. Prøv nå å svare på dette: Hva blir systemets endelige ordning?
Dette problemet og andre lignende, viser det seg, er umulig kompliserte. Med noe mer enn noen få hundre magneter, ville datasimuleringer ta ufattelig lang tid å spytte ut svaret.
Gjør nå disse magnetene til kvante - individuelle atomer underlagt de bysantinske reglene i kvanteverdenen. Som du kanskje gjetter, blir problemet enda vanskeligere. "Interaksjonene blir mer kompliserte," sa Henry Yuen ved Columbia University. "Det er en mer komplisert begrensning når to nabo 'kvantemagneter' er lykkelige."
Disse enkle systemene har gitt eksepsjonell innsikt i grensene for beregning, både i den klassiske og kvanteversjonen. Når det gjelder klassiske eller ikke-kvantesystemer, a landemerkesetning fra informatikk tar oss videre. Kalt PCP-teoremet (for "sannsynligvis kontrollerbart bevis"), sier det at ikke bare er den endelige tilstanden til magnetene (eller aspekter relatert til den) utrolig vanskelig å beregne, men det er også mange av trinnene som fører frem til det. Kompleksiteten i situasjonen er enda mer drastisk, med andre ord, med den endelige tilstanden omgitt av en sone av mystisk.
En annen versjon av PCP-teoremet, som ennå ikke er bevist, omhandler spesifikt kvantetilfellet. Dataforskere mistenker at kvante-PCP-formodningen er sann, og å bevise den vil endre vår forståelse av kompleksiteten til kvanteproblemer. Det anses uten tvil det viktigste åpne problemet i kvanteberegningskompleksitetsteori. Men så langt har det vært uoppnåelig.
For ni år siden identifiserte to forskere et delmål for å hjelpe oss å komme dit. De kom på en enklere hypotese, kjent som "no low-energy trivial state" (NLTS) formodning, som må være sann hvis kvante PCP-formodningen er sann. Å bevise det ville ikke nødvendigvis gjøre det lettere å bevise kvante PCP-formodningen, men det ville løse noen av de mest spennende spørsmålene.
Så i forrige måned tre informatikere beviste NLTS-antagelsen. Resultatet har slående implikasjoner for informatikk og kvantefysikk.
"Det er veldig spennende," sa Dorit Aharonov ved det hebraiske universitetet i Jerusalem. "Det vil oppmuntre folk til å se nærmere på det vanskeligere problemet med kvante-PCP-formodningen."
For å forstå det nye resultatet, start med å forestille deg et kvantesystem som et sett med atomer. Hvert atom har en egenskap, kalt spinn, som ligner litt på justeringen av en magnet, ved at den peker langs en akse. Men i motsetning til en magnets justering, kan et atoms spinn være i en tilstand som er en samtidig blanding av forskjellige retninger, et fenomen kjent som superposisjon. Videre kan det være umulig å beskrive spinnene til ett atom uten å ta hensyn til spinnene til andre atomer fra fjerne områder. Når dette skjer, sies de innbyrdes beslektede atomene å være i en tilstand av kvantesammenfiltring. Sammenfiltring er bemerkelsesverdig, men også skjør og lett forstyrret av termiske interaksjoner. Jo mer varme i et system, jo vanskeligere er det å vikle det inn.
Tenk deg nå å kjøle ned en haug med atomer til de nærmer seg absolutt null. Etter hvert som systemet blir kjøligere og sammenfiltringsmønstrene blir mer stabile, reduseres energien. Den lavest mulige energien, eller «jordenergi», gir en kortfattet beskrivelse av den kompliserte slutttilstanden til hele systemet. Eller i det minste ville det, hvis det kunne beregnes.
Fra slutten av 1990-tallet oppdaget forskere at for visse systemer kunne denne bakkeenergien aldri beregnes innen en rimelig tidsramme.
Imidlertid mente fysikere at et energinivå nær bakkeenergien (men ikke helt der) burde være lettere å beregne, siden systemet ville være varmere og mindre sammenfiltret, og derfor enklere.
Dataforskere var uenige. I følge det klassiske PCP-teoremet er energier nær slutttilstanden like vanskelige å beregne som selve den endelige energien. Og så kvanteversjonen av PCP-teoremet, hvis sant, vil si at forløperenergiene til bakkeenergien ville være like vanskelig å beregne som bakkeenergien. Siden det klassiske PCP-teoremet er sant, mener mange forskere at kvanteversjonen også burde være sann. "Sikkert, en kvanteversjon må være sann," sa Yuen.
De fysiske implikasjonene av et slikt teorem ville være dyptgripende. Det ville bety at det er kvantesystemer som beholder sammenfiltringen ved høyere temperaturer - totalt i motsetning til fysikernes forventninger. Men ingen kunne bevise at slike systemer eksisterer.
I 2013 begrenset Michael Freedman og Matthew Hastings, begge jobbet ved Microsoft Researchs Station Q i Santa Barbara, California, problemet. De bestemte seg for å se etter systemer hvis laveste og nesten laveste energier er vanskelige å beregne i henhold til bare én beregning: mengden kretser det ville ta for en datamaskin å simulere dem. Disse kvantesystemene, hvis de kunne finne dem, ville måtte beholde rike sammenfiltringsmønstre ved alle sine laveste energier. Eksistensen av slike systemer vil ikke bevise kvante PCP-formodningen - det kan være andre hardhetsmålinger å vurdere - men det vil telle som fremgang.
Dataforskere visste ikke om noen slike systemer, men de visste hvor de skulle lete etter dem: i studieområdet kalt kvantefeilkorreksjon, der forskere lager sammenfiltringsoppskrifter som er designet for å beskytte atomer mot forstyrrelser. Hver oppskrift er kjent som en kode, og det er mange koder av både større og mindre størrelse.
På slutten av 2021, informatikere fikk et stort gjennombrudd ved å lage kvantefeilkorrigerende koder av en i hovedsak ideell natur. I løpet av de påfølgende månedene bygde flere andre grupper av forskere på disse resultatene for å lage forskjellige versjoner.
De tre forfatterne av den nye artikkelen, som hadde samarbeidet om relaterte prosjekter de siste to årene, kom sammen for å bevise at en av de nye kodene hadde alle egenskapene som trengs for å lage et kvantesystem av den typen som Freedman og Hastings hadde antatt. . Ved å gjøre dette beviste de NLTS-antagelsen.
Resultatet deres viser at sammenfiltring ikke nødvendigvis er så skjørt og følsomt for temperatur som fysikere trodde. Og den støtter kvante PCP-formodningen, og antyder at selv borte fra bakkeenergien, kan et kvantesystems energi forbli praktisk talt umulig å beregne.
"Det forteller oss at det som virket usannsynlig å være sant, er sant," sa Isaac Kim ved University of California, Davis. "Om enn i et veldig merkelig system."
Forskere tror at forskjellige tekniske verktøy vil være nødvendig for å bevise den fulle kvante-PCP-formodningen. De ser imidlertid grunner til å være optimistiske om at det nåværende resultatet vil bringe dem nærmere.
De er kanskje mest fascinert av om de nyoppdagede NLTS-kvantesystemene - selv om det er mulig i teorien - faktisk kan skapes i naturen, og hvordan de vil se ut. I følge det nåværende resultatet ville de kreve komplekse mønstre av langdistanseforviklinger som aldri har blitt produsert i laboratoriet, og som bare kan bygges ved hjelp av astronomiske antall atomer.
"Dette er svært konstruerte objekter," sa Chinmay Nirkhe, en informatiker ved University of California, Berkeley, og en medforfatter av det nye papiret sammen med Anurag Anshu fra Harvard University og Nikolas Breuckmann ved University College London.
"Hvis du har evnen til å koble sammen virkelig fjerne qubits, tror jeg du kan realisere systemet," sa Anshu. "Men det er en annen reise å ta for å virkelig gå til lavenergispekteret." La til Breuckmann, "Kanskje det er en del av universet som er NLTS. Jeg vet ikke."
