Quantum information advantage based on Bell inequalities

Dit paper introduceert een alternatief voorstel voor een quantum-informatievoordeel gebaseerd op parallel herhaalde CHSH-spellen, dat een efficiëntere verificateur en een robuustere, minder geheugenintensieve quantumbewijzer biedt dan het recente experiment van Kretschmer et al.

De kern

De Quantum-Geheugen-uitdaging: Hoe een quantumcomputer slimmer is dan een klassieke computer (zonder sneller te zijn)

Stel je voor dat je twee vrienden hebt: Klassiek (een zeer ordelijke, maar beperkte bibliothecaris) en Quantum (een magische goochelaar die met onzichtbare draden werkt). Ze moeten samen een heel moeilijk raadsel oplossen, maar ze zitten in twee verschillende kamers en mogen niet met elkaar praten terwijl ze werken. Ze hebben wel een geheugen nodig om informatie tussen de twee kamers te vervoeren.

Dit artikel van Rahul Jain en Srijita Kundu beschrijft een nieuw spelletje dat laat zien waarom de quantum-goedelaar veel minder geheugen nodig heeft dan de bibliothecaris, zelfs als ze allebei even snel werken.

1. Het Spel: De "Telepathische" Test

Het spel heet een Bell-ongelijkheid (of in dit geval, een CHSH-spel). Het is als volgt:

• Tijd 0: De scheidsrechter geeft de bibliothecaris een geheim getal ($x$). Hij moet een antwoord geven ($a$) en dit opslaan in zijn geheugen.
• Tussenperiode: Hij moet dit geheugen bewaren.
• Tijd 1: De scheidsrechter geeft de bibliothecaris een nieuw geheim getal ($y$). Hij moet nu, gebaseerd op zijn oude geheugen én het nieuwe getal, een tweede antwoord ($b$) geven.
• De winnende voorwaarde: De antwoorden $a$ en $b$ moeten op een heel specifieke manier overeenkomen met de getallen $x$ en $y$.

Het probleem is: Als je alleen klassieke logica gebruikt, moet je je geheugen vol proppen met informatie over het eerste getal ($x$) om later het juiste antwoord te kunnen geven.

2. Het Nieuwe Spel: "Parallelle Gokken"

In eerdere experimenten (door Kretschmer et al.) werd getoond dat quantumcomputers minder geheugen nodig hebben, maar dat was een heel ingewikkeld spel dat leek op het raden van een willekeurig getal in een enorme database.

De auteurs van dit nieuwe paper hebben een simpeler en robuuster spel bedacht. Ze gebruiken een trucje genaamd "Parallelle Herhaling".

Stel je voor dat je niet één keer, maar tienduizend keer tegelijkertijd dit raadsel moet oplossen.

• De bibliothecaris krijgt 10.000 getallen ($x_1$ tot $x_{10.000}$).
• Hij moet 10.000 antwoorden geven.
• Later krijgt hij 10.000 nieuwe getallen ($y_1$ tot $y_{10.000}$) en moet hij 10.000 nieuwe antwoorden geven.
• Om te winnen, hoeft hij niet bij alle 10.000 vragen goed te zijn. Hij hoeft er maar 83% goed te hebben.

3. Waarom is de Quantum-goedelaar zo slim?

Hier komt de magie van de "quantum-verstrengeling" (entanglement) om de hoek kijken.

• De Bibliothecaris (Klassiek): Om 83% van de vragen goed te beantwoorden, moet hij zijn geheugen vullen met alle informatie over de eerste 10.000 getallen. Zonder die informatie is het een gok. Hij heeft dus een gigantisch geheugen nodig (duizenden bits).
• De Goochelaar (Quantum): De quantumcomputer gebruikt verstrengelde deeltjes (EPR-paren). Het geheimzinnige is: Hij slaat geen informatie op over de eerste getallen.
  • Stel je voor dat de quantumcomputer twee muntjes heeft die altijd hetzelfde kantelen, ook al zijn ze kilometers uit elkaar.
  • Als hij het eerste getal ($x$) ziet, doet hij een meting. Het resultaat is willekeurig, maar het verstrengelde deeltje dat hij bewaart, "weet" nog niets over $x$.
  • Als hij later het tweede getal ($y$) krijgt, meet hij het andere deeltje. Door de "spookachtige" verbinding tussen de deeltjes, komen de antwoorden ($a$ en $b$) op het juiste moment uit, zonder dat hij ooit de informatie van $x$ heeft hoeven opslaan.

De kernboodschap: De quantumcomputer heeft een informatie-geheugen van 0. Hij slaat de waarde van de input niet op, maar hij gebruikt de structuur van de quantumwereld om de puzzel op te lossen. De klassieke computer moet de puzzelstukjes fysiek opslaan.

4. Waarom is dit belangrijk?

• Minder geheugen: De auteurs tonen aan dat je voor dit spel ongeveer 10.000 qubits nodig hebt (wat technisch haalbaar is met huidige technologie), terwijl een klassieke computer duizenden bits aan informatie nodig zou hebben om hetzelfde te doen.
• Robuust tegen ruis: In de echte wereld zijn quantumcomputers niet perfect; ze maken fouten (ruis). Dit nieuwe spel is zo ontworpen dat het zelfs werkt als de quantumcomputer een beetje "dronken" is (met een foutmarge van 1%). De klassieke computer kan dit niet compenseren.
• Eenvoudiger dan voorheen: Het oude experiment vereiste het maken van extreem complexe, willekeurige kwantumtoestanden. Dit nieuwe spel vereist alleen maar simpele "verstrengelde paren" en standaard metingen, iets wat we al kunnen doen.

Samenvattend in één zin:

Dit paper laat zien dat je kunt bewijzen dat een quantumcomputer superieur is aan een klassieke computer, niet omdat hij sneller is, maar omdat hij een geheugen heeft dat "slimmer" is: hij slaat geen data op, maar gebruikt de fundamentele wetten van de natuurkunde om informatie te "telegrafen" zonder deze ooit te hoeven schrijven.

Technische samenvatting

Hier is een gedetailleerde technische samenvatting van het paper "Quantum information advantage based on Bell inequalities" van Rahul Jain en Srijita Kundu, in het Nederlands.

1. Probleemstelling

Het paper richt zich op het aantonen van kwantuminformatievoordeel (quantum information advantage). Waar eerdere experimenten zich vaak richtten op rekenkracht (reken tijd) of steekproeven (sampling), focust dit werk op het geheugengebruik (memory).

De kernvraag is: Kunnen we een computationele taak definiëren die een kwantumsysteem kan oplossen met aanzienlijk minder geheugen dan een klassiek systeem, zelfs als we aannemen dat het klassieke systeem oneindig veel rekenkracht heeft?

Het paper reageert op recent werk van Kretschmer et al. [KGD+25], dat een dergelijk voordeel demonstreerde op basis van het aantal qubits versus bits. De auteurs van dit paper vinden echter dat het tellen van het aantal qubits/bits een onvoldoende maatstaf is, omdat het niet onderscheidt of die qubits daadwerkelijk informatie over de input bevatten of slechts in een willekeurige staat verkeren. Ze willen een protocol dat bewijst dat een kwantumsysteem minder informatie over de input hoeft op te slaan dan een klassiek systeem.

2. Methodologie

Het Protocol: Parallel herhaalde CHSH-spellen

Het voorgestelde protocol is gebaseerd op de schending van Bell-ongelijkheden, specifiek het CHSH-spel (Clauser-Horne-Shimony-Holt).

• Opzet: Een verificateur (Verifier) en een bewijzer (Prover) wisselen berichten uit op twee tijdstippen, $t_0$ en $t_1$.
  • Bij $t_0$: De verificateur stuurt een input $x$ (een reeks van $n$ bits) naar de bewijzer. De bewijzer moet direct een antwoord $a$ terugsturen.
  • Tussen $t_0$ en $t_1$: De bewijzer moet informatie bewaren in een geheugenregister $M$.
  • Bij $t_1$: De verificateur stuurt een input $y$ naar de bewijzer. De bewijzer moet een antwoord $b$ terugsturen.
• Winvoorwaarde: De bewijzer wint als voor een groot deel van de $n$ kopieën geldt dat $a_i \oplus b_i = x_i \cdot y_i$. Specifiek wordt vereist dat dit voor minstens $t = 0.83n$ van de gevallen geldt (een drempelwaarde).
• Kwantumstrategie: De bewijzer deelt $n$ EPR-paren (verstrengelde qubits). De meting op $x$ gebeurt bij $t_0$ en de meting op $y$ bij $t_1$. Omdat de meting op $x$ de toestand van $y$ (via niet-signaleren) niet beïnvloedt, bevat het geheugen $M$ (het deel van de EPR-paren bij $t_1$) geen informatie over $x$.

Nieuwe Maatstaf voor Geheugen

In plaats van het aantal qubits te tellen, gebruiken de auteurs de gesmoothde max-mutuele informatie ($I^{\delta}_{\max}(X : M)$).

• Dit meet hoeveel informatie over de input $X$ er daadwerkelijk in het geheugenregister $M$ zit.
• Kwantumgeval: Door de eigenschappen van verstrengeling en het no-signaling principe, is $I(X : M) = 0$. Het geheugen bevat geen informatie over $x$.
• Klassiek geval: Om de winvoorwaarde te halen, moet een klassieke bewijzer informatie over $x$ in $M$ opslaan. De auteurs bewijzen dat de hoeveelheid informatie die moet worden opgeslagen exponentieel groot is ten opzichte van de gewenste winnende kans.

3. Belangrijkste Bijdragen

1. Alternatieve Definitie van Kwantuminformatievoordeel:
   De auteurs introduceren een definitie gebaseerd op informatie-inhoud in plaats van fysieke resources (aantal qubits). Dit is een robuustere maatstaf omdat het aantoont dat kwantumsystemen informatie kunnen "verbergen" of niet hoeven op te slaan op een manier die klassieke systemen niet kunnen.

2. Efficiënte Verificateur:
   Het protocol vereist dat de verificateur slechts $O(n)$ tijd neemt om te controleren of de winvoorwaarde is voldaan. Dit is aanzienlijk efficiënter dan het werk van [KGD+25], waarbij de verificateur complexe berekeningen (zoals het schatten van $\epsilon$ via lineaire cross-entropy) moet uitvoeren die mogelijk veel herhalingen vereisen.

3. Ruisbestendigheid (Noise-Robustness):
   Het protocol is ontworpen om robuust te zijn tegen ruis. Zelfs als de kwantumbewijzer werkt op apparatuur met een constante foutkans per poort (zodat de winnende kans per CHSH-kopie iets daalt, bijv. naar 0.84), blijft het protocol geldig. De kwantumsuperioriteit blijft bestaan zolang de ruis onder een bepaalde drempel ($\gamma \leq 0.01$) blijft.

4. Vereenvoudigde Hardware-eisen:
   In tegenstelling tot [KGD+25], die de voorbereiding van complexe Haar-random toestanden vereist (wat duizenden poorten en grote diepte nodig heeft), vereist dit protocol alleen:

   • Bereiding van EPR-paren.
   • Meting met 4 soorten enkel-qubit poorten.
     Deze operaties zijn binnen de mogelijkheden van huidige kwantumhardware.

4. Resultaten

• Theorema 1: Er bestaat een $(0, \Omega(n), 0.01)$ ruisbestendig bewijs van kwantuminformatievoordeel.
  • Completeness: Een kwantumprover kan de verificateur met hoge waarschijnlijkheid overtuigen, terwijl de informatie in het geheugen $I(X:M) = 0$ is.
  • Soundness: Een klassieke prover die minder dan een bepaalde drempel aan informatie ($I^{\delta}_{\max}$) opslaat, zal de verificateur slechts met een verwaarloosbare waarschijnlijkheid overtuigen.
• Concrete Parameters:
  • Voor een scheiding van 0 (kwantum) vs 100 (klassiek bits aan informatie), is een grootte van $n \approx 1.17 \times 10^4$ nodig.
  • De succeskans voor de kwantumprover is $\geq 0.903$.
  • De succeskans voor een klassieke prover met beperkt geheugen is $\leq 0.5$.
• Vergelijking met [KGD+25]:
  • [KGD+25] vereist 12 qubits maar een onduidelijk groot aantal klassieke bits (62-382) en heeft geen strikte ruisanalyse.
  • Dit paper vereist $\sim 10^4$ qubits (voor parallelle uitvoering), maar bewijst dat deze qubits geen informatie over de input bevatten, terwijl een klassiek systeem enorme hoeveelheden informatie moet opslaan.

5. Betekenis en Impact

Dit paper biedt een fundamenteel nieuwe kijk op het aantonen van kwantumsuperioriteit in termen van geheugen.

• Theoretische Impact: Het koppelt Bell-ongelijkheden direct aan communicatiecomplexiteit en geheugenbeperkingen, en toont aan dat kwantumverstrengeling het opslaan van informatie over inputs kan elimineren zonder de prestaties te verliezen.
• Praktische Impact: Omdat het protocol gebaseerd is op relatief eenvoudige CHSH-metingen en robuust is tegen ruis, is het experimenteel haalbaarder dan voorgaande voorstellen die complexe random circuits vereisen. Het biedt een pad naar experimentele demonstraties van kwantuminformatievoordeel met huidige technologie, zonder de noodzaak van onbewezen complexiteitstheoretische aannames (zoals bij sampling-problemen).

Samenvattend bewijzen de auteurs dat een kwantumsysteem een taak kan uitvoeren waarbij de noodzakelijke informatie die tussen twee tijdstippen moet worden bewaard, nul is, terwijl een klassiek systeem een exponentieel grote hoeveelheid informatie moet opslaan om dezelfde taak succesvol te voltooien.