Ett slående nytt bevis i kvantberäkningskomplexitet kan bäst förstås med ett lekfullt tankeexperiment. Kör ett bad och dumpa sedan ett gäng flytande stångmagneter i vattnet. Varje magnet kommer att vända sin orientering fram och tillbaka och försöka anpassa sig efter sina grannar. Den kommer att trycka och dra i de andra magneterna och tryckas och dras i retur. Försök nu att svara på detta: Vad blir systemets slutliga upplägg?
Det här problemet och andra liknande det visar sig vara omöjligt komplicerade. Med något mer än några hundra magneter skulle datorsimuleringar ta en befängd tid att spotta ut svaret.
Gör nu dessa magneter till kvantum - individuella atomer som är föremål för kvantvärldens bysantinska regler. Som du kanske gissar blir problemet ännu svårare. "Interaktionerna blir mer komplicerade," sa Henry Yuen vid Columbia University. "Det finns en mer komplicerad begränsning när två angränsande 'kvantmagneter' är lyckliga."
Dessa enkla system har gett exceptionella insikter om gränserna för beräkningar, både i den klassiska och kvantversionen. I fallet med klassiska eller icke-kvantsystem, a landmärkessats från datavetenskap tar oss vidare. Kallas PCP-teoremet (för "probabilistiskt kontrollerbart bevis"), det säger att det inte bara är det slutliga tillståndet för magneterna (eller aspekter relaterade till det) otroligt svårt att beräkna, utan det är också många av stegen som leder fram till det. Komplexiteten i situationen är ännu mer drastisk, med andra ord, med sluttillståndet omgivet av en zon av mystiskt.
En annan version av PCP-satsen, ännu inte bevisad, handlar specifikt om kvantfallet. Datavetare misstänker att kvant-PCP-förmodan är sann, och att bevisa att det skulle förändra vår förståelse av komplexiteten i kvantproblem. Det anses utan tvekan vara det viktigaste öppna problemet i teorin om kvantberäkningskomplexitet. Men än så länge har den varit oåtkomlig.
För nio år sedan identifierade två forskare ett delmål för att hjälpa oss komma dit. De kom på en enklare hypotes, känd som "no low-energy trivial state" (NLTS) förmodan, vilket måste vara sant om kvant-PCP-förmodan är sann. Att bevisa det skulle inte nödvändigtvis göra det lättare att bevisa kvant-PCP-förmodan, men det skulle lösa några av dess mest spännande frågor.
Sedan förra månaden, tre datavetare bevisade NLTS-förmodan. Resultatet har slående konsekvenser för datavetenskap och kvantfysik.
"Det är väldigt spännande," sa Dorit Aharonov vid hebreiska universitetet i Jerusalem. "Det kommer att uppmuntra människor att undersöka det svårare problemet med kvant-PCP-förmodan."
För att förstå det nya resultatet, börja med att föreställa dig ett kvantsystem som en uppsättning atomer. Varje atom har en egenskap, kallad spinn, som liknar inriktningen av en magnet, genom att den pekar längs en axel. Men till skillnad från en magnets inriktning kan en atoms spinn vara i ett tillstånd som är en samtidig blandning av olika riktningar, ett fenomen som kallas superposition. Vidare kan det vara omöjligt att beskriva spinn av en atom utan att ta hänsyn till spinn av andra atomer från avlägsna regioner. När detta händer, sägs dessa inbördes relaterade atomer vara i ett tillstånd av kvantintrassling. Intrassling är anmärkningsvärd, men också ömtålig och lätt störd av termiska interaktioner. Ju mer värme i ett system, desto svårare är det att trassla in det.
Föreställ dig nu att kyla ner ett gäng atomer tills de närmar sig absolut noll. När systemet blir svalare och mönster av intrassling blir mer stabila, minskar dess energi. Lägsta möjliga energi, eller "jordenergi", ger en kortfattad beskrivning av det komplicerade sluttillståndet för hela systemet. Eller åtminstone skulle det göra det, om det gick att beräkna.
Med början i slutet av 1990-talet upptäckte forskare att för vissa system kunde denna markenergi aldrig beräknas inom någon rimlig tidsram.
Men fysiker trodde att en energinivå nära markenergin (men inte riktigt där) borde vara lättare att beräkna, eftersom systemet skulle vara varmare och mindre intrasslat och därför enklare.
Datavetare var inte överens. Enligt den klassiska PCP-satsen är energier nära sluttillståndet lika svåra att beräkna som själva slutenergin. Och så skulle kvantversionen av PCP-satsen, om den stämmer, säga att prekursorenergierna till markenergin skulle vara lika svåra att beräkna som markenergin. Eftersom det klassiska PCP-teoremet är sant, tror många forskare att kvantversionen också borde vara sann. "Visst måste en kvantversion vara sann," sa Yuen.
De fysiska implikationerna av ett sådant teorem skulle vara djupgående. Det skulle betyda att det finns kvantsystem som behåller sin intrassling vid högre temperaturer - helt i strid med fysikernas förväntningar. Men ingen kunde bevisa att några sådana system existerar.
Under 2013 minskade Michael Freedman och Matthew Hastings, som båda arbetade på Microsoft Researchs Station Q i Santa Barbara, Kalifornien, problemet. De bestämde sig för att leta efter system vars lägsta och nästan lägsta energier är svåra att beräkna enligt bara ett mått: mängden kretsar det skulle ta för en dator att simulera dem. Dessa kvantsystem, om de kunde hitta dem, skulle behöva behålla rika mönster av intrassling vid alla sina lägsta energier. Förekomsten av sådana system skulle inte bevisa kvant-PCP-förmodan - det kan finnas andra hårdhetsmått att överväga - men det skulle räknas som framsteg.
Datavetare kände inte till några sådana system, men de visste vart de skulle leta efter dem: inom det studieområde som kallas kvantfelskorrigering, där forskare skapar recept för intrassling som är utformade för att skydda atomer från störningar. Varje recept är känt som en kod, och det finns många koder av både större och mindre storlek.
I slutet av 2021, datavetare gjort ett stort genombrott att skapa kvantfelkorrigerande koder av i huvudsak idealisk natur. Under de efterföljande månaderna byggde flera andra grupper av forskare på dessa resultat för att skapa olika versioner.
De tre författarna till den nya uppsatsen, som hade samarbetat i relaterade projekt under de senaste två åren, gick samman för att bevisa att en av de nya koderna hade alla egenskaper som behövs för att göra ett kvantsystem av det slag som Freedman och Hastings hade antagit. . Därmed bevisade de NLTS-förmodan.
Deras resultat visar att intrassling inte nödvändigtvis är så ömtålig och känslig för temperatur som fysiker trodde. Och det stöder kvant-PCP-förmodan, vilket tyder på att även borta från markenergin kan ett kvantsystems energi förbli praktiskt taget omöjlig att beräkna.
"Det säger oss att det som verkade osannolikt vara sant är sant," sa Isaac Kim vid University of California, Davis. "Om än i något väldigt konstigt system."
Forskare tror att olika tekniska verktyg kommer att behövas för att bevisa den fullständiga kvant-PCP-förmodan. De ser dock skäl att vara optimistiska om att det nuvarande resultatet kommer att föra dem närmare.
De är kanske mest fascinerade av huruvida de nyupptäckta NLTS-kvantsystemen – även om de är möjliga i teorin – faktiskt kan skapas i naturen och hur de skulle se ut. Enligt det aktuella resultatet skulle de kräva komplexa mönster av långväga intrassling som aldrig har producerats i laboratoriet, och som bara kunde byggas med hjälp av astronomiska antal atomer.
"Det här är mycket konstruerade föremål," sa Chinmay Nirkhe, en datavetare vid University of California, Berkeley, och en medförfattare till den nya uppsatsen tillsammans med Anurag Anshu från Harvard University och Nikolas Breuckmann från University College London.
"Om du har förmågan att koppla ihop riktigt avlägsna qubits, tror jag att du kan realisera systemet," sa Anshu. "Men det finns en annan resa att ta för att verkligen gå till lågenergispektrumet." Breuckmann lade till, "Kanske finns det någon del av universum som är NLTS. Jag vet inte."
