Quantum Annealing ist ein anderes Modell des Quantencomputings als alles andere auf dieser Seite. Es gibt keine Schaltung, keine Gatter, keinen Grover und keinen Shor-Algorithmus, der auf der Hardware läuft. Ein Annealer löst genau eine Form von Problem, Optimierung, indem er das Problem direkt in die Physik der Hardware kodiert und das System sich in eine energetisch niedrige Antwort einpendeln lässt.
Diese Anleitung formuliert dasselbe Max-Cut-Problem aus unserer QAOA-Anleitung als Annealing-Aufgabe, löst sie kostenlos mit D-Waves Ocean SDK und behandelt den praktischen Fehler, den fast jeder beim Übergang von einem Spielzeugbeispiel zu echter Hardware macht.
Die physikalische Idee
Ein Optimierungsproblem wird auf ein System von Qubits abgebildet, sodass die energetisch niedrigste Konfiguration des Systems, sein Grundzustand, der besten Lösung entspricht. Die Qubits starten in einem leicht vorzubereitenden Zustand und entwickeln sich langsam hin zum Energieprofil des Problems. Das adiabatische Theorem ist das, was das funktionieren lässt: Ein Quantensystem, das in seinem Grundzustand startet, bleibt während der Entwicklung im Grundzustand, solange die Entwicklung im Verhältnis zu den Energielücken des Systems langsam genug erfolgt. Liest man die Qubits am Ende aus, erhält man eine energetisch niedrige, hoffentlich optimale Lösung.
Das unterscheidet sich grundlegend vom Gate-basierten Computing. Eine Gate-basierte QPU führt eine beliebige, von dir festgelegte Abfolge von Operationen aus. Ein Annealer führt einen einzigen festen Prozess aus, physisches Entspannen zu einem Minimum hin, und der einzige Einfluss, den du hast, ist, wie das Problem in dieses Energieprofil kodiert wird.
Max-Cut als QUBO formulieren
Annealer lösen Probleme, die als QUBO (Quadratic Unconstrained Binary Optimization) formuliert sind: Minimiere einen Ausdruck binärer Variablen x_i ∈ {0, 1} mit ausschließlich linearen und paarweisen quadratischen Termen, ohne Terme höherer Ordnung.
Für Max-Cut trägt jede Kante (i, j) 2·x_i·x_j − x_i − x_j zur Zielfunktion bei. Geh die vier Fälle durch: Wenn x_i und x_j übereinstimmen (beide auf derselben Seite), ist dieser Term 0. Wenn sie sich unterscheiden (die Kante ist geschnitten), ist der Term −1. Die Summe über alle Kanten zu minimieren maximiert daher die Anzahl geschnittener Kanten, genau das Max-Cut-Ziel, umformuliert als Minimierung.
Mit demselben Vier-Knoten-Kreisgraphen wie in der QAOA-Anleitung:
import dimod
from neal import SimulatedAnnealingSampler
edges = [(0, 1), (1, 2), (2, 3), (3, 0)]
Q = {}
for i, j in edges:
Q[(i, i)] = Q.get((i, i), 0) - 1
Q[(j, j)] = Q.get((j, j), 0) - 1
Q[(i, j)] = Q.get((i, j), 0) + 2
bqm = dimod.BinaryQuadraticModel.from_qubo(Q)
Jede Kante in diesem Graphen wird gleichzeitig geschnitten, der Graph ist bipartit: {0, 2} gegen {1, 3}, sodass die Grundzustandsenergie exakt bei −4 liegt, ein Beitrag von −1 pro Kante. Diese Zahl ergibt sich direkt aus der Konstruktion des QUBO, nicht aus einem bereits ausgeführten Lauf, und das ist das Ziel, das der Sampler unten zu erreichen versucht.
Das kostenlos mit Simulated Annealing lösen
D-Waves Ocean SDK bringt neal mit, einen klassischen Simulated-Annealing-Sampler, der vollständig auf der eigenen Maschine läuft, ohne QPU-Konto, ohne Warteschlange, ohne Kosten. Das ist auch der Standard-Einstiegsschritt, um ein Annealing-Problem zu entwickeln, bevor man überhaupt echte Hardware anfasst, dieselbe Rolle, die AerSimulator an anderer Stelle auf dieser Seite für Gate-basierte Schaltungen spielt.
sampler = SimulatedAnnealingSampler()
sampleset = sampler.sample(bqm, num_reads=1000)
best = sampleset.first
print(best.sample, best.energy)
num_reads=1000 führt den Annealing-Prozess 1.000 Mal unabhängig aus und behält jedes Ergebnis, denn simuliertes wie echtes Quantum Annealing sind heuristisch: Kein einzelner Lauf garantiert, im Grundzustand zu landen, weshalb ein Bündel von Durchläufen und das Ergebnis mit der niedrigsten Energie darunter das Standardvorgehen ist. Für diesen Graphen landet best.energy erwartungsgemäß bei −4, wobei best.sample eine der beiden äquivalenten Zweiteilungen ausliest, {0, 2} auf der einen Seite und {1, 3} auf der anderen, oder umgekehrt. Beide sind gültig: Max-Cut kennt keinen Begriff davon, welche Seite "zuerst" kommt, das ist also eine echte Symmetrie im Problem, kein Fehler im Sampler.
Der Fehler: Das Embedding ignorieren
Alles oben läuft auf einem klassischen Simulated Annealer, der keine Konnektivitätsgrenzen kennt: Jede Variable interagiert frei mit jeder anderen. Echte D-Wave-Hardware funktioniert anders. Physische Qubits sitzen auf einer festen, dünn besetzten Topologie (Pegasus oder Zephyr, je nach Generation), und die meisten Qubit-Paare sind schlicht nicht direkt miteinander verdrahtet.
Um ein Problem zu platzieren, bei dem Variable i mit Variable j interagieren muss, aber kein physisches Qubit-Paar diese Verbindung bereitstellt, verkettet Oceans Minor-Embedding-Schritt mehrere physische Qubits, damit sie als eine logische Variable fungieren. Das läuft automatisch, EmbeddingComposite aus dwave-system übernimmt den Prozess, aber der Prozess ist nicht kostenlos: Ketten brauchen zusätzliche Qubits, und eine Kette "bricht" manchmal, die physischen Qubits, die eigentlich übereinstimmen sollen, landen nach dem Annealing bei unterschiedlichen Werten und verfälschen so unbemerkt das Auslesen dieser Variable. Größere oder dichtere Probleme brauchen längere Ketten, die häufiger brechen, und ausreichend dichte Probleme lassen sich auf einem gegebenen Chip irgendwann gar nicht mehr einbetten. Das ist die häufigste Überraschung für alle, die zum ersten Mal ein funktionierendes Simulated-Annealing-Problem auf echte Hardware übertragen: Der Algorithmus wurde nicht schlechter, die physische Konnektivität des Chips wurde zum Engpass.
Was Annealing nicht leistet
Ein Annealer führt keine Grover-Suche aus, keine Shor-Faktorisierung, und kennt überhaupt keinen allgemeinen Begriff von "Schaltung". Seine Qubits sind nicht direkt mit Gate-basierten Qubits vergleichbar: D-Waves Systeme haben über 5.000 Qubits, weit mehr als jede Gate-basierte QPU, aber diese Zahl beschreibt speziell die Optimierungskapazität auf der Problemklasse QUBO/Ising, nicht allgemeine Rechenleistung. Ob Annealing gegenüber den besten klassischen Optimierungsheuristiken bei praktischen Problemen einen echten Geschwindigkeitsvorteil liefert, bleibt in der Fachliteratur ernsthaft umstritten und scheint stark von der jeweiligen Problemstruktur abzuhängen, nichts, das man standardmäßig annehmen sollte.
Ausführung auf echter D-Wave-Hardware
Den Sampler austauschen, der Rest des Codes bleibt identisch:
from dwave.system import DWaveSampler, EmbeddingComposite
sampler = EmbeddingComposite(DWaveSampler())
sampleset = sampler.sample(bqm, num_reads=1000)
D-Waves Leap-Cloud-Dienst bietet ein kostenloses monatliches Kontingent an QPU-Zeit genau für diese Art von Experimenten an, das Annealing-Äquivalent zu IBM Quantums kostenlosem Tarif für Gate-basierte Hardware. EmbeddingComposite übernimmt den Minor-Embedding-Schritt automatisch, aber prüfe das zurückgegebene sampleset.info auf Statistiken zu Kettenbrüchen, bevor du einem Ergebnis jenseits eines kleinen Spielzeugproblems vertraust.
Nächste Schritte
- QAOA-Anleitung: der Gate-basierte Ansatz für dasselbe Max-Cut-Problem
- Glossareintrag Quantum Annealing: das Konzept in Kürze
- D-Waves Dual-Rail-Erasure-Qubit-Gatter: D-Waves Schritt in Richtung Gate-basierter Hardware neben seiner Annealing-Linie
- Glossar: QAOA, Quantenvorteil und der Rest des Vokabulars