Genuine certifiable randomness from a black-box

De auteurs demonstreren een methode voor de certificering van echte willekeur in een black-box setting, waarbij deterministische data zonder willekeurige seed kan worden uitgesloten door gebruik te maken van kwantummetingen op enkeldeeltjestoestanden.

De kern

Waarom dit papier zo belangrijk is (en wat het eigenlijk zegt)

Stel je voor dat je een vriend hebt die beweert dat hij een eerlijke munt kan gooien. Hij gooit de munt 100 keer en zegt: "Kijk, dit is willekeur!" Maar jij weet niet of hij een eerlijke munt gebruikt, of dat hij een trucje heeft bedacht om altijd 'kop' te laten vallen. In de wereld van computers en wiskunde noemen we dit het probleem van willekeur certificeren.

Deze paper, geschreven door Liam McGuinness, lost een groot raadsel op: Hoe bewijs je dat iets echt willekeurig is, zonder te hoeven kijken hoe het gemaakt wordt?

Hier is de uitleg in simpele taal, met een paar creatieve vergelijkingen.

1. Het oude probleem: De "Zwarte Doos"

Stel je voor dat je een zwarte doos hebt. Je ziet er niets van, je kunt er niet in kijken. De doos geeft je een getal. Is dat getal echt willekeurig, of heeft de doos een verborgen computerchip die een lijstje met getallen uit zijn hoofd kent?

Tot nu toe was het onmogelijk om dit te bewijzen als je de doos niet mag openen. Als je de doos niet mag openen, kan een slimme hacker altijd zeggen: "Ik heb een lijstje met getallen uit mijn hoofd geleerd, en dat is wat ik je geef." Zolang je niet weet hoe de doos werkt, kun je nooit zeker zijn dat het geen truc is.

2. De oplossing: De "Magische Kist"

De auteur zegt: "Wacht even, we hoeven de doos niet open te maken. We moeten de doos alleen een speciale opdracht geven."

In plaats van te vragen: "Geef me een willekeurig getal," zegt de verifier (de controleur) tegen de prover (de doos):
"Ik heb een magische kist met een geheim getal erin. Ik geef je de kist. Probeer het geheim te raden. Maar let op: als je de kist niet opent (meet), kun je het geheim nooit goed raden."

Hier komt de quantumfysica om de hoek kijken:

• De Kist: Een enkel deeltje (zoals een elektron) dat in een speciale staat zit.
• Het Geheim: Een onbekende instelling (een "fase") die de verifier heeft ingesteld.
• De Opdracht: De prover moet het geheim raden door het deeltje te meten.

3. De Vergelijking: De "Goocheltruc"

Stel je voor dat de verifier een goochelaar is. Hij houdt een bal in zijn hand die van kleur verandert, maar je kunt de kleur niet zien totdat je er naar kijkt.

• Als de goochelaar niet naar de bal kijkt (geen meting doet), kan hij de kleur niet weten. Hij moet raden.
• Als hij wel kijkt (meet), verandert de bal van kleur op een willekeurige manier (volgens de regels van de quantumwereld).

De paper laat zien dat als de prover het geheim (de kleur) goed raadt, hij noodzakelijkerwijs naar de bal heeft gekeken. En omdat het kijken naar een quantum-deeltje per definitie willekeurig is, is het antwoord ook willekeurig.

Als de prover probeert te liegen en zegt: "Ik heb het geraden zonder te kijken," dan zal zijn antwoord statistisch gezien te vaak fout zijn. De verifier kan dan zeggen: "Aha! Je hebt niet gemeten, want je antwoord was te perfect (of juist te slecht) voor iemand die niet keek."

4. Waarom is dit zo cool?

Vroeger hadden wetenschappers om dit te bewijzen twee dingen nodig:

1. Twee losgekoppelde doosjes: Ze moesten twee "provers" hebben die niet met elkaar konden praten (een ingewikkelde Bell-test).
2. Een willekeurige start: Ze moesten al een willekeurig getal hebben om te beginnen (een "seed").

Deze paper doet het beter en simpeler:

• Geen entanglement nodig: Je hebt maar één enkel deeltje nodig. Geen ingewikkelde koppelingen tussen twee deeltjes.
• Geen start-willekeur nodig: De verifier kan een vast getal kiezen (bijvoorbeeld "3"). Zolang de prover niet weet dat de verifier "3" heeft gekozen (wat de "zwarte doos" regelt), werkt het.
• Onkraakbaar: Zelfs als de prover een supercomputer heeft die alles kan berekenen, kan hij niet liegen. De natuurwetten (de Born-regel) zorgen ervoor dat je het geheim niet kunt raden zonder het deeltje te meten.

5. Het Experiment

De auteur heeft dit niet alleen op papier bedacht, maar het ook gedaan in het lab!

• Het materiaal: Ze gebruikten een klein gat in een diamant (een NV-centrum) dat als een mini-quantumcomputer fungeerde.
• Het proces: Ze stuurden een golfje naar het deeltje, lieten het deeltje "meten", en keken of het antwoord klopte met wat ze verwachtten van echte willekeur.
• Het resultaat: Het werkte! Ze konden bewijzen dat de data echt willekeurig was, puur op basis van de statistiek van de antwoorden.

Samenvatting in één zin

Deze paper bewijst dat je kunt weten of iemand echt willekeurig handelt door ze een raadsel te geven dat alleen opgelost kan worden door de natuurwetten van het quantum-universum te gebruiken, zonder dat je ooit hoeft te kijken hoe ze het oplossen.

Het is alsof je iemand vraagt om een sleutel te maken die alleen werkt als hij een deur opent die van binnen van kleur verandert. Als de sleutel past, weet je zeker dat hij de deur heeft geopend (gemeten), en dat het proces willekeurig was.

Technische samenvatting

Hier is een gedetailleerde technische samenvatting van het artikel "Genuine Certifiable Randomness from a Black-Box" van Liam P. McGuinness, geschreven in het Nederlands.

Titel: Echte Certificeerbare Willekeur uit een Black-Box

Auteur: Liam P. McGuinness (Instituut voor Quantumoptica, Universiteit van Ulm)

---

1. Het Probleem

Het artikel adresseert een fundamenteel probleem in de kwantuminformatica en cryptografie: het certifiëren van echte willekeur (randomness) in een "black-box" setting.

• De Uitdaging: In een black-box scenario moet een verificateur kunnen bepalen of data die van een onbetrouwbare "prover" (bewijzer) komt, echt willekeurig is, zonder enige kennis van de interne werking of fysieke toestand van de prover.
• Huidige Beperkingen: Bestaande methoden, zoals Bell Certified Randomness (BCR) en Circuit Sampling Randomness (CSR), zijn niet echt black-box.
  • BCR vereist dat de verificateur controleert of twee gescheiden partijen (Alice en Bob) niet communiceren (no-signaling constraint).
  • CSR vereist dat de verificateur aannames doet over de rekenkracht van de prover en dat deze geen toegang heeft tot onbeperkte rekenkracht om een kwantumcircuit deterministisch te simuleren.
• De Theoretische Barrière: Er heerst het idee dat echte black-box certificering onmogelijk is, gebaseerd op de redenering dat elke eindige reeks willekeurige data ook door een deterministische machine gegenereerd kan worden. Dit zou impliceren dat het onderscheid tussen willekeur en pseudowillekeur onmogelijk is zonder extra aannames.

2. Methodologie: Estimation Certified Randomness (ECR)

De auteur introduceert een nieuw protocol genaamd Estimation Certified Randomness (ECR). In plaats van de prover te vragen een functie te berekenen of een circuit te samplen, wordt de prover geconfronteerd met een schattingstaak.

• Het Protocol:

  1. De verificateur kiest een parameter $\theta$ (bijvoorbeeld een fase) en encodeert deze in een enkel kwantumtoestand $|\theta\rangle$.
  2. Deze toestand wordt naar de prover gestuurd (de "black-box").
  3. De prover moet een schatting $\hat{\theta}$ van de parameter teruggeven.
  4. De verificateur evalueert de kwaliteit van de schatting via de gemiddelde kwadratische fout (Mean Squared Error - MSE).

• De Kernaanname (Assumption 1): De prover heeft geen enkele informatie over $\theta$ behalve de informatie die verkregen wordt door het meten van de toestand $|\theta\rangle$. De prover mag geen "verborgen" informatie hebben of voorafgaande kennis van de gekozen waarde.

• De Wiskundige Basis:

  • Het artikel gebruikt een antipodale metriek (op een cirkel) in plaats van een Euclidische metriek. De afstand wordt gedefinieerd als $d^\circ[\theta, \hat{\theta}] = |\sin(\pi(\theta - \hat{\theta})/2)|$.
  • De verificateur kiest $\theta$ uit een antipodale kansverdeling (waarbij $\pi[\theta] = \pi[\theta+1]$).
  • Stelling 1 (No-measurement bound): Zonder een meting van $|\theta\rangle$ is de verwachte gemiddelde kwadratische fout (EMSE) voor elke schatting (deterministisch of probabilistisch) die niet van $\theta$ afhangt, exact gelijk aan 1/2.
  • Als de prover een schatting levert met een MSE lager dan 1/2, is het wiskundig onmogelijk dat dit deterministisch is. Het bewijst dat een probabilistische meting heeft plaatsgevonden.

3. Belangrijkste Bijdragen

1. Echte Black-Box Certificering: Het protocol vereist geen aannames over de rekenkracht van de prover, geen entanglement tussen partijen, en geen controle over de fysieke locatie van de prover. De verificateur hoeft alleen de statistiek van de teruggekomen data te controleren.
2. Geen Initiële Willekeur Nodig: In tegenstelling tot bestaande protocollen die een willekeurige "seed" nodig hebben (randomness expansion/amplification), kan de verificateur $\theta$ deterministisch kiezen. Zolang Assumption 1 geldt (de prover weet de keuze niet), is het resultaat gegarandeerd willekeurig.
3. Geen Entanglement Vereist: Het protocol werkt met een enkel niet-separabel kwantumtoestand (een enkele deeltjestoestand), waardoor complexe kwantumnetwerken overbodig zijn.
4. Uitdaging van de Church-Turing These: Het artikel stelt dat dit probleem niet opgelost kan worden door een deterministische Turing-machine met dezelfde foutmarge als een kwantum-machine. Dit suggereert een breuk met de klassieke interpretatie van de Church-Turing these in de context van willekeurigheidsgeneratie.
5. Nieuwe Schattingsgrenzen: De auteur leidt een nieuwe ondergrens af voor parameter schatting die sterker is dan de klassieke Cramér-Rao ondergrens. Deze nieuwe grens kan worden bereikt met slechts één meting en vereist geen onbevooroordeelde schatters.

4. Experimentele Resultaten

De auteur demonstreert het protocol experimenteel met een stikstof-leegte (NV) centrum in diamant.

• Opstelling: De verificateur bereidt de spin-toestand van het NV-centrum voor met een specifieke fase $\theta$. De prover (in dit geval een nabijgelegen meetopstelling) voert een meting uit in de X-basis.
• Data: Er werden duizenden rondes uitgevoerd waarbij $\theta$ werd gekozen uit een discrete set.
• Resultaten:
  • Deterministische strategieën (zonder meting) leverden een MSE van ongeveer 0.5 op (zoals voorspeld door Stelling 1).
  • Experimentele metingen met hoge fideliteit leverden een MSE van ongeveer 0.25 op.
  • Na 120 rondes kon de verificateur met 5-sigma betrouwbaarheid concluderen dat de data willekeurig was gegenereerd.
  • Dit bevestigt dat de prover daadwerkelijk een kwantummeting heeft uitgevoerd en niet een deterministische truc heeft gebruikt.

5. Betekenis en Implicaties

• Kritische Toets voor Willekeur: Dit biedt een methode om willekeur te certificeren zonder vertrouwen in de hardware van de tegenpartij. Dit is cruciaal voor veilige netwerken en cryptografie.
• Fundamentele Fysica: De resultaten suggereren dat de beperkingen van deterministische machines diep verankerd zijn in de natuurwetten (Born-regel, no-cloning theorema, onzekerheidsrelaties) en niet slechts een kwestie van rekenkracht zijn.
• P vs NP Probleem: De auteur suggereert dat deze aanpak (het begrenzen van de initiële informatie en het gebruik van fase-symmetrie) een nieuwe weg opent om het P vs NP-probleem aan te vallen, zonder diagonalisatieargumenten.
• Efficiëntie: Het protocol is goedkoper en minder resource-intensief dan bestaande methoden omdat het geen entanglement of complexe kwantumcomputers vereist, maar slechts een enkel deeltje per interactie.

Conclusie:
Het artikel bewijst dat "genuine certifiable randomness" in een black-box setting mogelijk is door het probleem te herformuleren als een statistisch schattingsprobleem. Door de onmogelijkheid voor een deterministische entiteit om een parameter te schatten met een foutmarge lager dan een specifieke theoretische grens (1/2 in de antipodale metriek), kan de verificateur met absolute zekerheid vaststellen dat de data het resultaat is van een kwantummeting en dus echt willekeurig is.