Physical Superintelligence (PSI) publicerade den 6 november ett pressmeddelande på sin webbplats och ett manuskript i sitt kodförråd på GitHub. Enligt dessa är Scott Aaronsons och Andris Ambainis förmodan bevisad. Förmodan hade varit olöst sedan 2008, uppger PSI.

Enligt manuskriptet togs dess matematiska påståenden fram av AI-modeller. David Turturean på PSI avgränsade problemet och byggde en harness, alltså ett program som ger modellen verktyg och kör dess arbetssteg. I harnessen arbetade flera instanser av en opublicerad modell från Anthropic. De sökte efter tidigare idéer, föreslog och testade nya och övervakade andra instansers arbete. Beviset var klart på körningens tredje dag, uppger PSI.

Även manuskriptets första utkast skrevs av modellen. Turturean säger sig ha granskat och redigerat utkastet och ansvara för dess riktighet.

Vad resultatet säger om kvantdatorer

Indata är en lång sträng av nollor och ettor. I frågemodellen räknar man hur många gånger algoritmen läser den. Sedan tidigare var det känt att sannolikheten att en kvantalgoritm svarar ”ja” efter T frågor är ett polynom i indatabitarna. Polynomets grad är högst 2T och dess värden ligger mellan noll och ett.

Enligt förmodan har ett sådant polynom en inflytelserik bit om polynomets värde inte är konstant. En bits inflytande (influence) är medelvärdet över alla indata av kvadraten på förändringen i polynomets värde när biten vänds. I manuskriptet anges att någon bit har ett inflytande på minst (ε/d)⁷, där d är polynomets grad och ε en nedre gräns för dess varians. Tidigare allmänna nedre gränser försvagades exponentiellt när graden växte.

Enligt ett tidigare resultat av Aaronson och Ambainis kan en vanlig algoritm därmed läsa inflytelserika bitar en i taget. Med högst (4T)⁸ ε⁻¹⁴ δ⁻⁸ frågor uppskattar den kvantalgoritmens ja-sannolikhet med ett fel på högst ε för alla indata utom en andel δ, står det i manuskriptet. Antalet frågor växer polynomiellt och inte exponentiellt.

Resultatet gäller inte strukturerade indata. Enligt manuskriptet kräver en större än polynomiell kvantuppsnabbning i frågemodellen struktur, till exempel en garanti för hur indata ser ut. Exempelvis bygger Shors faktoriseringsalgoritm på en sådan struktur, uppger PSI.

Beviset och kontrollen av det

Beviset följer Shachar Lovetts och Jiapeng Zhangs plan men ersätter den olikhet som de lämnade som förmodan med en ny. Beviset för den nya olikheten parar ihop indata en till en med hjälp av en determinant.

Enligt manuskriptet har huvudsatsen och dess följdsats formaliserats i bevisassistenten Lean, och Leans kärna har godkänt dem. Formaliseringen finns i PSI:s kodförråd. Beviset granskades av PSI:s rådgivare Jim Halverson.

Guy Blanc, Jordan Docter, Carmen Strassle och Li-Yang Tan vid Stanford University bevisade i augusti en konsekvens av förmodan i specialfallet där kvantalgoritmen läser sina indata i ett fast antal parallella omgångar. Enligt PSI har de läst beviset och skriver en kortare framställning av det för experter. I ett meddelande på PSI:s webbplats skriver de: ”Det här är ett enormt resultat. Det löser en årtionden gammal förmodan med viktiga konsekvenser för vilken sorts problem som medger kvantuppsnabbningar.”

Det rör sig om ett manuskript som företaget självt har publicerat. Källorna säger inget om referentgranskning.