⚛️ quantum physics

Separating Non-Interactive Classical Verification of Quantum Computation from Falsifiable Assumptions

Dit artikel bewijst dat er geen kwantum-black-box-reductie bestaat van niet-interactieve klassieke verificatie van kwantumberekeningen naar falsifieerbare aannames, wat impliceert dat dergelijke protocollen niet kunnen worden gebaseerd op standaard cryptografische veronderstellingen zoals LWE.

Oorspronkelijke auteurs: Mohammed Barhoush, Tomoyuki Morimae, Ryo Nishimaki, Takashi Yamakawa

Gepubliceerd 2026-02-23

📖 5 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Mohammed Barhoush, Tomoyuki Morimae, Ryo Nishimaki, Takashi Yamakawa

Oorspronkelijk artikel gelicentieerd onder CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dit is een AI-gegenereerde uitleg van het onderstaande artikel. Het is niet geschreven of goedgekeurd door de auteurs. Raadpleeg het oorspronkelijke artikel voor technische nauwkeurigheid. Lees de volledige disclaimer

De Kernvraag: Kan een simpele computer een quantumcomputer bedriegen?

Stel je voor dat je een quantumcomputer hebt. Dit is een superkrachtige machine die dingen kan berekenen die voor een normale computer (zoals je laptop of telefoon) onmogelijk lijken. Het probleem is: deze quantumcomputers zijn duur, groot en lastig te bedienen.

Dus, je wilt een taak uitbesteden aan een quantumcomputer (een "server"), maar je wilt zeker weten dat hij het goed doet. Je bent een "klassieke gebruiker" (je hebt geen quantumcomputer zelf). De vraag is: Kun je de resultaten van die quantumcomputer controleren zonder zelf een quantumcomputer te hebben?

In 2022 bedacht de wetenschapper Mahadev een manier om dit te doen. Hij bedacht een spelletje van vier berichten (vragen en antwoorden) tussen jou en de server. Als de server eerlijk is, wint hij het spel. Als hij liegt, val je hem op. Dit werkt, maar het vereist dat je een heel zwaar wiskundig probleem (LWE) gelooft dat "onoplosbaar" is voor hackers.

Het Nieuwe Onderzoek: Kan het korter?

De auteurs van dit artikel stellen de volgende vraag: Kunnen we dit spelletje nog korter maken? Kunnen we het doen met slechts één bericht? (Jij stuurt een sleutel, de server stuurt het antwoord, en klaar). Dit heet "Non-Interactive" (NI-CVQC).

Als dit zou lukken, zou het veel sneller en praktischer zijn. Maar de auteurs zeggen: "Nee, dat kan niet, tenzij je de basis van de moderne cryptografie op zijn kop zet."

De Analogie: De Magische Sleutelkast

Om dit uit te leggen, gebruiken we een analogie met een magische sleutelkast.

De Opdracht: Je wilt weten of een sleutel in een kast past. Alleen een magische quantumcomputer kan dit zien.
De Verificatie: Je wilt dat de quantumcomputer je een bewijs stuurt dat de sleutel past, zonder dat jij zelf naar de kast hoeft te kijken.
De "Valse" Assumptie: De huidige methode (Mahadev) vertrouwt op een geheim: "Niemand kan de kast openen zonder de magische sleutel." Dit is een falsifieerbare assumptie. Dat betekent: als iemand de kast open kan maken, kunnen we dat zien en zeggen: "Aha, je liegt!" (Het is een testbaar bewijs).

De auteurs bewijzen nu dat je nooit een systeem kunt bouwen dat werkt met één bericht (non-interactive) dat gebaseerd is op zo'n testbaar geheim.

Waarom niet? De "Onzichtbare Vriend"

Stel je voor dat je een systeem bouwt dat beweert: "Ik kan bewijzen dat de sleutel past met één bericht."
De auteurs zeggen: "Als dat systeem werkt, dan moet er een onzichtbare, super-snelle 'vriend' (een wiskundig bewijs) zijn die kan zien of de slecht past, zonder dat hij de magische sleutel nodig heeft."

Maar hier komt de twist:

Om dit systeem te laten werken, moet je aannemen dat er een probleem bestaat dat quantumcomputers kunnen oplossen, maar klassieke computers (zelfs met hulp van een "magische lijst" van antwoorden) niet.
Dit probleem heet een QMA-QCMA gap.
- QMA: Problemen die een quantumcomputer kan oplossen met een quantum-bewijs.
- QCMA: Problemen die een quantumcomputer kan oplossen met een klassiek bewijs (een gewoon stukje papier met cijfers).

De auteurs zeggen: "Als er een gat is tussen deze twee (dus als quantumcomputers echt iets kunnen wat klassieke computers niet kunnen, zelfs niet met een lijstje), dan is het onmogelijk om een 'één-bericht' verificatiesysteem te bouwen dat op de standaard cryptografische geheimen vertrouwt."

De "Gaten in de Muur" (De Bewijsvoering)

Hoe bewijzen ze dit? Ze gebruiken een slimme truc, vergelijkbaar met het Gentry-Wichs-bewijs (een beroemd bewijs uit de cryptografie):

Het Leugen-Scenario: Stel, er bestaat een systeem dat beweert dat het werkt.
De "Leugens" vinden: De auteurs laten zien dat als zo'n systeem bestaat, je een "leugenaar" kunt bouwen die een vals bewijs stuurt dat eruitziet als een echt bewijs.
De "Zoektocht": Normaal gesproken zou je moeten zoeken door een enorme berg aan mogelijke bewijzen om een leugen te vinden. Dat is te veel werk.
De Quantum-Hulp: Maar omdat we praten over quantumcomputers, kunnen we een "magische zoekmachine" (een QCMA-orakel) gebruiken die ons helpt om de juiste leugen te vinden, zonder dat we de hele berg hoeven te doorzoeken.
Het Paradox: Als je deze magische zoekmachine kunt gebruiken om een leugen te vinden, betekent dat dat de "testbare geheimen" (zoals LWE) eigenlijk niet veilig zijn. Je zou de sleutelkast kunnen openen zonder de sleutel.

Conclusie: Als je gelooft dat de standaard cryptografie (zoals LWE) veilig is, en je gelooft dat quantumcomputers echt krachtiger zijn dan klassieke computers (de QMA-QCMA gap), dan is het onmogelijk om een "één-bericht" verificatiesysteem te bouwen. Je zit vast aan het langere, vier-berichten spelletje van Mahadev.

Wat betekent dit voor de toekomst?

Geen snelle shortcuts: We kunnen niet zomaar het aantal berichten terugbrengen naar één als we willen vertrouwen op de huidige wiskundige geheimen.
De theorie is sterk: Dit is een "negatief resultaat", maar een heel belangrijk één. Het zegt ons waar we niet hoeven te zoeken. We hoeven niet te proberen een korter protocol te bouwen op basis van LWE, want dat is wiskundig onmogelijk (onder deze voorwaarden).
De "Magische Sleutel" is nodig: Om een korter protocol te hebben, zouden we waarschijnlijk een heel nieuw type wiskundig geheim nodig hebben dat nog niet bestaat, of we moeten accepteren dat het protocol iets langer duurt.

Samenvattend:
Het is alsof je probeert een slot te openen met één druk op de knop. De auteurs zeggen: "Als je gelooft dat de wereld zoals hij is (met veilige sloten en echte quantumkrachten), dan is dat onmogelijk. Je moet de deur openen met een paar stappen (vier berichten), of je moet een heel nieuw type slot uitvinden dat we nog niet kennen."

Titel: Het scheiden van niet-interactieve klassieke verificatie van kwantumcomputatie van falsifieerbare aannames

Auteurs: Mohammed Barhoush, Tomoyuki Morimae, Ryo Nishimaki, en Takashi Yamakawa.

1. Probleemstelling

De kern van dit onderzoek ligt in de cryptografie en kwantumcomplexiteitstheorie. Er bestaat een fundamentele vraag over de mogelijkheid om kwantumcomputaties te verifiëren door een volledig klassieke gebruiker (verifier) zonder dat er interactie nodig is met de kwantumserver (prover).

Achtergrond: Mahadev (2022) introduceerde het eerste protocol voor klassieke verificatie van kwantumcomputatie (CVQC) gebaseerd op de Learning-with-Errors (LWE) aanname. Dit protocol vereist echter vier berichten (interactieve ronde).
De Open Vraag: Is het mogelijk om een niet-interactief protocol (NI-CVQC) te construeren in het "plain model" (zonder extra aannames zoals een Quantum Random Oracle Model)? Een niet-interactief protocol zou bestaan uit één bericht van de prover naar de verifier na een instelling die onafhankelijk is van het specifieke bewijs.
De Uitdaging: Hoewel er vooruitgang is geboekt in het Quantum Random Oracle Model, blijft het reduceren van het aantal berichten in het plain model een langdurig open probleem. Als zo'n protocol bestaat, zou het waarschijnlijk gebaseerd moeten zijn op standaard cryptografische aannames (zoals LWE, RSA, of One-Way Functions), die allemaal "falsifieerbaar" zijn.

2. Methodologie en Technische Benadering

De auteurs bewijzen een onmogelijkheidsresultaat (separatie) door aan te tonen dat er geen kwantum black-box reductie bestaat van NI-CVQC naar enige falsifieerbare aanname. Ze gebruiken een bewijsstrategie die lijkt op de beroemde scheiding van Gentry en Wichs voor SNARGs, maar aangepast voor de kwantumcontext.

De methodologie omvat de volgende cruciale stappen:

A. Het Concept van Falsifieerbare Aannames

Een aanname is falsifieerbaar als er een efficiënt interactief spel bestaat tussen een uitdager en een adversary, waarbij de uitdager kan verifiëren of de adversary heeft gewonnen. Dit dekt bijna alle standaard cryptografische aannames.

B. De Nieuwe Hinderpaal: QMA-QCMA Gap Probleem

Om de scheiding te bewijzen, introduceren de auteurs het concept van een QMA-QCMA gap probleem.

Definitie: Dit is een taal in de complexiteitsklasse QMA waarbij "ja"-instanties (met een geldig kwantum getuige) en "nee"-instanties ononderscheidbaar zijn voor elke adversary die toegang heeft tot een QCMA-orakel (een orakel dat problemen in QCMA oplost, waarbij de getuige klassiek is).
Verschil met standaard scheiding: Het vereist meer dan alleen $QMA \neq QCMA$ . Het vereist dat zelfs met een QCMA-orakel (dat klassieke getuigen kan zoeken), een adversary de twee verdelingen niet kan onderscheiden.
Constructie: De auteurs bewijzen dat dergelijke problemen bestaan ten opzichte van een kwantum unitair orakel. Ze construeren een taal waarbij het onderscheid tussen ja en nee instanties afhankelijk is van het bezit van een specifieke Haarrandom toestand, die onmogelijk te onderscheiden is voor een adversary met alleen klassieke hulp (QCMA).

C. Bewijsstrategie (De "Leakage Lemma" aanpassing)

Het bewijs volgt een vierstappenproces, vergelijkbaar met Gentry-Wichs, maar met complexe aanpassingen voor kwantumprovers:

Aangepast Leakage Lemma: In klassieke scenario's (zoals bij SNARGs) kunnen "extra" informatie (zoals een bewijs) worden uitgeput via brute-force als ze kort zijn. In NI-CVQC zijn de bewijzen echter niet noodzakelijk kort, wat brute-force onmogelijk maakt.
- Oplossing: De auteurs geven de adversary toegang tot een QCMA-orakel. Dit orakel is krachtig genoeg om de zoektocht naar de juiste klassieke informatie (het bewijs) te faciliteren, maar niet krachtig genoeg om de onderliggende QMA-hardheid te doorbreken. Hiermee tonen ze aan dat de verdeling van "ja-instanties met echte bewijzen" en "nee-instanties met nep-bewijzen" statistisch ononderscheidbaar blijft, zelfs met deze extra hulp.
Van Steekproef- naar Orakel-Ononderscheidbaarheid: Een grote uitdaging is dat de honest prover in NI-CVQC een kwantum algoritme is. In eerdere werken (voor klassieke SNARGs) kon een kwantum orakel worden gesimuleerd met klassieke steekproeven. Hier werkt dat niet direct.
- Oplossing: Ze gebruiken de Compressed Oracle techniek (uit [29, 30]). Hiermee construeren ze een efficiënt, stateful kwantum algoritme ( $S$ ) dat kwantum-orakel-ononderscheidbaar is van de echte (inefficiënte) aanvalsalgoritme ( $P$ ).
Het Reductie-Argument:
- Stel er bestaat een kwantum black-box reductie $\Sigma$ die de soundness van NI-CVQC reduceert naar een falsifieerbare aanname.
- Omdat er een inefficiënte adversary $P$ bestaat die geldige bewijzen genereert voor "nee"-instanties (geconstrueerd via het gap-probleem), zou $\Sigma^P$ de falsifieerbare aanname moeten breken.
- Echter, omdat $P$ en de efficiënte simulator $S$ ononderscheidbaar zijn voor elke kwantum orakel-toegang, moet $\Sigma^S$ ook de aanname breken.
- Omdat $S$ efficiënt is, betekent dit dat de falsifieerbare aanname effectief door een efficiënt algoritme wordt gebroken, wat een contradictie is (tenzij de aanname zelf al vals is).

3. Belangrijkste Resultaten

Hoofdstelling (Theorem 1): Er bestaat geen kwantum black-box reductie van NI-CVQC voor QMA-talen naar enige falsifieerbare aanname, onder de veronderstelling dat er een sub-exponentieel QMA-QCMA gap-probleem bestaat.
Corollary 1: Gezien de LWE-aanname (die falsifieerbaar is) en de existentie van het gap-probleem, kan NI-CVQC niet worden gereduceerd tot het 4-berichten protocol van Mahadev. Dit impliceert dat als NI-CVQC mogelijk is, het gebaseerd moet zijn op niet-falsifieerbare aannames of dat de huidige cryptografische paradigma's onvoldoende zijn.
Constructie (Theorem 2): De auteurs bewijzen dat sub-exponentiële QMA-QCMA gap-problemen bestaan ten opzichte van een kwantum unitair orakel. Dit ondersteunt de geldigheid van hun veronderstelling.

4. Belang en Implicaties

Fundamentele Beperking: Dit resultaat is een sterke "negatieve" bevinding. Het suggereert dat het creëren van een niet-interactief protocol voor klassieke verificatie van kwantumcomputatie (in het plain model) fundamenteel moeilijker is dan het reduceren tot standaard cryptografische aannames.
Noodzaak van Niet-Falsifieerbare Aannames: Als NI-CVQC toch mogelijk is, moet het waarschijnlijk gebaseerd zijn op aannames die niet in het standaard "falsifieerbaar" raamwerk passen (zoals bepaalde aannames over het Quantum Random Oracle Model of specifieke algebraïsche structuren die niet als spel kunnen worden geformuleerd).
Complexiteitstheorie: Het werk verrijkt het begrip van de relatie tussen QMA en QCMA. Het toont aan dat er een specifieke "gap" nodig is die sterker is dan alleen $QMA \neq QCMA$ , en biedt een constructie hiervoor in een orakel-model.
Toekomstige Richtingen: Het resultaat laat ruimte voor onderzoek naar:
- Constructies van NI-CVQC die specifiek niet-falsifieerbare aannames gebruiken.
- Of de techniek kan worden uitgebreid naar BQP (in plaats van QMA), hoewel dit complexer is omdat BQP zelf falsifieerbaar is.
- Het onderzoeken van "adaptive soundness" versus "static soundness", waarbij het huidige resultaat alleen geldt voor het sterkere adaptive geval.

Conclusie

Dit artikel legt een fundamentele barrière bloot in de cryptografie van kwantumcomputatie. Het bewijst dat het dromen van een volledig niet-interactief, klassiek verifieerbaar protocol voor kwantumcomputatie, gebaseerd op de standaard cryptografische toolbox (zoals LWE), waarschijnlijk onbereikbaar is via black-box methoden. Dit dwingt de gemeenschap om na te denken over nieuwe cryptografische paradigmas of acceptatie van meer interactie.