Quantum circuit evolutionary framework applied on set partitioning problem

Dieser Artikel schlägt einen evolutionären Quantenschaltkreis-Rahmen vor, der eine variable Topologie und einen pseudo-counterdiabatischen evolutionären Term nutzt, um Set-Partitionierungsprobleme effektiv zu lösen, indem er Konvergenzstagnation überwindet und die Notwendigkeit klassischer Optimierer eliminiert.

Das Wesentliche

Stellen Sie sich vor, Sie versuchen, ein riesiges, komplexes Puzzle zu lösen. Das Ziel ist es, eine Gruppe von Menschen (wie Flugzeugbesatzungen) in Teams aufzuteilen, sodass jeder Flug genau einmal abgedeckt wird, ohne Überschneidungen oder fehlende Schichten, bei gleichzeitiger Minimierung der Kosten. In der Welt der Mathematik wird dies als Set-Partitioning-Problem bezeichnet. Es ist eine berüchtigt schwierige Herausforderung, die exponentiell schwerer wird, je mehr Personen und Flüge hinzukommen.

Dieser Artikel stellt eine neue Methode vor, mit der Quantencomputer dieses Puzzle angehen können. Anstatt das Standardrezept zu verwenden, dem die meisten Quantenalgorithmen folgen, entwickelten die Autoren ein Framework, das es dem Computer ermöglicht, während der Arbeit sein eigenes Rezept zu entwickeln.

Hier ist eine Aufschlüsselung ihres Ansatzes mit einfachen Analogien:

1. Der alte Weg: Der „feste Bauplan" (VQE)

Die meisten aktuellen Quantenalgorithmen, wie der Variational Quantum Eigensolver (VQE), funktionieren wie ein Koch, der einem strengen, unveränderlichen Kochbuch folgt.

• Das Setup: Die Struktur des „Schaltkreises" (die Schritte, die der Computer ausführt) ist festgelegt. Sie können keine Zutaten hinzufügen oder entfernen; Sie können nur die Mengen (die Parameter) anpassen.
• Das Problem: Wenn das Puzzle größer wird, gerät der Koch oft in ein „flaches Tal". Stellen Sie sich vor, Sie gehen durch ein nebliges Feld, in dem der Boden völlig flach ist. Egal, in welche Richtung Sie treten, Sie gehen weder bergauf noch bergab. Sie können nicht erkennen, ob Sie sich der Lösung nähern oder nicht. In der Quantenphysik nennt man dies ein Barren Plateau (leere Hochebene). Der Computer hört auf zu lernen, weil er keine Richtung zur Verbesserung finden kann.

2. Der neue Weg: Der „entwickelnde Bildhauer" (QCE)

Die Autoren schlagen ein Framework namens Quantum Circuit Evolution (QCE) vor. Anstatt eines festen Rezepts stellen Sie sich einen Bildhauer vor, der mit einem kleinen Lehmklumpen beginnt und in jedem Schritt Lehm hinzufügen, entfernen oder umformen darf.

• Funktionsweise: Der Computer beginnt mit einem sehr einfachen Schaltkreis (vielleicht nur ein Gatter). Anschließend erstellt er eine „Familie" leicht unterschiedlicher Versionen seiner selbst, indem er die Struktur zufällig mutiert (einen neuen Schritt hinzufügen, einen alten löschen oder eine Verbindung ändern).
• Die Selektion: Er testet alle diese Versionen. Diejenige, die das Puzzle am besten löst, überlebt und wird zum „Elternteil" für die nächste Runde. Die anderen werden verworfen.
• Der Vorteil: Da sich die Struktur selbst verändert, steckt der Computer nicht in einem flachen Tal fest. Er kann seinen gesamten Ansatz umgestalten, um einen Weg aus dem Nebel zu finden.

3. Die zwei getesteten Strategien

Der Artikel testete zwei spezifische Varianten dieses Ansatzes des „entwickelnden Bildhauers":

• Strategie A: Der reine Evolutionist (Ansatz-Free)
  Diese Version startet mit fast nichts und lässt den Computer die Struktur vollständig durch Versuch und Irrtum herausfinden, ähnlich wie die natürliche Selektion. Sie rät nicht, wie die Lösung aussehen sollte; sie entwickelt sich einfach weiter, bis sie funktioniert.

• Strategie B: Der physikinspirierte Evolutionist (Pseudo-Counterdiabatic)
  Dies ist der „Star" des Artikels. Die Autoren gaben dem Computer einen Hinweis basierend auf der Physik des Problems. Sie fügten dem Schaltkreis einen speziellen „Schubs" hinzu (ein Pseudo-Counterdiabatic-Term).

  • Die Analogie: Stellen Sie sich vor, Sie versuchen, eine schwere Kiste einen Hügel hinaufzuschieben. Der „reine Evolutionist" schiebt einfach zufällig herum, bis er einen Weg nach oben findet. Die „physikinspirierte" Version kennt die Form des Hügels und fügt eine spezifische Gegenkraft hinzu, um die Kiste reibungslos in Bewegung zu halten und zu verhindern, dass sie in flachen Stellen stecken bleibt.
  • Das Ergebnis: Diese Strategie schnitt am besten ab. Sie vermied das „Steckenbleiben" (Konvergenzstagnation) deutlich besser als die anderen Methoden, selbst wenn das Puzzle sehr groß war.

4. Die Ergebnisse

Die Autoren testeten diese Methoden auf einem Simulator (ein Computerprogramm, das wie ein Quantencomputer funktioniert) mit 35 verschiedenen Versionen des Flugplanungs-Puzzles.

• Der Gewinner: Die Methode Physikinspirierte Evolution (APCD-QCE) fand konsistent bessere Lösungen als die Standardmethode mit „festem Bauplan" (VQE).
• Der Stolperstein: Obwohl die neuen Methoden viel besser waren, hatten sie immer noch Schwierigkeiten, wenn das Puzzle extrem groß wurde (etwa 20 Qubits). Selbst der entwickelnde Bildhauer hatte manchmal nicht genug Zeit oder Komplexität, um die perfekte Lösung zu finden.
• Rauschen: Sie testeten auch, was passiert, wenn der Computer Fehler macht (Simulation von echtem „Rauschen"). Die neuen Methoden hielten sich recht gut, obwohl die Leistung erwartungsgemäß nachließ.

Das Fazit

Der Artikel behauptet, dass wir durch die Erlaubnis an einen Quantenschaltkreis, seine eigene Form zu verändern, anstatt nur seine Einstellungen zu justieren, die „Sackgassen" vermeiden können, die aktuelle Algorithmen gefangen halten. Insbesondere das Hinzufügen eines physikbasierten „Schubs" zu diesem Evolutionsprozess hilft dem Computer, schneller bessere Lösungen zu finden.

Obwohl dies noch nicht jedes Problem löst (insbesondere die allergrößten), bietet es einen vielversprechenden neuen Weg, Quantencomputer zur Lösung komplexer Optimierungsprobleme wie Planung und Ressourcenmanagement einzusetzen und potenziell die Notwendigkeit zu umgehen, dass klassische Computer die schwere Arbeit der Optimierung übernehmen.

Technische Zusammenfassung

Technische Zusammenfassung: Evolutionäres Quantenschaltungs-Framework angewendet auf das Set-Partitioning-Problem

Problemdefinition
Der Beitrag behandelt das Set-Partitioning-Problem (SPP), eine bekannte NP-schwere kombinatorische Optimierungsaufgabe. Das SPP umfasst die Aufteilung einer Menge von Elementen in sich gegenseitig ausschließende und erschöpfende Teilmengen, um das Gesamtgewicht zu minimieren, wobei sichergestellt wird, dass jedes Element genau einer Teilmenge angehört. Praktische Anwendungen umfassen die Flugzeugbesatzungsplanung. Um dies auf Quantenhardware zu lösen, formulieren die Autoren das SPP als Quadratisches Ungezwungenes Binäres Optimierungsproblem (QUBO), das anschließend auf einen Ising-Hamiltonoperator abgebildet wird. Die Studie zielt spezifisch auf die Einschränkungen aktueller Variationaler Quantenalgorithmen (VQAs) ab, wie etwa des Variationalen Quanten-Eigensolvers (VQE), die häufig unter „barren plateaus" leiden – einem Phänomen, bei dem Gradienten mit steigender Qubit-Anzahl exponentiell verschwinden und zu einer Stagnation der Konvergenz führen.

Methodik
Die Autoren schlagen ein evolutionäres Quantenschaltungs-Framework (QCE) vor, das vom Standard-VQE-Ansatz abweicht. Im Gegensatz zum VQE, der eine feste Schaltungstopologie (Ansatz) mit variierenden Parametern verwendet, die von einem klassischen Optimierer optimiert werden, entwickelt das QCE-Framework die Schaltungstopologie selbst weiter. Die Studie bewertet zwei unterschiedliche Strategien innerhalb dieses Frameworks:

1. Ansatz-freie Quantenschaltungs-Evolution (AF-QCE):

   • Inspiriert von vorheriger Literatur [13], beginnt dieser Ansatz mit einer minimalen Schaltung (ein einzelnes zufälliges Gatter) und entwickelt sich ohne einen vordefinierten Ansatz iterativ weiter.
   • Die Evolution stützt sich auf Mutationsoperationen: EINFÜGEN (ein Gatter hinzufügen), LÖSCHEN (ein Gatter entfernen), TAUSCHEN (ein Gatter ersetzen) und MODIFIZIEREN (Gatterparameter anpassen).
   • Eine Population von Schaltungen wird generiert, gemessen, und die bestperformende Schaltung wird als Elternteil für die nächste Generation ausgewählt, was eine monotone Reduktion der Kostenfunktion sicherstellt.

2. Ansatz mit pseudo-kounterdiabatischem evolutionärem Term (APCD-QCE):

   • Dieser Ansatz integriert eine physikinspirierte Struktur in den Ansatz, um die Konvergenz zu verbessern. Er nutzt einen Hamiltonoperator $H_T(\lambda) = H_{ad}(\lambda) + H_{pcd}(\lambda)$, wobei $H_{ad}$ einen adiabatischen Zeitentwicklungs-Hamiltonoperator darstellt und $H_{pcd}$ ein pseudo-kounterdiabatischer evolutionärer Term ist.
   • Der unitäre Operator ist definiert als $U = U_{ad}U_{pcd}$. Die Komponente $U_{ad}$ ist festgelegt (ein Trotter-Schritt), während $U_{pcd}$ unter Verwendung derselben evolutionären Mutationsstrategie wie bei AF-QCE weiterentwickelt wird.
   • Die Vorbereitung des Anfangszustands verwendet $|+\rangle^{\otimes n}$, und spezifische Parametereinstellungen ($\beta=0, \delta=0.5$) werden angewendet, um die Exploration des Hilbertraums zu erleichtern.

Experimenteller Aufbau
Experimente wurden unter Verwendung der Qiskit-Bibliothek auf einem Hochleistungs-Simulator (KUATOMU) unter zwei Szenarien durchgeführt:

• Rauschfrei: 35 Instanzen des SPP (im Bereich von 6 bis 20 Qubits) wurden getestet.
• Rauschbehaftet: Simulationen beinhalteten depolarisierende Fehlerkanäle ($\epsilon = 0.01$) auf spezifischen Qubits, um die Einschränkungen von NISQ-Geräten nachzuahmen.
• Vergleich: Die QCE-Strategien wurden gegen den Standard-VQE (unter Verwendung eines zweilokal-linearen Verschränkungsansatzes und des COBYLA-Optimierers) getestet.
• Metrik: Die Leistung wurde mittels des Approximationsverhältnisses ($R$) gemessen, definiert als das Verhältnis eines klassischen Referenzwerts (Gurobi-Löser) zum vom Quantenalgorithmus gefundenen minimalen Erwartungswert.

Hauptergebnisse

• Überlegenheit gegenüber VQE: In rauschfreien Szenarien schnitten sowohl AF-QCE als auch APCD-QCE den VQE deutlich besser ab. Die VQE-Leistung verschlechterte sich rapide mit steigender Qubit-Anzahl (oft ohne Konvergenz bei Instanzen $\ge 10$ Qubits), während die evolutionären Ansätze eine bessere Leistung beibehielten.
• APCD-QCE-Leistung: Die APCD-QCE-Strategie zeigte die robustesten Ergebnisse und erreichte in 25 von 35 Instanzen ein Approximationsverhältnis von 1,00 (optimal). Sie vermied effektiv die Konvergenzstagnation in den meisten Fällen, in denen VQE und AF-QCE Schwierigkeiten hatten.
• Skalierbarkeitsgrenzen: Trotz der Verbesserungen bestanden Skalierbarkeitsprobleme weiter. Bei 20-Qubit-Instanzen (insbesondere 20.1, 20.6 und 20.7) zeigten alle Methoden, einschließlich APCD-QCE, Anzeichen einer Konvergenzstagnation, wobei die Approximationsverhältnisse signifikant abfielen.
• Rauscheinfluss: In rauschbehafteten Simulationen verschlechterte sich die Leistung für alle Algorithmen, insbesondere bei kleineren Instanzen. Dennoch behielten die QCE-Frameworks im Allgemeinen eine vergleichbare oder bessere Leistung im Verhältnis zum VQE bei.

Bedeutung und Behauptungen
Das Papier behauptet, dass das vorgeschlagene QCE-Framework eine vielversprechende Alternative zu variationalen Algorithmen mit festem Ansatz für ganzzahlige Optimierungsprobleme darstellt. Zu den wichtigsten Beiträgen gehören:

• Minderung der Stagnation: Das Framework, insbesondere die APCD-QCE-Variante, zeigt eine bemerkenswerte Fähigkeit, die mit barren plateaus in Standard-VQAs verbundene Konvergenzstagnation zu vermeiden.
• Eliminierung klassischer Optimierer: Durch die direkte Evolution der Schaltungstopologie umgeht das Verfahren die Notwendigkeit klassischer Optimierer (wie COBYLA), um Parameter zu justieren, und adressiert damit einen Engpass in aktuellen VQA-Arbeitsabläufen.
• Pfad zur Skalierbarkeit: Obwohl keine vollständige Lösung für die 20-Qubit-Stagnation, deuten die Ergebnisse darauf hin, dass Schaltungen mit variabler Topologie einen „interessanten Pfad" zur Lösung größerer Optimierungsprobleme bieten. Die Autoren stellen fest, dass die APCD-QCE-Strategie bei hinreichend großer Anzahl von Generationen „fast immun" gegen Konvergenzstagnationseffekte ist, obwohl das Entkommen aus lokalen Minima im Mutationslandschaft weiterhin eine Herausforderung bleibt.

Die Autoren schließen, dass die Methode zwar mit zunehmender Qubit-Anzahl Skalierbarkeitsprobleme aufweist, die Integration physikinspirierter Terme (pseudo-kounterdiabatisch) in die evolutionäre Schaltungssuche jedoch ermutigende Ergebnisse für die Lösung kombinatorischer Probleme auf NISQ-Geräten liefert.