$\mathsf{EQP}\subseteq\mathsf{IP}$ Does Not Relativize

In de wereld van de informatica is er een fundamentele vraag over wat verschillende soorten machines daadwerkelijk kunnen oplossen. Aan de ene kant hebben we klassieke computers, de machines die ons dagelijks leven aandrijven en informatie verwerken door strikte, stapsgewijze logische regels te volgen. Aan de andere kant staan quantumcomputers, een nieuwere en meer exotische technologie die de vreemde wetten van de fysica gebruikt om vele mogelijkheden tegelijkertijd te verkennen. Decennialang hebben wetenschappers zich afgevraagd of deze twee soorten machines werkelijk verschillend zijn in hun kracht, of dat een slim genoeg klassieke computer uiteindelijk elke quantumtaak zou kunnen nabootsen. Om dit te testen, gebruiken onderzoekers vaak een theoretisch hulpmiddel genaamd een "oracle". Denk aan een oracle als een mysterieuze zwarte doos die specifieke vragen onmiddellijk beantwoordt. Door zowel een klassieke als een quantumcomputer toegang te geven tot dezelfde zwarte doos, kunnen wetenschappers zien of de quantummachine een probleem kan oplossen dat de klassieke machine simpelweg niet kan, ongeacht hoeveel tijd of inspanning deze erin steekt. Deze opstelling helpt de ware grenzen van klassieke logica te onthullen wanneer deze wordt geconfronteerd met quantum-snelheid.

Een recente studie door onderzoekers van de Stony Brook University heeft dit onderzoek verder voortgestuwd door een specifieke discussie over de grenzen van klassieke verificatie te beslechten. Het team construeerde een zeer specifiek type zwarte doos en een bijbehorend probleem dat een quantumcomputer met absolute zekerheid kan oplossen met slechts drie vragen aan de doos. Ze bewezen echter dat geen enkele klassieke computer, zelfs niet een die mag interageren met een krachtige, onbeperkte helper, ditzelfde probleem met dezelfde mate van zekerheid kan oplossen. Dit resultaat is significant omdat het laat zien dat het gat tussen quantum- en klassieke computing niet alleen een kwestie is van snelheid, maar van fundamentele bekwaamheid. Zelfs als een klassieke computer de toestemming krijgt om hulp te vragen van een superintelligentie-prover, kan hij de quantumoplossing voor deze specifieke taak nog steeds niet verifiëren. De onderzoekers hebben aangetoond dat deze scheiding standhoudt, zelfs wanneer de quantumcomputer vereist is om perfect exact te zijn, zonder ruimte voor fouten of waarschijnlijkheid.

De kern van hun ontdekking draait om een wiskundige puzzel bekend als "Forrelation". Stel je twee lijsten met getallen voor, waarbij elk getal ofwel positief ofwel negatief is. De puzzel vraagt je om uit te zoeken hoe nauw deze twee lijsten met elkaar verbonden zijn via een specifieke wiskundige transformatie. In deze nieuwe studie richtten de onderzoekers zich op een versie van de puzzel waarbij de relatie tussen de lijsten wordt beloofd precies één-half of precies negatief één-half te zijn. Een quantumcomputer kan bepalen welke van deze twee gevallen waar is door de zwarte doos slechts drie keer om informatie te vragen. Dit doet de computer door een delicaat interferentiepatroon te creëren, waarbij de antwoorden uit de doos elkaar in het ene scenario opheffen en in het andere scenario versterken, wat leidt tot een duidelijk, definitief antwoord.

De uitdaging voor de onderzoekers was om te bewijzen dat een klassieke computer dit niet kon doen. Ze moesten aantonen dat voor elke strategie die een klassieke computer zou kunnen gebruiken, er altijd een paar lijsten zouden zijn die identiek lijken voor de klassieke machine, maar die eigenlijk tot verschillende categorieën behoren. Om dit te doen, moesten ze een zeer specifieke set regels creëren voor het genereren van deze lijsten. Ze begonnen met een willekeurige distributie van getallen en pasten vervolgens zorgvuldig de tellingen van positieve en negatieve tekens aan om de exacte doelwaarden van de puzzel te bereiken. Dit aanpassingsproces, dat ze een "repair" (herstel) noemden, was het moeilijkste deel van het werk. Ze moesten ervoor zorgen dat terwijl ze de getallen corrigeerden om aan de exacte vereisten te voldoen, ze de lijsten niet per ongeluk anders lieten lijken voor een klassieke waarnemer. Als de lijsten er te verschillend uitzagen, zou een klassieke computer het verschil gemakkelijk kunnen opmerken en de puzzel kunnen oplossen.

De onderzoekers slaagden erin deze "gerepareerde" distributies te creëren. Ze bewezen dat zelfs na het maken van deze precieze aanpassingen, de resulterende lijsten ononderscheidbaar bleven voor elke klassieke computer die binnen de grenzen van de huidige complexiteitstheorie opereert. Dit omvat computers die werken met interactieve bewijzen, waarbij een verifieerder vragen stelt aan een krachtige prover, en computers die opereren binnen de polynomiale hiërarchie, een brede klasse van complexe logische problemen. Het bewijs toonde aan dat, ongeacht hoeveel berichten er werden uitgewisseld of hoe diep de logische redenering ook ging, de klassieke computer het verschil tussen de twee soorten lijsten niet betrouwbaar kon zien. De quantumcomputer kon ze daarentegen met absolute zekerheid onderscheiden met slechts drie queries.

Deze bevinding versterkt ons begrip van de grens tussen klassieke en quantumcomputing. Het bevestigt dat er problemen zijn waarbij quantummechanica een uniek voordeel biedt dat niet gereproduceerd kan worden door klassieke logica, zelfs niet met de hulp van onbeperkte rekenkracht van een prover. De onderzoekers suggereerden deze mogelijkheid niet alleen; ze leverden een rigoureuze wiskundige constructie die de mogelijkheid uitsluit dat klassieke computers in dit specifieke scenario ooit zouden kunnen inhalen. Hun werk steunt op een uniforme quantumalgoritme dat op dezelfde manier werkt voor elke input, gebruikmakend van een vaste set basisoperaties. Deze uniformiteit zorgt ervoor dat het quantumvoordeel geen toevalstreffer is van een specifieke opstelling, maar een robuust kenmerk van de quantumbenadering.

De implicaties van dit werk reiken verder dan alleen het oplossen van een theoretische puzzel. Het helpt de werkelijke kracht van quantumcomputers te definiëren in een wereld waarin ze op een dag voor praktische toepassingen gebruikt kunnen worden. Door aan te tonen dat bepaalde problemen fundamenteel buiten het bereik liggen van klassieke verificatie, benadrukt de studie de unieke rol die quantummachines zullen spelen in de toekomst van de informatica. De methode van de onderzoekers om distributies zorgvuldig te repareren om ononderscheidbaarheid te handhaven terwijl exacte beperkingen worden afgedwongen, is een nieuwe techniek die nuttig kan zijn in andere gebieden van de theoretische informatica. Het demonstreert een hoog niveau van controle over complexe wiskundige structuren, waardoor ze scenario's kunnen ontwerpen waarin de quantummechanica uitblinkt en de klassieke logica faalt.

Uiteindelijk biedt de studie een duidelijk antwoord op een langlopende vraag over de aard van computation. Het laat zien dat het vermogen van een quantumcomputer om een probleem met absolute zekerheid op te lossen met zeer weinig stappen, een capaciteit is die geen enkel klassiek systeem, hoe slim of krachtig ook, kan repliceren. Deze scheiding is niet alleen een gat in efficiëntie, maar een gat in soort. De onderzoekers hebben een brug geslagen tussen abstracte theorie en concreet bewijs, en laten zien dat de quantumwereld volgens regels werkt die fundamenteel verschillend zijn van onze dagelijkse ervaring. Hun werk staat als een testament voor de kracht van de quantummechanica en als een herinnering dat de grenzen van de klassieke computing rigider zijn dan we hadden gehoopt.