PSI: AI vond bewijs voor vermoeden uit 2008 over de grenzen van quantumcomputers

Eind oktober schreven we over vijf bewijzen in de quantum-informatietheorie die het Amerikaanse bedrijf Physical Superintelligence (PSI) met hulp van een eigen AI-systeem had gevonden. Elk van die bewijzen was ook gecontroleerd door Lean, een programma dat een wiskundig bewijs stap voor stap naloopt. Nu meldt PSI een veel groter resultaat: volgens het bedrijf heeft zijn AI-systeem een bewijs gevonden voor het Aaronson-Ambainis-vermoeden, een open vraag uit 2008 over de grenzen van quantumcomputers. PSI maakte dat op 6 november bekend.

Een vermoeden is een wiskundige bewering die veel onderzoekers voor waar houden, maar die nog niemand heeft bewezen. Dit vermoeden is genoemd naar de informatici Scott Aaronson (University of Texas at Austin) en Andris Ambainis, en geldt als een van de centrale open vragen over quantumcomputers. PSI is een jong bedrijf uit Cambridge in de Amerikaanse staat Massachusetts. Het ging in september 2026 van start en wil een natuurkundelab worden dat vanaf het begin op AI is gebouwd.

Waarom deze vraag ertoe doet

Quantumcomputers kunnen sommige problemen veel sneller oplossen dan gewone computers. Het bekendste voorbeeld is het algoritme van de wiskundige Peter Shor uit 1994, dat grote getallen ontbindt in de priemgetallen waaruit ze zijn opgebouwd. Bij alle bekende voorbeelden van zo'n enorme winst heeft het probleem een speciale regelmaat. Bij Shor is dat een patroon in de getallen dat zich steeds herhaalt. Aaronson en Ambainis vroegen zich af of dat altijd zo is. Kan een quantumcomputer ook enorm veel sneller zijn bij gewone, willekeurige invoer, zonder zo'n regelmaat?

Om dat te meten, tellen onderzoekers hoe vaak een algoritme in de invoer moet kijken. Stel dat de invoer een lange rij nullen en enen is, en dat het algoritme een ja-of-neevraag over die rij moet beantwoorden. Elke keer dat het naar één plek in de rij kijkt, telt als één stap. De vraag is dan hoeveel stappen een gewone computer nodig heeft om hetzelfde te doen als een quantumcomputer.

Daarbij gaat het om de manier waarop het verschil groeit. Bij een exponentieel verschil verdubbelt het aantal stappen van de gewone computer bijvoorbeeld bij elke extra stap van de quantumcomputer: bij 10 quantumstappen zijn het er ruim duizend, bij 20 al ruim een miljoen. Bij een polynomiaal verschil groeit het veel trager, zoals een kwadraat of een andere vaste macht: bij 10 quantumstappen 100, bij 20 stappen 400.

Aaronson en Ambainis lieten zien dat hun vermoeden, als het klopt, het antwoord geeft. Dan kan een gewone computer het antwoord van een quantumcomputer voor bijna alle invoer goed voorspellen met een aantal stappen dat hooguit polynomiaal groter is. Grote quantumwinsten vragen dan altijd om invoer met een speciale structuur.

Wat het vermoeden zegt

Het vermoeden zelf gaat over formules. De kans dat een quantumalgoritme "ja" antwoordt, kun je schrijven als een formule met de nullen en enen van de invoer erin, een zogeheten polynoom. Onderzoekers bewezen al eind jaren negentig dat die formule eenvoudiger is naarmate het algoritme minder stappen zet.

Het vermoeden zegt: zolang de uitkomst van zo'n formule niet voor elke invoer hetzelfde is, is er altijd minstens één plek in de invoer met merkbare invloed. Met invloed bedoelen wiskundigen hoeveel de uitkomst gemiddeld verandert als je op die ene plek een nul in een één verandert, of andersom.

Dat helpt een gewone computer. Is er altijd zo'n invloedrijke plek, dan kan hij die plek als eerste bekijken. Daarmee ligt een deel van de uitkomst vast. Volgens het vermoeden zit er in wat nog onzeker is weer een invloedrijke plek, die hij daarna bekijkt. Zo wordt de uitkomst bij elke stap zekerder, totdat die voor bijna alle invoer vrijwel vastligt. Dan weet de gewone computer wat de quantumcomputer zou antwoorden.

Het moeilijke was hoe groot die invloed minstens is. Al in 2006 bewezen andere onderzoekers dat er altijd zo'n plek is. Maar de invloed die ze konden garanderen, werd exponentieel kleiner naarmate de formule ingewikkelder werd. Met zo'n kleine invloed verandert elke stap van de gewone computer zo weinig aan de onzekerheid dat hij enorm veel stappen nodig heeft, en is er van de aanpak weinig over. PSI zegt nu te hebben bewezen dat de invloed alleen polynomiaal kleiner wordt, dus veel trager. Dat is precies wat Aaronson en Ambainis vermoedden.

Hoe het bewijs werd gevonden

PSI gebruikte een onderzoekssysteem dat het zelf heeft gebouwd en dat werkte met een niet-openbaar AI-model van het AI-bedrijf Anthropic. Het bedrijf noemt de naam van dat model niet. Volgens PSI had het systeem op de derde dag van een rekensessie op de eigen computers een volledig bewijs, en keurde Lean het goed. Daarna liet PSI het systeem verwante open vragen aanpakken. Daarbij verbeterde het systeem het resultaat nog twee keer, en ook die laatste versie keurde Lean goed.

Volgens PSI maakte de AI de wiskundige beweringen, de eerste versie van het artikel en de versie van het bewijs in Lean. David Turturean, onderzoeker bij PSI, bouwde het systeem, koos het probleem, liet het systeem draaien en heeft het artikel nagelezen. Hij is verantwoordelijk voor de juistheid ervan. Jim Halverson, adviseur van PSI, controleerde het bewijs, en adviseur Phiala Shanahan gaf commentaar op de Lean-versie.

Het bewijs volgt een plan van de wiskundigen Shachar Lovett en Jiapeng Zhang. Zij hadden een route naar het bewijs uitgestippeld, maar één tussenstap daarin was nog niet bewezen. Het nieuwe bewijs vervangt die tussenstap door een andere, die PSI wel heeft bewezen.

Dat Lean het bewijs controleert, is hier extra waardevol. Eind 2019 meldden twee wiskundigen al eens een bewijs van hetzelfde vermoeden, maar daarin bleek een subtiele fout te zitten. Lean keurt een bewijs alleen goed als elke stap klopt. Wat mensen nog wel moeten nagaan, is of de bewering zoals die in Lean is opgeschreven precies hetzelfde zegt als het vermoeden op papier. PSI heeft die beweringen in één apart bestand gezet, dat vakgenoten kunnen nalezen. Het artikel, het Lean-bewijs en de software om de controle zelf te draaien staan openbaar op GitHub.

Vakgenoten lezen mee

In augustus 2026 bewezen Guy Blanc, Jordan Docter, Carmen Strassle en Li-Yang Tan van Stanford University een deel van het vermoeden. Zij lieten zien dat er bij willekeurige invoer geen exponentiële winst is voor quantumalgoritmes die in een vast aantal rondes naar de invoer kijken, met in elke ronde veel plekken tegelijk. Zij lezen nu het bewijs van PSI na, hebben al commentaar gestuurd en schrijven een kortere uitleg voor vakgenoten. Op de site van PSI noemen ze het een enorm resultaat dat een vermoeden van decennia oud oplost.

Het artikel is nog niet in een wetenschappelijk tijdschrift verschenen en nog niet formeel beoordeeld door andere onderzoekers. Aaronson en Ambainis hebben vrijdagavond nog niet publiek gereageerd. Nu is het aan meer vakgenoten om het bewijs na te lopen. Omdat alles openbaar staat, kan dat meteen.

Wat betekent dit voor de weg naar de singulariteit?

Aan dit vermoeden werkten deskundigen achttien jaar, en een eerder bewijs bleek fout. Nu vond een AI-systeem volgens PSI binnen enkele dagen een bewijs dat een computer stap voor stap heeft gecontroleerd. Houdt het bewijs stand bij vakgenoten, dan is het een duidelijk voorbeeld van AI die een bekende open vraag uit de wiskunde oplost, met mensen die het probleem kiezen en het resultaat controleren.

Het resultaat zelf vertelt ook iets over quantumcomputers. Klopt het bewijs, dan staat vast dat wie een grote quantumwinst zoekt, moet kijken naar problemen met een speciale structuur, zoals bij Shor. Dat helpt onderzoekers om gerichter te zoeken naar taken waarvoor quantumcomputers echt het verschil maken. En omdat een computer elk bewijs van dit soort kan nalopen, hoeven onderzoekers het werk van een AI niet op zijn woord te geloven. Dat maakt het makkelijker om erop voort te bouwen.

Wat is de technologische singulariteit? Lees de uitleg →