A Parameter Setting Heuristic for the Quantum Alternating Operator Ansatz

Technische Zusammenfassung: Eine Heuristik zur Parametereinstellung für den Quantum Alternating Operator Ansatz

Problemstellung
Der Quantum Alternating Operator Ansatz (QAOA) ist ein prominanter parametrisierter Quantenalgorithmus zur Lösung kombinatorischer Optimierungsprobleme. Das effiziente Auffinden hochwertiger Parameter ($\vec{\gamma}, \vec{\beta}$) bleibt jedoch eine erhebliche praktische Herausforderung. Der Prozess der Parametereinstellung umfasst typischerweise eine variatielle quanten-klassische Schleife, in der ein klassischer Optimierer die Parameter basierend auf dem Erwartungswert einer Kostenfunktion aktualisiert, die auf Quantenhardware oder über eine teure klassische Simulation ausgewertet wird. Dieser Prozess steht vor Schwierigkeiten wie Barren Plateaus, zahlreichen lokalen Optima und der exponentiellen Skalierung der Ressourcen, die für die exakte klassische Auswertung von Erwartungswerten mit steigender Anzahl von Qubits ($n$) oder Schaltungstiefe ($p$) erforderlich sind. Zudem verschlimmern aktuelle Noisy Intermediate-Scale Quantum (NISQ)-Geräte diese Herausforderungen durch Rauschen und endliche Abtastfehler.

Methodik
Die Autoren schlagen eine „Homogene Heuristik zur Parametereinstellung“ vor, eine klassische Strategie, die darauf abzielt, die kostspielige Quanten- oder klassische Auswertung des Erwartungswerts der Kostenfunktion durch ein effizientes klassisches Modell zu ersetzen. Der Kern dieses Ansatzes beruht auf dem Konzept der Perfekten Homogenität.

1. Perfekte Homogenität: Diese wird als eine Zustandsigenschaft definiert, bei der alle Bitstrings $x$, die denselben Kostenwert $c(x)$ teilen, identische Quantenamplituden besitzen. Während diese Eigenschaft exakt nur für spezifische symmetrische Probleme oder im Grenzfall kleiner Parameter gilt, deuten empirische Beobachtungen darauf hin, dass hohe Überlappungen zwischen QAOA-Zuständen und perfekt homogenen Zuständen in verschiedenen Szenarien bestehen.
2. Klassischer homogener Proxy: Die Autoren konstruieren ein klassisches Modell, das als „Klassischer homogener Proxy“ bezeichnet wird und die Perfekte Homogenität unter der Annahme erzwingt. In diesem Proxy wird der Zustand nicht durch $2^n$ Amplituden beschrieben, sondern durch einen Satz von Amplituden $Q(c)$, die jedem eindeutigen Kostenwert $c$ entsprechen.
   • Die Evolution wird unter einer „Sum-of-Paths“-Perspektive modelliert. Die Autoren ersetzen die exakte Anzahl der Bitstrings bei einem bestimmten Hamming-Abstand durch eine spezifische Kostenfunktion $n(x; d, c)$ durch eine analytisch abgeleitete Verteilung $N(c'; d, c)$, die nur von den Kostenklassen abhängt.
   • Dies ermöglicht die rekursive Berechnung der Amplituden $Q_\ell(c)$ für jede Schicht $\ell$ unter Verwendung von Gleichung (5), was polynomiell mit der Problemgröße $n$ und der Anzahl der distinkten Kostenwerte $|C|$ skaliert, sofern $|C|$ polynomiell mit $n$ wächst.
3. Die Heuristik-Schleife: Das Verfahren zur Parametereinstellung (Algorithmus 3) nutzt diesen Proxy als innere Subroutine. Ein klassischer Optimierer sucht nach Parametern $(\vec{\gamma}, \vec{\beta})$, die die „homogene Parameter-Zielfunktion“ minimieren (eine Schätzung des Erwartungswerts der Kosten, die aus dem Proxy abgeleitet ist). Sobald optimale Parameter für den Proxy gefunden wurden, werden diese direkt auf den tatsächlichen QAOA-Schaltkreis angewendet.

Das Paper demonstriert, wie die notwendigen Verteilungen ($N(c'; d, c)$ und Kostenwahrscheinlichkeiten $P(c')$) für spezifische Klassen von Constraint-Satisfaction-Problemen (CSPs) mit zufällig gezogenen Klauseln, einschließlich random $k$-SAT, MaxCut auf Erdős-Rényi-Graphen und Max-$k$-XOR, berechnet werden können.

Wesentliche Beiträge

• Definition der Perfekten Homogenität und des Proxys: Die Autoren formalisieren die Bedingung der Perfekten Homogenität und definieren einen Klassischen Homogenen Proxy, der sowohl Zustandsbeschreibungen als auch Erwartungswerte effizient liefert.
• Polynomiale Skalierung: Die vorgeschlagene Methode ermöglicht die klassische Berechnung von Proxy-Parametern in einer Zeit, die polynomiell bezüglich der Anzahl der Variablen $n$ und der Tiefe $p$ skaliert, wodurch das exponentielle Ressourcenwachstum vermieden wird, das mit einer exakten Zustandsvektor-Simulation verbunden ist.
• Generalisierung auf CSP-Klassen: Das Paper liefert explizite Ableitungen für die Proxy-Verteilungen für vier Klassen von Zufalls-CSPs und zeigt, dass der Proxy eine ganze Klasse von Problemen beschreiben kann, statt nur eine einzelne Instanz.
• Heuristischer Rahmen: Die Autoren führen einen vollständigen Workflow (Algorithmus 3) ein, der diesen Proxy in Standard-Parameteroptimierungsschleifen integriert und dabei die Flexibilität in der Wahl der Parameter-Update-Schemata beibehält.

Ergebnisse
Die Autoren evaluierten die Heuristik numerisch auf MaxCut-Problemen über ungewichteten Erdős-Rényi-Zufallsgraphen ($G(n, p_e)$):

• Geringe Tiefe ($p \leq 3$): Für Graphen mit $n=20$ fand die Heuristik Parameter, die Approximationsverhältnisse lieferten, die mit denen der „Parameter-Transfer“-Strategie (Übertragung global optimierter Parameter von kleineren Instanzen) vergleichbar sind. Der Unterschied in der Performance war statistisch nicht signifikant, wobei die Heuristik in einigen Fällen eine leicht höhere durchschnittliche Performance zeigte.
• Hohe Tiefe ($p \leq 20$): Für Tiefen bis zu $p=20$ identifizierte die Heuristik erfolgreich Parameter, die monoton steigende Approximationsverhältnisse mit zunehmender Tiefe lieferten. Im Gegensatz dazu konnte eine Strategie, die mit identischen klassischen Ressourcen einen Parameter-Transfer nutzte, nicht konvergieren.
• Proxy-Genauigkeit: Die numerische Analyse zeigte, dass der Proxy große Überlappungen mit vollständigen Zustandsvektor-Simulationen beibehält, insbesondere bei linearen Rampen-Parameterschemata und in Regimen, in denen der Parameter $\gamma$ klein ist. Die im Proxy verwendeten analytischen Verteilungen korrelierten hochgradig mit empirischen Durchschnitten über Zufallsgraph-Instanzen.

Bedeutung und Ansprüche
Das Paper behauptet, dass die Homogene Heuristik einen praktischen Weg für die Parametereinstellung in Regimen bietet, die aufgrund von Rauschen für NISQ-Geräte und aufgrund exponentieller Skalierung für klassische Methoden derzeit unzugänglich sind. Durch den Ersatz der teuren Auswertung des Erwartungswerts durch einen polynomialen klassischen Proxy ermöglicht die Methode die Untersuchung tieferer QAOA-Schaltkreise (z. B. $p=20$), bei denen bisherige Strategien scheitern.

Die Autoren betonen, dass die Heuristik zwar nicht garantiert, optimale Parameter für jede spezifische Instanz zu finden, aber eine robuste, klassenweite Strategie bietet, die bei geringen Tiefen konkurrenzfähig mit etablierten Methoden ist und sie bei höheren Tiefen übertrifft. Die Arbeit legt nahe, dass die Annahme der Perfekten Homogenität, obwohl sie nicht universell exakt ist, als ausreichend genaue Approximation dient, um die Parameteroptimierung in vielen kombinatorischen Optimierungsszenarien, insbesondere bei zufälligen Constraints, zu leiten. Die Autoren schließen mit einem Ausblick auf zukünftige Richtungen, wie etwa die Integration instanzspezifischer Informationen in den Proxy und die Erweiterung des Ansatzes auf andere variatielle Quantenalgorithmen wie den Variational Quantum Eigensolver (VQE).