Utility-Scale QAOA

Schau dir das Video über Utility-Scale QAOA von Olivia Lanes an, oder öffne es in einem separaten Fenster auf YouTube.

Überblick über die Lektion

Bisher in diesem Kurs haben wir dir hoffentlich ein solides Fundament des Frameworks und der Werkzeuge vermittelt, die benötigt werden, um Probleme im Utility-Maßstab auf einem Quantencomputer zu lösen. Nun werden wir diese Werkzeuge endlich in Aktion sehen.

In dieser Lektion werden wir uns mit einem Beispiel des Max-Cut-Problems im Utility-Maßstab die Hände schmutzig machen, einem bekannten Problem der Graphentheorie, bei dem es darum geht, einen Graphen optimal in zwei Teile zu partitionieren. Wir beginnen mit einem einfachen Fünf-Knoten-Graphen, um unser Gespür dafür zu entwickeln, wie ein Quantencomputer uns bei der Lösung des Problems helfen kann, und wenden das dann auf eine Version des Problems im Utility-Maßstab an.

Diese Lektion dient als breiter Überblick über den Ansatz, den wir zur Lösung dieses Problems verwenden. Es handelt sich nicht um einen Code-Walkthrough. Zu dieser Lektion gibt es jedoch ein Tutorial mit tatsächlichem Code, den du ausführen kannst, um das Max-Cut-Problem auf einem Quantencomputer zu lösen.

Das Problem

Zur Erinnerung: Nicht alle Rechenprobleme sind für Quantencomputing geeignet. „Einfache Probleme" werden durch diese Technologie keine Vorteile erhalten, da klassische Computer diese bereits problemlos lösen können.

Die drei Anwendungsfälle, für die wir am optimistischsten sind, sind:

1. Natursimulation
2. Verarbeitung von Daten mit komplexer Struktur
3. Optimierung

Heute konzentrieren wir uns auf den dritten Anwendungsfall: Optimierung. Bei einem Optimierungsproblem suchen wir in der Regel nach dem größten oder kleinsten möglichen Wert einer gegebenen Funktion. Die Schwierigkeit, diese Extrema mit klassischen Methoden zu finden, kann exponentiell zunehmen, wenn die Problemgröße wächst.

Das Optimierungsproblem, das uns heute interessiert, heißt Max-Cut, das wir mit einem Algorithmus namens Quantum Approximate Optimization Algorithm (QAOA) lösen werden.

Was ist Max-Cut?

Wir beginnen mit einem Graphen, der aus einer Sammlung von Knoten (oder Vertices) besteht, von denen einige durch Kanten verbunden sind. In dem Problem werden wir gebeten, die Knoten des Graphen in zwei Teilmengen aufzuteilen, indem wir die Kanten, die sie verbinden, „schneiden". Wir wollen die Partition finden, die die Anzahl der auf diese Weise geschnittenen Kanten maximiert – daher der Name „Max-Cut".

Die obige Abbildung zeigt beispielsweise einen Fünf-Knoten-Graphen mit einer Max-Cut-Lösung auf der rechten Seite. Er schneidet durch fünf Kanten, was das Beste ist, was man mit diesem Graphen erreichen kann.

Da ein Fünf-Knoten-Graph so klein ist, ist es nicht allzu schwierig, den Max-Cut im Kopf herauszufinden oder es mit ein paar Schnitten auf einem Stück Papier auszuprobieren. Aber wie du dir vorstellen kannst, wird das Problem schwieriger und schwieriger, wenn die Anzahl der Knoten wächst – zum Teil, weil die Anzahl der zu berücksichtigenden möglichen Schnitte exponentiell mit der Anzahl der Knoten wächst. Und ab einem bestimmten Punkt wird selbst dies für Supercomputer mit den bekannten klassischen Algorithmen schwierig.

Wir möchten eine Möglichkeit haben, das Max-Cut-Problem für diese größeren, komplizierteren Graphen zu lösen, da das Problem viele praktische Anwendungen hat, darunter Betrugserkennung im Finanzwesen, Graph-Clustering, Netzwerkdesign und Social-Media-Analyse. Max-Cut wird oft als Teilproblem innerhalb eines bestimmten Ansatzes zu einem größeren Problem angetroffen. Daher ist es viel häufiger, als wir naiv denken würden.

Die Lösung

Nun werden wir den Ansatz durchgehen, den wir verwenden, um das Max-Cut-Problem auf einem Quantencomputer zu lösen. Wir werden das mit einem einfachen Fünf-Knoten-Graphen tun. Du kannst dem Python-Notebook-Tutorial folgen. Nach diesem einfachen Beispiel wird das Tutorial dich durch ein Beispiel des Problems im Utility-Maßstab führen.

Der erste Schritt ist, unseren Graphen zu erstellen, indem wir die Anzahl der Knoten und die Kanten, die zwei Knoten verbinden, definieren. Du kannst dies tun, indem du ein Paket namens rustworkx importierst, wie im Tutorial demonstriert. Das Ergebnis wird ein Graph sein, der so aussieht:

Wir werden das Qiskit-Patterns-Framework verwenden, um die Max-Cut-Lösungen für diesen Graphen auf unserem Quantencomputer zu finden.

Abbilden (Map)

Wir müssen das Problem auf unseren Quantencomputer abbilden. Dazu stellen wir zunächst fest, dass das Maximieren der Anzahl von Schnitten in einem Graphen mathematisch geschrieben werden kann als:

$$\max\limits_{x\in\{0,1\}^n} \sum\limits_{(i,j)} {x_i + x_j - 2x_ix_j}$$

Wobei $i$ und $j$ Knoten im Graphen sind, und $x_i$ und $x_j$ entweder 0 oder 1 sind, je nachdem, auf welcher Seite der Partition sich jeder Knoten befindet (eine Gruppe ist als „0" und eine als „1" bezeichnet). Wenn $x_i$ und $x_j$ auf derselben Seite der Partition sind, ist der Ausdruck in der Summe gleich null. Wenn sie auf entgegengesetzten Seiten sind, also ein Schnitt zwischen ihnen liegt, ist der Ausdruck gleich eins. Die Anzahl der Schnitte zu maximieren maximiert also die Summe.

Wir können das auch umdrehen und nach dem Minimum suchen, indem wir jeden der Werte mit minus eins multiplizieren.

$$\min\limits_{x\in\{0,1\}^n} \sum\limits_{(i,j)} {2x_ix_j - x_i - x_j}$$

Nun sind wir bereit abzubilden. Es kann ziemlich entmutigend sein zu überlegen, wie man von einem Graphen wie dem, den wir gerade gezeichnet haben, zu einem Quantencircuit kommt. Aber wir gehen es Schritt für Schritt an.

Denk daran: Wir werden versuchen, Max-Cut mit QAOA zu lösen. In der QAOA-Methodik wollen wir letztendlich einen Operator (oder mit anderen Worten einen Hamiltonianer) haben, der die Kostenfunktion unseres hybriden Algorithmus darstellt, sowie einen parametrisierten Circuit (den Ansatz), mit dem wir mögliche Lösungen für das Problem darstellen.

QUBO

Wir können aus diesen Kandidatenlösungen abtasten und sie dann mit der Kostenfunktion bewerten. Dazu nutzen wir eine Reihe von mathematischen Umformulierungen, einschließlich der Quadratic Unconstrained Binary Optimization-Notation – kurz QUBO – was eine nützliche Möglichkeit ist, kombinatorische Optimierungsprobleme zu kodieren. In QUBO wollen wir finden:

$$\min\limits_{x\in\{0,1\}^n} x^TQx$$

wobei $Q$ eine $n\times n$-Matrix reeller Zahlen ist, $n$ der Anzahl von Knoten in unserem Graphen entspricht, hier fünf.

Um QAOA anzuwenden, müssen wir unser Problem als Hamiltonianer formulieren – das ist eine Funktion oder Matrix, die die Gesamtenergie eines Systems darstellt. Insbesondere möchten wir einen Kosten-Hamiltonianer erstellen, der die Eigenschaft hat, dass der Grundzustand dem Minimalwert der Funktion entspricht. Um unser Optimierungsproblem zu lösen, werden wir also versuchen, den Grundzustand von $H$ auf einem Quantencomputer vorzubereiten. Dann liefert das Abtasten aus diesem Zustand mit hoher Wahrscheinlichkeit die Lösung für $\min 𝑓(𝑥)$.

Abbildung auf einen Kosten-Hamiltonianer

Wie sich herausstellt, haben wir Glück, denn das QUBO-Problem ist sehr eng verwandt mit und tatsächlich rechnerisch äquivalent zu einem der berühmtesten und allgegenwärtigsten Hamiltoniane in der Physik: dem Ising-Hamiltonianer.

Um das QUBO-Problem als Ising-Hamiltonianer zu schreiben, müssen wir eigentlich nur eine einfache Variablensubstitution durchführen:

$$x_i = \frac{1-z_i}{2}.$$

Wir werden hier nicht alle Schritte durchgehen, aber sie sind im beigefügten Notebook erklärt. Am Ende ist die Minimierung des QUBO-Ausdrucks identisch mit der Minimierung dieses Ausdrucks:

$$\min_{x\in\{0,1\}^n} x^TQx\Longleftrightarrow \min_{z\in\{-1,1\}^n}z^TQz + b^Tz$$

Nochmals leicht umgeschrieben haben wir unseren Kosten-Hamiltonianer, wobei das Minimum des Ausdrucks den Grundzustand darstellt, Z der Pauli-Z-Operator ist und $b$ ein reeller skalarer Koeffizient ist:

$$H_C=\sum_{ij}Q_{ij}Z_iZ_j + \sum_i b_i Z_i$$

Nachdem wir unseren Hamiltonianer haben, müssen wir ihn in Termen von zweistelligen Pauli-ZZ-Operatoren umschreiben, die wir leicht in Zwei-Qubit-Gates in unserem Quantencircuit konvertieren können. Wir werden sechs Objekte – oder Pauli-Strings – erhalten, die jeweils einer der sechs Kanten im Graphen entsprechen. Jedes der fünf Elemente in einem String stellt eine Operation auf einem Knoten dar – die Identität, wenn der Knoten nicht mit dieser bestimmten Kante verbunden ist, und den Pauli-Z-Operator, wenn er es ist. In Qiskit werden Bitstrings, die Qubits darstellen, umgekehrt indiziert. Eine Kante zwischen den Knoten 0 und 1 wird zum Beispiel als IIIZZ kodiert, und eine Kante zwischen 2 und 4 wird als ZIZII kodiert.

Den Quantencircuit konstruieren

Mit unserem Hamiltonianer in Pauli-Operatoren geschrieben sind wir bereit, unseren Quantencircuit zu konstruieren, der es uns ermöglicht, mit einem Quantencomputer gute Lösungen abzutasten:

Der QAOA-Algorithmus orientiert sich am Adiabatischen Theorem, das besagt: Wenn wir im Grundzustand eines zeitabhängigen Hamiltonianers beginnen und der Hamiltonianer sich langsam genug entwickelt, wird der Endzustand bei ausreichender Zeit der Grundzustand des End-Hamiltonianers sein. QAOA kann als die diskrete, trotterisierte Version dieses Quantum Adiabatic Algorithm betrachtet werden, wobei jeder Trotter-Schritt eine Schicht des QAOA-Algorithmus darstellt. Anstatt sich von einem Zustand zum anderen zu entwickeln, wechseln wir in jeder Schicht also zwischen unserem Kosten-Hamiltonianer und einem sogenannten „Mixer"-Hamiltonianer hin und her, den wir später in dieser Lektion behandeln werden.

Der Vorteil von QAOA ist, dass er schneller als der Quantum Adiabatic Algorithm ist, aber er liefert näherungsweise statt optimale Lösungen. Im Grenzfall, wo die Anzahl der Schichten gegen unendlich geht, konvergiert QAOA zu dem QAA-Fall, aber natürlich ist das rechnerisch sehr aufwändig.

Um unseren Quantencircuit zu erstellen, werden wir abwechselnde Operatoren anwenden, die durch $\gamma$ und $\beta$ parametrisiert sind und die Diskretisierung der Zeitentwicklung darstellen.

Die drei Hauptteile des QAOA-Circuits sind also:

1. der anfängliche Testzustand, in Grau, der der Grundzustand des Mixers ist und durch Anwenden eines Hadamard-Gates auf jedes Qubit erstellt wird
2. die Kosten-Hamiltonianer-Entwicklung, die wir zuvor besprochen haben, in dunkelviolett
3. die Entwicklung unter dem Mixer-Hamiltonianer, den wir noch nicht behandelt haben, in hellviolett.

Unser Start-Hamiltonianer wird Mixer genannt, weil sein Grundzustand die Superposition aller möglichen Bitstrings von Interesse ist: daher wird am Anfang eine Mischung aller möglichen Lösungen erzwungen.

Der Mixer-Hamiltonianer ist die einfache Summe von Pauli-X-Operationen auf jedem Knoten des Graphen. Qiskit erlaubt es dir, einen anderen, benutzerdefinierten Mixer-Operator zu verwenden, wenn du möchtest, aber wir werden hier den Standard verwenden. Wie du also sehen kannst, wird durch Qiskit viel der Arbeit für uns erledigt, sodass das Finden des Mixer-Hamiltonianers und des Startzustands trivial wird. Die einzige Arbeit, die wir leisten mussten, war, die Kostenfunktion zu finden.

Jede Iteration dieser Operatoren wird als Schicht bezeichnet. Diese Schichten können als Diskretisierung der Zeitentwicklung des Systems betrachtet werden, wie zuvor beschrieben. Das abwechselnde Muster ergibt sich aus der Trotter-Zerlegung und approximiert die Exponentialfunktionen nicht-kommutierender Matrizen. Im Allgemeinen gilt: Je mehr Schichten oder Schritte wir einbeziehen, desto näher kommen wir der kontinuierlichen Zeitentwicklung wie in QAA, sodass das Ergebnis theoretisch genauer sein wird. Für dieses Beispiel werden wir jedoch zunächst mit einer Schicht abtasten. Denk daran, dass sowohl der Kosten-Hamiltonianer als auch der Mixer parametrisiert sind und wir noch optimale Werte für $\gamma$ und $\beta$ finden müssen.

Optimieren (Optimize)

Obwohl der Circuit, den wir gerade erstellt haben, ziemlich einfach aussieht und nützlich ist, um ein intuitives Verständnis aufzubauen, versteht der Quantenchip nicht, was das QAOA-Gate ist. Wir müssen das in eine Reihe von Einzel- und Zwei-Qubit-„nativen" Gates umwandeln, die direkt auf der Hardware ausgeführt werden können. Native Gates sind diejenigen, die direkt auf den Qubits ausgeführt werden können. Solche Circuits werden als in der Instruction Set Architecture (ISA) des Backends geschrieben bezeichnet.

Die Qiskit-Bibliothek bietet eine Reihe von Transpilierungsdurchläufen, die eine breite Palette von Circuit-Transformationen abdecken. Wir wollen sicherstellen, dass der Circuit für unsere Zwecke optimiert ist.

Erinnere dich an die vorherige Lektion, dass der Transpilierungsprozess mehrere Schritte umfasst:

• Initiales Mapping der Qubits im Circuit (also Entscheidungsvariablen) auf physische Qubits auf dem Gerät.
• Entfaltung der Anweisungen im Quantencircuit zu den hardware-nativen Anweisungen, die das Backend versteht.
• Routing aller Qubits im Circuit, die miteinander interagieren, auf physische Qubits, die benachbart zueinander sind.

Und wie immer finden sich weitere Details dazu in der Dokumentation.

Vor der Transpilierung müssen wir jedoch wählen, auf welchem Backend wir unseren Circuit ausführen werden, da der Transpiler für verschiedene Prozessoren unterschiedlich optimiert. Das ist ein weiterer Grund, warum es wichtig ist, einen automatisierten Transpiler zu verwenden – du möchtest nicht den zeitaufwändigen Prozess durchlaufen, deinen Circuit manuell zu optimieren, nur um festzustellen, dass du deinen Circuit eigentlich auf einem anderen Prozessor mit anderen Eigenschaften ausführen möchtest.

Übergib dein bevorzugtes Backend an die Transpilierungsfunktion und gib deinen Optimierungsgrad an. Im Tutorial wählst du Level 3, den höchsten und gründlichsten Level.

Damit haben wir einen transpilierten Circuit, der bereit ist, auf Hardware ausgeführt zu werden!

Ausführen (Execute)

Bisher haben wir den Circuit transpiliert und dabei die Parameter Gamma und Beta unberührt gelassen – aber wir können den Circuit nicht wirklich ausführen, ohne diese Parameter anzugeben. Im QAOA-Workflow werden die optimalen QAOA-Parameter in einer iterativen Optimierungsschleife gefunden, bei der wir eine Reihe von Circuit-Auswertungen durchführen und dann einen klassischen Optimierer verwenden, um die optimalen $\beta$- und $\gamma$-Parameter zu finden. Wir müssen jedoch irgendwo beginnen, also machen wir eine anfängliche Schätzung von $\gamma=\pi/2$ und $\beta=\pi$.

Ausführungsmodi

Nun sind wir fast bereit, den Circuit auszuführen – versprochen! Aber zunächst ist es wichtig zu beachten, dass du deinen Job auf verschiedene Arten senden kannst, die als Ausführungsmodi bezeichnet werden.

• Job-Modus: Eine einzelne Primitive-Anfrage des Estimators oder Samplers wird ohne einen Kontextmanager gestellt. Circuits und Eingaben werden als Primitive Unified Blocs (PUBs) verpackt und als Ausführungsaufgabe auf dem Quantencomputer eingereicht.

• Batch-Modus: Ein Multi-Job-Manager für die effiziente Durchführung eines Experiments, das aus einem Bündel unabhängiger Jobs besteht. Verwende den Batch-Modus, um mehrere Primitive-Jobs gleichzeitig einzureichen.

• Session-Modus: Ein dediziertes Fenster für die Ausführung einer Multi-Job-Workload. Dies ermöglicht es Nutzern, mit Variationsalgorithmen auf vorhersehbarere Weise zu experimentieren und sogar mehrere Experimente gleichzeitig auszuführen, indem die Parallelität im Stack genutzt wird. Verwende Sessions für iterative Workloads oder Experimente, die dedizierten Zugang erfordern. Beispiele findest du unter „Jobs in einer Session ausführen".

Für ein QAOA-Experiment wäre eine Session eine gute Wahl, wenn du Zugang dazu hast, da wir unseren Circuit viele Male mit verschiedenen Parameterwerten abtasten müssen, um das Optimum zu finden.

Zurück zum Optimierungsproblem. Wir müssen bessere Werte für Gamma und Beta finden als nur unsere groben ersten Schätzungen. Das tun wir, indem wir unsere Kostenfunktion und diese anfänglichen Schätzungen in einen Scipy-Optimierer COBYLA einspeisen.

Hier siehst du den Wert der Kostenfunktion über die Iterationen. Er beginnt ein wenig unstetig und geht auf und ab, setzt sich dann aber auf einen niedrigen Wert. Wir werden die Werte verwenden, die Scipy gefunden hat und die der niedrigsten Auswertung der Kostenfunktion entsprechen.

Nachdem wir unsere Kostenfunktion durch das Finden besserer Parameterwerte reduzieren konnten, werden wir unseren Circuit mit den neuen Werten, die wir für Gamma und Beta gefunden haben, ausführen. Ich habe die spezifischen Werte, die ich hier verwende, aufgelistet, aber denk daran: Wenn du das selbst ausprobierst oder sogar das gleiche Tutorial-Notebook erneut ausführst, könnten sich diese Werte leicht ändern. Nun führen wir unseren optimierten Circuit mit diesen Werten aus und finden unsere Kandidatenlösung für unser Max-Cut-Problem.

In der Nachverarbeitungsphase werden wir die Daten analysieren und diese Ergebnisse anzeigen, um zu sehen, ob unser Quantenalgorithmus die richtigen Lösungen gefunden hat.

Nachverarbeiten (Post-process)

Lass uns nun ein Histogramm der Daten plotten, um die endgültige Lösung anzusehen:

Die Bitstrings stellen dar, wie jeder der Knoten durch den Schnitt in zwei Gruppen (als „0" und „1" bezeichnet) aufgeteilt wurde. Es sollte vier Lösungen geben, die alle den maximalen Wert geschnittener Kanten ergeben. Diese vier sind in Violett dargestellt. Du kannst sofort sehen, dass 4 Lösungen viel wahrscheinlicher sind als alle anderen. Der wahrscheinlichste Bitstring ist 0,1,0,1,1. (Denk daran – die Reihenfolge der Qubits ist in den Plot-Bitstrings umgekehrt!)

Aus diesem Plot können wir den wahrscheinlichsten Bitstring nehmen und ihn als partitionierten Graphen darstellen, mit dem Schnitt durch fünf Kanten:

Das ist also tatsächlich eine Max-Cut-Lösung. Aber es ist nicht die einzige! Wegen der Symmetrie dieses Graphen gibt es mehrere richtige Lösungen. Anstatt die Knoten 0 und 3 innerhalb des Schnitts zu haben, könnten wir die Knoten 2 und 4 einschließen. Du kannst sehen, dass ich lediglich meinen Schnitt drehen musste, um diese neuen Punkte einzuschließen. Die Anzahl der geschnittenen Kanten bleibt fünf. Es gibt insgesamt vier Max-Cut-Lösungen, da jede der beiden Lösungen, die wir notiert haben, auch einen „entgegengesetzten" Partner hat, bei dem die violetten Knoten grau und die grauen Knoten violett sind – sodass der Schnitt gleich bleibt, aber jeder Knoten effektiv auf die andere Seite der Partition wechselt.

Schauen wir uns das Histogramm und die vier wahrscheinlichsten Lösungen nochmals kurz an. Idealerweise würden es jeweils die vier echten Max-Cut-Lösungen sein. Das Problem ist, dass der Algorithmus die vierte und letzte Lösung tatsächlich nicht als eine der vier wahrscheinlichsten Antworten identifiziert hat. Sie war die fünftwahrscheinlichste. Die vierte Lösung, die der Algorithmus identifizierte, ist falsch – wenn du sie zeichnen würdest, würdest du sehen, dass die Lösung nur vier Schnitte hat.

Aber denk daran: Das ist ein Näherungsalgorithmus. Er ist nicht unfehlbar und nicht zu 100% korrekt. Du musst etwas von deinem eigenen Wissen und Verständnis einbringen, um die Lösungen zu überprüfen.

Dieser Fehler kann aus mehreren Quellen entstehen:

1. Es könnte an der Näherungsnatur des Algorithmus selbst liegen, sowie an der kleinen Anzahl von Schichten, die ich verwendet habe.
2. Es könnte sich um einen endlichen Stichprobenfehler handeln; dieser könnte reduziert werden, wenn ich die Anzahl der Shots in meinem Experiment erhöhe.
3. Es könnte auch ein Auslesefehler sein, da die vierte echte Lösung nur um ein Bit abweicht.

Diese Art von Fehleranalyse ist es, was nötig ist, um ein Praktiker des Quantencomputings zu werden. Du musst die Leistung der Hardware verstehen und wissen, wie diese zu bestimmten Arten von Fehlern beitragen kann und wie man diese korrigiert.

Vergessen wir jedoch nicht, dass es 32 mögliche Bitstrings gab, und dass die vier echten Lösungen unter den fünf besten Kandidaten waren. Und wir haben nur zwei Schichten verwendet, um das zu finden. Wenn wir im Allgemeinen unsere Chancen erhöhen wollten, jedes Mal den besten Max-Cut zu finden, könnten wir die Schichttiefe erhöhen. Dabei gibt es einige Feinheiten, aber das ist Stoff für eine spätere Lektion.

Im Utility-Maßstab

Jetzt, da du einen Vorgeschmack auf den Prozess der Lösung eines kleinen Max-Cut-Problems auf einem Quantencomputer bekommen hast, fordere ich dich heraus, es im großen Maßstab zu tun. Folge dem verlinkten Tutorial, um zu sehen, wie viele Schnitte du in einem 125-Knoten-Graphen erzielen kannst.