A brief history of quantum vs classical computational advantage

Dieser Übersichtsartikel fasst umfassend alle Experimente zusammen, die einen Vorteil der Quantenberechnung beanspruchen, untersucht kritisch deren Herausforderungen und Widerlegungen, diskutiert theoretische Vorteile bei spezifischen Problemen und hebt den jüngsten Fortschritt in der Quantenfehlerkorrektur als entscheidenden Schritt zur Erzielung eines Vorteils im Shor-Algorithmus hervor.

Das Wesentliche

Das große Bild: Das große Rennen

Stellen Sie sich ein Rennen zwischen zwei Läufern vor: Klassische Computer (die superschnellen, zuverlässigen Marathonläufer, die wir heute nutzen) und Quantencomputer (die mysteriösen, blitzschnellen Sprinter, die nach den seltsamen Regeln der Quantenphysik operieren).

Das Ziel dieses Papiers ist es, eine Punktzahl zu führen für jedes Mal, wenn der Quanten-Sprinter behauptete: „Ich kann dieses spezifische Rätsel schneller lösen als der klassische Läufer!" Der Autor, Ryan LaRose, agiert wie ein Sport-Historiker, der jedes Rennen, jeden Protest und jede Disqualifikation überprüft, um uns genau zu sagen, wo das Rennen heute steht.

Das Papier definiert „Vorteil" einfach: Wer beendet die Aufgabe zuerst? Es spielt keine Rolle, ob die Aufgabe nützlich ist (wie die Heilung einer Krankheit) oder nur ein albernnes Rätsel; die einzige Frage ist die Geschwindigkeit.

---

Teil 1: Die Rennen mit „albernen Rätseln" (Experimenteller Vorteil)

Bisher haben die Quanten-Sprinter versucht, drei spezifische Arten von „albernen" Rennen zu gewinnen. Diese sind noch nicht nützlich für den Bau von Brücken oder das Schreiben von E-Mails; sie wurden speziell dafür entwickelt, für klassische Computer schwer, aber für Quantencomputer einfach zu sein.

1. Das Rennen des Zufälligen Schaltkreis-Sampling (Das „Münzwurf"-Chaos)

• Die Aufgabe: Stellen Sie sich eine Maschine vor, die 53 Münzen gleichzeitig auf völlig zufällige, chaotische Weise wirft. Der Quantencomputer macht dies und zeichnet das Muster von Kopf und Zahl auf. Der klassische Computer muss raten, wie das Muster wäre.
• Der erste Sieg (Google, 2019): Googles Computer „Sycamore" erledigte dies in 200 Sekunden. Sie behaupteten, ein klassischer Supercomputer würde 10.000 Jahre benötigen, um dieselbe Mathematik zu berechnen.
• Der Gegenangriff: Die klassischen Läufer gaben nicht auf. Sie erfanden neue, intelligentere Wege, das Rätsel zu lösen.
  • Analogie: Stellen Sie sich vor, der klassische Läufer erkannte, dass er nicht die ganze Strecke laufen musste; er konnte eine Abkürzung durch einen Tunnel nehmen, den er gefunden hatte.
  • Das Ergebnis: Im Laufe der Zeit wurden klassische Computer schneller. Bis 2024 schaffte es ein klassischer Supercomputer, dieselbe Aufgabe in 86 Sekunden zu erledigen, und schlug damit den Quantencomputer.
• Das Urteil: Googles erster Sieg wurde „widerlegt". Der klassische Läufer holte auf und überholte ihn. Allerdings versuchte Google erneut mit größeren, schwierigeren Rätseln (mehr Münzen, mehr Würfe), und diese neueren Rennen sind noch nicht widerlegt.

2. Das Rennen des Gaußschen Boson-Sampling (Das „Photonen-Flipper")

• Die Aufgabe: Anstelle von Münzen verwendet dieses Rennen Lichtteilchen (Photonen), die durch ein Labyrinth aus Spiegeln hüpfen. Der Quantencomputer schießt sie hinein, und sie landen an bestimmten Stellen. Der klassische Computer muss berechnen, wo sie gelandet sind.
• Die Teilnehmer: Teams aus China (USTC) und Kanada (Xanadu) bauten diese lichtbasierten Rennläufer.
• Der Gegenangriff: Genau wie beim Münzwurf-Rennen fanden klassische Computer „Schlupflöcher". Sie erkannten, dass, wenn die Lichtteilchen nicht perfekt waren (was sie nie sind), die Mathematik einfacher wurde. Sie bauten neue Algorithmen, um das Lichtlabyrinth viel schneller zu simulieren als erwartet.
• Das Urteil: Die meisten dieser Behauptungen wurden „schwach widerlegt". Das bedeutet, dass die klassischen Computer die Quantencomputer auf den größten Rätseln noch nicht geschlagen haben, aber sie sind nah genug dran, dass ein etwas besserer klassischer Computer in naher Zukunft wahrscheinlich könnte.

3. Das Rennen der Quantensimulation (Die „Wettervorhersage")

• Die Aufgabe: Die Simulation, wie sich ein komplexes System (wie ein magnetisches Material) im Laufe der Zeit verändert.
• Die Teilnehmer: IBM und D-Wave.
• Der Gegenangriff: IBM behauptete, ein magnetisches System schneller simuliert zu haben als ein klassischer Computer. Aber innerhalb von zwei Wochen zeigten klassische Forscher, dass sie es auf einem Laptop in wenigen Minuten simulieren konnten.
• Das Urteil: IBMs Behauptung wurde schnell „widerlegt". Der klassische Läufer fand eine viel schnellere Route. Der jüngste Versuch von D-Wave wird noch beobachtet, wird aber wahrscheinlich ähnliche Herausforderungen面临.

---

Teil 2: Die „theoretischen" Rennen (Die mathematischen Beweise)

Manchmal sagen Mathematiker: „Wenn wir einen perfekten Quantencomputer bauen, sollte er dieses Rennen gewinnen." Aber die Geschichte zeigt, dass klassische Mathematiker sehr gut darin sind, neue Tricks zu finden.

• Das Rennen des Empfehlungssystems: Ein Quantenalgorithmus wurde vorgeschlagen, um Filme schneller für Sie zu empfehlen als jeder klassische Computer.
  • Die Wendung: Ein klassischer Mathematiker (Ewin Tang) erkannte: „Hey, wenn wir dem klassischen Computer dieselbe spezielle Datenstruktur geben, die der Quantencomputer verwendet, kann er das Problem genauso schnell lösen!"
  • Das Ergebnis: Der Quantenvorteil verschwand. Dies wird „Dequantisierung" genannt.
• Das Optimierungsrennen: Ähnliche Geschichten passierten mit Algorithmen, die entwickelt wurden, um komplexe Planungsprobleme zu lösen. Der Quantenvorteil wurde behauptet, und dann wurde ein klassischer Algorithmus gefunden, der genauso gut war.

---

Teil 3: Die letzte Grenze (Fehlerkorrektur)

Hier ist die wichtigste Schlussfolgerung des Papiers: Quantencomputer sind zerbrechlich.

• Die Analogie: Stellen Sie sich den Quanten-Sprinter als einen Glasläufer vor. Er ist unglaublich schnell, aber wenn er über einen winzigen Kieselstein (Rauschen) stolpert, zerspringt er. Um einen Marathon zu laufen (wie das Faktorisieren großer Zahlen, um Verschlüsselung zu brechen), müssen sie eine Rüstung tragen.
• Die Rüstung: Diese Rüstung heißt Quantenfehlerkorrektur. Sie verwendet viele physikalische „Glas"-Qubits, um ein stabiles „logisches" Qubit zu erstellen.
• Der aktuelle Status: Wir beginnen gerade, diese Rüstung zu bauen.
  • 2024 kündigte Google einen neuen Chip (Willow) an, bei dem das „logische" Qubit (das gepanzerte) länger überlebte als die einzelnen „physikalischen" Qubits (die Glas-Stücke).
  • Dies ist der „Heilige Gral"-Moment. Es beweist, dass das Hinzufügen weiterer Teile zur Fehlerbehebung das System tatsächlich besser macht, nicht schlechter.
• Die Zukunft: Solange wir diese Rüstung nicht haben, können wir die „nützlichen" Rennen nicht laufen (wie das Brechen von Codes oder das Simulieren neuer Medikamente). Das Papier argumentiert, dass Fehlerkorrektur die letzte Grenze ist, bevor Quantencomputer klassische Computer bei realen Problemen wirklich schlagen können.

Zusammenfassung: Wo stehen wir?

Das Papier kommt zu dem Schluss, dass das Rennen ein Seilziehen ist.

1. Quantencomputer machen einen großen Sprung nach vorne.
2. Klassische Computer werden schlauer, finden Abkürzungen und holen auf (oder überholen sie).
3. Quantencomputer bauen bessere Hardware und versuchen es erneut.

Im Moment befinden wir uns an der Grenze. Wir haben gesehen, wie Quantencomputer bei spezifischen, nutzlosen Rätseln gewinnen, aber klassische Computer haben Wege gefunden, sie bei fast allen davon zu schlagen. Das Papier legt nahe, dass Quantencomputer, um ein nützliches Rennen zu gewinnen, zuerst die Kunst der Fehlerkorrektur beherrschen müssen. Bis dahin wird die Führung weiterhin die Seiten wechseln.

Technische Zusammenfassung

Titel: Eine kurze Geschichte des quantenmechanischen gegenüber dem klassischen Rechenvorteils
Autoren: Ryan LaRose
Quelle: Quantum (Angenommen am 14.05.2026)

Problemstellung

Der Artikel befasst sich mit dem sich wandelnden Landschaftsbild des „quantenmechanischen Rechenvorteils" (auch als Quantenüberlegenheit oder jenseits-klassische Berechnung bezeichnet). Das zentrale Problem besteht darin, die sich verschiebende Grenze zwischen dem, was für klassische Computer und dem, was für Quantencomputer rechnerisch machbar ist, zu definieren und zu verfolgen. Die Autoren definieren den Rechenvorteil spezifisch als eine Verkürzung der Lösungszeit für ein gegebenes Problem, unabhängig von der praktischen Nützlichkeit des Problems. Die Übersichtsarbeit zielt darauf ab, alle experimentellen Behauptungen eines quantenmechanischen Vorteils bis heute zu katalogisieren, zusammen mit den nachfolgenden klassischen Herausforderungen, Widerlegungen und theoretischen Entwicklungen, die den Status dieser Behauptungen verändert haben.

Methodik

Der Artikel wendet eine umfassende Übersetzungsmethodik an, die historische Daten aus der experimentellen Physik, der Informatik und der Komplexitätstheorie synthetisiert.

1. Chronologische Katalogisierung: Die Autoren erstellen eine Zeitleiste aller Experimente, die einen quantenmechanischen Vorteil beanspruchen, und kategorisieren sie nach Problemtyp: Random Circuit Sampling (RCS), Gaussian Boson Sampling (GBS) und Quantensimulation (QSim).
2. Statusklassifizierung: Jedem Experiment wird ein Status basierend auf nachfolgender Literatur zugewiesen:
   • Nicht widerlegt: Kein klassischer Algorithmus hat das Experiment bisher schneller simuliert.
   • Herausgefordert: Klassische Algorithmen haben die Simulationszeiten verbessert oder spezifische experimentelle Aspekte in Frage gestellt.
   • Schwach widerlegt: Es existiert ein klassischer Algorithmus, der das Experiment wahrscheinlich auf zukünftiger klassischer Hardware simulieren könnte.
   • Widerlegt: Ein klassischer Computer hat das Experiment schneller simuliert als das Quantengerät.
3. Theoretische Analyse: Die Übersichtsarbeit untersucht den theoretischen Vorteil in spezifischen Domänen (approximative Optimierung, Empfehlungssysteme, Quantenchemie), um hervorzuheben, wie „Dequantisierung" (die Entwicklung klassischer Algorithmen, die von quantenmechanischen inspiriert sind) theoretische Beschleunigungen untergraben kann.
4. Fehlerkorrektur-Review: Der Artikel verfolgt die Geschichte von Quantenfehlerkorrektur-Experimenten (QEC) und identifiziert sie als notwendige „letzte Grenze" für das Erreichen eines Vorteils in Algorithmen wie Shors Algorithmus, die fehlertolerante Systeme erfordern.

Hauptbeiträge

• Umfassende Status-Tabelle: Der Artikel stellt Tabelle 1 bereit, eine chronologische Liste aller Behauptungen eines quantenmechanischen Vorteils (von Googles Sycamore 2019 bis zur Simulation von D-Wave 2024) und deren aktuellen Stand bezüglich klassischer Widerlegungen.
• Detaillierte Darstellung von Herausforderungen: Er dokumentiert den „Wettrüsten" zwischen Quantenexperimenten und klassischer Simulation. Bemerkenswerte Beiträge umfassen die Verfolgung von Optimierungen der Tensor-Netzwerk-Kontraktion (z. B. „big head"-Algorithmen, Hypergraph-Partitionierung) und Strategien zur Ausnutzung von Rauschen, die die geschätzten klassischen Laufzeiten für bestimmte Experimente von tausenden Jahren auf Stunden oder Sekunden reduziert haben.
• Klärung von Metriken: Die Übersichtsarbeit analysiert kritisch die Cross-Entropy-Benchmark (XEB)-Fidelität, diskutiert Lücken, in denen klassische Algorithmen hohe XEB-Werte „vortäuschen" können, ohne den gesamten Schaltkreis zu simulieren, und unterscheidet zwischen schwachen und starken Widerlegungen.
• Theoretische Dequantisierung: Der Artikel erläutert, wie theoretische Vorteile bei der Max-E3LIN2-Optimierung und in Empfehlungssystemen verloren gingen, als klassische Algorithmen (z. B. von Barak et al. und Ewin Tang) unter ähnlichen Eingabeannahmen die quantenmechanische Leistung erreichten oder übertrafen.
• QEC-Fortschritte: Tabelle 2 und Abschnitt 4 fassen den raschen Fortschritt von Fehlerkorrektur-Experimenten zusammen und vermerken den Übergang von einfachen Wiederholungs-Codes zu Oberflächen-Codes mit Distanzen bis zu 7 sowie den jüngsten Meilenstein von Googles Experiment 2024, bei dem die logischen Fehlerraten unter die Schwelle der physikalischen Fehlerraten fielen.

Ergebnisse

• Experimentelle Volatilität: Die Übersichtsarbeit stellt fest, dass fast jede große experimentelle Behauptung eines quantenmechanischen Vorteils erheblichen Herausforderungen begegnet ist.
  • Googles RCS 2019 (53 Qubits): Ursprünglich wurde eine klassische Laufzeit von 10.000 Jahren behauptet. Dies wurde durch Tensor-Netzwerk-Optimierungen herausgefordert und schließlich 2024 (Zhao et al.) stark widerlegt, indem 1.432 GPUs verwendet wurden, um das Experiment in 86,4 Sekunden zu simulieren.
  • USTC GBS (Jiuzhang 1.0, 2.0, 3.0): Behauptungen eines Vorteils wurden von Oh et al. (2023) schwach widerlegt, die Tensor-Netzwerke nutzten, um diese Experimente signifikant schneller als die Quantengeräte zu simulieren, obwohl die Experimente im „starken" Sinne für die größten Instanzen weiterhin nicht widerlegt sind.
  • IBM QSim (2023): Eine Behauptung eines Vorteils bei der Simulation des Transversalfeld-Ising-Modells wurde innerhalb weniger Wochen durch mehrere klassische Ansätze (Tensor-Netzwerke, Belief Propagation, Clifford-Störungstheorie), die auf Laptops oder einzelnen GPUs liefen, widerlegt.
  • D-Wave (2024): Eine jüngste Behauptung eines Vorteils in der Quantensimulation bleibt zum Zeitpunkt der Abfassung nicht widerlegt, obwohl die Autoren anmerken, dass sie wahrscheinlich ein Ziel für zukünftige klassische Herausforderungen sein wird.
• Theoretische Verschiebungen: Der Artikel zeigt, dass der theoretische Vorteil nicht statisch ist. Algorithmen für Empfehlungssysteme und approximative Optimierung (QAOA) haben ihre quantenmechanischen Vorteile durch „dequantisierte" klassische Algorithmen verloren, die ähnliche Datenstrukturen oder Approximationstechniken nutzen.
• Fehlerkorrektur-Meilensteine: Während fehlertolerantes Quantencomputing noch nicht realisiert ist, hebt die Übersichtsarbeit hervor, dass logische Qubits nun Lebensdauern erreichen, die länger sind als ihre physikalischen Komponenten, und dass die Fehlerraten sich der Schwelle für skalierbare Fehlertoleranz nähern.

Bedeutung und Behauptungen

Der Artikel behauptet, dass die Geschichte des quantenmechanischen Vorteils ein dynamisches, sich verschiebendes Ziel und kein statisches Errungenschaft ist.

• Sich bewegendes Ziel: Die Autoren betonen, dass der Rechenvorteil relativ zu den zum spezifischen Zeitpunkt bestbekannten klassischen Algorithmen und der Hardware definiert ist. Da sich klassische Algorithmen verbessern (oft inspiriert durch quantenmechanische Erkenntnisse), verschiebt sich die Grenze des Vorteils zurück zu klassischen Computern.
• Verifikationskrise: Ein erheblicher Teil des Artikels hebt die Schwierigkeit hervor, einen quantenmechanischen Vorteil zu verifizieren. Viele aktuelle Experimente (wie RCS) sind klassisch schwer zu verifizieren, was ein Paradoxon schafft, bei dem die Behauptung eines Vorteils auf klassischen Berechnungen beruht, die selbst unlösbar sind. Der Artikel weist auf „peaked circuit sampling" und „Hidden Code Sampling" als vorgeschlagene zukünftige Richtungen für effizient verifizierbare Vorteile hin.
• Die Rolle der Fehlerkorrektur: Die Übersichtsarbeit postuliert, dass für Algorithmen mit nachgewiesenen exponentiellen Beschleunigungen (wie Shors Algorithmus) die „letzte Grenze" nicht nur die Qubit-Anzahl ist, sondern die Quantenfehlerkorrektur. Ohne Fehlertoleranz kann der Overhead der Fehlerkorrektur jeden theoretischen Vorteil zunichtemachen.
• Bescheidene Perspektive: Die Autoren schließen daraus, dass ein quantenmechanischer Vorteil zwar für spezifische Probleme wahrscheinlich ist, das Feld sich derzeit jedoch an der „Grenze" zwischen quantenmechanischer und klassischer Dominanz befindet. Sie warnen davor, einen dauerhaften Vorteil vorauszusetzen, und merken an, dass sich der Status wahrscheinlich weiter verschieben wird, während sich sowohl klassische als auch quantenmechanische Technologien entwickeln. Der Artikel dient als historische Aufzeichnung, um Forscher zu neuen Problemformulierungen zu bewegen, die klassisch schwer, quantenmechanisch einfach, effizient verifizierbar und wissenschaftlich nützlich sind.