KI-system skal ha bevist 18 år gammel formodning om kvantedatamaskiner
Forskningsselskapet PSI har offentliggjort et maskinkontrollert bevis for Aaronson–Ambainis-formodningen. Den matematiske påstanden kan kontrolleres, men uavhengig faglig gjennomgang gjenstår.
·5 min lesing
Konseptillustrasjon av matematisk kompleksitet og formell beviskontroll, ikke en figur fra PSI-beviset.Illustrasjon generert med OpenAI for Progress Radar
Et forskningssystem med kunstig intelligens skal ha løst et matematisk problem som har stått åpent siden 2008. Den 6. november kunngjorde Physical Superintelligence (PSI) at systemet hadde funnet et bevis for Aaronson–Ambainis-formodningen, et spørsmål om grensene for hvor mye raskere kvantedatamaskiner kan være enn vanlige datamaskiner.
PSI har offentliggjort både en faglig fremstilling og en formell versjon av beviset skrevet for Lean, et program som kontrollerer matematiske slutninger. Det gjør resultatet mer etterprøvbart enn en vanlig KI-generert påstand. Beviset er likevel ikke fagfellevurdert, og det er fortsatt viktig å kontrollere at den formelle påstanden nøyaktig tilsvarer den opprinnelige formodningen.
Hva var det uløste problemet?
Scott Aaronson og Andris Ambainis formulerte formodningen i 2008. Den handler om polynomer som beskriver hvordan sannsynligheten for et ja-svar fra en kvantealgoritme avhenger av bitene i inndataene. Den matematiske påstanden sier, forenklet, at et slikt polynom med lav grad og merkbar variasjon må ha minst én inngangsbit som påvirker resultatet tilstrekkelig mye.
Det har en konsekvens for såkalt spørringskompleksitet: hvor mange ganger en algoritme må undersøke inndataene. Dersom formodningen holder, kan en klassisk algoritme etterligne en kvantealgoritmes svar på nesten alle tilfeldig valgte inndata med høyst polynomisk flere spørringer. Resultatet gjelder denne bestemte modellen og denne typen gjennomsnittlig oppførsel, ikke en generell øvre grense for all kvanteberegning eller total kjøretid.
Et KI-system og et kontrollerbart bevis
PSI oppgir at et internt forskningssystem brukte instanser av en ikke offentlig tilgjengelig modell fra Anthropic. Ifølge selskapet fant systemet et fullstendig bevis på den tredje dagen av én kjøring, før det forbedret den matematiske grensen ytterligere to ganger.
Den offentliggjorte formaliseringen viser en konkret grense: For et polynom av grad d med varians minst ε finnes en bit med innflytelse på minst en konstant ganger ε opphøyd i 5/2, delt på d opphøyd i 6. PSI viser at dette også oppfyller den svakere formen med (ε/d) opphøyd i 7, slik den opprinnelige formodningen etterspør.
Lean-koden og kontrollinstruksjonene er offentlig tilgjengelige. PSI rapporterer kontroller med flere beviskontrollere og uten ekstra aksiomer eller ufullførte bevissteg i hovedresultatet. Dette er dokumentasjon fra prosjektet selv. Vi har ikke kjørt kontrollene uavhengig, og den maskinelle kontrollen omfatter ikke automatisk alle forklaringer og konsekvenser i forskningsartikkelen.
Hva betyr resultatet for kvanteteknologi?
Et gyldig bevis vil avklare en viktig teoretisk grense: På typiske, ustrukturerte ja/nei-inndata kan kvantealgoritmer ikke få en eksponentiell fordel i antall spørringer under de aktuelle forutsetningene. Det utelukker ikke store kvantefordeler for problemer med særskilt struktur, og endrer ikke eksisterende algoritmer som Shors faktorisering.
PSI sier at forskere ved Stanford som tidligere løste et spesialtilfelle, har lest og kommentert beviset og arbeider med en kortere faglig fremstilling. En uavhengig publisert verifikasjon og ordinær fagfellevurdering er foreløpig ikke dokumentert. Nyheten er derfor både et mulig gjennombrudd i kvantekompleksitet og en viktig prøve på hvordan KI-utviklet matematikk bør kontrolleres.
Et eksperiment publisert i Nature viser posisjonsverifisering basert på en Bell-test over et kvantenettverk. Resultatet er lovende, men sikkerhetsdemonstrasjonen gjelder en avgrenset trusselmodell.
To studier publisert 16. november viser at automatisk kvantefeilretting kan beskytte en logisk kvantebit lenger enn systemets beste fysiske kvantebit. Den ene rapporterer 2,0 millisekunders levetid, 18 prosent over referansen.
Forskere har laget et porøst krystallmateriale der lys danner elektronpar med kontrollert spinnpolarisering. Spinnresponsen endres med løsemiddelet rundt materialet, et mulig første steg mot kjemisk følsomme kvantesystemer.