⚛️ quantum physics

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

Diese Arbeit etabliert enge Quantenabfrageschranken für das Erreichen hoher linearer Kreuzentropie-Benchmark-Scores beim Random Circuit Sampling, wobei bewiesen wird, dass das Überschreiten der idealen Leistung $\Omega(N^{1/3})$ Abfragen erfordert und eine nahezu optimale glatte Min-Entropie für die Ausgaben zertifiziert wird, wodurch dadurch rigorose Sicherheitsgarantien für zertifizierte Zufälligkeit gegenüber verschränkten Angreifern bereitgestellt werden.

Ursprüngliche Autoren: Keshav Bhateja, Mehdi Esmaili, Atul Mantri

Veröffentlicht 2026-10-06

📖 6 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Keshav Bhateja, Mehdi Esmaili, Atul Mantri

Originalarbeit lizenziert unter CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ Dies ist eine KI-generierte Erklärung des untenstehenden Papers. Sie wurde nicht von den Autoren verfasst oder gebilligt. Für technische Genauigkeit konsultieren Sie das Originalpaper. Vollständigen Haftungsausschluss lesen

Im Wettlauf darum zu beweisen, dass Quantencomputer Dinge leisten können, die für klassische Maschinen unmöglich sind, haben sich Wissenschaftler auf eine spezifische Art von Experiment konzentriert: die Aufforderung an ein Quantengerät, eine Liste von Zufallszahlen zu generieren. Diese Zahlen sind nicht einfach nur irgendwelche Zufallsfolgen; sie werden aus einem komplexen, unsichtbaren Muster gezogen, das durch einen zufälligen Quantenschaltkreis erzeugt wird. Um zu überprüfen, ob das Gerät korrekt arbeitet, verwenden Forscher ein Bewertungssystem namens „Linear Cross-Entropy Benchmark“. Dieser Score misst, wie oft das Gerät Zahlen wählt, die eine ideale Quantenmaschine am häufigsten wählen würde. Wenn das Gerät ehrlich ist und perfekt arbeitet, erreicht es einen spezifischen, hohen Score. Wenn es lediglich zufällig rät, erzielt es einen wesentlich niedrigeren Score. Jahrelang galt dieser Test als Goldstandard für die Behauptung eines „Quantenvorteils“ (Quantum Advantage), doch eine entscheidende Frage blieb unbeantwortt: Beweist ein hoher Score tatsächlich, dass das Gerät echte, unvorhersehbare Zufälligkeit erzeugt? Ein geschickter Angreifer könnte ein Gerät potenziell so manipulieren, dass es hohe Scores erzielt, indem er einfach die wahrscheinlichsten Antworten auswendig lernt, was den Output vorhersagbar macht, obwohl der Score gut aussieht.

Ein Team von Forschern der Virginia Tech hat diese Frage nun mit mathematischer Gewissheit beantwortet und eine strikte Grenze dafür festgelegt, was ein hoher Score zertifizieren kann und was nicht. Sie bewiesen, dass ein Quantengerät, um auch nur geringfügig besser abzuschneiden als die bestmögliche ehrliche Maschine, eine gewaltige Anzahl interner Operationen ausführen muss – weit mehr, als jeder effiziente klassische Computer bewältigen könnte. Speziell zeigten sie, dass ein Gerät, um den idealen Score um einen festen Betrag zu übertreffen, eine Anzahl von Abfragen (Queries) benötigt, die proportional zur Kubikwurzel der Gesamtzahl der möglichen Ergebnisse ist. Dieses Ergebnis fungiert als fundamentale Grenze, ähnlich wie ein Tempolimit auf einer Autobahn, das sicherstellt, dass kein effizienter Trick einen hohen Score vortäuschen kann. Darüber hinaus demonstrierten sie, dass, wenn ein Gerät innerhalb einer winzigen Spanne dieses idealen Scores bleibt, sein Output tatsächlich unvorhersehbar ist. Selbst wenn ein Angreifer das Gerät gebaut hat, über eine geheime Quantenverbindung mit ihm verfügt und das gesamte Setup im Nachhinein kennt, kann er den Output nicht mit nennenswerter Genauigkeit erraten. Das Gerät erzeugt effektiv fast das maximal mögliche Maß an Zufälligkeit, mit nur einem kleinen, unvermeidbaren Informationsverlust.

Die Forscher gelangten zu diesen Schlussfolgerungen, indem sie eine neue Methode entwickelten, um den „Fortschritt“ eines Quantenalgorithmus zu verfolgen, während er ein unbekanntes System abfragt. Stellen Sie sich einen Quantencomputer vor, der versucht, die Form eines verborgenen Objekts zu erlernen, indem er es mit einer Sonde abtastet. Das Team entwickelte ein mathematisches Maß, das bei einem Gerät, das einfach nur ehrlich den Regeln folgt, bei Null beginnt. Sie bewiesen, dass dieses Fortschrittsmaß jedes Mal, wenn das Gerät eine Abfrage tätigt, um mehr über das System zu erfahren, nur um einen sehr kleinen Betrag wachsen kann. Um einen Score zu erreichen, der die ehrliche Maschine übertrifft, müsste das Gerät genug Fortschritt akkumulieren, um eine Barriere zu durchbrechen, aber die Mathematik zeigt, dass dies eine unpraktikable Anzahl von Schritten erfordert. Diese Methode ermöglichte es ihnen, die Lücke zwischen dem, was theoretisch möglich war, und dem, was bewiesen notwendig war, zu schließen, und bestätigte eine langjährige Vermutung über die Schwierigkeit, diese Ergebnisse vorzutäuschen.

Über die bloße Beweisführung der Grenzen des Vortäuschens von Ergebnissen hinaus beschreibt die Arbeit auch einen spezifischen Algorithmus, der tatsächlich diese hohen Scores erreichen kann, jedoch nur unter Verwendung der maximal zulässigen Anzahl an Abfragen. Dieser „Squaring-Algorithmus“ arbeitet, indem er mehrere Stichproben nimmt, sie speichert und dann eine Technik namens „Amplitude Amplification“ verwendet, um die Wahrscheinlichkeit zu erhöhen, eine Übereinstimmung zu finden. Dieser Prozess quadriert effektiv die Wahrscheinlichkeitsverteilung und begünstigt die wahrscheinlichsten Ergebnisse noch stärker als die ehrliche Maschine. Die Existenz dieses Algorithmus beweist, dass die von ihnen gefundene untere Schranke „tight“ ist; sie ist nicht nur eine theoretische Wand, sondern ein erreichbarer Gipfel, der einen spezifischen, ressourcenintensiven Aufstieg erfordert. Diese Dualität – zu beweisen, dass man Ergebnisse nicht leicht vortäuschen kann, aber auch zu zeigen, wie schwer es ist, legitim zu gewinnen – liefert ein vollständiges Bild der Landschaft.

Die Implikationen für zertifizierte Zufälligkeit sind tiefgreifend. In vielen Sicherheitsanwendungen müssen wir Zufallszahlen generieren, die selbst derjenige, der den Generator gebaut hat, nicht vorhersagen kann. Die Studie bestätigt, dass, wenn ein Quantengerät den Standardtest mit einem Score sehr nah am Ideal besteht, es eine Zeichenfolge generiert, die fast so viel Zufälligkeit enthält wie die Länge der Zeichenfolge selbst. Für ein Gerät, das mit sechzig Qubits arbeitet und somit Zeichenfolgen von sechzig Bits produzieren kann, garantiert ein nahezu perfekter Score, dass der Output etwa vierundfünfzig Bits echter, zertifizierter Zufälligkeit enthält. Dies gilt selbst gegenüber einem Angreifer, der mit dem Gerät verschränkt ist und jedes Detail seiner Konstruktion kennt. Die einzige verlorene Information ist ein kleiner Betrag, der mit der Anzahl der Abfragen des Geräts zusammenhängt, was für praktische Zwecke vernachlässigbar ist.

Diese Arbeit erstreckt sich auch auf andere Arten des Quanten-Samplings, einschließlich derer, die in photonischen Experimenten mit Lichtteilchen verwendet werden. Die Forscher zeigten, dass dieselben Regeln gelten: Um den idealen Score zu übertreffen, muss ein Gerät eine spezifische, große Anzahl von Operationen ausführen, und um nahe am idealen Score zu bleiben, muss es echte Zufälligkeit erzeugen. Sie verknüpften diese Erkenntnisse sogar mit einem anderen Problem: der Erzeugung einer „Collision Distribution“, bei der das Gerät aufgefordert wird, Paare von Zahlen auszugeben, die mit höherer Wahrscheinlichkeit identisch sind. Sie fanden heraus, dass das Erzeugen dieser spezifischen Art von Verteilung ebenfalls die gleiche Kubikwurzel-Anzahl an Abfragen erfordert, wodurch diese scheinbar unterschiedlichen Aufgaben unter einem einzigen mathematischen Gesetz vereint werden.

Die Studie behauptet nicht, dass aktuelle Quantencomputer bereits perfekt sind. Reale Geräte erzielen aufgrund von Rauschen und Fehlern oft deutlich niedrigere Scores. Das Papier etabliert jedoch die theoretische Decke und den Boden dessen, was möglich ist. Es sagt uns: Wenn wir jemals ein Gerät sehen, das nahe am Maximum punktet, können wir darauf vertrauen, dass es etwas wahrhaft Quantenmechanisches tut und echte Zufälligkeit erzeugt. Umgekehrt, wenn ein Gerät behauptet, Zufälligkeit zu erzeugen, aber nicht in der Lage ist, diesen Score ohne eine unzumutbare Anzahl von Schritten zu erreichen, wissen wir, dass es nicht das tut, was es vorgibt. Die Forschung bietet das notwendige rigorose Fundament, um von experimentellen Demonstrationen zu zuverlässiger, zertifizierter Quanten-Zufälligkeit überzugehen und sicherzustellen, dass die Zukunft der Quantensicherheit auf festem, bewiesenem Boden steht.

Technische Zusammenfassung: Enge untere Schranken für die Abfragekomplexität beim Quanten-Sampling, mit Anwendung auf zertifizierte Zufälligkeit

Problemstellung
Experimente zum Random Circuit Sampling sind die führenden Demonstrationen des quantencomputationalen Vorteils, die typischerweise mittels des linearen Cross-Entropy-Benchmarks (XEB) verifiziert werden. Der XEB-Score misst, wie gut die Ausgabeverteilung eines Geräts mit der idealen Verteilung $p$ übereinstimmt, indem er den Durchschnitt von $N p(z)$ für die zurückgegebenen Strings $z$ berechnet, wobei $N=2^n$ . Während ein hoher Score auf einen Quantenvorteil hindeutet, garantiert er nicht inhärent, dass das Gerät tatsächlich aus $p$ gezogen hat oder dass die Ausgabe zufällig ist. Ein Gerät könnte einen hohen Score erzielen, indem es deterministisch den wahrscheinlichsten String ausgibt (den ein Angreifer kennen könnte), wodurch es die Erzeugung zertifizierter Zufälligkeit verfehlt.

Diese Arbeit adressiert zwei grundlegende Fragen im Quanten-Abfragemodell (Query Model):

Score-Limits: Wie hoch kann der Score eines effizienten Quantengeräts relativ zum idealen Score sein? Kann ein effizientes Gerät den idealen Score um eine Konstante übertreffen?
Zertifizierung von Zufälligkeit: Wenn ein Gerät einen Score nahe dem Ideal erreicht, wie viel glatte Min-Entropie (zertifizierte Zufälligkeit) enthält seine Ausgabe, selbst gegenüber einem Angreifer (Eve), der mit dem Gerät verschränkt sein kann und das Orakel (den Schaltkreis oder die Funktion) nachträglich erfährt.

Methodik
Die Autoren arbeiten im Abfragemodell, in dem der Schaltkreis durch ein Orakel ersetzt wird, das aus einem bekannten Ensemble stammt. Sie analysieren zwei spezifische Ensembles:

Fourier-Sampling: Das Orakel ist eine gleichverteilt zufällige Funktion $f: \{0,1\}^n \to \{\pm 1\}$ . Der ehrliche Sampler erzielt einen Score von etwa 3.
Haar-Zufallslzustände: Das Orakel verbirgt einen gleichmäßig zufälligen Einheitsvektor $|\phi\rangle$ (zugänglich über ein kanonisches Zustandspräparations-Orakel oder Haar-zufälligen Unitary-Zugriff). Der ehrliche Sampler erzielt etwa 2.

Die Kernmethodik besteht darin, ein Fortschrittsmaß $\lambda$ zu definieren, das die Abweichung des Zustands eines Geräts vom „ehrlichen“ Zustand (der eine einzige Abfrage macht) quantifiziert. Die Analyse folgt einem dreistufigen Rahmen:

Score-Schranke: Der erwartete Score $B(A)$ ist in Bezug auf das Fortschrittsmaß begrenzt: $B(A) \leq \text{Idealer Score} + O(\lambda + \lambda^2)$ .
Wachstums-Schranke: Es wird gezeigt, dass jede Abfrage $\lambda$ nur um $O(\sqrt{(t+1)/N})$ erhöht, wobei $t$ die Anzahl der vorangegangenen Abfragen ist. Folglich gilt nach $q$ Abfragen $\lambda = O(q^{3/2}/\sqrt{N})$ .
Zufälligkeitsextraktion: Für Geräte mit Scores nahe dem Ideal (kleines Defizit $\delta$ ) wird der Beweis der Score-Schranke dahingehend verfeinert, dass die Ausgabenzweige des Geräts nahe an spezifischen Hilfsvektoren liegen. Diese Vektoren werden durch Operatoren erzeugt, die ausschließlich auf dem Gerät wirken, wobei deren Normen durch $\text{poly}(q)\sqrt{p(z)}$ begrenzt sind. Diese Struktur impliziert, dass die Fähigkeit von Eve, die Ausgabe zu erraten, begrenzt ist, selbst wenn sie das Orakel kennt.

Wesentliche Beiträge und Ergebnisse

1. Enge untere Schranken für das Übertreffen des idealen Scores
Die Arbeit etabliert, dass der ideale Score als „Tsirelson-Schranke“ für effiziente Quantengeräte in diesen Sampling-Aufgaben fungiert.

Abfragekomplexität: Um den idealen Score um eine Konstante $\epsilon$ $ϵ$ zu übertreffen, benötigt ein Quantenalgorithmus $\Omega(N^{1/3})$ $Ω (N^{1/3})$ Abfragen.
- Für Fourier-Sampling erfordert ein erwarteter Score von $3 + \epsilon$ eine Anzahl von $q \geq \Omega(N^{1/3})$ .
- Für Haar-Zufallslzustände erfordert ein erwarteter Score von $2 + \epsilon$ eine Anzahl von $q \geq \Omega(N^{1/3})$ .
Obere Schranken: Die Autoren bestätigen, dass $O(N^{1/3})$ Abfragen ausreichen, um den idealen Score durch einen „Squaring-Algorithmus“ (eine Variante des Kollisionsfindungs-Algorithmus) um eine Konstante zu übertreffen. Dieser Algorithmus speichert $m \approx N^{1/3}$ ideale Stichproben und nutzt Amplitudenverstärkung (Amplitude Amplification), um die Ausgabe in Richtung des Quadrats der idealen Verteilung, $p(z)^2$ , zu verzerren.
Tightness (Engheit): Diese Schranken sind eng; die Lücke zwischen dem ehrlichen Sampler (1 Abfrage) und der Fähigkeit, den idealen Score signifikant zu übertreffen, ist exakt durch den $N^{1/3}$ -Schwellenwert charakterisiert.

2. Zertifizierte Zufälligkeit beim idealen Score
Die Arbeit beweist, dass ein Gerät, das polynomielle Anzahl von Abfragen durchführt und einen Score innerhalb von $o(1)$ des Ideals erreicht, eine Ausgabe mit nahezu maximaler Zufälligkeit erzeugt.

Min-Entropie: Sowohl für Fourier-Sampling als auch für Haar-Zufallslzustände (über das kanonische Orakel) besitzt die Ausgabe $Z$ eine glatte Min-Entropie $H_{\min}^\eta(Z | RE) \geq n - O(\log n)$ , wobei $R$ das Orakel und $E$ das Register von Eve ist.
Adversarielles Modell: Dies gilt selbst dann, wenn Eve mit dem Gerät verschränkt ist und die vollständige Beschreibung des Orakels (die Funktion $f$ oder den Vektor $\phi$ ) erfährt, nachdem das Gerät $Z$ ausgegeben hat.
Parameter: Der Glättungsparameter $\eta$ skaliert als $O(\sqrt{\delta} + q^{3/4}N^{-1/4})$ . Wenn das Defizit $\delta$ vernachlässigbar ist und $q$ polynomiell in $n$ ist, ist die Glättung vernachlässigbar, was $n - O(\log n)$ Bits an Zufälligkeit zertifiziert.
Optimalität: Der Verlust von $O(\log n)$ wird als nahezu optimal gezeigt. Die Autoren konstruieren Geräte mittels Amplitudenverstärkung, die nahezu ideale Scores erreichen, aber die Ausgabe auf eine bekannte Menge der Größe $N/q^2$ beschränken, was die Min-Entropie auf $n - 2\log q$ begrenzt.

3. Zusätzliche Ergebnisse

Kollisionsverteilung: Die Arbeit zeigt, dass das Sampling der Kollisionsverteilung (proportional zu $p(z)^2$ ) eine Abfragekomplexität von $\Theta(N^{1/3})$ besitzt.
Quanten-Hadamard-Produkte: Ein kohärenter Version des Squaring-Algorithmus wird präsentiert, um das Quanten-Hadamard-Produkt zweier Zustände mit gleichmäßiger Amplitudenamplitude vorzubereiten. Dieser Algorithmus erreicht einen Trace-Distanz-Fehler von $O(N^{-1/6})$ mit $O(N^{1/3})$ Abfragen, was die $\sqrt{N}$ Abfragen verbessert, die durch Standard-Amplitudenverstärkung erforderlich wären.

Bedeutung und Behauptungen
Die Arbeit beansprucht, unwiderlegbare, informationstheoretische Garantien für Quanten-Sampling-Aufgaben zu liefern und damit offene Fragen zur „Quanten-Suprematie-Tsirelson-Ungleichung“ zu lösen.

Analogie zu CHSH: Die Ergebnisse ziehen eine direkte Parallele zum CHSH-Spiel. So wie die Tsirelson-Schranke ( $\cos^2(\pi/8)$ ) die Gewinnwahrscheinlichkeit von Quantenstrategien begrenzt und bei dieser Schranke Zufälligkeit zertifiziert, begrenzt der ideale XEB-Score die Leistung effizienter Quanten-Sampler und zertifiziert die Zufälligkeit nahe diesem Wert.
Unbedingliche Sicherheit: Im Gegensatz zu früheren Ergebnissen, die auf computergestützten Härteannahmen basierten oder die Kenntnis des Angreifers einschränkten (z. B. das Nicht-Erfahren des vollständigen Orakels), bietet diese Arbeit unbedingte Schranken gegen einen Angreifer, der das Orakel lernt und beliebige Verschränkung hält.
Einschränkungen: Die Autoren merken an, dass sich ihre Ergebnisse auf das Orakel-Modell beziehen. Für reale Geräte (wie in [AAB+19]) liegen die Scores derzeit weit vom Ideal entfernt (z. B. 1.002 vs. 2), was bedeutet, dass die aktuellen Garantien für zertifizierte Zufälligkeit in experimentellen Settings auf anderen, schwächeren Annahmen beruhen (z. B. [AH23]). Des Weiteren erfordert das Ergebnis für Haar-Zufallslzustände das kanonische Zustandspräparations-Orakel anstelle des vollen Unitary-Zugriffs, da ein Angreifer, der einen vollen Haar-Zufalls-Unitary lernt, potenziell die Ausgaben mit den Spalten des Unitaries korrelieren könnte.

Zusammenfassend definiert die Arbeit rigoros die Grenzen des effizienten Quanten-Samplings und beweist, dass das Erreichen der idealen Score-Schranke nahezu die gesamte mögliche Zufälligkeit zertifiziert, selbst gegenüber mächtigen Quanten-Angreifern.

Mehr davon