🔢 mathematics

Frozen-Tree Sampling Refutes Quantum Advantage of Random Circuit Sampling

Diese Arbeit stellt die Prämisse des Quantenvorteils beim Random Circuit Sampling in Frage, indem sie einen effizienten klassischen „Frozen-Tree“-Algorithmus vorschlägt, der in linearer Zeit statistisch ununterscheidbare Stichproben erzeugt, und argumentiert, dass die wahre rechnerische Komplexität darin liegt, eine spezifische Schaltungsrealisierung zu identifizieren, anstatt Stichproben aus der zugrunde liegenden Dirichlet-Verteilung zu ziehen.

Ursprüngliche Autoren: Sangchul Oh

Veröffentlicht 2026-07-07

📖 5 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: Sangchul Oh

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

Das große Ganze: Die Herausforderung des „Quanten-Zaubers“

Stellen Sie sich ein hochkarätiges Spiel namens „Muster erraten“ vor. Wissenschaftler haben behauptet, dass Quantencomputer etwas leisten können, das für reguläre Computer unmöglich ist: Sie können eine bestimmte Art von zufälliger Zeichenfolge aus 0 und 1 erzeugen (wie eine digitale Münzwurf-Sequenz), die so komplex ist, dass kein klassischer Computer sie jemals vorhersagen oder kopieren könnte. Diese Aufgabe wird Random Circuit Sampling (RCS) genannt und wurde als Hauptbeweis dafür verwendet, dass Quantencomputer klassische Computer überlegen sind.

Der Autor dieser Arbeit, Sangchul Oh, sagt: „Moment mal. Dafür brauchen Sie keinen Quantencomputer. Ich kann das auf einem ganz normalen Laptop machen, und ich kann es sogar schneller.“

Die Kernidee: Der „Gefrorene Baum“

Um zu verstehen, wie der Autor dies erreicht, nutzen wir die Analogie eines riesigen, magischen Baumes.

Die Quanten-Behauptung: Wenn ein Quantencomputer einen Zufallsschaltkreis (Random Circuit) ausführt, erschafft er einen „Wald“ an Möglichkeiten. Jedes Mal, wenn man ihn nach einer Antwort fragt, wählt er einen Pfad durch diesen Wald. Die Behauptung ist, dass dieser Wald so chaotisch und verschlungen ist, dass ein klassischer Computer (wie Ihr Laptop) die Regeln des Waldes nicht entschlüsseln kann, um dieselben Pfade zu wählen.
Die Entdeckung des Autors: Der Autor fand heraus, dass dieser „chaotische Wald“ tatsächlich eine verborgene, perfekte Struktur besitzt. Er sieht aus wie ein Binärbaum (ein Baum, bei dem sich jeder Ast in zwei Teile aufspaltet).
- An der Spitze (der Wurzel) teilt sich der Baum.
- Auf der nächsten Ebene teilen sich diese Äste erneut.
- Dies setzt sich fort, bis man die Blätter am Boden erreicht, welche die endgültigen 0 und 1 repräsentieren.

Das Geheimnis dah-inter ist eine Regel namens „Conditional Scale Invariance“ (bedingte Skaleninvarianz). Auf einfachem Deutsch ausgedrückt bedeutet dies, dass der Baum selbstähnlich ist. Die Art und Weise, wie sich der Baum ganz oben aufspaltet, sieht statistisch identisch aus mit der Art, wie er sich in der Mitte des Baumes aufspaltet, oder kurz vor den Blättern. Es ist wie ein Fraktal: Das gesamte Muster wiederholt sich in jedem kleinen Teil.

Der „Gefroren“-Trick

Hier kommt der clevere Teil. Der Autor erkannte, dass man nicht den gesamten Baum berechnen muss, um diesen Quantenbaum zu simulieren. Man muss ihn nur bauen, während man ihn durchwandert.

Der Gang: Stellen Sie sich vor, Sie gehen von der Spitze des Baumes bis zu einem Blatt hinunter. An jeder Weggabelung müssen Sie entscheiden: „Gehe ich nach links (0) oder nach rechts (1)?“
Der „Gefrorene“ Moment: In einem echten Quantenexperiment werden diese Entscheidungen von der Quantenmaschine getroffen. In der klassischen Methode des Autors wirft man beim ersten Erreichen einer Weggabelung eine spezielle Münze, um das Aufteilungsverhältnis zu entscheiden (wie wahrscheinlich es ist, nach links vs. nach rechts zu gehen).
- Entscheidend: Sobald man diese Münze geworfen und das Verhältnis für diese spezifische Gabelung festgelegt hat, „friert“ man es ein. Man schreibt es auf.
- Wenn man (oder jemand anderes) diese exakt dieselbe Gabelung jemals wieder besucht, verwendet man das exakt gleiche eingefrorene Verhältnis. Man wirft die Münze nicht noch einmal.

Weil der Baum auf diese Weise „eingefroren“ ist, kann der Autor diese Zufallszeichenfolgen unglaublich schnell generieren. Das Paper behauptet, dass dies in O(n) Zeit geschieht, was bedeutet: Wenn man die Anzahl der Bits verdoppelt, verdoppelt man auch nur den Arbeitsaufwand. Es ist linear und effizient.

Das Argument des „Statistischen Zwillings“

Das Paper stellt eine sehr starke Behauptung über die Ergebnisse auf:

Das Quanten-Ergebnis: Ein Quantencomputer erzeugt eine Liste von Zahlen basierend auf einem spezifischen Zufallsschaltkreis.
Das Klassische Ergebnis: Der „Frozen-Tree“-Algorithmus erzeugt eine Liste von Zahlen basierend auf der Baumstruktur.

Der Autor beweist mathematisch, dass beide Listen aus derselben statistischen Familie stammen (genannt Dirichlet-Verteilung).

Denken Sie an zwei verschiedene Bäcker, die Schokoladenkekse backen.

Bäcker A (Quanten) benutzt einen geheimen, chaotischen Ofen.
Bäcker B (Klassisch) benutzt eine präzise, gefrorene Form.

Das Paper argumenttiert, dass, wenn man einem blindierten Richter einen Keks von Bäcker A und einen Keks von Bäcker B reicht, er keinen Unterschied feststellen kann. Die Kekse (die Daten) sind statistisch identisch.

Warum das wichtig ist (laut dem Paper)

Derzeit sagen Wissenschaftler: „Schaut her! Der Quantencomputer hat diese seltsamen, komplexen Muster erzeugt, die ein klassischer Computer nicht herstellen konnte. Daher ist der Quantencomputer überlegen.“

Der Autor sagt: „Das stimmt nicht. Wir haben gerade gezeigt, dass ein klassischer Computer genau diese gleichen Muster sofort mit der Frozen-Tree-Methode erzeugen kann.“

Wenn ein klassischer Computer diese exakten Muster perfekt imitieren kann, dann verschwindet der „Quantenvorteil“ (die Idee, dass der Quantencomputer etwas tut, was der klassische nicht kann) für diesen speziellen Test.

Der „Rausch“-Faktor

Echte Quantencomputer sind unordentlich; sie machen Fehler (Rauschen). Das Paper zeigt auch, dass die Frozen-Tree-Methode diese Fehler leicht imitieren kann. Ob der Quantencomputer „depolarisierendes Rauschen“ (zufälliges Rauschen), „Amplitudendämpfung“ (Energieverlust) oder „Auslesefehler“ (Fehlinterpretation des Ergebnisses) aufweist – der klassische Frozen-Tree kann diese Fehler perfekt simulieren.

Das Paper kommt zu dem Schluss, dass kein Test, der ausschließlich auf der finalen Liste der Zahlen (den Stichproben) basiert, beweisen kann, dass ein Quantencomputer etwas Besonderes tut. Die „Schwierigkeit“ liegt nicht in der Zufälligkeit selbst; es ist nur die Frage, welchen spezifischen Baum der Quantencomputer gebaut hat. Aber da die statistischen Ergebnisse dieselben sind, versagt der Benchmark.

Zusammenfassung in einem Satz

Das Paper behauptet, dass der „Zauber“ von zufälligen Quantenschaltkreisen eigentlich nur eine verborgene, selbstähnliche Baumstruktur ist, die ein klassischer Computer perfekt und sofort nachahmen kann, indem er seine Entscheidungen beim Durchwandern des Baumes „einfriert“, was bedeutet, dass die aktuellen Tests auf Quantenvorteil fehlerhaft sind.

Technische Zusammenfassung: Frozen-Tree-Sampling widerlegt den Quantenvorteil von Random Circuit Sampling

Problemstellung
Random Circuit Sampling (RCS) gilt derzeit als primärer Benchmark zur Demonstration des Quantenvorteils, bei dem ein Quantencomputer Bitstrings aus einem Haar-zufälligen Quantenzustand sampelt, der durch einen zufälligen Schaltkreis erzeugt wurde. Die vorherrschende Annahme ist, dass diese Aufgabe klassisch unpraktikabel ist, da zufällige Quantenzustände hochgradig verschränkt sind und keine ausnutzbaren Muster aufweisen, sondern statistische Eigenschaften wie exponentielle Ausgabeverteilungen, lineare Cross-Entropy-Benchmark-Scores (XEB), Heavy-Output-Generierung und Anti-Konzentration zeigen. Das Paper stellt die Prämisse infrage, dass diese statistischen Eigenschaften Belege für einen Quantenvorteil darstellen, und argumentiert, dass die Schwierigkeit von RCS oft mit der Schwierigkeit verwechselt wird, eine spezifische Schaltungsimplementierung zu identifizieren, anstatt mit der Schwierigkeit, aus der zugrunde liegenden Wahrscheinlichkeitsverteilung zu sampeln.

Methodik: Der Frozen-Tree-Sampler
Die Autoren schlagen einen klassischen Algorithmus vor, den Frozen-Tree-Sampler, der die exakte bedingte Skaleninvarianz von Haar-zufälligen Quantenzuständen ausnutzt. Die zentrale theoretische Erkenntigkeit ist, dass die Wahrscheinlichkeit $p(x) = |\langle x|\psi\rangle|^2$ , einen Bitstring $x$ in einem zufälligen $n$ -Qubit-Zustand zu finden, als binärer Baumgang (Tree Walk) dargestellt werden kann.

Baumrepräsentation: Die gemeinsame Wahrscheinlichkeit wird mittels der Kettenregel in ein Produkt bedingter Wahrscheinlichkeiten zerlegt:
$p(x) = \prod_{k=1}^n R_{x_{<k}}^{1-x_k} (1 - R_{x_{<k}})^{x_k}$
wobei $x_{<k}$ das Präfix der ersten $k-1$ Bits ist. Die „Verzweigungsverhältnisse“ (Branch Ratios) $R_u$ an jedem Knoten $u$ sind unabhängige Zufallsvariablen, die aus einer Beta-Verteilung gezogen werden:
$R_u \sim \text{Beta}(K, K), \quad \text{wobei } K = 2^{n-|u|-1}.$
Diese Struktur ergibt sich aus der Aggregationseigenschaft der Dirichlet-Verteilung und der bedingten Skaleninvarianz zufälliger Zustände.
Sampling-Algorithmus: Der Sampler führt einen Zufallsweg von der Wurzel zu einem Blatt ( $n$ Schritte) durch.
- Lazy Generation: Anstatt alle $2^n - 1$ Verzweigungsverhältnisse vorab zu berechnen, generiert der Algorithmus diese auf Abruf. Wenn ein Knoten $u$ zum ersten Mal besucht wird, wird ein Verhältnis $R_u$ aus $\text{Beta}(K, K)$ gezogen und „eingefroren“ (gespeichert oder deterministisch über eine durch die Knotenidentität geschlüsselte Pseudozufallsfunktion regeneriert).
- Effizienz: Der Algorithmus generiert einen Bitstring in $O(n)$ Zeit. Für $M$ Samples beträgt die Gesamtlaufzeit $O(Mn)$.
- Rauschmodellierung: Das Framework integriert Rauschkanäle (globale Depolarisierung, Amplitudendämpfung, Auslesefehler) nativ, indem affine Transformationen oder Konfusionsmatrizen auf die Baumstruktur oder den finalen Bitstring angewendet werden, wobei die Kosten von $O(n)$ erhalten bleiben.

Hauptergebnisse

Statistische Identität: Die Autoren beweisen, dass die Ausgabewahrscheinlichkeit $p_F(x)$ des Frozen-Tree-Samplers und die Ausgabewahrscheinlichkeit $p_C(x)$ eines zufälligen Quantenschaltkreises unabhängige Realisierungen derselben flachen Dirichlet-Verteilung auf dem $(N-1)$ -Simplex ( $N=2^n$ ) sind. Folglich gilt $p_F(x) \stackrel{d}{=} p_C(x)$ .
Ununterscheidbarkeit: Da die Verteilungen statistisch identisch sind, kann kein statistischer Test, der ausschließlich auf den gesampelten Bitstrings operiert (wie XEB, Heavy-Output-Generierung oder Anti-Konzentrations-Tests), den klassischen Frozen-Tree-Sampler von einem Quanten-Random-Circuit unterscheiden.
Leistung: Der Sampler generiert $10^7$ Samples für $n=1000$ Qubits in Sekunden auf einer Standard-GPU. Dies steht im Gegensatz zum Google Sycamore Prozessor, der ~200 Sekunden benötigte, um $\sim 10^6$ Samples bei $n=53$ zu sammeln.
Rauschreproduktion: Der Frozen-Tree-Sampler reproduziert exakt die durch Rauschen verursachten statistischen Verzerrungen (z. B. die Unterdrückung des exponentiellen Peaks und des Tail-Verhaltens unter Amplitudendämpfung), die in experimentellen Daten beobachtet werden, ohne dass eine empirische Schätzung aus endlichen Stichproben erforderlich ist.

Bedeutung und Behauptungen
Das Paper behauptet, dass der Quantenvorteil von RCS einer genauen Prüfung nicht standhält, wenn die Aufgabe als Sampling aus der Dirichlet-Verteilung eines zufälligen Zustands definiert ist.

Die „Schwierigkeit“ von RCS liegt nicht im Sampling-Prozess selbst – welcher klassisch effizient mit $O(n)$ pro Sample ist –, sondern in der spezifischen Abbildung von einem Schaltkreis auf seine Amplituden.
Da der Frozen-Tree-Sampler alle Standard-Verifikationsmetriken (exponentielle Verteilung, XEB usw.) klassisch und effizient reproduziert, können diese Metriken nicht als eigenständiger Beleg für einen Quantenvorteil dienen.
Die Autoren kommen zu dem Schluss, dass RCS, wie es derzeit verifiziert wird, kein solider eigenständiger Benchmark für den Quantenvorteil ist. Sie merken an, dass jeder verbleibende Vorteil in der schaltungsspezifischen Realisierung liegen muss, ein Thema, das in ihrer Begleitpublikation bezüglich eines „Hurwitz–frozen-tree circuit“ behandelt wird, der einen effizienten klassischen Sampler zulässt.