Scaling Laws for Parameter Setting in Digitized Counterdiabatic QAOA

In der weiten Landschaft des modernen Computings gehören zu den hartnäckigsten Herausforderungen das Finden der einen besten Anordnung unter einer schwindelerregenden Anzahl von Möglichkeiten. Ob es darum geht, Lieferwagen durch eine Stadt zu leiten, Maschinen in einer Fabrik zu planen oder Finanztransaktionen abzuwickeln – dies sind Probleme der kombinatorischen Optimierung. Jahrzehntelang haben Wissenschaftler auf Quantencomputer gehofft – Maschinen, die die seltsamen Regeln der subatomaren Welt nutzen –, um diese Rätsel schneller zu lösen, als es klassische Computer jemals könnten. Eines der vielversprechendsten Werkzeuge für diese Aufgabe ist ein Algorithmus namens Quantum Approximate Optimization Algorithm, oder kurz QAOA. Man kann ihn sich wie eine geführte Suche vorstellen: Der Computer bereitet einen Quantenzustand vor, wendet eine Reihe von Operationen an, die durch spezifische Zahlen namens Parameter gesteuert werden, und misst dann das Ergebnis, um zu sehen, wie nah er der perfekten Lösung gekommen ist. Der Haken dabei ist, dass der Computer für jedes neue Problem normalerweise einen langen, langsamen Prozess durchlaufen muss, um die besten Zahlen zu ermitteln. Dieser „Tuning“-Schritt verschlingt Zeit und Ressourcen und hebt oft den Geschwindigkeitsvorteil auf, den der Quantencomputer eigentlich bieten sollte.

Die Forscher Yaocheng Chen und Jiapei Zhuang haben einen Weg gefunden, diesen Engpass für einen speziellen Typ von Quantenalgorithmus zu umgehen, der darauf ausgelegt ist, gewichtete Probleme zu handhaben, bei denen die Verbindungen zwischen den Elementen unterschiedliche Stärken aufweisen. Sie entdeckten, dass die optimalen Einstellungen für die Steuerungen des Algorithmus nicht zufällig oder für jedes einzelne Problem einzigartig sind. Stattdessen folgen diese Einstellungen einem vorhersehbaren Muster, das auf zwei einfachen Fakten über das Problem selbst basiert: wie viele Verbindungen die Elemente im Durchschnitt haben und wie stark diese Verbindungen sind. Durch das Studium tausender verschiedener Problemkonfigurationen in Simulationen entwickelte das Team eine Reihe von Regeln, die die optimalen Einstellungen für ein neues Problem allein durch den Blick auf dessen grundlegende Statistiken vorhersagen können. Das bedeutet, dass man einem Quantencomputer ein frisches, ungelöstes Problem übergeben und ihm sofort die richtigen Anweisungen geben kann, um mit der Suche zu beginnen, ohne Zeit damit zu verschwenden, herauszufinden, was diese Anweisungen sein sollten.

Das Team konzentrierte sich auf eine anspruchsvolle Version des Standardalgorithmus, die als „digitized counterdiabatic QAOA“ bekannt ist. Während die Standardversion zwei Arten von Operationen verwendet, um durch mögliche Antworten zu navigieren, fügt diese verbesserte Version eine dritte Art von Operation hinzu, die darauf ausgelegt ist, das System daran zu hindern, stecken zu bleiben oder Fehler zu machen, während es sich entwickelt. Dieser zusätzliche Schritt macht den Algorithmus leistungsfähiger, aber auch komplexer, da er drei Sätze von Zahlen erfordert, die für jede Schicht des Prozesses abgestimmt werden müssen. Die Forscher begannen mit massiven Offline-Simulationen auf einer Vielzahl von Graphstrukturen – mathematischen Karten von Verbindungen –, die von einfachen Ringen bis hin zu komplexen, zufälligen Netzwerken reichen. Sie optimierten die Einstellungen für jeden dieser tausenden Graphen, um die absolut beste Leistung zu finden.

Was aus diesem Berg von Daten hervorging, war eine auffallende Regelmäßigkeit. Als die Forscher die Größe der Verbindungen und die durchschnittliche Anzahl der Verbindungen pro Element berücksichtigten, kollabierten die optimalen Einstellungen für alle verschiedenen Graphen in einem engen Cluster. Es war, als ob die spezifischen Details jedes Graphen nicht so wichtig wären wie die Gesamtgröße des Problems. Das Team stellte fest, dass sie die besten Einstellungen mit einer einfachen Formel beschreiben konnten, die die durchschnittliche Anzahl der Verbindungen und die Stärke der Verbindungen als Eingabewerte nutzt. Diese Formel fungiert wie ein universeller Schlüssel: Sobald man die grundlegenden Statistiken eines neuen Problems kennt, kann man sie einsetzen und genau die Zahlen erhalten, die benötigt werden, um den Quantenkreis auszuführen. Das Ergebnis ist eine „eingefrorene“ Rezeptur, ein fester Satz von Regeln, der die korrekten Parameter sofort zuweist und so den langwierigen Suchprozess vollständig überspringt.

Um zu testen, ob diese Abkürzung tatsächlich funktionierte, ließen die Forscher Simulationen auf 1.050 verschiedenen Testgraphen laufen, die der Algorithmus zuvor noch nie gesehen hatte. Sie verglichen ihren formelbasierten Ansatz mit einer Standardmethode, die einen festen Satz von Zahlen für alle verwendet. In jedem Fall, von flachen Schaltkreisen mit nur einer Ebene an Operationen bis hin zu tieferen mit vier Ebenen, lieferte die formelbasierte Methode eine höhere mittlere Wahrscheinlichkeit, die optimale Lösung zu sampeln, als der standardmäßige feste Ansatz. Bei einer Tiefe von vier Ebenen erreichte die mittlere Wahrscheinlichkeit der optimalen Lösung für die neue Methode 19,36 %, verglichen mit 13,11 % für den standardmäßigen festen Ansatz. Dieser Vorteil blieb über verschiedene Arten von Netzwerken und verschiedene Arten der Zuweisung von Verbindungsstärken hinweg bestehen. Die Forscher testeten die Methode sogar auf einem echten Quantenprozessor, dem IBM ibm_fez, unter Verwendung kleiner, einheitlicher Netzwerke. Obwohl das Rauschen in der echten Hardware die Ergebnisse bei tieferen Ebenen erschwerte, zeigte die formelbasierte Methode selbst auf der flachsten Ebene einen klaren Vorteil, was beweist, dass die aus Simulationen abgeleiteten Regeln auf physische Maschinen übertragbar sind.

Die Studie untersuchte auch, ob diese vorab berechneten Einstellungen als guter Ausgangspunkt für eine weitere Verfeinerung dienen könnten. In einem separaten Experiment nahmen die Forscher die durch ihre Formel bereitgestellten Einstellungen und nutzten sie, um eine standardmäßige Optimierungssuche auf einem kleinen Satz von Graphen zu initialisieren. Sie fanden heraus, dass der Start mit den Zahlen der Formel es der Suche ermöglichte, eine bessere Lösung viel schneller zu erreichen als ein Start mit einer zufälligen Vermutung. Tatsächlich erreichte der formelbasierte Start eine höhere durchschnittliche Qualität der Lösung, als eine Zufallssuche selbst nach 500 Versuchen erreichen konnte. Dies deutet darauf hin, dass die Formel die Suche nicht nur ersetzt, sondern eine hochwertige Startplattform bietet, die jede anschließende Feinabstimmung effektiver macht.

Die Forscher waren jedoch vorsichtig darauf bedacht, anzumerken, wo ihre Methode an Grenzen stößt. Die Regeln wurden von Graphen mit einer moderaten Anzahl von Verbindungen abgeleitet, und als sie die Formel auf Graphen mit sehr wenigen Verbindungen testeten, sank die Leistung, insbesondere bei tieferen Schaltkreisen. Dies deutet darauf hin, dass die Skalierungsgesetze zwar mächtig sind, aber Grenzen haben und nicht blindlings auf jeden möglichen Typ von Netzwerk angewendet werden sollten. Darüber hinaus wurde der Vergleich Schicht für Schicht durchgeführt, was bedeutet, dass der verbesserte Algorithmus mehr physische Operationen pro Schritt verwendet als der Standardalgorithmus. Die Forscher räumten ein, dass ein fairerer Vergleich die Gesamtzahl der Operationen berücksichtigen müsste – eine Frage, die für zukünftige Studien offen bleibt.

Letztendlich zeigt diese Arbeit, dass das Verhalten komplexer Quantenalgorithmen beherrschbar wird, wenn man die einfache Geometrie der Probleme versteht, die sie lösen. Indem sie erkannten, dass die besten Einstellungen von der Skala des Netzwerks abhängen und nicht von seinen spezifischen Details, haben die Forscher ein schwieriges, instanzspezifisches Tuning-Problem in eine einfache Berechnung verwandelt. Dieser Wechsel ermöglicht es Quantencomputern, ihre kostbare Zeit mit dem Lösen von Problemen zu verbringen, anstatt mit dem Lernen, wie man sie löst, was das Versprechen der Quantenoptimierung einen Schritt näher an die praktische Realität bringt. Die Ergebnisse legen nahe, dass für eine breite Palette von kombinatorischen Problemen der Weg zur besten Antwort kein Mysterium ist, das jedes Mal von Grund auf neu gelöst werden muss, sondern ein Muster, das direkt aus der eigenen Struktur des Problems abgelesen werden kann.