{
"cells": [
{
"cell_type": "markdown",
"id": "bc51e7bf-e582-49ba-93f8-035624d56ccf",
"metadata": {},
"source": [
"---\n",
"title: \"Näherungsweiser Quanten-Optimierungsalgorithmus\"\n",
"description: \"Lösen Sie das Max-Cut-Problem mithilfe von QAOA unter Verwendung eines Qiskit-Musters im industriellen Maßstab.\"\n",
"---\n",
"\n",
"{/* cspell:ignore frameon popcount fval */}\n",
"\n",
"\n",
"\n",
"# Näherungsweiser Quanten-Optimierungsalgorithmus\n",
"\n",
"*Geschätzte Nutzungsdauer: 22 Minuten auf einem Heron r3 Prozessor (HINWEIS: Dies ist nur eine Schätzung. Ihre Laufzeit kann variieren.)*\n",
"\n"
]
},
{
"cell_type": "markdown",
"id": "learning-outcomes-prereqs",
"metadata": {},
"source": [
"\n",
"\n",
"## Lernziele\n",
"\n",
"* Wie man ein klassisches kombinatorisches Optimierungsproblem (Max-Cut) auf einen Quanten-Hamiltonian abbildet\n",
"* So implementieren und führen Sie den Quantum Approximate Optimization Algorithm (QAOA) mithilfe von Sitzungen des „ IBM Quantum “-Compute-Service aus\n",
"* Wie man einen QAOA-Workflow von einem kleinen Simulatorbeispiel auf die Ausführung auf Hardware im industriellen Maßstab skaliert\n",
"\n",
"\n",
"\n",
"## Voraussetzungen\n",
"\n",
"* [Grundlagen von Quantenschaltungen](/learning/courses/basics-of-quantum-information)\n",
"* [Variationsalgorithmen](/learning/courses/variational-algorithm-design)\n",
"* [QAOA im Detail](/learning/courses/quantum-computing-in-practice/utility-scale-qaoa) – eine umfassende Darstellung des QAOA-Algorithmus und seiner Anwendung im großtechnischen Maßstab\n",
"\n"
]
},
{
"cell_type": "markdown",
"id": "de201dbb",
"metadata": {},
"source": [
"\n",
"\n",
"## Hintergrund\n",
"\n",
"Der **Quantum Approximate Optimization Algorithm (QAOA)** ist ein hybrides, iteratives Verfahren, das Quanten- und klassische Methoden kombiniert, um kombinatorische Optimierungsprobleme zu lösen. In diesem Tutorial werden Sie QAOA einsetzen, um das **Maximum-Cut-** Problem (Max-Cut) zu lösen – ein NP-schweres Optimierungsproblem mit Anwendungen in den Bereichen Clustering, Netzwerkwissenschaft und statistische Physik. Gegeben sei ein Graph aus Knoten, die durch Kanten verbunden sind. Das Ziel besteht darin, die Knoten in zwei Mengen zu unterteilen, sodass die Anzahl der Kanten, die die Teilung kreuzen, maximiert wird.\n",
"\n",
"Die kombinatorische Optimierung spielt auch bei Herausforderungen im Bereich der Nachhaltigkeit eine Rolle, beispielsweise bei der Planung von Lieferrouten zur Senkung des Kraftstoffverbrauchs und bei der Zuweisung von Ressourcen zur Vermeidung von Materialverschwendung. Das Max-Cut-Beispiel vermittelt, wie man ein Ziel als Kosten-Hamiltonian formuliert und mit QAOA mögliche Lösungen untersucht. Um diesen Ansatz auf ein Nachhaltigkeitsproblem anzuwenden, sind ein Ziel und Randbedingungen erforderlich, die die beabsichtigte Anwendung widerspiegeln.\n",
"\n",
"\n",
"\n",
"\n",
"\n",
"### Von der klassischen Optimierung zu Quantenschaltungen\n",
"\n",
"Max-Cut lässt sich als klassisches binäres Optimierungsproblem formulieren. Jedem Knoten wird eine binäre Variable „ $x_i \\in \\{0, 1\\}$ “ zugewiesen, die angibt, zu welcher Menge er gehört. Das Ziel besteht darin, die Anzahl der Kanten zu maximieren, deren Endpunkte zu unterschiedlichen Mengen gehören:\n",
"\n",
"$$\n",
"\\max_{x \\in \\{0,1\\}^n} \\sum_{(i,j)} x_i + x_j - 2x_ix_j.\n",
"$$\n",
"\n",
"Dies entspricht einem **quadratischen, uneingeschränkten binären** Optimierungsproblem (QUBO) der Form $\\min_x\\, x^T Q x$. Durch eine Standard-Variablensubstitution ( $x_i \\to (1 - Z_i)/2$ ) lässt sich das QUBO als **Kostenhamiltonian** umschreiben, dessen Grundzustand die optimale Lösung kodiert. Im Allgemeinen enthält dieser Hamilton-Operator sowohl quadratische als auch lineare Terme:\n",
"\n",
"$$\n",
"H_C = \\sum_{ij} Q_{ij} \\, Z_i Z_j + \\sum_i b_i \\, Z_i.\n",
"$$\n",
"\n",
"Für das hier betrachtete ungewichtete Max-Cut-Problem gehen die linearen Koeffizienten gegen Null ( $b_i = 0$ ) und gilt für jede Kante $Q_{ij} = 1$, was die einfachere Form $H_C = \\sum_{(i,j) \\in E} Z_i Z_j$ ergibt, die Sie im folgenden Code umsetzen werden. Die oben genannte allgemeinere Form ist das, was Sie benötigen, um diesen Arbeitsablauf an gewichtete Graphen oder andere QUBO-darstellbare Probleme anzupassen.\n",
"\n",
"\n",
"\n",
"### So funktioniert QAOA\n",
"\n",
"QAOA erstellt Lösungsvorschläge, indem es abwechselnd Schichten zweier Operatoren auf einen anfänglichen Überlagerungszustand $H^{\\otimes n}|0\\rangle$ anwendet: den **Kostenoperator** $e^{-i\\gamma_k H_C}$ und einen **Mischoperator** $e^{-i\\beta_k H_m}$. Die Winkel $\\gamma_k$ und $\\beta_k$ werden in einer klassischen Rückkopplungsschleife optimiert; der Quantencomputer berechnet die Kostenfunktion, und ein klassischer Optimierer aktualisiert die Parameter bis zur Konvergenz. Diese iterative Schleife wird innerhalb einer Quantum-Compute- **Sitzung** ausgeführt, wodurch das Quantencomputer-Gerät über alle Iterationen hinweg reserviert bleibt, um eine geringere Latenz zu gewährleisten.\n",
"\n",
"\n",
"\n",
"Eine ausführlichere Darstellung der QAOA-Theorie, einschließlich der vollständigen Herleitung vom QUBO zum Hamilton-Operator, finden Sie im [QAOA-Kursmodul](/learning/courses/utility-scale-quantum-computing/variational-quantum-algorithms#1-introduction).\n",
"\n",
"In diesem Tutorial lösen Sie zunächst das Max-Cut-Problem an einem kleinen Graphen mit fünf Knoten und skalieren anschließend denselben Arbeitsablauf auf ein Problem im industriellen Maßstab mit 100 Knoten auf echter Hardware. *Hinweis zum Tarifzugang:* In diesem Tutorial werden Quantum Compute [-Sitzungen](/docs/guides/execution-modes#session-mode) verwendet, die nur im Premium-Tarif verfügbar sind. Wenn Sie den „Open Plan“-Tarif nutzen, können Sie dieses Tutorial nicht wie beschrieben ausführen; stattdessen müssen Sie `Session` auf [den](/docs/guides/execution-modes#job-mode) Job-Modus umstellen (d. h., jede Iteration als eigenständigen Job einreichen, anstatt die Optimierungsschleife mit zu umschließen `Session(...)`). Der Workflow läuft zwar weiterhin, aber bei jeder Iteration entsteht die volle Warteschlangenlatenz, anstatt ein reserviertes Gerät wiederzuverwenden. Weitere Informationen finden Sie unter „[Übersicht über die verfügbaren Tarife](/docs/guides/plans-overview) “.\n",
"\n"
]
},
{
"cell_type": "markdown",
"id": "381800e5",
"metadata": {},
"source": [
"\n",
"\n",
"## Anforderungen\n",
"\n",
"Bevor Sie mit diesem Tutorial beginnen, sollten Sie sicherstellen, dass Sie Folgendes installiert haben:\n",
"\n",
"* Qiskit SDK v2.0 oder höher, mit [Visual](/docs/api/qiskit/visualization) isierungsunterstützung\n",
"* Qiskit Runtime v0.22 oder später (`pip install qiskit-ibm-runtime`)\n",
"\n",
"Außerdem benötigen Sie Zugriff auf eine Instanz unter [IBM Quantum® Platform](/docs/guides/cloud-setup).\n",
"\n"
]
},
{
"cell_type": "markdown",
"id": "f5307376",
"metadata": {},
"source": [
"\n",
"\n",
"## Einrichtung\n",
"\n"
]
},
{
"cell_type": "code",
"execution_count": 1,
"id": "37b3acfc",
"metadata": {},
"outputs": [],
"source": [
"import matplotlib.pyplot as plt\n",
"import rustworkx as rx\n",
"from rustworkx.visualization import mpl_draw as draw_graph\n",
"import numpy as np\n",
"from scipy.optimize import minimize\n",
"from collections import defaultdict\n",
"from typing import Sequence\n",
"\n",
"\n",
"from qiskit.quantum_info import SparsePauliOp\n",
"from qiskit.circuit.library import QAOAAnsatz\n",
"from qiskit.transpiler.preset_passmanagers import generate_preset_pass_manager\n",
"\n",
"from qiskit_ibm_runtime import QiskitRuntimeService\n",
"from qiskit_ibm_runtime import Session, EstimatorV2 as Estimator\n",
"from qiskit_ibm_runtime import SamplerV2 as Sampler"
]
},
{
"cell_type": "markdown",
"id": "68fd0b4f-baa4-45dc-9f4c-d9cdff01a651",
"metadata": {},
"source": [
"\n",
"\n",
"## Ein kleines Beispiel\n",
"\n",
"In diesem Abschnitt wird jeder Schritt des QAOA-Workflows anhand einer kleinen Max-Cut-Instanz mit fünf Knoten erläutert. Trotz der Bezeichnung „im kleinen Maßstab“ läuft dieses Beispiel dennoch auf echter „ IBM Quantum “-Hardware – der Code wählt ein Backend mit 127 oder mehr Qubits aus und führt den Schaltkreis dort aus.\n",
"\n"
]
},
{
"cell_type": "markdown",
"id": "0cbca6cb",
"metadata": {},
"source": [
"Initialisieren Sie Ihr Problem, indem Sie einen Graphen mit $n=5$ Knoten erstellen.\n",
"\n"
]
},
{
"cell_type": "code",
"execution_count": 2,
"id": "6ced6bea",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
""
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"n_small = 5\n",
"\n",
"graph = rx.PyGraph()\n",
"graph.add_nodes_from(np.arange(0, n_small, 1))\n",
"edge_list = [\n",
" (0, 1, 1.0),\n",
" (0, 2, 1.0),\n",
" (0, 4, 1.0),\n",
" (1, 2, 1.0),\n",
" (2, 3, 1.0),\n",
" (3, 4, 1.0),\n",
"]\n",
"graph.add_edges_from(edge_list)\n",
"draw_graph(graph, node_size=600, with_labels=True)"
]
},
{
"cell_type": "markdown",
"id": "a06e4386-d7bd-4914-9baa-36a5cc60e3ab",
"metadata": {},
"source": [
"\n",
"\n",
"### Schritt 1: Klassische Eingaben einem Quantenproblem zuordnen\n",
"\n",
"Stelle den klassischen Graphen als **Quantenschaltungen** und **-operatoren** dar. Wie im [Hintergrund](#background) beschrieben, reduziert sich der Kosten-Hamiltonian für den ungewichteten Max-Cut auf $H_C = \\sum_{(i,j) \\in E} Z_i Z_j$, und QAOA verwendet eine parametrisierte Ansatzschaltung, um Kandidaten für Grundzustände von $H_C$ zu erzeugen.\n",
"\n"
]
},
{
"cell_type": "markdown",
"id": "a5b9e551-38a1-4543-b9f1-caaefb0ef3a9",
"metadata": {},
"source": [
"\n",
"\n",
"#### Erstellen Sie den Kostenhamiltonian\n",
"\n",
"Wandle die Kanten des Graphen in Pauli- $Z_iZ_j$ -Terme um, um die $H_C$ zu konstruieren (siehe [„Hintergrund“](#background) für die Herleitung).\n",
"\n"
]
},
{
"cell_type": "code",
"execution_count": 3,
"id": "52d1ba92",
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Cost Function Hamiltonian: SparsePauliOp(['IIIZZ', 'IIZIZ', 'ZIIIZ', 'IIZZI', 'IZZII', 'ZZIII'],\n",
" coeffs=[1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j])\n"
]
}
],
"source": [
"def build_max_cut_paulis(\n",
" graph: rx.PyGraph,\n",
") -> list[tuple[str, list[int], float]]:\n",
" \"\"\"Convert graph edges to a list of ZZ Pauli terms.\n",
"\n",
" The returned list is in the sparse format expected by\n",
" ``SparsePauliOp.from_sparse_list``: each element is\n",
" ``(pauli_string, qubit_indices, coefficient)``.\n",
" \"\"\"\n",
" pauli_list = []\n",
" for edge in list(graph.edge_list()):\n",
" weight = graph.get_edge_data(edge[0], edge[1])\n",
" pauli_list.append((\"ZZ\", [edge[0], edge[1]], weight))\n",
" return pauli_list\n",
"\n",
"\n",
"max_cut_paulis = build_max_cut_paulis(graph)\n",
"cost_hamiltonian = SparsePauliOp.from_sparse_list(max_cut_paulis, n_small)\n",
"print(\"Cost Function Hamiltonian:\", cost_hamiltonian)"
]
},
{
"cell_type": "markdown",
"id": "33f71b0d-4a2a-4082-8c1a-ce9d2b769048",
"metadata": {},
"source": [
"\n",
"\n",
"#### Bau die QAOA-Ansatzschaltung\n",
"\n"
]
},
{
"cell_type": "markdown",
"id": "00431c46-30c2-40f9-99df-40baf8da98f6",
"metadata": {},
"source": [
"Verwenden `QAOAAnsatz` Sie, um die parametrisierte QAOA-Schaltung aus dem Kosten-Hamilton-Operator zu konstruieren. Hier verwenden `reps=2` wir (zwei QAOA-Schichten, vier Parameter: $\\beta_0, \\beta_1, \\gamma_0, \\gamma_1$ ).\n",
"\n"
]
},
{
"cell_type": "code",
"execution_count": 4,
"id": "7bd8c6d4-f40f-4a11-a440-0b26d9021b53",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
""
]
},
"execution_count": 4,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"circuit = QAOAAnsatz(cost_operator=cost_hamiltonian, reps=2)\n",
"circuit.measure_all()\n",
"\n",
"circuit.draw(\"mpl\")"
]
},
{
"cell_type": "code",
"execution_count": 5,
"id": "315c495a",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"ParameterView([ParameterVectorElement(β[0]), ParameterVectorElement(β[1]), ParameterVectorElement(γ[0]), ParameterVectorElement(γ[1])])"
]
},
"execution_count": 5,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"circuit.parameters"
]
},
{
"cell_type": "markdown",
"id": "82f70daa-ff68-447a-8064-8b7df7a646cf",
"metadata": {},
"source": [
"\n",
"\n",
"### Schritt 2: Optimierung des Problems für die Ausführung auf Quantenhardware\n",
"\n"
]
},
{
"cell_type": "markdown",
"id": "c08be444-e3ed-4178-a10b-414069b1b411",
"metadata": {},
"source": [
"Die abstrakte Schaltung in hardwarenahe Befehle umwandeln. Dieser Schritt umfasst die Quantenbit-Zuordnung, die Gatterzerlegung, die Routing-Verarbeitung und die Fehlerunterdrückung. Weitere Informationen finden Sie in der [Dokumentation](/docs/guides/transpile) zur Transpilierung.\n",
"\n"
]
},
{
"cell_type": "code",
"execution_count": 6,
"id": "3f28a422-805c-4d3d-b5f6-62539e9133bd",
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"\n"
]
},
{
"data": {
"text/plain": [
""
]
},
"execution_count": 6,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"service = QiskitRuntimeService()\n",
"backend = service.least_busy(\n",
" operational=True, simulator=False, min_num_qubits=127\n",
")\n",
"print(backend)\n",
"\n",
"# Create pass manager for transpilation. Level 3 is the most aggressive\n",
"# preset: slower to transpile, but produces shorter circuits that are\n",
"# more robust to hardware noise.\n",
"pm = generate_preset_pass_manager(optimization_level=3, backend=backend)\n",
"\n",
"candidate_circuit = pm.run(circuit)\n",
"candidate_circuit.draw(\"mpl\", fold=False, idle_wires=False)"
]
},
{
"cell_type": "markdown",
"id": "4e75cad7-f599-4937-b5fe-f4d01f53423c",
"metadata": {},
"source": [
"\n",
"\n",
"### Schritt 3: Mit „ Qiskit primitives “ ausführen\n",
"\n"
]
},
{
"cell_type": "markdown",
"id": "9b99ce67-f121-4244-b62a-536be38fea86",
"metadata": {},
"source": [
"Die QAOA-Optimierungsschleife wird innerhalb einer Quantum Compute [-Sitzung](/docs/guides/execution-modes) ausgeführt, damit das Gerät über alle Iterationen hinweg reserviert bleibt. Ein Schätzer berechnet bei jedem Schritt $\\langle H_C \\rangle$, und ein klassischer Optimierer (COBYLA) aktualisiert die Parameter bis zur Konvergenz.\n",
"\n",
"\n",
"\n"
]
},
{
"cell_type": "markdown",
"id": "00b2b0f1-9bad-4ad3-b93e-5cbf40395dbf",
"metadata": {},
"source": [
"Legen Sie die Anfangsparameter fest und führen Sie die Optimierungsschleife aus:\n",
"\n"
]
},
{
"cell_type": "code",
"execution_count": 7,
"id": "afa5747f-44dc-4e41-a875-7b6f896f13e2",
"metadata": {},
"outputs": [],
"source": [
"# QAOA doesn't prescribe principled default angles — any bounded choice\n",
"# works as a warm start for problems this small. beta and gamma are\n",
"# periodic (beta in [0, pi] and gamma in [0, 2*pi] modulo the underlying\n",
"# Pauli-rotation periods), and pi/2 and pi are just midpoints of those\n",
"# ranges. For harder problems you would typically warm start from known\n",
"# good angles or transfer parameters from smaller instances.\n",
"initial_gamma = np.pi\n",
"initial_beta = np.pi / 2\n",
"init_params = [initial_beta, initial_beta, initial_gamma, initial_gamma]"
]
},
{
"cell_type": "code",
"execution_count": 8,
"id": "3e64a862",
"metadata": {},
"outputs": [],
"source": [
"def cost_func_estimator(params, ansatz, hamiltonian, estimator):\n",
" # transform the observable defined on virtual qubits to\n",
" # an observable defined on all physical qubits\n",
" isa_hamiltonian = hamiltonian.apply_layout(ansatz.layout)\n",
"\n",
" pub = (ansatz, isa_hamiltonian, params)\n",
" job = estimator.run([pub])\n",
"\n",
" results = job.result()[0]\n",
" cost = results.data.evs\n",
"\n",
" objective_func_vals.append(cost)\n",
"\n",
" return cost"
]
},
{
"cell_type": "code",
"execution_count": 9,
"id": "2df241a9",
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
" message: Return from COBYLA because the trust region radius reaches its lower bound.\n",
" success: True\n",
" status: 0\n",
" fun: -2.0402211719947774\n",
" x: [ 3.041e+00 1.212e+00 2.081e+00 4.471e+00]\n",
" nfev: 36\n",
" maxcv: 0.0\n"
]
}
],
"source": [
"objective_func_vals = [] # Global variable\n",
"with Session(backend=backend) as session:\n",
" # If using qiskit-ibm-runtime<0.24.0, change `mode=` to `session=`\n",
" estimator = Estimator(mode=session)\n",
" estimator.options.default_shots = 1000\n",
"\n",
" # Set simple error suppression/mitigation options\n",
" estimator.options.dynamical_decoupling.enable = True\n",
" estimator.options.dynamical_decoupling.sequence_type = \"XY4\"\n",
" estimator.options.twirling.enable_gates = True\n",
" estimator.options.twirling.num_randomizations = \"auto\"\n",
" estimator.options.environment.job_tags = [\"TUT_QAOA\"]\n",
"\n",
" result = minimize(\n",
" cost_func_estimator,\n",
" init_params,\n",
" args=(candidate_circuit, cost_hamiltonian, estimator),\n",
" method=\"COBYLA\",\n",
" tol=1e-2,\n",
" )\n",
" print(result)"
]
},
{
"cell_type": "markdown",
"id": "01d6b81c",
"metadata": {},
"source": [
"Der Optimierer konnte die Kosten senken und bessere Parameter für die Schaltung finden.\n",
"\n",
"Eine sanft abfallende Kurve, die sich dann abflacht, ist ein typisches Anzeichen für Konvergenz. Eine unruhige, nicht-monotone Kurve deutet in der Regel darauf hin, dass ein vorgelagerter Schritt überprüft werden muss; häufige Ursachen sind zu wenige Iterationen pro Bewertung (hohe Schättevarians), ungeeignete Startparameter oder eine Schaltung, deren Tiefe durch Hardware-Rauschen dominiert wird. COBYLA ist derivatfrei und relativ robust gegenüber mäßigem Rauschen; wenn das Rauschen jedoch die tatsächlichen Kostenverbesserungen pro Schritt überlagert, kann sein lineares Näherungsmodell den tatsächlichen Abstieg nicht mehr von zufälligen Schwankungen unterscheiden, und der Optimierer driftet ab.\n",
"\n"
]
},
{
"cell_type": "code",
"execution_count": 10,
"id": "e14ecc92",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
""
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"plt.figure(figsize=(12, 6))\n",
"plt.plot(objective_func_vals)\n",
"plt.xlabel(\"Iteration\")\n",
"plt.ylabel(\"Cost\")\n",
"plt.show()"
]
},
{
"cell_type": "markdown",
"id": "1f9c8a9c",
"metadata": {},
"source": [
"Weisen Sie die optimierten Parameter zu und generieren Sie Stichproben der endgültigen Verteilung mithilfe der Sampler-Primitive.\n",
"\n"
]
},
{
"cell_type": "code",
"execution_count": 11,
"id": "2989e76e-4296-4dd8-b065-2b8fced064cf",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
""
]
},
"execution_count": 11,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"optimized_circuit = candidate_circuit.assign_parameters(result.x)\n",
"optimized_circuit.draw(\"mpl\", fold=False, idle_wires=False)"
]
},
{
"cell_type": "code",
"execution_count": 12,
"id": "d8f0e302",
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"{18: 0.039, 5: 0.0665, 20: 0.0973, 29: 0.0063, 9: 0.0899, 13: 0.0379, 2: 0.0047, 1: 0.0153, 11: 0.0932, 14: 0.0327, 12: 0.0314, 25: 0.0193, 21: 0.0398, 6: 0.0224, 4: 0.0197, 10: 0.0387, 3: 0.0181, 26: 0.07, 17: 0.0327, 19: 0.0332, 22: 0.0914, 24: 0.007, 0: 0.0033, 8: 0.0066, 30: 0.0158, 28: 0.0169, 27: 0.0222, 16: 0.0073, 7: 0.0057, 23: 0.0062, 15: 0.0054, 31: 0.0041}\n"
]
}
],
"source": [
"# If using qiskit-ibm-runtime<0.24.0, change `mode=` to `backend=`\n",
"sampler = Sampler(mode=backend)\n",
"sampler.options.default_shots = 10000\n",
"\n",
"# Set simple error suppression/mitigation options\n",
"sampler.options.dynamical_decoupling.enable = True\n",
"sampler.options.dynamical_decoupling.sequence_type = \"XY4\"\n",
"sampler.options.twirling.enable_gates = True\n",
"sampler.options.twirling.num_randomizations = \"auto\"\n",
"\n",
"sampler.options.environment.job_tags = [\"TUT_QAOA\"]\n",
"\n",
"pub = (optimized_circuit,)\n",
"job = sampler.run([pub], shots=int(1e4))\n",
"counts_int = job.result()[0].data.meas.get_int_counts()\n",
"counts_bin = job.result()[0].data.meas.get_counts()\n",
"shots = sum(counts_int.values())\n",
"final_distribution_int = {key: val / shots for key, val in counts_int.items()}\n",
"final_distribution_bin = {key: val / shots for key, val in counts_bin.items()}\n",
"print(final_distribution_int)"
]
},
{
"cell_type": "markdown",
"id": "dace5fed-5555-4f1c-9109-7f5a31832d04",
"metadata": {},
"source": [
"\n",
"\n",
"### Schritt 4: Nachbearbeitung und Rückgabe des Ergebnisses im gewünschten klassischen Format\n",
"\n",
"Extrahieren Sie die wahrscheinlichste Bitfolge aus der Stichprobenverteilung. Dies ist der beste Schnitt, den QAOA gefunden hat.\n",
"\n"
]
},
{
"cell_type": "code",
"execution_count": 13,
"id": "d4f7fc70-883f-4b6b-8e92-2fc4afbbea46",
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Result bitstring: [0, 0, 1, 0, 1]\n"
]
}
],
"source": [
"# auxiliary functions to sample most likely bitstring\n",
"def to_bitstring(integer, num_bits):\n",
" result = np.binary_repr(integer, width=num_bits)\n",
" return [int(digit) for digit in result]\n",
"\n",
"\n",
"keys = list(final_distribution_int.keys())\n",
"values = list(final_distribution_int.values())\n",
"most_likely = keys[np.argmax(np.abs(values))]\n",
"most_likely_bitstring = to_bitstring(most_likely, len(graph))\n",
"most_likely_bitstring.reverse()\n",
"\n",
"print(\"Result bitstring:\", most_likely_bitstring)"
]
},
{
"cell_type": "code",
"execution_count": 14,
"id": "650875e9-adbc-43bd-9505-556be2566278",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
""
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"plt.rcParams.update({\"font.size\": 10})\n",
"final_bits = final_distribution_bin\n",
"values = np.abs(list(final_bits.values()))\n",
"top_4_values = sorted(values, reverse=True)[:4]\n",
"positions = []\n",
"for value in top_4_values:\n",
" positions.append(np.where(values == value)[0])\n",
"fig = plt.figure(figsize=(11, 6))\n",
"ax = fig.add_subplot(1, 1, 1)\n",
"plt.xticks(rotation=45)\n",
"plt.title(\"Result Distribution\")\n",
"plt.xlabel(\"Bitstrings (reversed)\")\n",
"plt.ylabel(\"Probability\")\n",
"ax.bar(list(final_bits.keys()), list(final_bits.values()), color=\"tab:grey\")\n",
"for p in positions:\n",
" ax.get_children()[int(p[0])].set_color(\"tab:purple\")\n",
"plt.show()"
]
},
{
"cell_type": "markdown",
"id": "207443f2-34d9-424a-a6d7-44707ef1488b",
"metadata": {},
"source": [
"\n",
"\n",
"#### Den besten Schnitt visualisieren\n",
"\n",
"Anhand der optimalen Bitfolge kannst du diesen Schnitt dann im ursprünglichen Graphen visualisieren.\n",
"\n"
]
},
{
"cell_type": "code",
"execution_count": 15,
"id": "33135970-8bc4-4fb2-ab87-08726a432ce4",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
""
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"# auxiliary function to plot graphs\n",
"def plot_result(G, x):\n",
" colors = [\"tab:grey\" if i == 0 else \"tab:purple\" for i in x]\n",
" pos, _default_axes = rx.spring_layout(G), plt.axes(frameon=True)\n",
" rx.visualization.mpl_draw(\n",
" G, node_color=colors, node_size=100, alpha=0.8, pos=pos\n",
" )\n",
"\n",
"\n",
"plot_result(graph, most_likely_bitstring)"
]
},
{
"cell_type": "markdown",
"id": "2119575f-f3cf-45bc-ae2b-93c046391eb6",
"metadata": {},
"source": [
"Berechne nun den Wert des Schnitts:\n",
"\n"
]
},
{
"cell_type": "code",
"execution_count": 16,
"id": "2f6a73c4-f5ae-4647-a0dd-d77a13f66388",
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"The value of the cut is: 5\n"
]
}
],
"source": [
"def evaluate_sample(x: Sequence[int], graph: rx.PyGraph) -> float:\n",
" assert len(x) == len(\n",
" list(graph.nodes())\n",
" ), \"The length of x must coincide with the number of nodes in the graph.\"\n",
" return sum(\n",
" x[u] * (1 - x[v]) + x[v] * (1 - x[u])\n",
" for u, v in list(graph.edge_list())\n",
" )\n",
"\n",
"\n",
"cut_value = evaluate_sample(most_likely_bitstring, graph)\n",
"print(\"The value of the cut is:\", cut_value)"
]
},
{
"cell_type": "markdown",
"id": "76a7241e",
"metadata": {},
"source": [
"Bei einem so kleinen Graphen lässt sich das wahre Optimum leicht durch Brute-Force-Methode ermitteln, sodass Sie die Ergebnisse überprüfen können, indem Sie das QAOA-Ergebnis mit der exakten Lösung vergleichen.\n",
"\n"
]
},
{
"cell_type": "code",
"execution_count": 17,
"id": "0a3b5267",
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Classical optimum (brute force): 5\n",
"QAOA cut value: 5\n"
]
}
],
"source": [
"# Classical baseline: enumerate all 2**n_small bitstrings and take the best cut.\n",
"def brute_force_max_cut(graph: rx.PyGraph) -> tuple[int, list[int]]:\n",
" n = len(list(graph.nodes()))\n",
" best_cut = -1\n",
" best_x: list[int] = []\n",
" for i in range(2**n):\n",
" x = [(i >> k) & 1 for k in range(n)]\n",
" cut = evaluate_sample(x, graph)\n",
" if cut > best_cut:\n",
" best_cut = int(cut)\n",
" best_x = x\n",
" return best_cut, best_x\n",
"\n",
"\n",
"classical_best, classical_x = brute_force_max_cut(graph)\n",
"print(f\"Classical optimum (brute force): {classical_best}\")\n",
"print(f\"QAOA cut value: {cut_value}\")"
]
},
{
"cell_type": "markdown",
"id": "large-scale-header",
"metadata": {},
"source": [
"\n",
"\n",
"## Beispiel für groß angelegte Hardware\n",
"\n",
"Unter IBM Quantum Platform haben Sie Zugriff auf zahlreiche Geräte mit über 100 Qubits. Wählen Sie einen aus, auf dem das Max-Cut-Problem in einem gewichteten Graphen mit 100 Knoten gelöst werden soll. Dies ist ein Problem im „Großmaßstab“. Der Arbeitsablauf folgt denselben Schritten wie oben, gilt jedoch für einen wesentlich größeren Graphen.\n",
"\n"
]
},
{
"cell_type": "markdown",
"id": "large-scale-steps-intro",
"metadata": {},
"source": [
"\n",
"\n",
"### Durchgängiger Arbeitsablauf im Versorgungsmaßstab\n",
"\n",
"Im Folgenden werden alle vier Schritte am Beispiel des Graphen mit 100 Knoten dargestellt. Der Aufbau entspricht dem des kleinen Beispiels: Karte, Transpile, Ausführung, Nachbearbeitung – allerdings mit einem größeren Problem, das der Übersichtlichkeit halber auf die vier folgenden Zellen aufgeteilt wurde.\n",
"\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "large-scale-helpers",
"metadata": {},
"outputs": [],
"source": [
"# Precomputed parity lookup table: _PARITY[b] = +1 if popcount(b) is even, else -1.\n",
"# We use this to vectorize expectation-value evaluation across all Pauli terms.\n",
"_PARITY = np.array(\n",
" [-1 if bin(i).count(\"1\") % 2 else 1 for i in range(256)],\n",
" dtype=np.complex128,\n",
")\n",
"\n",
"\n",
"def evaluate_sparse_pauli(state: int, observable: SparsePauliOp) -> complex:\n",
" \"\"\"Expectation value of a SparsePauliOp on a single computational-basis state.\n",
"\n",
" For a Z-only observable (which QAOA cost Hamiltonians are, after the\n",
" QUBO-to-Hamiltonian mapping), the eigenvalue of each Pauli term on a\n",
" computational-basis state is simply (-1)**popcount(z_mask AND state),\n",
" i.e., the parity of the bitwise-AND of the term's Z-support and the\n",
" measured bitstring.\n",
"\n",
" This routine packs the Z-support of every Pauli term into bytes, ANDs\n",
" them against the measured state in a single vectorized op, and looks up\n",
" the parity in _PARITY. For a 100-qubit / ~hundreds-of-terms Hamiltonian\n",
" over 10_000 samples, this is dramatically faster than calling\n",
" SparsePauliOp.expectation_value per sample.\n",
" \"\"\"\n",
" packed_uint8 = np.packbits(observable.paulis.z, axis=1, bitorder=\"little\")\n",
" state_bytes = np.frombuffer(\n",
" state.to_bytes(packed_uint8.shape[1], \"little\"), dtype=np.uint8\n",
" )\n",
" reduced = np.bitwise_xor.reduce(packed_uint8 & state_bytes, axis=1)\n",
" return np.sum(observable.coeffs * _PARITY[reduced])\n",
"\n",
"\n",
"def best_solution(samples, hamiltonian):\n",
" \"\"\"Return the sampled bitstring (as int) with the lowest Hamiltonian cost.\"\"\"\n",
" min_cost = float(\"inf\")\n",
" min_sol = None\n",
" for bit_str in samples.keys():\n",
" candidate_sol = int(bit_str)\n",
" fval = evaluate_sparse_pauli(candidate_sol, hamiltonian).real\n",
" if fval <= min_cost:\n",
" min_cost = fval\n",
" min_sol = candidate_sol\n",
" return min_sol\n",
"\n",
"\n",
"def _plot_cdf(objective_values: dict, ax, color):\n",
" x_vals = sorted(objective_values.keys(), reverse=True)\n",
" y_vals = np.cumsum([objective_values[x] for x in x_vals])\n",
" ax.plot(x_vals, y_vals, color=color)\n",
"\n",
"\n",
"def plot_cdf(dist, ax, title):\n",
" _plot_cdf(dist, ax, \"C1\")\n",
" ax.vlines(min(list(dist.keys())), 0, 1, \"C1\", linestyle=\"--\")\n",
" ax.set_title(title)\n",
" ax.set_xlabel(\"Objective function value\")\n",
" ax.set_ylabel(\"Cumulative distribution function\")\n",
" ax.grid(alpha=0.3)\n",
"\n",
"\n",
"def samples_to_objective_values(samples, hamiltonian):\n",
" \"\"\"Convert the samples to values of the objective function.\"\"\"\n",
" objective_values = defaultdict(float)\n",
" for bit_str, prob in samples.items():\n",
" candidate_sol = int(bit_str)\n",
" fval = evaluate_sparse_pauli(candidate_sol, hamiltonian).real\n",
" objective_values[fval] += prob\n",
" return objective_values"
]
},
{
"cell_type": "markdown",
"id": "4dc0c8ff",
"metadata": {},
"source": [
"**Schritt 1** : Erstellen Sie den Graphen, den Kosten-Hamiltonian und den Ansatz.\n",
"\n"
]
},
{
"cell_type": "code",
"execution_count": 19,
"id": "94190344",
"metadata": {},
"outputs": [],
"source": [
"# Step 1: build the 100-node graph, cost Hamiltonian, and QAOA ansatz.\n",
"n_large = 100\n",
"graph_100 = rx.PyGraph()\n",
"graph_100.add_nodes_from(np.arange(0, n_large, 1))\n",
"elist = []\n",
"for edge in backend.coupling_map:\n",
" if edge[0] < n_large and edge[1] < n_large:\n",
" elist.append((edge[0], edge[1], 1.0))\n",
"graph_100.add_edges_from(elist)\n",
"\n",
"max_cut_paulis_100 = build_max_cut_paulis(graph_100)\n",
"cost_hamiltonian_100 = SparsePauliOp.from_sparse_list(\n",
" max_cut_paulis_100, n_large\n",
")\n",
"\n",
"circuit_100 = QAOAAnsatz(cost_operator=cost_hamiltonian_100, reps=1)\n",
"circuit_100.measure_all()"
]
},
{
"cell_type": "markdown",
"id": "c91f0c16",
"metadata": {},
"source": [
"**Schritt 2** : Transpile für das ausgewählte Hardware-Backend.\n",
"\n"
]
},
{
"cell_type": "code",
"execution_count": 20,
"id": "2b59da0e",
"metadata": {},
"outputs": [],
"source": [
"# Step 2: transpile for hardware.\n",
"pm = generate_preset_pass_manager(optimization_level=3, backend=backend)\n",
"candidate_circuit_100 = pm.run(circuit_100)"
]
},
{
"cell_type": "markdown",
"id": "eb2c4d66",
"metadata": {},
"source": [
"**Schritt 3** : Führen Sie die QAOA-Optimierungsschleife innerhalb einer Sitzung aus und nehmen Sie anschließend eine Stichprobe.\n",
"\n"
]
},
{
"cell_type": "code",
"execution_count": 21,
"id": "e5aceab3",
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
" message: Return from COBYLA because the trust region radius reaches its lower bound.\n",
" success: True\n",
" status: 0\n",
" fun: -17.172689238986344\n",
" x: [ 2.574e+00 4.166e+00]\n",
" nfev: 28\n",
" maxcv: 0.0\n"
]
}
],
"source": [
"# Step 3: run the QAOA optimization loop on the device, then sample the\n",
"# final distribution with the optimized parameters.\n",
"initial_gamma = np.pi\n",
"initial_beta = np.pi / 2\n",
"init_params = [initial_beta, initial_gamma]\n",
"\n",
"objective_func_vals = [] # Global variable\n",
"with Session(backend=backend) as session:\n",
" estimator = Estimator(mode=session)\n",
" estimator.options.default_shots = 1000\n",
"\n",
" # Set simple error suppression/mitigation options\n",
" estimator.options.dynamical_decoupling.enable = True\n",
" estimator.options.dynamical_decoupling.sequence_type = \"XY4\"\n",
" estimator.options.twirling.enable_gates = True\n",
" estimator.options.twirling.num_randomizations = \"auto\"\n",
" estimator.options.environment.job_tags = [\"TUT_QAOA\"]\n",
"\n",
" result = minimize(\n",
" cost_func_estimator,\n",
" init_params,\n",
" args=(candidate_circuit_100, cost_hamiltonian_100, estimator),\n",
" method=\"COBYLA\",\n",
" )\n",
" print(result)\n",
"\n",
"# Assign optimal parameters and sample the final distribution.\n",
"optimized_circuit_100 = candidate_circuit_100.assign_parameters(result.x)\n",
"\n",
"sampler = Sampler(mode=backend)\n",
"sampler.options.default_shots = 10000\n",
"\n",
"# Set simple error suppression/mitigation options\n",
"sampler.options.dynamical_decoupling.enable = True\n",
"sampler.options.dynamical_decoupling.sequence_type = \"XY4\"\n",
"sampler.options.twirling.enable_gates = True\n",
"sampler.options.twirling.num_randomizations = \"auto\"\n",
"\n",
"# Add a unique tag to the job execution\n",
"sampler.options.environment.job_tags = [\"TUT_QAOA\"]\n",
"\n",
"pub = (optimized_circuit_100,)\n",
"job = sampler.run([pub], shots=int(1e4))\n",
"\n",
"counts_int = job.result()[0].data.meas.get_int_counts()\n",
"shots = sum(counts_int.values())\n",
"final_distribution_100_int = {\n",
" key: val / shots for key, val in counts_int.items()\n",
"}"
]
},
{
"cell_type": "markdown",
"id": "7f0c5980",
"metadata": {},
"source": [
"**Schritt 4** : Bearbeite die Stichprobenverteilung nach, um den besten Schnitt zu ermitteln.\n",
"\n"
]
},
{
"cell_type": "code",
"execution_count": 22,
"id": "010571f7",
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Result bitstring: [1, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 1, 0, 0, 1, 1, 0, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 1, 1, 1, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0]\n",
"The value of the cut is: 156\n"
]
}
],
"source": [
"# Step 4: find the best-cost sample and evaluate its cut value.\n",
"best_sol_100 = best_solution(final_distribution_100_int, cost_hamiltonian_100)\n",
"best_sol_bitstring_100 = to_bitstring(int(best_sol_100), len(graph_100))\n",
"best_sol_bitstring_100.reverse()\n",
"\n",
"print(\"Result bitstring:\", best_sol_bitstring_100)\n",
"\n",
"cut_value_100 = evaluate_sample(best_sol_bitstring_100, graph_100)\n",
"print(\"The value of the cut is:\", cut_value_100)"
]
},
{
"cell_type": "markdown",
"id": "large-scale-convergence-md",
"metadata": {},
"source": [
"Überprüfen Sie, ob die im Optimierungszyklus minimierten Kosten konvergiert sind, und stellen Sie die Ergebnisse grafisch dar.\n",
"\n"
]
},
{
"cell_type": "code",
"execution_count": 23,
"id": "large-scale-viz",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
""
]
},
"metadata": {},
"output_type": "display_data"
},
{
"data": {
"text/plain": [
""
]
},
"metadata": {},
"output_type": "display_data"
},
{
"data": {
"text/plain": [
""
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"# Plot convergence\n",
"plt.figure(figsize=(12, 6))\n",
"plt.plot(objective_func_vals)\n",
"plt.xlabel(\"Iteration\")\n",
"plt.ylabel(\"Cost\")\n",
"plt.show()\n",
"\n",
"# Visualize the cut\n",
"plot_result(graph_100, best_sol_bitstring_100)\n",
"\n",
"# Plot cumulative distribution function\n",
"result_dist = samples_to_objective_values(\n",
" final_distribution_100_int, cost_hamiltonian_100\n",
")\n",
"fig, ax = plt.subplots(1, 1, figsize=(8, 6))\n",
"plot_cdf(result_dist, ax, backend.name)"
]
},
{
"cell_type": "markdown",
"id": "69ebc85b-6a29-4671-8d16-1ac97f089607",
"metadata": {},
"source": [
"\n",
"\n",
"## Nächste Schritte\n",
"\n",
"Wenn Sie diese Arbeit interessant fanden, könnten Sie auch an folgenden Materialien interessiert sein:\n",
"\n",
"\n",
" * [Fortgeschrittene Techniken für QAOA](/docs/tutorials/advanced-techniques-for-qaoa) – Untersuchung fortgeschrittener Strategien zur Verbesserung der QAOA-Leistung\n",
" * [Herausforderung zur multikriteriellen Optimierung](https://github.com/qiskit-community/qdc-challenges-2025/blob/main/challenges/Track_B/qmoo/qmoo_qdc25.ipynb) – stellen Sie Ihre Fähigkeiten bei dieser Community-Herausforderung zur multikriteriellen Quantenoptimierung auf die Probe\n",
" * [Transpilation-Dokumentation](/docs/guides/transpile) zur Feinabstimmung der Schaltungsoptimierung\n",
" * [Fehlerunterdrückung und -minderung](/docs/guides/error-mitigation-and-suppression-techniques) zur Verbesserung der Hardwareergebnisse\n",
"\n",
"\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"id": "a1b8767d",
"source": "© IBM Corp., 2017-2026"
}
],
"metadata": {
"kernelspec": {
"display_name": "Python 3",
"language": "python",
"name": "python3"
},
"language_info": {
"codemirror_mode": {
"name": "ipython",
"version": 3
},
"file_extension": ".py",
"mimetype": "text/x-python",
"name": "python",
"nbconvert_exporter": "python",
"pygments_lexer": "ipython3",
"version": "3"
},
"hours": 1,
"qpuSeconds": 1320
},
"nbformat": 4,
"nbformat_minor": 5
}