Achieving perfect completeness for one- and two-message quantum proof systems

In de wereld van de informatica bestaat er een fundamenteel verschil tussen het controleren van een oplossing en het vinden ervan. Stel je een wiskundige voor die beweert een moeilijke puzzel te hebben opgelost. Als de oplossing correct is, kan een verifieerder het werk snel controleren en het antwoord bevestigen. Dit is de essentie van een bewijssysteem: een manier voor een krachtige maar onbetrouwbare partij om een zwakkere partij ervan te overtuigen dat een stelling waar is. In de klassieke wereld, waar computers bits gebruiken die ofwel nul of één zijn, is dit proces goed begrepen. Echter, wanneer we overstappen naar quantumcomputing, waar informatie bestaat in delicate toestanden van superpositie en verstrengeling, veranderen de regels. Quantumbewijssystemen stellen een bewijzer in staat om quantuminformatie naar een verifieerder te sturen, die vervolgens een meting uitvoert om te beslissen of de claim wordt geaccepteerd. Een cruciale eigenschap van deze systemen is "volledigheid" (completeness), wat meet hoe vaak de verifieerder een ware stelling accepteert. Ideaal gezien zou een systeem "perfecte volledigheid" moeten hebben, wat betekent dat het nooit een fout maakt wanneer de stelling daadwerkelijk waar is; de verifieerder zou met absolute zekerheid moeten accepteren.

Decennialang wisten onderzoekers dat quantumbewijssystemen met drie of meer uitwisselingen van berichten deze perfecte zekerheid kunnen bereiken. Maar een hardnekkige vraag bleef bestaan voor de eenvoudigste gevallen: konden systemen met slechts één of twee berichten hetzelfde doen? In een systeem met één bericht stuurt de bewijzer een enkele quantumtoestand, bekend als een getuige (witness), en de verifieerder controleert deze. In een systeem met twee berichten wisselen de bewijzer en de verifieerder één bericht heen en weer. Jarenlang was het een mysterie of deze slankere systemen ooit even betrouwbaar gemaakt konden worden zonder extra stappen toe te voegen. Deze vraag was niet louter academisch; het raakte aan de grenzen van wat quantumcomputers efficiënt kunnen verifiëren. Als deze eenvoudige systemen geen perfecte volledigheid konden bereiken, zou dat duiden op een fundamentele beperking in hoe we quantumbewijzen kunnen vertrouwen.

Een team van onderzoekers heeft dit langlopende raadsel nu opgelost. Ze hebben aangetoond dat quantumbewijssystemen met één bericht en systemen met twee berichten inderdaad perfecte volledigheid kunnen bereiken. Hun werk bewijst dat het mogelijk is om protocollen te construeren waarbij de verifieerder een ware stelling met honderd procent zekerheid accepteert, zonder extra rondes van communicatie toe te voegen. Deze bevinding is van toepassing op verschillende specifieke klassen van quantumbewijssystemen, inclusief die waar de verifieerder alleen klassieke willekeurige vragen stuurt of helften van verstrengelde deeltjesparen stuurt. De onderzoekers hebben niet alleen gesuggereerd dat dit mogelijk is; ze hebben een concrete wiskundige constructie geleverd die elk bestaand bewijssysteem transformeert naar een nieuw systeem dat perfect compleet is.

Het pad naar deze oplossing omvatte twee verschillende strategieën, afgestemd op de specifieke uitdagingen van één-bericht en twee-bericht systemen. Voor het geval met twee berichten bedachten de onderzoekers een slimme methode om een langere interactie te comprimeren naar een kortere, terwijl de betrouwbaarheid behouden blijft. Ze begonnen met een bekende techniek die de acceptatiekans precies op één-half aanpaste, om een eerlijke basis te garanderen. Vervolgens introduceerden ze een nieuwe transformatie die van de "uiteinden" van de interactie naar binnen werkt. In plaats van in het midden te beginnen en naar buiten uit te waaieren, bereidt de verifieerder de initiële en finale toestanden van de interactie simultaan voor. De bewijzer wordt vervolgens gevraagd de kloof tussen deze twee toestanden te overbruggen. Als de stelling waar is, kan de bewijzer de twee takken perfect uitlijnen, en accepteert de verifieerder met zekerheid. Als de stelling onwaar is, kunnen de takken niet uitlijnen, en detecteert de verifieerder de discrepantie. Deze "inwaartse" benadering stelde hen in staat om een vier-bericht systeem terug te vouwen naar twee berichten zonder de garantie van perfecte volledigheid te verliezen.

Voor het één-bericht geval was de uitdaging anders. Hier stuurt de bewijzer een enkele quantumtoestand, en de verifieerder moet deze controleren zonder enige heen-en-weer communicatie. De onderzoekers benaderden dit door het verificatieproces te behandelen als een wiskundig probleem met betrekking tot matrices, die rasters van getallen zijn die beschrijven hoe quantumtoestanden veranderen. Ze construeerden een specifieke matrix waarbij de "kern" (kernel)—een speciale verzameling toestanden die de matrix in nul verandert—exact overeenkomt met de geldige bewijzen voor ware stellingen. Als de stelling waar is, bestaat er een quantumtoestand die perfect in deze kern zit, en de verifieerder kan de aanwezigheid ervan met absolute zekerheid controleren. Als de stelling onwaar is, bestaat er geen dergelijke toestand, en zal de verifieerder altijd een fout detecteren. Om dit te laten werken, moesten ze ervoor zorgen dat de getallen die deze matrix definiëren, precies berekend kunnen worden met de beperkte reeks operaties die beschikbaar zijn in quantumcomputers. Ze toonden aan dat ze door een specifieke set quantum logische poorten te gebruiken, deze matrix exact konden bouwen, waardoor de kleine afrondingsfouten die dergelijke berekeningen gewoonlijk teisteren, werden vermeden.

De resultaten zijn definitief voor de klassen van systemen die zij bestudeerden. De onderzoekers bewezen dat voor één-bericht systemen die gebruikmaken van een specifieke set quantum poorten, de verifieerder ware stellingen altijd met zekerheid kan accepteren. Op dezelfde manier, voor twee-bericht systemen, of de verifieerder nu klassieke vragen of quantum verstrengelde paren stuurt, is perfecte volledigheid haalbaar. In het scenario met twee berichten reduceert het nieuwe protocol de kans op een valse acceptatie tot een zeer klein getal, minder dan één procent, wat nog kleiner gemaakt kan worden door het proces te herhalen. Het werk verheldert ook de grenzen van deze technieken. De gebruikte methoden steunen op specifieke wiskundige structuren die goed werken voor single-prover systemen, maar niet direct uitbreidbaar zijn naar complexere scenario's met meerdere bewijzers die niet met elkaar kunnen communiceren. Dit laat een nieuwe vraag open: of zelfs complexere quantumbewijssystemen ook perfect compleet gemaakt kunnen worden.

Deze prestatie is significant omdat het een grote onzekerheid in de theorie van quantumverificatie wegneemt. Het toont aan dat de efficiëntie van quantumbewijssystemen niet ten koste gaat van de betrouwbaarheid. Zelfs met het minimale aantal berichten kan een quantumverifieerder onfeilbaar worden gemaakt wanneer de waarheid aan zijn zijde staat. De onderzoekers bereikten dit niet door een nieuw fysiek fenomeen te vinden, maar door de manier waarop bestaande quantumprotocollen gestructureerd zijn te heroverwegen. Ze toonden aan dat door de start- en eindpunten van een interactie zorgvuldig uit te lijnen, of door een precieze wiskundige filter voor geldige bewijzen te construeren, de mogelijkheid van een fout volledig geëlimineerd kan worden. Dit werk biedt een volledig beeld van perfecte volledigheid voor de eenvoudigste quantumbewijssystemen, en lost een vraag op die al sinds de vroege dagen van de quantum complexiteitstheorie openstaat.