Generative Quantum Search for Combinatorial Optimization: Learning Shallow Quantum Samplers for Classically Refined Solution Subspaces

Technisches Resümee: Generatives Quanten-Suchen für kombinatorische Optimierung

Problemstellung
Diese Forschungsarbeit untersucht, ob flache Quanten-Sampler die Leistung klassischer Sampler bei der kombinatorischen Optimierung übertreffen können, indem sie eine höhere Wahrscheinlichkeitsmasse innerhalb eines „klassischen Erholungseinzugsgebiets“ (classical recovery basin) platzieren. Die Studie adaptiert die Architektur des Generative Quantum Eigensolver + Quantum-Selected Configuration Interaction (GQE+QSCI), die ursprünglich für die Quantenchemie entwickelt wurde, auf den Bereich der Graphoptimierung (speziell das Maximum Weighted Independent Set, MWIS). Die Kernhypothese ist, dass ein Quanten-Sampler eine Verteilung von Kandidatenlösungen generieren kann, die – wenn sie durch einen klassischen Reparatur- und Expansionsalgorithmus verfeinert werden – eine höhere Erfolgsrate erzielen als klassische Sampler.

Methodik
Der Autor schlägt das GQO+QSS (Generative Quantum Optimization + Quantum-Selected Search) Framework vor, das einem vierstufigen Prozess folgt:

1. Generative Policy: Ein Machine-Learning-Modell (graph-konditionierte Policy) generiert Quantenschaltkreis-Programme (z. B. QAOA-Parameter).
2. Quanten-Sampling: Die Schaltkreise werden auf einem Simulator oder einer QPU (Piast-Q) ausgeführt, um Bitstrings (Kandidatenlösungen) zu erzeugen.
3. Klassische Reparatur: Eine problemspezifische Reparaturfunktion korrigiert unzulässige Lösungen, gefolgt von einer lokalen Expansion (z. B. $r$-Flip-Nachbarschaft), um einen eingeschränkten Suchraum zu erstellen.
4. Eingeschränkter Solver: Ein exakter klassischer Solver findet die optimale Lösung innerhalb dieses eingeschränkten Subraums.

Zentrale theoretische Formulierung
Die Arbeit formalisiert die Frage nach dem „Quantenvorteil“ mittels der Erholungseinzugsgebiets-Masse ($p_r$):
$$p_r(q_\theta, G) = \Pr_{x \sim q_\theta} [x \in A_r(G)]$$
wobei $A_r(G)$ die Menge der Zustände ist, die nach Reparatur und $r$-Flip-Expansion das globale Optimum enthalten. Die Erfolgswahrscheinlichkeit mit $B$ Shots ist $P_{success} = 1 - (1 - p_r)^B$. Die Studie postuliert, dass die kritische Metrik nicht die Größe des gesampelten Subraums im Verhältnis zum Gesamtraum ($|S_Q|/2^n$) ist, sondern die Wahrscheinlichkeitsmasse $p_r$, die der Sampler in das Erholungsgebiet legt.

Experimentelles Protokoll

• Datensätze: 150 MWIS-Instanzen, deren Grundwahrheiten mittels CBC + Brute-Force-Verifizierung zertifiziert wurden.
• Baselines: Neun Sampler wurden verglichen, darunter Uniform Random, Greedy, Simulated Annealing (SA), Tabu Search, Multi-Start Local Search, Metropolis, Warm-Start QAOA, Oracle QAOA (Best-of-50 Konfigurationen) und eine passend gelernte klassische Policy.
• Beschränkungen: Ein vorregistriertes, eingefrorenes Protokoll mit einem festen Budget von 200 Shots pro Sampler.
• Hardware: Die Experimente umfassten Simulationen sowie die Ausführung auf dem Piast-Q Trapped-Ion-Prozessor (20 Qubits).

Kernergebnisse

1. Dominanz der Klassik: Tabu Search und Simulated Annealing (SA) übertrafen alle Quanten- und gelernten klassischen Sampler über alle getesteten Problemgrößen ($n=16$ bis $n=28$) hinweg signifikant. Tabu Search erreichte eine Erholungseinzugsgebiets-Masse ($p_r$) von 0,822 bei $n=16$ bis 0,944 bei $n=18$, mit Werten von 0,878 bei $n=20$, 0,943 bei $n=24$ und 0,901 bei $n=28$. SA lag in diesen Größenordnungen zwischen 0,088 und 0,428.
2. Unterleistung der Quanten-Systeme: Alle Quanten-Sampler (Warm-Start QAOA, Oracle QAOA und generative Policies) verloren gegen SA und Tabu Search bei jeder Problemgröße unter dem fairen, vorregistrierten Protokoll.
3. Das „Oracle“-Artefakt: Frühere positive Ergebnisse, die zeigten, dass QAOA SA übertrifft, wurden als Artefakte der pro Instanz erfolgenden Konfigurationswahl identifiziert (eine „Oracle“-Obergrenze). Bei der Evaluierung mit zufälligen Konfigurationen (eine einsetzbare Methode) erreichte Oracle QAOA eine $p_r$ von 0,014 bei $n=28$, weit unter den 0,088 von SA.
4. Parität der gelernten Klassik: Eine gelernte klassische Policy (140K Parameter) erreichte eine Leistung, die mit Oracle QAOA vergleichbar war ($p_r = 0,005–0,101$ vs. $0,014–0,113$), was darauf hindeutet, dass der Quantenschaltkreis in diesem Setting keinen strukturellen Vorteil gegenüber einem passenden klassischen Modell bietet.
5. Hardware-Robustheit: Experimente auf Piast-Q zeigten eine 93,4%ige Konsistenz zwischen QPU- und Simulator-Samples, was die Hardware-Robustheit bestätigt, aber keinen Quantenvorteil bei der Optimierungsqualität offenbarte.
6. Erholungsübergang: Die Studie kartierte einen „Recovery Transition“, bei dem die klassische Reparatur für $n \le 16$ ausreichend ist, aber für $n \ge 20$ mit 2-Flip-Expansion zu scheitern beginnt. Selbst in diesem Übergangsregime behielten starke klassische Baselines (SA, Tabu) eine überlegene Leistung bei.

Bedeutung und Behauptungen
Die Arbeit präsentiert sich als eine Falsifikationsstudie. Ihre primäre Behauptung ist, dass unter strenger, vorregistrierter Evaluierung mit passenden gelernten Baselines flache, von QAOA abgeleitete Vorschlagsverteilungen (proposal distributions) keine passenden klassischen Vorschlagsmodelle übertreffen können, um die klassischen Erholungseinzugsgebiete für MWIS zu erfassen.

• Kein Quantenvorteil: Der Autor behauptet explizit, dass kein Quantenvorteil für die GQO+QSS-Architektur in den getesteten Regimen besteht.
• Widerlegung früherer Behauptungen: Die Studie führt frühere positive Ergebnisse auf den „Oracle“-Effekt der Auswahl der besten Konfiguration pro Instanz zurück, was jedoch keine einsetzbare Methode darstellt.
• Metriken-Korrektur: Die Arbeit argumentiert, dass die „Subspace Fraction“ ($|S_Q|/2^n$) eine tautologische Metrik unter festen Shot-Budgets ist und dass die Erholungseinzugsgebiets-Masse ($p_r$) die wissenschaftlich korrekte Größe zur Messung ist.
• Zukünftige Richtung: Der Autor legt nahe, dass für das Quanten-Sampling ein Wert entstehen muss, wenn es konsistent mehr Masse in das Erholungsgebiet legt als starke klassische Baselines (wie SA) in Regimen, in denen die klassische Reparatur versagt ($n \ge 55$) – eine Herausforderung, der aktuelle flache Schaltkreise bisher nicht gerecht wurden.

Die Arbeit kommt zu dem Schluss, dass die GQO+QSS-Architektur zwar ein valides Framework für hybride Optimierung ist, aktuelle flache Quanten-Sampler jedoch keinen strukturellen Vorteil gegenüber starken klassischen stochastischen Suchmethoden für die spezifische Aufgabe der MWIS-Erholung bieten.