Cross-Platform Benchmarking of Near-Term Quantum Optimisation Algorithms

Die Studie stellt einen anwendungsorientierten Benchmarking-Rahmen für nahe-zukünftige Quantenoptimierungsalgorithmen vor, der auf einem dichten QUBO-Problem aus der Materialwissenschaft basiert und zeigt, dass die Leistung von VQE und Quantum Annealing auf kommerziellen Geräten durch Verbindungsbeschränkungen, Rauschen und klassische Overheads auf bis zu 72 Variablen begrenzt ist.

Das Wesentliche

🧩 Der große Quanten-Wettbewerb: Wer findet den besten Weg?

Stellen Sie sich vor, Sie haben einen riesigen, verworrenen Labyrinth aus Straßen. Ihr Ziel ist es, eine bestimmte Anzahl von Häusern (Städten) zu schließen, aber so, dass die verbleibenden offenen Straßen so kurz und effizient wie möglich sind. Das ist im Grunde das Problem, das die Forscher in diesem Papier gelöst haben: Sie wollten herausfinden, wie man eine spezielle Art von Graphit-Struktur (Graphen) mit Löchern so verändert, dass sie energetisch am stabilsten ist.

Das ist ein klassisches Optimierungsproblem: Es gibt unzählige Möglichkeiten, die Löcher zu setzen, aber nur eine (oder wenige) ist die absolut beste.

Um zu testen, ob Quantencomputer wirklich besser sind als normale Computer, haben die Autoren einen großen Wettkampf veranstaltet. Sie haben verschiedene "Läufer" (Algorithmen) auf verschiedenen "Strecken" (Hardware) gegeneinander antreten lassen.

🏃‍♂️ Die Läufer (Die Algorithmen)

1. Der brute-force-Läufer (Klassisch):

   • Wie er läuft: Er probiert jede einzelne mögliche Kombination aus. Er geht jeden Weg im Labyrinth ab, egal wie lange es dauert.
   • Ergebnis: Er findet immer die perfekte Lösung, aber er ist extrem langsam. Bei großen Problemen bricht er zusammen, weil es einfach zu viele Wege gibt.

2. Der Simulated-Annealing-Läufer (Klassisch, aber schlau):

   • Wie er läuft: Stellen Sie sich vor, Sie schmelzen Metall und lassen es langsam abkühlen. Anfangs macht er viele zufällige, chaotische Schritte (wie heiße Atome), um nicht in einer schlechten Lösung stecken zu bleiben. Je kälter es wird, desto vorsichtiger wird er und sucht nach dem tiefsten Tal im Labyrinth.
   • Ergebnis: Er ist der Schnellste und Effizienteste. Er findet fast immer die beste Lösung und skaliert hervorragend, selbst bei riesigen Problemen.

3. Der VQE-Läufer (Quanten-Gate-basiert):

   • Wie er läuft: Das ist wie ein Musiker, der eine Melodie (eine Lösung) spielt und sie immer wieder leicht verstimmt, bis sie perfekt klingt. Er nutzt einen Quantencomputer, der wie ein sehr empfindliches Instrument ist.
   • Das Problem: Der Quantencomputer ist "laut" (Rauschen). Der Musiker wird oft von Störgeräuschen abgelenkt und vergisst die Melodie. Außerdem dauert das Einstellen der Instrumente (die Berechnungen auf dem klassischen Computer) ewig.
   • Ergebnis: Bei kleinen Problemen okay, aber bei großen Problemen (über 50 Variablen) verliert er den Faden und findet keine gute Lösung mehr.

4. Der Quantum-Annealing-Läufer (Quanten-Annealer):

   • Wie er läuft: Stellen Sie sich einen Ball vor, der einen Berg hinunterrollt. Der Quanten-Annealer nutzt Quanteneffekte, damit der Ball nicht in kleinen Tälern (lokalen Minima) hängen bleibt, sondern durch den Berg "tunneln" kann, um direkt ins tiefste Tal zu gelangen.
   • Das Problem: Der Berg ist nicht perfekt geformt. Um ihn zu nutzen, muss man den Ball erst auf eine sehr spezielle, krumme Rampe legen (das nennt man "Embedding"). Dieser Aufbau dauert lange und kostet Zeit.
   • Ergebnis: Er ist schneller als der VQE-Läufer, aber langsamer als der klassische Simulated-Annealing-Läufer. Er kann Probleme bis zu einer gewissen Größe lösen, aber die "Rampe" wird bei sehr großen Problemen zum Flaschenhals.

🏆 Das Ergebnis des Wettbewerbs

Die Forscher haben Probleme mit bis zu 72 Variablen (Städten) getestet. Hier ist, was sie herausfanden:

• Der Klassische Gewinner: Der Simulated Annealing-Algorithmus (auf einem normalen Supercomputer) war der klare Sieger. Er war schneller, genauer und konnte Probleme lösen, die für die Quantencomputer zu groß waren (bis zu 388 Variablen!).
• Die Quanten-Probleme:
  • Rauschen: Die Quantencomputer sind noch nicht perfekt. Wie ein Radio mit schlechtem Empfang stören sie die Berechnungen.
  • Verbindungen: Die Quanten-Chips sind nicht so vernetzt wie ein perfektes Labyrinth. Um komplexe Probleme zu lösen, müssen die Läufer Umwege nehmen (SWAP-Gates), was sie verlangsamt.
  • Zeit: Der Zeitverlust durch das "Aufbauen" der Quanten-Experimente (Encoding/Embedding) war oft größer als die eigentliche Rechenzeit auf dem Quantenchip.

💡 Die wichtigste Erkenntnis

Die Studie zeigt, dass wir noch nicht an dem Punkt sind, an dem Quantencomputer klassische Computer in dieser Art von Aufgaben komplett ablösen. Der klassische "Simulated Annealing"-Läufer ist derzeit der König.

Aber: Es ist kein Grund zur Verzweiflung!
Die Forscher haben einen neuen Maßstab (Benchmark) entwickelt. Sie haben gezeigt, wie man diese Wettkämpfe fair und transparent durchführt. Sie haben gelernt, wie man die Quantencomputer besser "einstellt" (z. B. durch kleine Strafen für falsche Lösungen und das Entfernen von schlechten Ergebnissen im Nachhinein).

Zusammengefasst:
Stellen Sie sich vor, wir bauen gerade die ersten echten Rennwagen (Quantencomputer). Derzeit ist ein sehr schneller, aber einfacher Fahrrad (klassischer Algorithmus) noch schneller auf der Strecke. Aber die Ingenieure (die Forscher) haben jetzt eine perfekte Teststrecke gebaut, um zu sehen, wo die Rennwagen hängen bleiben und wie man sie in Zukunft schneller macht. Der Weg zur "Quanten-Überlegenheit" ist noch lang, aber wir wissen jetzt genau, wo wir ansetzen müssen.

Technische Zusammenfassung

1. Problemstellung und Zielsetzung

Das Papier adressiert die Notwendigkeit eines rigorosen, fairen und transparenten Benchmarkings für nahe-zukünftige (near-term) Quantenoptimierungsalgorithmen. Der Fokus liegt auf der Bewertung, ob Quantencomputer einen Vorteil gegenüber klassischen Computern bei kombinatorischen Optimierungsproblemen bieten können.

Als Testfall wurde ein Problem aus der Materialwissenschaft gewählt: Die Suche nach der energieärmsten Konfiguration von defekten Graphen-Strukturen.

• Modellierung: Das Problem wird als Densest k-Subgraph (DkS) Problem formuliert, bei dem aus einem hexagonalen Graphen-Netzwerk (Graphen) eine bestimmte Anzahl von Atomen (Leerstellen/Vakanzien) entfernt werden muss, um die verbleibenden Kohlenstoff-Kohlenstoff-Bindungen zu maximieren (d.h. die Energie zu minimieren).
• Formulierung: Das Problem wird in ein Quadratic Unconstrained Binary Optimization (QUBO) Problem übersetzt. Dies ist ein NP-hartes Problem, das für klassische Computer im Worst-Case unlösbar ist, aber für Quantencomputer potenzielle Beschleunigung bietet.
• Besonderheit: Es handelt sich um ein hochdichtes QUBO (vollständig verbunden), was eine große Herausforderung für die Hardware-Konnektivität darstellt.

2. Methodik

Die Autoren entwickelten ein plattformübergreifendes Benchmarking-Framework, das verschiedene Algorithmen und Hardware-Plattformen unter gleichen Bedingungen vergleicht.

Verglichene Algorithmen:

1. Klassische Methoden:
   • Brute Force: Exakte Lösung (als Referenz).
   • Simulated Annealing (SA): Ein heuristischer probabilistischer Algorithmus.
   • Random Sampling: Zufällige Suche als Baseline.
2. Quantenmethoden:
   • Variational Quantum Eigensolver (VQE): Ein hybrides Quanten-Klassisches Verfahren, ausgeführt auf einem gate-basierten Quantenprozessor (IBM ibm_fez, 156 Qubits) und einem noise-freien State-Vector-Simulator.
   • Quantum Annealing (QA): Ausgeführt auf einem D-Wave Advantage 6.4 System (5612 physikalische Qubits).

Wichtige methodische Aspekte:

• Post-Selection: Da die QUBO-Formulierung die Randbedingung (feste Anzahl an Vakanzien) nur über Strafterme ($\lambda$) erzwingt, wurden Lösungen, die diese Bedingung verletzen, nachträglich klassisch gefiltert. Es wurde gezeigt, dass kleine Strafkoeffizienten $\lambda$ in Kombination mit Post-Selection bessere Ergebnisse liefern als große $\lambda$-Werte, da diese den Energiebereich des QUBO unnötig vergrößern.
• Metriken: Die Leistung wurde nicht nur nach der Lösungsqualität, sondern auch nach der Ressourcennutzung bewertet:
  • Optimal Solution Probability ($P_s$): Wahrscheinlichkeit, den Grundzustand zu finden.
  • Approximation Ratio (AR): Verhältnis der gefundenen Energie zum theoretischen Optimum.
  • User Runtime: Gesamte Zeit vom Start bis zum Ergebnis (inkl. Encoding, Latenz, Device-Zeit).
  • QPU Time: Reine Zeit auf dem Quantenprozessor.
• Embedding: Für das D-Wave System wurden zwei Embedding-Techniken verglichen: Minor Embedding (Standard-Heuristik) und Clique Embedding (optimiert für vollständig verbundene Graphen).

3. Wichtige Beiträge

Das Papier leistet mehrere signifikante Beiträge zur aktuellen Forschung:

• Einheitliches Framework: Einführung eines fairen Benchmarking-Ansatzes, der gate-basierte VQAs, Quanten-Annealing und klassische Algorithmen auf denselben QUBO-Instanzen vergleicht.
• Skalierungsanalyse: Untersuchung des Verhaltens der Algorithmen bei steigender Problemgröße (bis zu 72 Variablen für Quantenmethoden und bis zu 388 für klassische SA).
• Technische Einblicke:
  • Aufdeckung des großen Overheads durch das Embedding bei Quanten-Annealing und wie effizientere Techniken (Clique Embedding) dies reduzieren können.
  • Analyse der Auswirkungen von Rauschen und Dekohärenz auf die Konvergenz von VQE.
  • Demonstration, dass klassische Berechnungs-Overheads (Kompilierung, Optimierung) oft den größten Teil der Gesamtzeit bei hybriden Algorithmen ausmachen, nicht die reine QPU-Zeit.
• Ergebnisse zu Hyperparametern: Systematische Suche nach optimalen Parametern (z.B. $\lambda$, Kettenstärke, Annealing-Zeit) für jede Plattform.

4. Ergebnisse

Leistung bei kleinen Problemen (18 Variablen):

• Simulated Annealing (SA) war der klare Gewinner in Bezug auf Lösungsqualität ($P_s \approx 0.99$) und Laufzeit.
• Quantum Annealing (QA) und VQE zeigten deutlich niedrigere Erfolgswahrscheinlichkeiten ($P_s \approx 0.18 - 0.39$ nach Post-Selection).
• VQE auf echter Hardware litt unter Rauschen, was zu einer schlechteren Konvergenz und höheren Varianz führte als auf dem Simulator.

Skalierung und Limitierungen:

• Klassisch: Simulated Annealing skalierte polynomial und konnte Probleme mit bis zu 388 Variablen lösen.
• Quantum Annealing:
  • Mit Minor Embedding konnten Probleme bis zu 72 Variablen gelöst werden, jedoch mit stark abnehmender Erfolgswahrscheinlichkeit und stark wachsendem Embedding-Overhead.
  • Mit Clique Embedding war die Laufzeit stabiler, aber die maximale lösbare Größe lag bei ca. 50 Variablen, bevor die Erfolgswahrscheinlichkeit gegen Null ging.
  • Es gibt Hinweise auf eine polynomiale Skalierung der Laufzeit bei Verwendung von Clique Embedding, was theoretisch für bestimmte Phasenübergänge erwartet wird.
• VQE:
  • Die Skalierung war stark eingeschränkt. Ab 50 Variablen konnte keine Konvergenz mehr erreicht werden.
  • Bei 72 Variablen wurden suboptimale Lösungen gefunden, aber die Konvergenzkriterien wurden oft nicht innerhalb der maximalen Iterationen erfüllt.
  • Die Laufzeit auf der IBM-Hardware war extrem hoch (Größenordnung von Stunden pro Experiment), hauptsächlich aufgrund klassischer Overheads (Kompilierung, Optimierungsschleifen).

Schlussfolgerungen zur Leistung:
Aktuelle Quantengeräte (Stand Januar 2025/2026) können bei diesem spezifischen dichten QUBO-Problem noch keinen Vorteil gegenüber klassischen Heuristiken wie Simulated Annealing bieten. Die Hauptlimitierungen sind:

1. Hardware-Konnektivität: Erfordert aufwendiges Embedding, was Qubits verschwendet und Kettenbrüche verursacht.
2. Rauschen: Führt zu falschen Minima und schlechter Konvergenz bei VQE.
3. Klassische Overheads: Die Zeit für das Vorbereiten und Optimieren der Quantenschaltkreise dominiert oft die reine Quantenberechnungszeit.

5. Bedeutung und Ausblick

Die Studie unterstreicht, dass der Weg zum „Quantum Advantage" bei Optimierungsproblemen noch weit ist. Sie liefert ein wichtiges Framework für zukünftige Vergleiche, das über reine Hardware-Metriken hinausgeht und den gesamten „End-to-End"-Prozess betrachtet.

• Für die Hardware: Die Ergebnisse zeigen, dass Verbesserungen der Qubit-Konnektivität (z.B. von Heavy-Hex zu Square-Lattice bei neuen IBM-Prozessoren) und Reduzierung von Fehlerraten kritisch sind.
• Für Algorithmen: Es werden zukünftige Forschungsrichtungen aufgezeigt, wie z.B. „Warm Starts" (Start mit klassischen Lösungen), Transferlernen von Parametern, fortgeschrittene Fehlerminderung und die Nutzung von CVaR (Conditional Value at Risk) zur Verbesserung der Konvergenz.
• Allgemeine Relevanz: Obwohl das Testproblem spezifisch ist, ist das entwickelte Benchmarking-Framework auf allgemeine Optimierungsprobleme übertragbar und hilft, den Fortschritt von Quantenhardware und Algorithmen realistisch zu bewerten.

Zusammenfassend stellt das Paper fest, dass klassische Heuristiken derzeit überlegen sind, aber das vorgestellte Framework essenziell ist, um zukünftige Fortschritte in der Quantenhardware und Algorithmenentwicklung objektiv zu messen.