QAOA im Versorgungsmaßstab

Sehen Sie sich das Video von Olivia Lanes zum Thema QAOA im Großmaßstab an oder öffnen Sie das Video in einem separaten Fenster unter YouTube.

---

Lektionsübersicht:

Wir hoffen, dass wir Ihnen in diesem Kurs eine solide Grundlage für den Rahmen und die Werkzeuge vermittelt haben, die Sie benötigen, um Probleme im großen Maßstab auf einem Quantencomputer zu lösen. Jetzt werden wir diese Werkzeuge endlich in Aktion sehen.

In dieser Lektion beschäftigen wir uns mit einem Beispiel aus der Praxis für das Max-Cut-Problem, einem bekannten Problem der Graphentheorie, bei dem es darum geht, wie man einen Graphen am besten in zwei Teile aufteilt. Wir beginnen mit einem einfachen Graphen mit fünf Knoten, um ein Gefühl dafür zu bekommen, wie ein Quantencomputer uns bei der Lösung des Problems helfen kann, und wenden dies dann auf eine groß angelegte Version des Problems an.

Diese Lektion bietet einen allgemeinen Überblick über unseren Lösungsansatz für dieses Problem. Dies wird keine detaillierte Code-Erläuterung sein. Zu dieser Lektion gibt es jedoch ein Tutorial mit konkretem Code, den Sie ausführen können, um das Max-Cut-Problem auf einem Quantencomputer zu lösen.

---

Das Problem

Zur Erinnerung: Nicht alle Rechenprobleme sind für das Quantencomputing geeignet. "Einfache Probleme" werden von dieser Technologie nicht profitieren, weil klassische Computer sie bereits sehr gut lösen können.

Die drei Anwendungsfälle, denen wir am optimistischsten entgegensehen, sind:

1. simulation der Natur
2. verarbeitung von Daten mit komplexer Struktur
3. Optimierung

Heute werden wir uns auf den dritten Anwendungsfall konzentrieren, die Optimierung. Bei einem Optimierungsproblem suchen wir im Allgemeinen nach dem größt- oder kleinstmöglichen Wert für eine bestimmte Funktion. Die Schwierigkeit, diese Extrema mit klassischen Methoden zu finden, kann mit zunehmender Größe des Problems exponentiell ansteigen.

Das Optimierungsproblem, das uns heute interessiert, wird als „Max-Cut“ bezeichnet. Wir werden es mithilfe eines Algorithmus lösen, der als „Quantum Approximate Optimization Algorithm“ (QAOA) bekannt ist.

Was ist Max-Cut?

Wir beginnen mit einem Graphen, der aus einer Menge von Knoten besteht, von denen einige durch Kanten miteinander verbunden sind. In der Aufgabe sollen wir die Knoten des Graphen in zwei Teilmengen aufteilen, indem wir die Kanten, die sie verbinden, „durchtrennen“. Wir wollen die Teilung finden, die die Anzahl der auf diese Weise durchtrennten Kanten maximiert – daher der Name „Max-Cut“

Die obige Abbildung zeigt beispielsweise einen Graphen mit fünf Knoten, wobei rechts die Max-Cut-Lösung dargestellt ist. Es schneidet fünf Kanten, was das Beste ist, was man bei diesem Graphen erreichen kann.

Da ein Graph mit fünf Knoten so klein ist, fällt es nicht allzu schwer, den Max-Cut im Kopf zu berechnen oder durch Ausprobieren einiger Schnitte auf einem Blatt Papier zu ermitteln. Aber wie Sie sich vorstellen können, wird das Problem mit zunehmender Anzahl von Knoten immer schwieriger – unter anderem, weil die Anzahl der zu berücksichtigenden möglichen Schnitte exponentiell mit der Anzahl der Knoten wächst. Und ab einem bestimmten Punkt wird dies selbst für Supercomputer mit den bekannten klassischen Algorithmen schwierig.

Wir suchen nach einer Möglichkeit, das Max-Cut-Problem für diese größeren, komplexeren Graphen zu lösen, da das Problem zahlreiche praktische Anwendungsbereiche hat, darunter Betrugsaufdeckung im Finanzwesen, Graph-Clustering, Netzwerkdesign und die Analyse sozialer Medien. Max-Cut taucht häufig als Teilproblem innerhalb eines bestimmten Lösungsansatzes für ein größeres Problem auf. Das kommt also viel häufiger vor, als wir naiv annehmen würden.

---

Lösung

Nun werden wir den Ansatz durchgehen, den wir zur Lösung des Max-Cut-Problems auf einem Quantencomputer verwenden. Wir werden dies anhand eines einfachen Graphen mit fünf Knoten veranschaulichen. Sie können die Schritte mithilfe des Python-Notebook-Tutorials nachvollziehen. Nach diesem einfachen Beispiel führt Sie das Tutorial durch ein Beispiel für die Anwendung des Problems im industriellen Maßstab.

Der erste Schritt besteht darin, unseren Graphen zu erstellen, indem wir die Anzahl der Knoten und die Kanten, die zwei Knoten verbinden, festlegen. Sie können dies tun, indem Sie ein Paket mit dem Namen rustworkx importieren, wie im Lehrgang gezeigt. Das Ergebnis wird ein Diagramm sein, das wie folgt aussieht:

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

Zuordnung

Wir müssen das Problem auf unserem Quantencomputer abbilden. Dazu sei zunächst angemerkt, dass die Maximierung der Anzahl von Schnitten in einem Graphen mathematisch wie folgt beschrieben werden kann:

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

Dabei sind $i$ und $j$ Knoten im Graphen, und $x_i$ und $x_j$ sind entweder 0 oder 1, je nachdem, auf welcher Seite der Partition sich der jeweilige Knoten befindet (eine Gruppe ist mit "0" und eine mit "1" gekennzeichnet). Wenn $x_i$ und $x_j$ auf der gleichen Seite der Trennwand liegen, ist der Ausdruck in der Summe gleich Null. Wenn sie sich auf gegenüberliegenden Seiten befinden, also ein Schnitt zwischen ihnen liegt, ist der Ausdruck gleich eins. Wenn man also die Anzahl der Schnitte maximiert, wird die Summe maximiert.

Wir können dies 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}$$

Jetzt sind wir bereit für die Kartierung. Es kann ziemlich entmutigend sein, darüber nachzudenken, wie man von einem Graphen wie dem, den wir gerade gezeichnet haben, zu einem Quantenschaltkreis kommt. Aber wir werden einen Schritt nach dem anderen machen.

Denkt daran: Wir werden versuchen, das Max-Cut-Problem mit QAOA zu lösen. In der QAOA-Methodik streben wir letztlich einen Operator (oder, mit anderen Worten, einen Hamilton-Operator) an, der zur Darstellung der Kostenfunktion unseres hybriden Algorithmus dient, sowie einen parametrisierten Schaltkreis (den Ansatz), mit dem wir mögliche Lösungen für das Problem darstellen.

QUBO

Wir können aus diesen Lösungsvorschlägen eine Stichprobe ziehen und sie dann anhand der Kostenfunktion bewerten. Dazu nutzen wir eine Reihe von mathematischen Umformulierungen, darunter die Notation der Quadratic Unconstrained Binary Optimization - kurz QUBO -, die eine nützliche Methode zur Kodierung kombinatorischer Optimierungsprobleme darstellt. In QUBO wollen wir finden:

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

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

Um QAOA anzuwenden, müssen wir unser Problem als Hamiltonian formulieren - das ist eine Funktion oder Matrix, die die Gesamtenergie eines Systems darstellt. Konkret wollen wir einen Hamiltonian der Kostenfunktion 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 herzustellen. Eine Stichprobe aus diesem Zustand ergibt dann mit hoher Wahrscheinlichkeit die Lösung für $\min 𝑓(𝑥)$.

Abbildung auf eine Kostenfunktion Hamilton

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

Um das QUBO-Problem als Ising-Hamiltonian darzustellen, müssen wir eigentlich nur eine einfache Variablenumstellung von $x \in \{0, 1\}^n$ auf $z \in \{-1, 1\}^n$ vornehmen:

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

• Details zu

  Zunächst ist zu beachten, dass wir unseren QUBO-Ausdruck als Summe von Matrixtermen umschreiben können:

  $$x^TQx = \sum_{ij}Q_{ij}x_ix_j$$

  Wendet man die Variablenänderung an, so ergibt sich

  $$\sum_{ij}Q_{ij}(\frac{1-z_i}{2})(\frac{1-z_j}{2}) = \sum_{ij}\frac{Q_{ij}}{4}(1 - z_i - z_j + z_iz_j)$$

  was sich wie folgt umformulieren lässt.

  $$\sum_{ij}\frac{Q_{ij}}{4}z_iz_j - \frac{Q_{ij}}{4}z_i - \frac{Q_{ij}}{4}z_j + \frac{Q_{ij}}{4}$$

  Wir können den Konstantenausdruck weglassen, da er keinen Einfluss darauf hat, welches „ $z$ “ das QUBO-Problem minimiert. Zudem können wir diesen Ausdruck mit vier multiplizieren, um den ursprünglichen Wert von $Q$ wiederherzustellen, da dies ebenfalls keinen Einfluss auf die optimale Wahl von $z$ hat.

  $$\sum_{ij}Q_{ij}z_iz_j - Q_{ij}z_i - Q_{ij}z_j = z^TQz + (-\sum_{ij} Q_{ij}z_i + Q_{ij}z_j)$$

  Indem wir gleichartige lineare Terme zusammenfassen, können wir unseren linearen Koeffizientenvektor $b$ mithilfe der folgenden Gleichung definieren:

  $$b_i = -\sum_{j} Q_{ij} + Q_{ji}$$

  Damit ist die Umformung der Variablen zu „ $z \in \{-1, 1\}^n$ “ abgeschlossen, nachdem man in die vorherige Gleichung eingesetzt hat.

  $$z^TQz + b^Tz$$

Letztendlich entspricht die Minimierung des QUBO-Ausdrucks der Minimierung dieses Ausdrucks, wobei $b$ ein reeller Skalar ist:

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

Nach einer weiteren leichten Umformung erhalten wir unseren Hamilton-Kostenfunktion, wobei das Minimum des Ausdrucks den Grundzustand darstellt und der Pauli-Z-Operator Z ist:

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

Nun, da wir unseren Hamiltonian haben, müssen wir ihn in Form von zweilokalen Pauli-ZZZ-Operatoren umschreiben, die wir leicht in Zwei-Qubit-Gatter in unserem Quantenschaltkreis umwandeln können. Am Ende haben wir sechs Objekte - oder Pauli-Strings -, die jeweils einer der sechs Kanten im Graphen entsprechen. Jedes der fünf Elemente in einer Zeichenkette steht für eine Operation an einem Knoten - die Identität, wenn der Knoten nicht mit dieser bestimmten Kante verbunden ist, und der Pauli-Z-Operator, wenn er es ist. In Qiskit werden Bitstrings, die Qubits darstellen, rückwärts indiziert. Zum Beispiel wird eine Kante zwischen den Knoten 0 und 1 als IIIZZ und eine Kante zwischen 2 und 4 als ZIZII kodiert.

Konstruieren Sie den Quantenschaltkreis

Nachdem wir unseren Hamiltonian in Form von Pauli-Operatoren geschrieben haben, können wir unseren Quantenschaltkreis konstruieren, der es uns ermöglicht, mit einem Quantencomputer gute Lösungen zu finden:

Der QAOA-Algorithmus stützt sich auf das Adiabatische Theorem, das besagt, dass, wenn wir im Grundzustand eines zeitabhängigen Hamiltonianers beginnen, sich der Hamiltonianer langsam genug entwickelt und genügend Zeit zur Verfügung steht, der Endzustand der Grundzustand des endgültigen Hamiltonianers sein wird. QAOA kann als diskrete, trotterisierte Version dieses quantenadiabatischen Algorithmus betrachtet werden, wobei jeder Trotterschritt eine Schicht des QAOA-Algorithmus darstellt. Anstatt sich also von einem Zustand zum anderen zu entwickeln, werden wir in jeder Schicht zwischen unserem Kostenfunktions-Hamiltonian und einem sogenannten "Mixer"-Hamiltonian hin- und herwechseln, den wir später in dieser Lektion behandeln werden.

Der Vorteil von QAOA ist, dass er schneller ist als der quantenadiabatische Algorithmus, aber er liefert Näherungslösungen und nicht die optimalen. Im Grenzfall, wenn die Anzahl der Schichten gegen unendlich geht, konvergiert QAOA zum QAA-Fall, aber das ist natürlich sehr rechenintensiv.

Um unsere Quantenschaltung zu erstellen, werden wir alternierende Operatoren anwenden, die durch $\gamma$ und $\beta$ parametrisiert sind und die Diskretisierung der zeitlichen Entwicklung darstellen.

Die drei Hauptbestandteile des QAOA-Kreislaufs sind also:

1. der anfängliche Versuchszustand (grau), der der Grundzustand des Mischers ist und durch Anwendung eines Hadamard-Gatters auf jedes Qubit erzeugt wird
2. die Entwicklung der Kostenfunktion, die wir bereits besprochen haben, in dunkelviolett
3. die Entwicklung unter dem Mischer-Hamiltonian, den wir noch nicht behandelt haben, in helllila.

Unser Start-Hamiltonian wird Mixer genannt, weil sein Grundzustand die Überlagerung aller möglichen Bitstrings von Interesse ist: Er erzwingt also zu Beginn eine Mischung aller möglichen Lösungen.

Der Mischer-Hamiltonian ist die einfache Summe der Pauli-X-Operationen an jedem Knoten des Graphen. Qiskit erlaubt es Ihnen, einen anderen, benutzerdefinierten Mixer-Operator zu verwenden, wenn Sie es wünschen, aber wir werden hier den Standardoperator verwenden. Sie sehen also, dass uns mit Qiskit ein Großteil der Arbeit abgenommen wird, so dass es trivial ist, den Mischer-Hamiltonian und den Ausgangszustand zu bestimmen. Die einzige Arbeit, die wir zu tun hatten, war, die Kostenfunktion zu finden.

Jede Iteration dieser Operatoren wird als Schicht bezeichnet. Diese Schichten können, wie bereits beschrieben, als Diskretisierung der zeitlichen Entwicklung des Systems betrachtet werden. Das alternierende Muster ergibt sich aus der Trotter-Zerlegung und approximiert die Exponentialfunktionen nichtkommutierender Matrizen. Im Allgemeinen gilt: Je mehr Schichten oder Schritte wir einbeziehen, desto näher kommen wir einer kontinuierlichen Zeitentwicklung, wie bei QAA, sodass das Ergebnis theoretisch umso genauer ausfällt. In diesem Beispiel beginnen wir jedoch zunächst mit nur einer Ebene. Denken Sie daran, dass sowohl der Hamilton-Operator der Kostenfunktion als auch der Mixer parametrisiert sind; wir müssen also noch optimale Werte für $\gamma$ und $\beta$ ermitteln.

Optimieren

Die Schaltung, die wir gerade erstellt haben, sieht zwar ziemlich einfach aus und ist nützlich, um ein intuitives Verständnis zu entwickeln, aber denken Sie daran, dass der Quantenchip nicht versteht, was das QAOA-Gatter ist. Wir müssen dies in eine Reihe von "nativen" Ein- und Zwei-Qubit-Gattern umwandeln, die direkt auf der Hardware ausgeführt werden können. Native Gatter sind Gatter, die direkt auf den Qubits ausgeführt werden können. Solche Schaltungen werden in der Instruction Set Architecture (ISA) des Backends geschrieben.

Die Qiskit-Bibliothek bietet eine Reihe von Transpilationspässen, die für eine Vielzahl von Schaltkreistransformationen geeignet sind. Wir wollen sicherstellen, dass die Schaltung für unseren Zweck optimiert ist.

Aus der vorangegangenen Lektion wissen Sie, dass der Umsetzungsprozess mehrere Schritte umfasst:

• Anfängliche Zuordnung der Qubits im Schaltkreis (d. h. der Entscheidungsvariablen) zu den physischen Qubits auf dem Gerät.
• Abwickeln der Befehle im Quantenschaltkreis zu den nativen Hardwarebefehlen, die das Backend versteht.
• Weiterleitung aller Qubits im Schaltkreis, die miteinander interagieren, an benachbarte physikalische Qubits.

Und wie immer finden Sie weitere Einzelheiten dazu in der Dokumentation.

Vor dem Transpilieren müssen wir jedoch auswählen, auf welchem Backend wir unsere Schaltung ausführen wollen, da der Transpiler für verschiedene Prozessoren unterschiedlich optimiert ist. Dies ist ein weiterer Grund, warum es wichtig ist, einen automatisierten Transpiler zu verwenden - Sie möchten nicht den zeitaufwändigen Prozess der manuellen Optimierung Ihrer Schaltung durchlaufen, nur um dann festzustellen, dass Sie Ihre Schaltung eigentlich auf einem anderen Prozessor mit anderen Eigenschaften betreiben wollen.

Übergeben Sie das Backend Ihrer Wahl an die Transpiler-Funktion und geben Sie Ihre Optimierungsstufe an. Im Lernprogramm wählen Sie Stufe 3, die höchste und gründlichste Stufe.

Und damit haben wir eine umgesetzte Schaltung, die bereit ist, auf der Hardware ausgeführt zu werden!

Ausführen

Bisher haben wir die Schaltung transpiliert, ohne die Parameter Gamma und Beta zu ändern – doch ohne die Angabe dieser Parameter lässt sich die Schaltung nicht ausführen. Im QAOA-Workflow werden die optimalen QAOA-Parameter in einer iterativen Optimierungsschleife ermittelt, in der wir eine Reihe von Schaltungsauswertungen durchführen und anschließend mithilfe eines klassischen Optimierers die optimalen Parameter 𝛽 und 𝛾 ermitteln. Wir müssen jedoch irgendwo anfangen, daher nehmen wir zunächst folgende Werte als Ausgangspunkt: $\gamma=\pi/2$ und $\beta=\pi$.

Ausführungsmodi

Jetzt sind wir fast so weit, dass wir den Rundgang machen können - ich verspreche es! Zunächst ist es jedoch wichtig zu wissen, dass Sie Ihren Auftrag auf verschiedene Arten senden können, die als Ausführungsmodi bezeichnet werden.

• Auftragsmodus: Es wird eine einzelne Anforderung an die Estimator- oder Sampler-Primitive ohne Kontextmanager gestellt. Schaltkreise und Eingaben werden als „Primitive Unified Blocks“ (PUBs) gebündelt und als Ausführungsaufgabe an den Quantencomputer übermittelt.

• Batch-Modus: Ein Multi-Job-Manager für die effiziente Durchführung eines Experiments, das aus einem Bündel unabhängiger Aufträge besteht. Verwenden Sie den Batch-Modus, um mehrere primitive Aufträge gleichzeitig zu übermitteln

• Sitzungsmodus: Ein dediziertes Fenster für die Ausführung eines Multi-Job-Workloads. Dies ermöglicht es den Nutzern, mit Variationsalgorithmen in einer besser vorhersehbaren Weise zu experimentieren und sogar mehrere Experimente gleichzeitig durchzuführen, um die Parallelität im Stack zu nutzen. Verwenden Sie Sitzungen für iterative Workloads oder Experimente, die einen speziellen Zugriff erfordern. Beispiele finden Sie unter Aufträge in einer Sitzung ausführen.

Für ein QAOA-Experiment wäre eine Sitzung eine gute Wahl, wenn Sie Zugang dazu haben, da wir unsere Schaltung viele Male mit verschiedenen Parameterwerten testen müssen, um das Optimum zu finden.

Zurück zu dem Optimierungsproblem. Wir müssen bessere Werte für Gamma und Beta finden als nur unsere groben ersten Schätzungen. Wir werden dies tun, indem wir unsere Kostenfunktion und diese anfänglichen Schätzungen in einen scipy-Optimierer COBYLA einfügen.

Hier sehen Sie den Wert der Kostenfunktion über die Iterationen hinweg. Zu Beginn ist er etwas unruhig und geht auf und ab, pendelt sich dann aber auf einen niedrigen Wert ein. Wir verwenden die von scipy ermittelten Werte, die der niedrigsten Bewertung der Kostenfunktion entsprechen.

Nachdem wir nun unsere Kostenfunktion durch die Ermittlung besserer Werte für unsere Parameter optimieren konnten, werden wir unsere Schaltung mit den neuen Werten für Gamma und Beta ausführen. Ich habe hier die konkreten Werte aufgeführt, die ich verwende, aber denk daran: Wenn du dich selbst daran versuchst oder auch nur dasselbe Tutorial-Notebook erneut ausführst, können sich diese Werte geringfügig ändern. Nun lassen wir unseren optimierten Algorithmus mit diesen Werten laufen und ermitteln unsere Lösungsvariante für unser Max-Cut-Problem.

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

Nachbearbeitung

Stellen wir nun ein Histogramm der Daten auf, um die endgültige Lösung zu betrachten:

Die Bitfolgen stellen dar, wie jeder der Knoten durch den Schnitt in zwei Gruppen (mit "0" und "1" gekennzeichnet) aufgeteilt wurde. Es sollte vier Lösungen geben, die alle den maximalen Wert des Kantenschnitts ergeben. Diese vier sind in lila dargestellt. Sie können sofort erkennen, dass 4 Lösungen viel wahrscheinlicher sind als alle anderen. Die höchste und damit wahrscheinlichste Lösung der Bitfolge ist 0,1,0,1,1. (Denken Sie daran, dass die Reihenfolge der Qubits in den Plot-Bitstrings vertauscht ist!)

Aus diesem Diagramm können wir den wahrscheinlichsten Bitstring als partitionierten Graphen darstellen, wobei der Schnitt durch fünf Kanten verläuft:

Das ist also tatsächlich eine Max-Cut-Lösung. Aber das ist nicht das einzige! Aufgrund der Symmetrie dieser Grafik gibt es mehrere richtige Lösungen. Anstatt die Knoten 0 und 3 in den Schnitt einzubeziehen, könnten wir stattdessen die Knoten 2 und 4 einbeziehen. Wie du siehst, musste ich lediglich meinen Schnitt drehen, um diese neuen Punkte einzubeziehen. Die Anzahl der geschnittenen Kanten bleibt bei fünf. Es gibt also insgesamt vier Max-Cut-Lösungen, da jede der beiden zuvor genannten Lösungen auch einen „entgegengesetzten“ Partner hat, bei dem die violetten Knoten grau und die grauen Knoten violett sind – der Schnitt bleibt also derselbe, aber jeder Knoten wechselt praktisch auf die entgegengesetzte Seite der Teilung.

Schauen wir uns noch einmal kurz das Histogramm und die vier wahrscheinlichsten Lösungen an. Im Idealfall wären dies alle vier echten Max-Cut-Lösungen. Das Problem ist, dass der Algorithmus die vierte und letzte Lösung tatsächlich nicht als eine der vier wahrscheinlichsten Antworten identifiziert hat. Es war die fünftwahrscheinlichste Möglichkeit. Die vierte Lösung, die der Algorithmus ermittelt hat, ist falsch – wenn man sie zeichnen würde, würde man sehen, dass die Lösung nur vier Schnitte aufweist.

Aber denken Sie daran: Dies ist ein Näherungsalgorithmus. Sie ist nicht unfehlbar, und sie ist auch nicht zu 100 % korrekt. Sie müssen einen Teil Ihres eigenen Wissens und Verständnisses einsetzen, um die Lösungen auf ihre Tauglichkeit hin zu überprüfen.

Dieser Fehler kann an mehreren Stellen auftreten:

1. Das könnte an der ungefähren Natur des Algorithmus selbst liegen und an der geringen Anzahl der von mir verwendeten Ebenen.
2. Es könnte sich um einen endlichen Stichprobenfehler handeln, der sich verringern ließe, wenn ich die Anzahl der Aufnahmen in meinem Experiment erhöhe.
3. Es könnte sich auch um einen Auslesefehler handeln, da die vierte echte Lösung nur um ein Bit abweicht.

Diese Art der Fehleranalyse ist das, was man braucht, um ein Praktiker des Quantencomputers zu werden. Sie müssen die Leistung der Hardware verstehen und wissen, wie diese zu bestimmten Fehlern beitragen kann und wie man sie korrigieren kann.

Wir sollten jedoch nicht vergessen, dass es 32 mögliche Bitfolgen gab und dass die vier tatsächlichen Lösungen unter den fünf besten Kandidaten waren. Und dafür haben wir nur zwei Schichten verwendet. Generell gilt: Wenn wir unsere Chancen erhöhen wollen, jedes Mal den besten Max-Cut zu finden, könnten wir die Schichttiefe erhöhen. Das hat zwar einige Feinheiten, aber das behandeln wir in einer späteren Lektion.

---

Im Versorgungsmaßstab

Nachdem Sie nun einen ersten Eindruck davon gewonnen haben, wie man ein kleines Max-Cut-Problem auf einem Quantencomputer löst, fordere ich Sie auf, dies in größerem Maßstab zu versuchen. Folgen Sie der Anleitung unter dem Link, um zu sehen, wie viele Schnitte Sie in einem Graphen mit 125 Knoten erzielen können.