⚛️ quantum physics

Tight Query Lower Bounds for Quantum Sampling, with an Application to Certified Randomness

Dit artikel stelt strikte kwantum-query-ondergrenzen vast voor het bereiken van hoge lineaire cross-entropie benchmarkscores in random circuit sampling, waarbij wordt bewezen dat het overtreffen van ideale prestaties $\Omega(N^{1/3})$ queries vereist en het certificeren van bijna optimale gladde min-entropie voor outputs, waardoor rigoureuze beveiligingsgaranties worden geboden voor gecertificeerde willekeur tegen verstrengelde tegenstanders.

Oorspronkelijke auteurs: Keshav Bhateja, Mehdi Esmaili, Atul Mantri

Gepubliceerd 2026-10-06

📖 6 min leestijd🧠 Diepgaand

CC BY 4.0

Oorspronkelijke auteurs: Keshav Bhateja, Mehdi Esmaili, Atul Mantri

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

In de race om te bewijzen dat quantumcomputers dingen kunnen die onmogelijk zijn voor klassieke machines, hebben wetenschappers zich gericht op een specifiek soort experiment: een quantumapparaat vragen om een lijst met willekeurige getallen te genereren. Deze getallen zijn niet zomaar willekeurige reeksen; ze zijn afkomstig uit een complex, onzichtbaar patroon dat wordt gecreëerd door een willekeurige quantumcircuit. Om te controleren of het apparaat correct werkt, gebruiken onderzoekers een scoresysteem genaamd de lineaire cross-entropie benchmark. Deze score meet hoe vaak het apparaat getallen kiest die de ideale quantummachine het meest frequent zou kiezen. Als het apparaat eerlijk is en perfect werkt, behaalt het een specifieke, hoge score. Als het simpelweg willekeurig gokt, krijgt het een veel lagere score. Jarenlang was deze test de gouden standaard voor het claimen van "quantumvoordeel", maar een cruciale vraag bleef onbeantwoord: bewijst een hoge score daadwerkelijk dat het apparaat echte, onvoorspelbare willekeur genereert? Een slimme tegenstander zou een apparaat potentieel kunnen manipuleren om een hoge score te halen door simpelweg de meest waarschijnlijke antwoorden te onthouden, waardoor de output voorspelbaar wordt, ook al ziet de score er goed uit.

Een team onderzoekers aan de Virginia Tech heeft deze vraag nu met wiskundige zekerheid beantwoord, door een strikte grens te stellen aan wat een hoge score wel en niet kan certificeren. Ze bewezen dat voor een quantumapparaat om zelfs maar iets beter te scoren dan de best mogende eerlijke machine, het een enorm aantal interne operaties moet uitvoeren, veel meer dan welke efficiënte klassieke computer dan ook zou kunnen managen. Specifiek toonden ze aan dat een apparaat, om de ideale score met een vast bedrag te overtreffen, een aantal queries moet maken dat proportioneel is aan de derdemachtswortel van het totaal aantal mogelijke uitkomsten. Dit resultaat fungeert als een fundamentele limiet, vergelijkbaar met een snelheidslimiet op een snelweg, die garandeert dat geen enkele efficiënte truc een hoge score kan vervalsen. Verder demonstreerden ze dat als een apparaat binnen een kleine marge van deze ideale score blijft, de output werkelijk onvoorspelbaar is. Zelfs als een tegenstander het apparaat heeft gebouwd, een geheime quantumverbinding met het apparaat deelt en de volledige opstelling achteraf leert kennen, kan hij de output niet met enige significante nauwkeurigheid raden. Het apparaat produceert effectief bijna de maximale hoeveelheid willekeur die mogelijk is, met slechts een klein, onvermijdelijk informatieverlies.

De onderzoekers kwamen tot deze conclusies door een nieuwe manier te ontwikkelen om de "progressie" van een quantumalgoritme te volgen terwijl het een onbekend systeem bevraagt. Stel je een quantumcomputer voor die probeert de vorm van een verborgen object te leren kennen door het met een sonde aan te raken. Het team creëerde een wiskundige maatstaf die op nul begint voor een apparaat dat simpelweg de regels eerlijk volgt. Ze bewezen dat elke keer dat het apparaat een query maakt om meer over het systeem te leren, deze progressiematstaf slechts met een zeer kleine hoeveelheid kan groeien. Om een score te bereiken die de eerlijke machine verslaat, zou het apparaat genoeg progressie moeten accumuleren om een barrière te doorbreken, maar de wiskunde laat zien dat dit een onpraktisch groot aantal stappen vereist. Deze methode stelde hen in staat om de kloof te dichten tussen wat theoretisch mogelijk was en wat bewezen noodzakelijk was, waarmee een langlopende vermoedens over de moeilijkheid van het vervalsen van deze resultaten werd bevestigd.

Buiten het bewijzen van de limieten van het vervalsen van resultaten, beschrijft het artikel ook een specifiek algoritme dat daadwerkelijk deze hoge scores kan bereiken, maar alleen door het maximaal toegestane aantal queries te gebruiken. Dit "kwadrateringsalgoritme" werkt door verschillende monsters te nemen, ze op te slaan en vervolgens een techniek genaamd amplitude amplification te gebruiken om de waarschijnlijkheid van het vinden van een match te vergroten. Dit proces kwadrateert effectief de waarschijnlijkheidsverdeling, waardoor de meest waarschijnlijke uitkomsten nog sterker worden bevoordeeld dan de eerlijke machine doet. Het bestaan van dit algoritme bewijst dat de ondergrens die zij vonden nauw aansluit; het is niet alleen een theoretische muur, maar een bereikbare piek die een specifieke, hulpbron-intensieve klim vereist. Deze dualiteit — het bewijzen dat je resultaten niet gemakkelijk kunt vervalsen, maar ook laten zien hoe moeilijk het is om legitiem te winnen — biedt een compleet beeld van het landschap.

De implicaties voor gecertificeerde willekeur zijn diepgaand. In veel beveiligingstoepassingen moeten we willekeurige getallen genereren die zelfs de persoon die de generator heeft gebouwd, niet kan voorspellen. De studie bevestigt dat als een quantumapparaat de standaardtest doorstaat met een score die zeer dicht bij de ideale score ligt, het een reeks bits genereert die bijna evenveel willekeur bevat als de lengte van de reeks zelf. Voor een apparaat dat werkt met zestig qubits, dat reeksen van zestig bits kan produceren, garandeert een bijna perfecte score dat de output ongeveer vierentwintig bits van echte, gecertificeerde willekeur bevat. Dit geldt zelfs tegen een tegenstander die verstrengeld is met het apparaat en elk detail van de constructie kent. De enige verloren informatie is een kleine hoeveelheid die gerelateerd is aan het aantal queries dat het apparaat maakt, wat verwaarloosbaar is voor praktische doeleinden.

Dit werk strekt zich ook uit tot andere typen quantum-sampling, inclusclusief die gebruikt worden in fotonische experimenten met lichtdeeltjes. De onderzoekers toonden aan dat dezelfde regels van toepassing zijn: om de ideale score te verslaan, moet een apparaat een specifieke, grote hoeveelheid operaties uitvoeren, en om nabij de ideale score te blijven, moet het echte willekeur produceren. Ze verbonden deze bevindingen zelfs aan een ander probleem: het creëren van een "collision distribution", waarbij het apparaat wordt gevraagd om paren getallen te produceren die waarschijnlijker hetzelfde zijn. Ze vonden dat het genereren van dit specifieke type distributie ook dezelfde derdemachtswortel-aantal queries vereist, wat deze schijnbaar verschillende taken onder één enkele wiskundige wet brengt.

De studie beweert niet dat huidige quantumcomputers al perfect zijn in dit opzicht. Real-world apparaten scoren vaak veel lager dan de ideale score vanwege ruis en fouten. Echter, het artikel stelt het theoretische plafond en de vloer vast voor wat mogelijk is. Het vertelt ons dat als we ooit een apparaat zien dat scoreert nabij de top, we erop kunnen vertrouwen dat het iets echt quanta-achtig doet en echte willekeur produceert. Omgekeerd, als een apparaat beweert willekeur te genereren maar niet in staat is deze score te bereiken zonder een onredelijk aantal stappen, weten we dat het niet doet wat het beweert. Het onderzoek biedt de rigoureuze fundering die nodig is om van experimentele demonstraties naar betrouwbare, gecertificeerde quantumwillekeur te gaan, en zorgt ervoor dat de toekomst van quantumbeveiliging op een solide, bewezen grond rust.

Technische Samenvatting: Strakke Ondergrens voor Query-complexiteit bij Quantum Sampling, met een Toepassing op Gecertificeerde Willekeur

Probleemstelling
Random circuit sampling-experimenten zijn de belangrijkste demonstraties van kwantumcomputationele voorsprong, die doorgaans worden geverifieerd met de lineaire cross-entropie benchmark (XEB). De XEB-score meet hoe goed de outputdistributie van een apparaat overeenkomt met de ideale distributie $p$ door het gemiddelde van $N p(z)$ te berekenen voor de geretourneerde strings $z$ , waarbij $N=2^n$ . Hoewel een hoge score duidt op kwantumvoordeel, certificeert dit niet inherent dat het apparaat uit $p$ heeft gesampled of dat de output willekeurig is. Een apparaat zou een hoge score kunnen behalen door deterministisch de meest waarschijnlijke string te produceren (die een tegenstander zou kunnen kennen), waardoor het faalt om gecertificeerde willekeur te produceren.

Dit artikel behandelt twee fundamentele vragen in het quantum query-model:

Scorelimieten: Hoe hoog kan een efficiënt kwantumapparaat scoren ten opzichte van de ideale score? Kan een efficiënt apparaat de ideale score met een constante overtreffen?
Willekeurscertificering: Als een apparaat een score nabij de ideale score behaalt, hoeveel smooth min-entropie (gecertificeerde willekeur) bevat de output dan, zelfs tegen een tegenstander (Eve) die verstrengeld kan zijn met het apparaat en de oracle (het circuit of de functie) achteraf leert kennen?

Methodologie
De auteurs werken in het query-model, waarbij het circuit wordt vervangen door een oracle getrokken uit een bekende ensemble. Ze analyseren twee specifieke ensembles:

Fourier Sampling: Het oracle is een uniform willekeurige functie $f: \{0,1\}^n \to \{\pm 1\}$ . De eerlijke sampler scoort ongeveer 3.
Haar-Random States: Het oracle verbergt een uniform willekeurige eenheidsvector $|\phi\rangle$ (bereikbaar via een canonieke state-preparation oracle of Haar-random unitary access). De eerlijke sampler scoort ongeveer 2.

De kernmethodologie bestaat uit het definiëren van een progressiemaat $\lambda$ die de afwijking van de toestand van een apparaat van de "eerlijke" toestand (die een enkele query maakt) kwantificeert. De analyse volgt een driestapsraamwerk:

Scorebound: De verwachte score $B(A)$ wordt begrensd in termen van de progressiemaat: $B(A) \leq \text{Ideale Score} + O(\lambda + \lambda^2)$ .
Groei-bound: Er wordt aangetoond dat elke query $\lambda$ slechts met $O(\sqrt{(t+1)/N})$ verhoogt, waarbij $t$ het aantal voorgaande queries is. Bijgevolg is $\lambda$ na $q$ queries $= O(q^{3/2}/\sqrt{N})$ .
Willekeurextractie: Voor apparaten met scores nabij de ideale score (kleine tekortkoming $\delta$ ), wordt het bewijs van de scorebound verfijnd om aan te tonen dat de output-vertakkingen van het apparaat dicht bij specifieke hulpvectoren liggen. Deze vectoren worden gegenereerd door operatoren die uitsluitend op het apparaat inwerken, met normen begrensd door $\text{poly}(q)\sqrt{p(z)}$ . Deze structuur impliceert dat de capaciteit van Eve om de output te raden beperkt is, zelfs als zij de oracle kent.

Kernbijdragen en Resultaten

1. Strakke ondergrenzen voor het overtreffen van de ideale score
Het artikel stelt vast dat de ideale score fungeert als een "Tsirelson-grens" voor efficiënte kwantumapparaten in deze sampling-taken.

Query-complexiteit: Om de ideale score met een constante $\epsilon$ $ϵ$ te overtreffen, vereist een kwantumalgoritme $\Omega(N^{1/3})$ $Ω (N^{1/3})$ queries.
- Voor Fourier sampling vereist een verwachte score van $3 + \epsilon$ dat $q \geq \Omega(N^{1/3})$ .
- Voor Haar-random states vereist een verwachte score van $2 + \epsilon$ dat $q \geq \Omega(N^{1/3})$ .
Bovengrenzen: De auteurs bevestigen dat $O(N^{1/3})$ queries voldoende zijn om de ideale score met een constante te overtreffen met behulp van een "squaring algorithm" (een variant van het collision-finding algoritme). Dit algoritme slaat $m \approx N^{1/3}$ ideale samples op en gebruikt amplitude amplification om de output te biassen naar het kwadraat van de ideale distributie, $p(z)^2$ .
Strakheid: Deze grenzen zijn strak; de kloof tussen de eerlijke sampler (1 query) en het vermogen om de ideale score significant te overtreffen wordt exact gekarakteriseerd door de $N^{1/3}$ drempelwaarde.

2. Gecertificeerde willekeur bij de ideale score
Het artikel bewijst dat een apparaat dat polynomiaal veel queries uitvoert en een score behaalt binnen $o(1)$ van de ideale score, een output produceert met bijna maximale willekeur.

Min-entropie: Voor zowel Fourier sampling als Haar-random states (via de canonieke oracle), heeft de output $Z$ een smooth min-entropie $H_{\min}^\eta(Z | RE) \geq n - O(\log n)$ , waarbij $R$ de oracle is en $E$ de register van Eve.
Adversarieel model: Dit geldt zelfs als Eve verstrengeld is met het apparaat en de volledige beschrijving van de oracle (de functie $f$ of de vector $\phi$ ) leert nadat het apparaat $Z$ heeft uitgegeven.
Parameters: De smoothing parameter $\eta$ schaalt als $O(\sqrt{\delta} + q^{3/4}N^{-1/4})$ . Als het tekort $\delta$ verwaarloosbaar is en $q$ polynomiaal in $n$ is, is de smoothing verwaarloosbaar, wat $n - O(\log n)$ bits aan willekeur certificeert.
Optimaliteit: De $O(\log n)$ verliezen zijn bijna optimaal. Het artikel construeert apparaten met amplitude amplification die bijna ideale scores behalen maar de output beperken tot een bekende verzameling van grootte $N/q^2$ , wat de min-entropie beperkt tot $n - 2\log q$ .

3. Aanvullende resultaten

Collision Distributie: Het artikel toont aan dat het samplen van de collision distributie (proportioneel aan $p(z)^2)$ een query-complexiteit heeft van $\Theta(N^{1/3})$ .
Quantum Hadamard Producten: Een coherente versie van het squaring algorithm wordt gepresenteerd om de quantum Hadamard product van twee toestanden met uniforme amplitude-magnitudes voor te bereiden. Dit algoritme bereikt een trace distance error van $O(N^{-1/6})$ met $O(N^{1/3})$ queries, wat een verbetering is ten opzichte van de $\sqrt{N}$ queries die vereist zijn door standaard amplitude amplification.

Betekenis en Claims
Het artikel claimt onvoorwaardelijke, informatie-theoretische garanties te bieden voor kwantum sampling-taken, waarmee openstaande vragen over de "kwantum suprematie Tsirelson-ongelijkheid" worden opgelost.

Analogie met CHSH: De resultaten trekken een directe parallel met het CHSH-spel. Net zoals Tsirelson's grens ( $\cos^2(\pi/8)$ ) de winstkans van kwantumstrategieën limiteert en willekeur certificeert bij die grens, limiteert de ideale XEB-score de prestaties van efficiënte kwantum samplers en certificeert het willekeur nabij die score.
Onvoorwaardelijke veiligheid: In tegenstelling tot eerdere resultaten die vertrouwden op computationele hardheid-aannames of beperkte kennis van de tegenstander (bijv. het niet leren van de volledige oracle), biedt dit werk onvoorwaardelijke grenzen tegen een tegenstander die de oracle leert kennen en willekeurige verstrengeling bezit.
Beperkingen: De auteurs merken op dat hun resultaten van toepassing zijn in het oracle-model. Voor real-world apparaten (zoals in [AAB+19]) liggen de scores momenteel ver van het ideaal (bijv. 1.002 vs. 2), wat betekent dat de huidige garanties voor gecertificeerde willekeur in experimentele settings steunen op andere, zwakkere aannames (bijv. [AH23]). Bovendien vereist het resultaat voor Haar-random states de canonieke state-preparation oracle in plaats van volledige unitary access, aangezien een tegenstander die een volledige Haar-random unitary leert, potentieel de outputs kan correleren met de kolommen van de unitary.

Samenvattend definieert het artikel rigoureus de limieten van efficiënte kwantum sampling, waarbij wordt bewezen dat de ideale score een harde barrière is voor efficiënte kwantumapparaten en dat het benaderen van deze barrière bijna alle mogere willekeur certificeert, zelfs tegen krachtige kwantumtegenstanders.

Meer zoals dit