⚛️ quantum physics

Toward quantum scaling advantage in approximate optimization

Diese Arbeit stellt jüngste Behauptungen über Quanten-Skalierungsvorteile beim Lösen von QUBO-Problemen infrage, indem sie demonstriert, dass die klassische Simulated Bifurcation Machine bei größeren Instanzen eine vergleichbare oder überlegene Leistung erbringt, wodurch die berichtete Quanten-Klassik-Lücke geschlossen wird und darauf hindeutet, dass echte Quantenvorteile wahrscheinlich auf spezifische dünnbesetzte Problemklassen beschränkt sind, sobald Hardware-Overheads berücksichtigt werden.

Ursprüngliche Autoren: J. Pawłowski, P. Tarasiuk, J. Tuziemski, Ł. Pawela, B. Gardas

Veröffentlicht 2026-07-13

📖 4 Min. Lesezeit🧠 Tiefgang

CC BY 4.0

Ursprüngliche Autoren: J. Pawłowski, P. Tarasiuk, J. Tuziemski, Ł. Pawela, B. Gardas

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

Stellen Sie sich vor, Sie versuchen, den tiefsten Punkt in einer riesigen, nebligen Gebirgskette zu finden. Dies ist ein klassisches Rätsel für Computer, das man ein Optimierungsproblem nennt. Vor kurzem behaupteten Forscher, dass eine spezielle Art von „Quanten“-Bergsteiger (ein Quantum Annealer) den Boden viel schneller erreichen könnte als ein klassischer Computer, wenn die Berge größer werden. Sie nannten dies einen „Quantenvorteil“.

Aber ein neues Team von Wissenschaftlern beschloss, diesen Anspruch mit einem ganz anderen Bergsteiger zu überprüfen: der Simulated Bifurcation Machine (SBM).

Denken Sie beim Quanten-Bergsteiger an jemanden, der „thermische Fluktuationen“ nutzt – im Grunde erschüttert er den Boden, um zu sehen, ob er über einen kleinen Hügel springen kann. Die SBM hingegen ist wie ein Bergsteiger, der den Chaos reitet. Anstatt den Boden zu erschüttern, reitet er auf einer wilden, nichtlinearen Welle, die sich spaltet und springt (bifurkiert), geleitet von den Gesetzen der Physik, aber laufend auf einer Standard-Grafikkarte (GPU).

Hier ist das, was die Autoren fanden, als sie diese beiden Bergsteiger gegeneinander antreten ließen:

1. Der „Quantenvorteil“ könnte eine Illusion sein
Die vorangegangene Studie behauptete, der Quanten-Bergsteiger würde gewinnen. Die Autoren fanden jedoch heraus, dass, wenn man die SBM verwendet, diese genauso schnell oder sogar schneller läuft als die Quantenmaschine. Tatsächlich schloss die SBM bei den getesteten Problemgrößen (bis zu etwa 1.322 logischen Variablen) die Lücke vollständig. Der vermeintliche „Vorteil“ der Quantenmaschine verschwand, sobald man die Zeit berücksichtigte, die für die Vorbereitung des Durchlaufs und das Auslesen der Ergebnisse benötigt wird.

2. Kleine Berge lügen
Die Autoren argumentieren, dass die vorherige Studie Berge betrachtete, die zu klein waren, um die wahre Geschichte zu erzählen. Es ist, als würde man die Geschwindigkeit eines Marathonläufers basierend auf einem 100-Meter-Sprint beurteilen; die Startzeit spielt hier eine zu große Rolle. Als die Autoren die SBM an viel größeren Bergen testeten – bis zu 38.320 Variablen (was eine Quantenmaschine mit mindestens 1,5 × 10⁵ physischen Qubits erfordern würde, um dies überhaupt zu versuchen) – hielt sich die klassische SBM dennoch wacker. Die Skalierung blieb robust, was darauf hindeutet, dass die Quantenmaschine für diese spezifischen Arten von Problemen derzeit nicht das klassische Chaos-Maschinen-Modell schlägt.

3. Die „Zeit“-Falle
Ein großer Teil der Verwirrung kommt daher, wie man Zeit misst.

Die Quantenmaschine: Die vorangegangene Studie verwendete die „Annealing-Zeit“ (die Zeit, die die Maschine laut Angabe mit dem Klettern verbracht hat), was eine voreingestellte Zahl wie 14.100 µs für die Programmierung und 20,5 µs pro Stichprobe für Verzögerungen ist. Sie zählten nicht die Zeit, die benötigt wird, um mit der Maschine zu kommunizieren oder das Ergebnis auszulesen.
Die SBM: Die Autoren maßen die tatsächliche Zeit, die es dauerte, die Antwort zu erhalten, einschließlich des gesamten „Overheads“, wie etwa dem Verschieben von Daten zwischen dem Gehirn des Computers und seiner Grafikkarte.

Als die Autoren die realen Zeitkosten für die Quantenmaschine berücksichtigten, verschwand ihr Geschwindigkeitsvorteil. Die zuvor beobachtete „schnelle“ Skalierung lag hauptsächlich daran, dass sie die Zeit ignorierten, die man benötigt, um die Maschine bereit zu machen.

4. Wo könnte die Quantenmaschine gewinnen?
Das Paper sagt nicht, dass Quantencomputer nutzlos sind. Die Autoren deuten an, dass es einen spezifischen, engen Pfad gibt, auf dem Quanten gewinnen könnten: 3D-Spin-Glas-Probleme. In diesen speziellen, spärlich besetzten Rätseln scheint der Quanten-Bergsteiger extrem schnell (im Nanosekundenbereich) hochwertige Lösungen zu finden, wenn man nur die reine Kletterzeit betrachtet. Die Autoren mahnen jedoch zur Vorsicht und sagen, dass dies nur ein potenzieller Vorteil ist. Momentan hebt die zusätzliche Zeit, die für die Programmierung und das Auslesen benötigt wird, diesen Geschwindigkeitsvorteil auf. Sie legen nahe, dass ein echter Vorteil entstehen könnte, falls zukünftige Hardware diese Overheads reduzieren kann, aber im Moment bleibt es ein „Was wäre wenn“.

Das Fazit
Die Autoren kommen zu dem Schluss, dass die Behauptung eines „Quanten-Skalierungsvorteils“ für die spezifischen Probleme, die sie getestet haben, wahrscheinlich nicht korrekt ist. Die chaotische, klassische SBM ist ein mächtiger Konkurrent, der die Quantenmaschine matcht oder schlägt, wenn man das gesamte Rennen misst, nicht nur den Sprint. Sie schlagen vor, dass wir, um einen echten Sieg für Quantencomputer zu sehen, nach viel größeren Problemen und anderen Arten von Rätseln suchen müssen und darauf warten müssen, dass die Hardware aufhört, Zeit mit Setup und Auslesen zu verschwenden.

Kurz gesagt: Der Quanten-Bergsteiger ist derzeit nicht schneller als der chaotische klassische Bergsteiger, wenn man die gesamte Reise misst. Der „Vorteil“ war wahrscheinlich nur ein Trick der Zeitmessung.

Technische Zusammenfassung: Auf den Weg zu einem Quanten-Skalierungsvorteil in der approximativen Optimierung

Problemstellung
Die vorliegende Arbeit setzt sich mit einer jüngst aufgestellten Behauptung (Ref. [1]) auseinander, wonach das Quanten-Annealing von D-Wave einen Skalierungsvorteil gegenüber klassischen Heuristiken beim approximativen Lösen von QUBO-Problemen (Quadratic Unconstrained Binary Optimization) aufweist. Die Autoren argumentieren, dass der berichtete Vorteil kein echter Quanteneffekt ist, sondern ein Artefakt methodischer Annahmen, insbesondere der Verwendung von „Quantum Annealing Correction“ (QAC) und der Definition von Laufzeitmetriken, welche die Hardware-Overheads ausschließen. Die zentrale Frage ist, ob ein klassischer Algorithmus, der die wesentlichen operativen Merkmale des Quanten-Annealings teilt (nahezu parallele Evolution und eine definierte Beziehung zwischen Energielücke, Laufzeit und Lösungsqualität), den berichteten Skalierungsvorteil reproduzieren oder gar übertreffen kann.

Methodik
Die Autoren verwenden die Simulated Bifurcation Machine (SBM), einen klassischen Solver, der auf nichtlinearer Hamilton-Dynamik und chaotischem Verhalten basiert, statt auf thermischen Fluktuationen. Die SBM wird aus einer „Dequantisierung“ der Quantendynamik abgeleitet und nutzt ein Netzwerk gekoppelter nichtlinearer Oszillatoren.

Algorithmus: Die SBM löst das Ising-Modell (äquivalent zu QUBO), indem sie ein System von Variablen $x_i, y_i$ entwickelt, die durch diskretisierte Bewegungsgleichungen gesteuert werden. Das System durchläuft eine Sequenz von Bifurkationen, die durch einen linearen Zeitplan $p(t)$ getrieben werden und das System zu Zuständen niedriger Energie führen.
Metriken: Die Leistung wird unter Verwendung der Metrik Time-to- $\epsilon$ ( $TT_\epsilon$ ) bewertet, definiert als die Zeit, die benötigt wird, um mit einer Wahrscheinlichkeit von 99 % eine Lösung innerhalb einer Optimalitätslücke $\epsilon$ zum Grundzustand zu finden. Die Autoren analysieren den Median der $TT_\epsilon$ ( $[TT_\epsilon]_{Med}$ ) über mehrere Instanzen hinweg.
Skalierungsanalyse: Die Studie passt Potenzgesetz-Beziehungen $[TT_\epsilon]_{Med} \propto N^\alpha$ an, um den Skalierungsexponenten $\alpha$ zu bestimmen.
Experimenteller Umfang:
1. Reproduktion: Die Autoren re-evaluieren die spezifischen „Sidon-28“-Instanzen aus Ref. [1] (logische Qubits $N \in [142, 1322]$ ) unter Verwendung der SBM auf GPUs.
2. Extrapolation: Sie erweitern die Analyse auf wesentlich größere Instanzen ( $N$ bis zu $\approx 3,8 \times 10^4$ ), ein Regime, das für Quanten-Annealer derzeit unzugänglich ist.
3. Alternative Problemklasse: Sie untersuchen 3D-Spin-Glas-Instanzen, eine Klasse, in der Quanten-Annealer im „Fast Annealing“-Regime theoretisch gut abschneiden sollten.
Zeitliche Erfassung: Eine kritische Komponente der Methodik ist die strikte Unterscheidung zwischen:
- Gemessener Zeit ( $t_{runtime}$ oder $t_{tot}$ ): Beinhaltet alle Overheads (Programmierung, Auslesen, CPU-GPU-Kommunikation, Warteschlangen).
- Set/Annealing-Zeit ( $\tau$ oder $t_{GPU}$ ): Die reine Rechenzeit, exklusive der Overheads. Die Autoren argumentieren, dass der Vergleich der gemessenen klassischen Zeit gegen die ungemessene Quanten-„Set“-Zeit die Ergebnisse zugunsten der Quantengeräte verzerrt.

Wesentliche Beiträge und Ergebnisse

Schließung der Quanten-Klassik-Lücke: Bei den spezifisch untersuchten Instanzen aus Ref. [1] erreicht die GPU-basierte SBM Skalierungsexponenten ( $\alpha$ ), die vergleichbar mit – und in einigen Regimen besser als – den besten QAC-Ergebnissen sind. Wenn die Overheads in die Gesamtlaufzeit der SBM einbezogen werden, erreicht sie die Werte des Quanten-Annealers oder übertrifft sie sogar. Beim Vergleich der reinen Rechenzeiten ( $t_{GPU}$ vs. $\tau$ ) verringert sich der Abstand weiter, was darauf hindeutet, dass der berichtete Vorteil hochgradig sensitiv gegenüber der Definition der Overheads ist.
Endliche Größen-Effekte (Finite-Size Effects): Die Autoren zeigen, dass die Skalierungsexponenten stark von den Overheads bei kleinen Systemgrößen ( $N < 1500$ ) beeinflusst werden. Mit zunehmender Systemgröße auf $N \approx 3,8 \times 10^4$ verschwindet der Einfluss der Overheads, und die SBM zeigt eine robuste polynomielle Skalierung. Dies deutet darauf hin, dass die kleinen Instanzen in Ref. [1] nicht ausreichten, um asymptotisches Verhalten abzuleiten.
Widerlegung eines universellen Vorteils: Die Studie kommt zu dem Schluss, dass Quanten-Annealer für die untersuchten QUBO-Probleme und Laufzeit-Erfassungsmethoden keinen klaren Skalierungsvorteil gegenüber SBM-ähnlichen Solvern aufweisen. Der zuvor berichtete „Vorteil“ wird auf den Ausschluss von Overheads und die spezifischen Beschränkungen von QAC zurückgeführt.
Identifizierung potenzieller Vorteil-Regime: Das Paper identifiziert 3D-Spin-Glas-Instanzen als potenziellen Kandidaten für einen echten Quantenvorteil. In diesem Regime, wenn die Annealing-Zeit $\tau$ als Proxy für die Laufzeit verwendet wird, zeigt der Quanten-Annealer eine überlegene Skalierung im Vergleich zur SBM. Die Autoren merken jedoch an, dass nach Einbeziehung realistischer Overheads (Programmierung, Auslesen) dieser scheinbare Vorteil für die aktuelle Hardware verschwindet. Sie legen nahe, dass zukünftige Geräte mit reduzierten Hardware-Overheads in dieser spezifischen, spärlich besetzten (sparse) Problemklasse potenziell einen echten Vorteil realisieren könnten.

Bedeutung und Ansprüche
Das Paper beansprucht, ein konzeptionelles Fundament für das Voranschreiten zu einem echten Quantenvorteil zu liefern, indem es den Vergleichsmaßstab von thermischen Solvern (wie PT-ICM) zu quanteninspirierten, chaotischen Solvern (SBM) verschiebt.

Bescheidene Ansprüche: Die Autoren behaupten nicht, dass Quanten-Annealing nutzlos sei; vielmehr argumentieren sie, dass Behauptungen eines „Quantenvorteils“ gegen stetig verbesserte klassische Algorithmen validiert werden müssen und alle operativen Overheads berücksichtigen müssen.
Reinterpretation von Daten: Sie postulieren, dass die beobachtete Skalierung in Ref. [1] nicht eindeutig als Quanteneffekt interpretiert werden kann, da sie auch durch ein klassisches System reproduziert werden kann, das dieselben dynamischen Merkmale wie das Quanten-Annealing aufweist.
Zukunftsausblick: Das Paper legt nahe, dass ein echter Skalierungsvorteil möglicherweise nur für spezifische, spärlich besetzte Problemklassen (wie 3D-Spin-Gläser) erreichbar ist und dies nur dann, wenn die Hardware-seitigen Laufzeitbeschränkungen (Overheads) signifikant gemindert wurden. Bis dahin ist es unwahrscheinlich, dass aktuelle Generationen von Quantenprozessoren (QPUs) unter strenger Zeitrechnung die klassischen Solver bei der approximativen diskreten Optimierung übertreffen werden.

Mehr davon