Hoewel het berekenen van complexiteit misschien op pure wiskunde lijkt, bestaat er een diepgaand verband tussen computers en de natuurkundige wetten die hun hulpbronnen – tijd en geheugen – bepalen. Complexiteitstheorie is inderdaad niet alleen pure wiskunde, maar de studie van wiskunde die door de werkelijkheid wordt beperkt. Als je de regels van de werkelijkheid verandert, verander je de grenzen van wat mogelijk is. En het veranderen van de natuurkundige wetten die in computerhardware een rol spelen, zal drastisch veranderen wat een computer kan doen!
Nu blijkt uit een baanbrekend nieuw artikel van promovendus Junqiao (Randy) Lin dat zelfs binnen de kwantummechanica de keuze voor een ander wiskundig model voor kwantumverstrengeling de grenzen van wat kenbaar is volledig verandert. Dit fundamentele resultaat heeft Lin de prestigieuze Best Student Paper-prijs opgeleverd op STOC 2026, een toonaangevende conferentie op het gebied van de theoretische informatica. Lin is onderzoeker bij QuSoft, het Nederlandse onderzoekscentrum voor kwantumsoftware en -technologie dat is opgericht door het CWI en de UvA.
De waarheid achterhalen
Om de wetenschappelijke bevindingen van het artikel te begrijpen, moeten we kijken naar een concept dat ‘interactieve bewijssystemen’ wordt genoemd. Stel je voor dat je een journalist bent die een debat gaat leiden tussen twee briljante maar onbetrouwbare wetenschappers die beweren dat ze een onoplosbaar wiskundig probleem hebben opgelost. Je hebt niet de middelen om hun berekeningen zelf te controleren; je enige kans om te weten of ze de waarheid spreken, is door tijdens de paneldiscussie met hen in gesprek te gaan.
In de complexiteitstheorie ben jij de verificateur (een computer met beperkte rekenkracht), en zijn de wetenschappers de bewijzers (almachtige maar oneerlijke systemen). Door hen scherpe, strategische vragen te stellen om ze elkaar te laten controleren, kun je hun eigen interacties gebruiken om ze op een leugen te betrappen of erachter te komen of hun bewering daadwerkelijk waar is. Ook al zijn ze oneindig veel slimmer dan jij!
Dit model, waarbij de waarheid via een dialoog wordt geverifieerd, vindt zijn oorsprong in een baanbrekend resultaat uit 1990 van de computerwetenschappers László Babai, Lance Fortnow en Carsten Lund. Zij bewezen dat een bepaalde klasse, bekend als MIP = NEXP, geldt. Eenvoudig gezegd toonden zij aan dat een bescheiden verificateur, door meerdere afzonderlijke bewijzers aan een kruisverhoor te onderwerpen, plotseling de oplossingen voor ongelooflijk omvangrijke, exponentiële problemen kon bevestigen; problemen die veel krachtiger zijn dan gewone, efficiënte verificatie.
Kwantumverstrengeling komt in beeld
Dertig jaar lang gingen onderzoekers ervan uit dat deze almachtige bewijzers in volledig geïsoleerde, klassieke ruimtes werden bewaard. Maar in 2020 bracht een baanbrekend artikel de wetenschappelijke wereld op zijn kop door de kwantummechanica in het verhaal te betrekken.
Als je de proefpersonen gedeelde kwantumverstrengeling geeft – een bizar natuurkundig verschijnsel waarbij twee deeltjes zo sterk met elkaar verbonden raken dat wat er met het ene gebeurt onmiddellijk invloed heeft op het andere, zelfs aan de andere kant van het universum – kunnen ze hun antwoorden op manieren synchroniseren die in een klassieke wereld onmogelijk zijn. Dit leidt tot een nieuwe complexiteitsklasse, genaamd MIP*.
Twee wiskundige beschrijvingen van kwantumverstrengeling
Omdat kwantumverstrengeling zo vreemd is, hebben wiskundigen en natuurkundigen decennia lang geprobeerd de exacte regels ervoor op te schrijven. In de loop der tijd zijn er twee verschillende wiskundige kaders ontstaan om deze kwantumcorrelaties te beschrijven:
- Het tensorproductmodel: Hierbij wordt ervan uitgegaan dat de twee verstrengelde systemen verschillend zijn en fysiek van elkaar gescheiden in de ruimte. Dit is het gangbare model dat tegenwoordig wordt gebruikt voor de bouw van kwantumcomputers.
- Het Commuting-Operator-model: Dit is een breder, algemener wiskundig raamwerk. In plaats van aandacht te besteden aan fysieke scheiding, richt het zich op de volgorde van bewerkingen — waarbij wordt gewaarborgd dat bewerkingen die op het ene systeem worden uitgevoerd, het andere systeem niet verstoren.
De doorbraak van 2020: MIP* = RE, maakte gebruik van het eerste raamwerk (het tensorproductmodel). Hiermee werd aangetoond dat wanneer bewijzers dit soort verstrengeling gebruiken, de kracht van de verificateur drastisch toeneemt. Plotseling kan een computer met beperkte capaciteit uitspraken verifiëren die „recursief opsombaar” (RE) zijn. Dit betekent dat de computer altijd kan vaststellen of een uitspraak waar is, ook al zou het programma oneindig lang kunnen draaien als de uitspraak onwaar is. Het ultieme voorbeeld hiervan is hetberoemde Halting-probleemvan Alan Turing – het vaststellen of een computerprogramma oneindig in een lus blijft hangen of uiteindelijk stopt – waarvan eerder werd aangenomen dat het onberekenbaar was.
Dit inzicht heeft niet alleen de informatica veranderd; het heeft ook een kettingreactie teweeggebracht in andere vakgebieden, waardoor belangrijke, al lang bestaande raadsels, zoals de inbeddingsstelling van Connes in de operatoralgebra en het probleem van Tsirelson in de kwantummechanica, werden weerlegd.
De kwantumbeschrijving omdraaien: MIP^co = coRE
Dit is precies waar het bekroonde artikel van Lin om de hoek komt kijken. In plaats van het standaardkader van het tensorproduct te gebruiken, onderzocht Lin wat er gebeurt met interactieve bewijzen vanuit dat tweede, algemenere perspectief: het model van commuterende operatoren, MIP^co.
Zijn belangrijkste resultaat bewijst iets verbazingwekkends: MIP^co = coRE
Door het wiskundige raamwerk te veranderen dat wordt gebruikt om kwantumverstrengeling te beschrijven, keert de kracht van het gehele systeem volledig om. In plaats van de waarheid van onberekenbare problemen te verifiëren (RE), kan de verificateur nu alleen nog definitief bevestigen wanneer een bewering onwaar is (coRE). Als de bewering daadwerkelijk waar is, kan de computer in een oneindige lus terechtkomen.
Het onderzoek van Lin biedt een geheel nieuwe formulering van onberekenbaarheid, met verstrekkende gevolgen die terugreiken tot de operatoralgebra en de kwantummechanica. Uiteindelijk leidt dit tot een opvallende conclusie: wat we via de wiskunde van het rekenen kunnen verifiëren, verandert drastisch, afhankelijk van welk van de twee wiskundige kaders we gebruiken om de natuurkunde te modelleren.
