{
"cells": [
{
"cell_type": "markdown",
"id": "1a869c2d-ae51-47d3-8a41-bfcf5e505f59",
"metadata": {},
"source": [
"---\n",
"title: \"Fortgeschrittene Techniken für QAOA\"\n",
"description: \"Dieses Notizbuch stellt fortgeschrittene Techniken zur Verbesserung der Leistung des Quantum Approximate Optimization Algorithm (QAOA) mit einer großen Anzahl von Qubits vor.\"\n",
"---\n",
"\n",
"{/* cspell:ignore pysat, lbrack, frameon, IEICE */}\n",
"\n",
"\n",
"\n",
"# Fortgeschrittene Techniken für QAOA\n",
"\n",
"*Geschätzte Nutzungsdauer: 3 Minuten auf einem r2 Heron-Prozessor (HINWEIS: Dies ist nur eine Schätzung. Ihre Laufzeit kann variieren.)*\n",
"\n"
]
},
{
"cell_type": "markdown",
"id": "1a6bbeef-966f-45e1-89aa-e964ef891eeb",
"metadata": {},
"source": [
"\n",
"\n",
"## Voraussetzungen\n",
"\n",
"* Grundlagen des Quantenalgorithmus zur approximativen Optimierung (QAOA)\n",
"* Das Tutorial [zur Lösung von Quantenoptimierungsproblemen im industriellen Maßstab](/docs/tutorials/quantum-approximate-optimization-algorithm)\n",
"* Die Lektion „[QAOA im industriellen Maßstab](/learning/courses/quantum-computing-in-practice/utility-scale-qaoa#utility-scale-qaoa) “ (Teil des Kurses „[Quanteninformatik in der Praxis](/learning/courses/quantum-computing-in-practice) “) unter IBM Quantum® Learning\n",
"\n",
"\n",
"\n",
"## Lernziele\n",
"\n",
"* Setzen Sie fortschrittliche Techniken ein, die zur Verbesserung der QAOA-Transpilation beitragen und Möglichkeiten zur Steigerung der QAOA-Leistung bieten\n",
"\n",
"Eine ausführliche Anleitung zu den Inhalten dieses Tutorials finden Sie in diesem [Qiskit-Video](https://youtu.be/rBfK-l-qSNk?si=PC28gFAdu4JYSYdk).\n",
"\n"
]
},
{
"cell_type": "markdown",
"id": "ea97567d-810f-4cca-8edf-a47d70ea870a",
"metadata": {},
"source": [
"\n",
"\n",
"## Hintergrund\n",
"\n",
"Dieses Tutorial stellt zwei fortgeschrittene Techniken vor, mit denen sich die Leistungsfähigkeit des **Algorithmus** zur approximativen Quantenoptimierung (QAOA) bei einer großen Anzahl von Qubits verbessern lässt.\n",
"\n",
"Zu den fortgeschrittenen Techniken in diesem Notizbuch gehören:\n",
"\n",
"* **SWAP-Strategie mit SAT-Initialisierung** : Hierbei handelt es sich um einen speziell für QAOA entwickelten Transpiler-Durchlauf, der eine SWAP-Strategie und einen SAT-Löser kombiniert, um die Auswahl der auf der QPU zu verwendenden physikalischen Qubits zu optimieren. Die SWAP-Strategie nutzt die Kommutativität der QAOA-Operatoren, um die Gatter neu anzuordnen, sodass Schichten von SWAP-Gattern gleichzeitig ausgeführt werden können, wodurch sich die Schaltungstiefe verringert [\\[1\\]](#references). Der SAT-Solver wird verwendet, um eine Anfangsabbildung zu finden, die die Anzahl der SWAP-Operationen minimiert, die erforderlich sind, um die Qubits im Schaltkreis auf die physikalischen Qubits des Geräts abzubilden [\\[2\\]](#references).\n",
"* **CVaR Kostenfunktion** : In der Regel wird der Erwartungswert des Kostenhamiltonians als Kostenfunktion für QAOA verwendet; wie jedoch in [\\[3\\]](#references) gezeigt wurde, kann die Fokussierung auf den Randbereich der Verteilung anstelle des Erwartungswerts die Leistung von QAOA bei kombinatorischen Optimierungsproblemen verbessern. Das „ CVaR “ erfüllt diesen Zweck. Für eine gegebene Menge von Schüssen mit den entsprechenden Zielwerten des betrachteten Optimierungsproblems ist der bedingte Value-at-Risk ( CVaR ) mit einem Konfidenzniveau von $\\alpha \\in [0, 1]$ als der Durchschnitt der $\\alpha$ besten Schüsse definiert [\\[3\\]](#references).\n",
" Somit entspricht $\\alpha = 1$ dem erwarteten Standardwert, während $\\alpha=0$ dem Minimalwert der gegebenen Aufnahmen entspricht und $\\alpha \\in (0, 1)$ einen Kompromiss darstellt zwischen der Fokussierung auf bessere Aufnahmen und einer gewissen Mittelwertbildung, um die Optimierungslandschaft zu glätten. Darüber hinaus kann die „ CVaR “ als Methode zur Fehlerminderung eingesetzt werden, um die Qualität der Schätzung des Objektivwerts zu verbessern [\\[4\\]](#references).\n",
"\n",
"Am Ende dieses Tutorials sollten Sie in der Lage sein, diese Techniken anzuwenden, um bei der Ausführung von QAOA für Ihre Optimierungsprobleme die besten Ergebnisse zu erzielen.\n",
"\n"
]
},
{
"cell_type": "markdown",
"id": "40fb546e-85e0-450b-a5ea-5d08950d129f",
"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 später, mit [Visual](/docs/api/qiskit/visualization) isierungsunterstützung\n",
"* v0.43Qiskit Runtime oder später (`pip install qiskit-ibm-runtime`)\n",
"* Rustworkx-Grafikbibliothek (`pip install rustworkx`)\n",
"* Python SAT (`pip install python-sat`)\n",
"\n"
]
},
{
"cell_type": "markdown",
"id": "50285e5f-1a7b-471c-a223-1ae0af19d9ed",
"metadata": {},
"source": [
"\n",
"\n",
"## Einrichtung\n",
"\n"
]
},
{
"cell_type": "code",
"execution_count": 91,
"id": "d019ea68-61e0-4341-84c7-e612ca10dde7",
"metadata": {},
"outputs": [],
"source": [
"from __future__ import annotations\n",
"\n",
"import numpy as np\n",
"import rustworkx as rx\n",
"from dataclasses import dataclass\n",
"from itertools import combinations\n",
"from threading import Timer\n",
"from collections.abc import Callable, Iterable\n",
"from pysat.formula import CNF, IDPool\n",
"from pysat.solvers import Solver\n",
"from scipy.optimize import minimize\n",
"from rustworkx.visualization import mpl_draw as draw_graph\n",
"\n",
"from qiskit.quantum_info import SparsePauliOp\n",
"from qiskit.circuit.library import QAOAAnsatz\n",
"from qiskit.circuit import QuantumCircuit, ParameterVector\n",
"from qiskit.transpiler import CouplingMap, PassManager\n",
"from qiskit.transpiler.preset_passmanagers import generate_preset_pass_manager\n",
"from qiskit.transpiler.passes.routing.commuting_2q_gate_routing import (\n",
" SwapStrategy,\n",
" FindCommutingPauliEvolutions,\n",
" Commuting2qGateRouter,\n",
")\n",
"\n",
"from qiskit_ibm_runtime import QiskitRuntimeService, Session\n",
"from qiskit_ibm_runtime import SamplerV2 as Sampler"
]
},
{
"cell_type": "markdown",
"id": "8b77b0c9-f5a6-476e-86b8-069ba14f9ab3",
"metadata": {},
"source": [
"\n",
"\n",
"### Max-Cut-Problem\n",
"\n",
"Betrachten wir die Lösung des **Max-Cut-** Problems in einem Graphen mit 100 Knoten unter Verwendung von QAOA.\n",
"Das Max-Cut-Problem ist ein kombinatorisches Optimierungsproblem, das auf einem Graphen $G = (V, E)$ definiert ist, wobei $V$ die Menge der Knoten und $E$ die Menge der Kanten ist. Das Ziel besteht darin, die Knoten in zwei Mengen, $S$ und $V \\setminus S$, zu unterteilen, sodass die Anzahl der Kanten zwischen den beiden Mengen maximiert wird.\n",
"In diesem Beispiel verwenden wir einen Graphen mit 100 Knoten, der auf einer Hardware-Kopplungskarte basiert.\n",
"\n"
]
},
{
"cell_type": "markdown",
"id": "663d13f5-a5f7-4b67-a89b-26deb41224ec",
"metadata": {},
"source": [
"\n",
"\n",
"## Beispiel für einen Simulator im kleinen Maßstab\n",
"\n",
"Da das Ziel dieses Tutorials darin besteht, zu zeigen, wie sich QAOA in Größenordnungen verhält, die über die Kapazitäten eines Simulators hinausgehen, werden wir diesen Schritt überspringen.\n",
"\n",
"Wenn Sie einen simulatorbasierten QAOA-Workflow ausprobieren möchten, sehen Sie sich das Tutorial [zum algorithmischen Ansatz der approximativen Quantenoptimierung](/docs/tutorials/quantum-approximate-optimization-algorithm) an.\n",
"\n"
]
},
{
"cell_type": "markdown",
"id": "6ca05a7c-5fde-4485-a3ad-c0ba02844e50",
"metadata": {},
"source": [
"\n",
"\n",
"## Beispiel für groß angelegte Hardware\n",
"\n"
]
},
{
"cell_type": "markdown",
"id": "b825afbf-10fd-4926-bd65-05272044f107",
"metadata": {},
"source": [
"\n",
"\n",
"### Schritt 1: Klassische Eingaben einem Quantenproblem zuordnen\n",
"\n",
"\n",
"\n",
"#### Grafik → Hamilton-Funktion\n",
"\n",
"Zunächst muss das Problem auf einen Quantenschaltkreis abgebildet werden, der für die QAOA geeignet ist. Einzelheiten zu diesem Vorgang finden Sie im [einführenden QAOA-Tutorial](/docs/tutorials/quantum-approximate-optimization-algorithm).\n",
"\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "8c25db38-5f36-4a39-bdde-4f83616a6dde",
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"\n"
]
}
],
"source": [
"# Instantiate runtime to access backend\n",
"service = QiskitRuntimeService()\n",
"backend = service.least_busy(\n",
" min_num_qubits=100, operational=True, simulator=False\n",
")\n",
"print(backend)"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "e04ce982-8294-4ebe-8dcc-f74205938800",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
"True"
]
},
"execution_count": 96,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"# Check if the coupling map is symmetric. We will add a conditional below\n",
"# to avoid over-counting edges for symmetric/bi-directional coupling maps.\n",
"\n",
"backend.coupling_map.is_symmetric"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "8b864d32-9483-45ea-831f-60488e330adb",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
""
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"n = 100\n",
"graph_100 = rx.PyGraph()\n",
"graph_100.add_nodes_from((np.arange(0, n, 1)))\n",
"w = 1.0\n",
"elist = []\n",
"\n",
"for edge in backend.coupling_map:\n",
" if (edge[0] < n) and (edge[1] < n):\n",
" # Conditional to avoid over-counting edges\n",
" if (\n",
" edge[1],\n",
" edge[0],\n",
" w,\n",
" ) not in elist:\n",
" elist.append((edge[0], edge[1], w))\n",
"\n",
"graph_100.add_edges_from(elist)\n",
"draw_graph(graph_100, with_labels=True)"
]
},
{
"cell_type": "code",
"execution_count": 98,
"id": "e39c4e42-ce97-4a04-8879-da4d33a684bc",
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Cost Function Hamiltonian: SparsePauliOp(['IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZ', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZI', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZIIIIIIIIIIIIZIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZIIIIIIIIIZIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZIIIIIIZIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZIIIZIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZIIIIIIZIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZIIIIIIIIIZIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZIIIIIIIIIIIIZIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZIIIIIIIIIIIIIIIZIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZIIIIIIIIIIIIIIZIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZIIIIIIIIIIIZIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZIIIIIIIIZIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZIIIIIZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZIIIIZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZIIIIIIIZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZIIIIIIIIIIZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZIIIIIIIIIIIIIZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZIIIIIIIIIIIIZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZIIIIIIIIIZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZIIIIIIZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZIIIZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZIIIIIIZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZIIIIIIIIIZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIZIIIIIIIIIIIIZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIZIIIIIIIIIIIIIIIZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIZIIIIIIIIIIIIIIZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIZIIIIIIIIIIIZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIZIIIIIIIIZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIZIIIIIZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIZIIIIZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIZIIIIIIIZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIZIIIIIIIIIIZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIZIIIIIIIIIIIIIZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIZIIIIIIIIIIIIZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIZIIIIIIIIIZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IZIIIIIIZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'ZIIIZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII'],\n",
" coeffs=[1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j,\n",
" 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j,\n",
" 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j,\n",
" 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j,\n",
" 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j,\n",
" 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j,\n",
" 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j,\n",
" 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j,\n",
" 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j,\n",
" 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j,\n",
" 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j,\n",
" 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j,\n",
" 1.+0.j, 1.+0.j, 1.+0.j])\n"
]
}
],
"source": [
"# Construct cost hamiltonian\n",
"\n",
"\n",
"def build_max_cut_paulis(graph: rx.PyGraph) -> list[tuple[str, float]]:\n",
" \"\"\"Convert the graph to Pauli list.\n",
"\n",
" This function does the inverse of `build_max_cut_graph`\n",
" \"\"\"\n",
" pauli_list = []\n",
" for edge in list(graph.edge_list()):\n",
" paulis = [\"I\"] * len(graph)\n",
" paulis[edge[0]], paulis[edge[1]] = \"Z\", \"Z\"\n",
"\n",
" weight = graph.get_edge_data(edge[0], edge[1])\n",
"\n",
" pauli_list.append((\"\".join(paulis)[::-1], weight))\n",
"\n",
" return pauli_list\n",
"\n",
"\n",
"max_cut_paulis = build_max_cut_paulis(graph_100)\n",
"\n",
"cost_hamiltonian = SparsePauliOp.from_list(max_cut_paulis)\n",
"print(\"Cost Function Hamiltonian:\", cost_hamiltonian)"
]
},
{
"cell_type": "markdown",
"id": "4e576068-53e7-4a06-a83b-87e95de141e9",
"metadata": {},
"source": [
"\n",
"\n",
"### Schritt 2: Optimierung des Problems für die Ausführung auf Quantenhardware\n",
"\n",
"\n",
"\n",
"#### SWAP-Strategie mit der SAT-Anfangsabbildung\n",
"\n",
"Wir werden demonstrieren, wie man QAOA-Schaltungen mit Hilfe der **SWAP-Strategie mit SAT Initial Mapping**, einem speziell für QAOA entwickelten Transpiler-Pass für quadratische Probleme, erstellt und optimiert.\n",
"\n",
"In diesem Beispiel wählen wir eine SWAP-Einfügungsstrategie für Blöcke von pendelnden Zwei-Qubit-Gates, die Schichten von SWAP-Gates anwendet, die gleichzeitig auf der Kopplungskarte ausgeführt werden können. Diese Strategie wird in [\\[1\\]](#references) vorgestellt und an übergeben `Commuting2qGateRouter`, das als standardisierter Qiskit-Transpiler-Durchlauf bereitgestellt wird (siehe [`Commuting2qGateRouter`](/docs/api/qiskit/qiskit.transpiler.passes.Commuting2qGateRouter)). In diesem Beispiel verwenden wir eine Line-Swap-Strategie.\n",
"\n"
]
},
{
"cell_type": "code",
"execution_count": 99,
"id": "7c54402a-7696-4b0e-826a-6e0ac4c54395",
"metadata": {},
"outputs": [],
"source": [
"# Extract longest path with no repeated nodes\n",
"nodes = rx.longest_simple_path(graph_100)\n",
"\n",
"# Collect even edges and odd edges\n",
"even_edges = [\n",
" (nodes[i], nodes[i + 1])\n",
" if nodes[i] < nodes[i + 1]\n",
" else (nodes[i + 1], nodes[i])\n",
" for i in range(0, len(nodes) - 1, 2)\n",
"]\n",
"odd_edges = [\n",
" (nodes[i], nodes[i + 1])\n",
" if nodes[i] < nodes[i + 1]\n",
" else (nodes[i + 1], nodes[i])\n",
" for i in range(1, len(nodes) - 1, 2)\n",
"]\n",
"edge_list = [\n",
" (edge[0], edge[1]) if edge[0] < edge[1] else (edge[1], edge[0])\n",
" for edge in graph_100.edge_list()\n",
"]\n",
"\n",
"swap_strategy = SwapStrategy(CouplingMap(edge_list), (even_edges, odd_edges))"
]
},
{
"cell_type": "markdown",
"id": "ba53fd1d-0d68-43e3-9102-4c6e64f04de7",
"metadata": {},
"source": [
"\n",
"\n",
"#### Ordnen Sie das Diagramm mithilfe eines SAT-Mappers neu zu\n",
"\n",
"Selbst wenn eine Schaltung aus kommutierenden Gatterelementen besteht (dies ist bei der QAOA-Schaltung der Fall, aber auch bei Trotter-Simulationen von Ising-Hamiltonianen), ist die Suche nach einer guten Anfangsabbildung eine anspruchsvolle Aufgabe. Wenn wir den in [\\[2\\]](#references) vorgestellten SAT-basierten Ansatz anwenden, können wir effektive Anfangsabbildungen für Schaltungen mit kommutierenden Gatterelementen ermitteln, was zu einer erheblichen Verringerung der Anzahl der erforderlichen SWAP-Schichten führt. Wie in der Veröffentlichung dargelegt, hat sich gezeigt, dass dieser Ansatz auf bis zu *500 Qubits* skalierbar ist.\n",
"\n",
"Der folgende Code zeigt, wie die `SATMapper` von Matsuo et al. verwendet wird, um den Graphen neu abzubilden. Dieses Verfahren ermöglicht es, das Problem auf einen optimaleren Anfangszustand für eine bestimmte SWAP-Strategie abzubilden, was zu einer erheblichen Verringerung der Anzahl der für die Ausführung der Schaltung erforderlichen SWAP-Schichten führt.\n",
"\n",
"In `SATMapper` wird das Problem, eine gute Anfangsabbildung zu finden, als SAT-Problem formuliert. Ein SAT-Solver wird verwendet, um eine solche Anfangsabbildung für den QAOA-Schaltkreis zu finden. `python-sat` (kurz:`pysat` ) ist eine Python Bibliothek für einen SAT-Solver, und wir werden sie zur Lösung des SAT-Problems in diesem Beispiel verwenden.\n",
"\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "df9d861a-64e8-49ee-aed1-c41f437fa743",
"metadata": {},
"outputs": [],
"source": [
"\"\"\"A class to solve the SWAP gate insertion initial mapping problem\n",
"using the SAT approach from https://arxiv.org/abs/2212.05666.\n",
"\"\"\"\n",
"\n",
"\n",
"@dataclass\n",
"class SATResult:\n",
" \"\"\"A data class to hold the result of a SAT solver.\"\"\"\n",
"\n",
" satisfiable: bool # Satisfiable is True if the SAT model could be solved\n",
" # in a given time.\n",
" solution: dict # The solution to the SAT problem if it is satisfiable.\n",
" mapping: list # The mapping of nodes in the pattern graph to nodes in the\n",
" # target graph.\n",
" elapsed_time: float # The time it took to solve the SAT model.\n",
"\n",
"\n",
"class SATMapper:\n",
" r\"\"\"A class to introduce a SAT-approach to solve\n",
" the initial mapping problem in SWAP gate insertion for commuting gates.\n",
"\n",
" When this pass is run on a DAG it will look for the first instance of\n",
" :class:`.Commuting2qBlock` and use the program graph :math:`P` of this block\n",
" of gates to find a layout for a given swap strategy. This layout is found\n",
" with a binary search over the layers :math:`l` of the swap strategy. At each\n",
" considered layer a subgraph isomorphism problem formulated as a SAT is solved\n",
" by a SAT solver. Each instance is whether it is possible to embed the program\n",
" graph :math:`P` into the effective connectivity graph :math:`C_l` that is\n",
" achieved by applying :math:`l` layers of the swap strategy to the coupling map\n",
" :math:`C_0` of the backend. Since solving SAT problems can be hard, a\n",
" ``time_out`` fixes the maximum time allotted to the SAT solver for each\n",
" instance. If this time is exceeded the considered problem is deemed\n",
" unsatisfiable and the binary search proceeds to the next number of swap\n",
" layers :math:``l``.\n",
" \"\"\"\n",
"\n",
" def __init__(self, timeout: int = 60):\n",
" \"\"\"Initialize the SATMapping.\n",
"\n",
" Args:\n",
" timeout: The allowed time in seconds for each iteration of the SAT\n",
" solver. This variable defaults to 60 seconds.\n",
" \"\"\"\n",
" self.timeout = timeout\n",
"\n",
" def find_initial_mappings(\n",
" self,\n",
" program_graph: rx.PyGraph,\n",
" swap_strategy: SwapStrategy,\n",
" min_layers: int | None = None,\n",
" max_layers: int | None = None,\n",
" ) -> dict[int, SATResult]:\n",
" r\"\"\"Find an initial mapping for a given swap strategy. Perform a\n",
" binary search over the number of swap layers, and for each number\n",
" of swap layers solve a subgraph isomorphism problem formulated as\n",
" a SAT problem.\n",
"\n",
" Args:\n",
" program_graph (rx.PyGraph): The program graph with commuting gates, where\n",
" each edge represents a two-qubit gate.\n",
" swap_strategy (SwapStrategy): The swap strategy to use to find the\n",
" initial mapping.\n",
" min_layers (int): The minimum number of swap layers to consider.\n",
" Defaults to the maximum degree of the\n",
" program graph - 2.\n",
" max_layers (int): The maximum number of swap layers to consider.\n",
" Defaults to the number of qubits in the\n",
" swap strategy - 2.\n",
"\n",
" Returns:\n",
" dict[int, SATResult]: A dictionary containing the results of the SAT\n",
" solver for each number of swap layers.\n",
" \"\"\"\n",
" num_nodes_g1 = len(program_graph.nodes())\n",
" num_nodes_g2 = swap_strategy.distance_matrix.shape[0]\n",
" if num_nodes_g1 > num_nodes_g2:\n",
" return SATResult(False, [], [], 0)\n",
" if min_layers is None:\n",
" # use the maximum degree of the program graph - 2\n",
" # as the lower bound.\n",
" min_layers = max((d for _, d in program_graph.degree)) - 2\n",
" if max_layers is None:\n",
" max_layers = num_nodes_g2 - 1\n",
"\n",
" variable_pool = IDPool(start_from=1)\n",
" variables = np.array(\n",
" [\n",
" [variable_pool.id(f\"v_{i}_{j}\") for j in range(num_nodes_g2)]\n",
" for i in range(num_nodes_g1)\n",
" ],\n",
" dtype=int,\n",
" )\n",
" vid2mapping = {v: idx for idx, v in np.ndenumerate(variables)}\n",
" binary_search_results = {}\n",
"\n",
" def interrupt(solver):\n",
" # This function is called to interrupt the solver when the\n",
" # timeout is reached.\n",
" solver.interrupt()\n",
"\n",
" # Make a cnf (conjunctive normal form) for the one-to-one\n",
" # mapping constraint\n",
" cnf1 = []\n",
" for i in range(num_nodes_g1):\n",
" clause = variables[i, :].tolist()\n",
" cnf1.append(clause)\n",
" for k, m in combinations(clause, 2):\n",
" cnf1.append([-1 * k, -1 * m])\n",
" for j in range(num_nodes_g2):\n",
" clause = variables[:, j].tolist()\n",
" for k, m in combinations(clause, 2):\n",
" cnf1.append([-1 * k, -1 * m])\n",
"\n",
" # Perform a binary search over the number of swap layers to find the\n",
" # minimum number of swap layers that satisfies the subgraph isomorphism\n",
" # problem.\n",
" while min_layers < max_layers:\n",
" num_layers = (min_layers + max_layers) // 2\n",
"\n",
" # Create the connectivity matrix. Note that if the swap strategy\n",
" # cannot reach full connectivity then its distance matrix will have\n",
" # entries with -1. These entries must be treated as False.\n",
" d_matrix = swap_strategy.distance_matrix\n",
" connectivity_matrix = (\n",
" (-1 < d_matrix) & (d_matrix <= num_layers)\n",
" ).astype(int)\n",
" # Make a cnf for the adjacency constraint\n",
" cnf2 = []\n",
" for e_0, e_1 in list(program_graph.edge_list()):\n",
" clause_matrix = np.multiply(\n",
" connectivity_matrix, variables[e_1, :]\n",
" )\n",
" clause = np.concatenate(\n",
" (\n",
" [[-variables[e_0, i]] for i in range(num_nodes_g2)],\n",
" clause_matrix,\n",
" ),\n",
" axis=1,\n",
" )\n",
" # Remove 0s from each clause\n",
" cnf2.extend([c[c != 0].tolist() for c in clause])\n",
"\n",
" cnf = CNF(from_clauses=cnf1 + cnf2)\n",
"\n",
" with Solver(bootstrap_with=cnf, use_timer=True) as solver:\n",
" # Solve the SAT problem with a timeout.\n",
" # Timer is used to interrupt the solver when the\n",
" # timeout is reached.\n",
" timer = Timer(self.timeout, interrupt, [solver])\n",
" timer.start()\n",
" status = solver.solve_limited(expect_interrupt=True)\n",
" timer.cancel()\n",
" # Get the solution and the elapsed time.\n",
" sol = solver.get_model()\n",
" e_time = solver.time()\n",
"\n",
" print(\n",
" f\"Layers: {num_layers}, Status: {status}, Time: {e_time}\"\n",
" )\n",
" if status:\n",
" # If the SAT problem is satisfiable, convert the solution\n",
" # to a mapping.\n",
" mapping = [vid2mapping[idx] for idx in sol if idx > 0]\n",
" binary_search_results[num_layers] = SATResult(\n",
" status, sol, mapping, e_time\n",
" )\n",
" max_layers = num_layers\n",
" else:\n",
" # If the SAT problem is unsatisfiable, return the last\n",
" # satisfiable solution.\n",
" binary_search_results[num_layers] = SATResult(\n",
" status, sol, [], e_time\n",
" )\n",
" min_layers = num_layers + 1\n",
"\n",
" return binary_search_results\n",
"\n",
" def remap_graph_with_sat(\n",
" self, graph: rx.PyGraph, swap_strategy, max_layers\n",
" ):\n",
" \"\"\"Applies the SAT mapping.\n",
"\n",
" Args:\n",
" graph (nx.Graph): The graph to remap.\n",
" swap_strategy (SwapStrategy): The swap strategy to use\n",
" to find the initial mapping.\n",
"\n",
" Returns:\n",
" tuple: A tuple containing the remapped graph, the edge map, and the\n",
" number of layers of the swap strategy that was used to find the\n",
" initial mapping. If no solution is found then the tuple contains\n",
" None for each element. Note the returned edge map `{k: v}` means that\n",
" node `k` in the original graph gets mapped to node `v` in the\n",
" Pauli strings.\n",
" \"\"\"\n",
" num_nodes = len(graph.nodes())\n",
" results = self.find_initial_mappings(\n",
" graph, swap_strategy, 0, max_layers\n",
" )\n",
" solutions = [k for k, v in results.items() if v.satisfiable]\n",
"\n",
" if len(solutions):\n",
" min_k = min(solutions)\n",
" edge_map = dict(results[min_k].mapping)\n",
" # Create the remapped graph\n",
" remapped_graph = rx.PyGraph()\n",
" remapped_graph.add_nodes_from(range(num_nodes))\n",
" mapping = dict(results[min_k].mapping)\n",
" for i, graph_edge in enumerate(list(graph.edge_list())):\n",
" remapped_edge = tuple(mapping[node] for node in graph_edge)\n",
" remapped_graph.add_edge(*remapped_edge, graph.edges()[i])\n",
" return remapped_graph, edge_map, min_k\n",
" else:\n",
" return None, None, None"
]
},
{
"cell_type": "code",
"execution_count": 101,
"id": "e689e09e-6ca7-4154-8602-d1d954ebe80b",
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Layers: 0, Status: True, Time: 0.022812999999999306\n",
"Map from old to new nodes: {0: 0, 1: 1, 2: 2, 3: 3, 4: 4, 5: 5, 6: 6, 7: 7, 8: 8, 9: 9, 10: 10, 11: 11, 12: 12, 13: 13, 14: 14, 15: 15, 16: 16, 17: 17, 18: 18, 19: 19, 20: 20, 21: 21, 22: 22, 23: 23, 24: 24, 25: 25, 26: 26, 27: 27, 28: 28, 29: 29, 30: 30, 31: 31, 32: 32, 33: 33, 34: 34, 35: 35, 36: 36, 37: 37, 38: 38, 39: 39, 40: 40, 41: 41, 42: 42, 43: 43, 44: 44, 45: 45, 46: 46, 47: 47, 48: 48, 49: 49, 50: 50, 51: 51, 52: 52, 53: 53, 54: 54, 55: 55, 56: 56, 57: 57, 58: 58, 59: 59, 60: 60, 61: 61, 62: 62, 63: 63, 64: 64, 65: 65, 66: 66, 67: 67, 68: 68, 69: 69, 70: 70, 71: 71, 72: 72, 73: 73, 74: 74, 75: 75, 76: 76, 77: 77, 78: 78, 79: 79, 80: 80, 81: 81, 82: 82, 83: 83, 84: 84, 85: 85, 86: 86, 87: 87, 88: 88, 89: 89, 90: 90, 91: 91, 92: 92, 93: 93, 94: 94, 95: 95, 96: 96, 97: 97, 98: 98, 99: 99}\n",
"Min SWAP layers: 0\n"
]
},
{
"data": {
"text/plain": [
""
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"sm = SATMapper(timeout=10)\n",
"remapped_graph, edge_map, min_swap_layers = sm.remap_graph_with_sat(\n",
" graph=graph_100, swap_strategy=swap_strategy, max_layers=1\n",
")\n",
"print(\"Map from old to new nodes: \", edge_map)\n",
"print(\"Min SWAP layers:\", min_swap_layers)\n",
"draw_graph(remapped_graph, node_size=200, with_labels=True, width=1)"
]
},
{
"cell_type": "code",
"execution_count": 102,
"id": "ecf6e8c3-65c2-4430-8dd3-d67b8842045d",
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"SparsePauliOp(['IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZ', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZI', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZIIIIIIIIIIIIZIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZIIIIIIIIIZIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZIIIIIIZIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZIIIZIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZIIIIIIZIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZIIIIIIIIIZIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZIIIIIIIIIIIIZIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZIIIIIIIIIIIIIIIZIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZIIIIIIIIIIIIIIZIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZIIIIIIIIIIIZIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZIIIIIIIIZIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZIIIIIZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZIIIIZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZIIIIIIIZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZIIIIIIIIIIZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZIIIIIIIIIIIIIZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZIIIIIIIIIIIIZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZIIIIIIIIIZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZIIIIIIZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZIIIZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZIIIIIIZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZIIIIIIIIIZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIZIIIIIIIIIIIIZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIZIIIIIIIIIIIIIIIZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIZIIIIIIIIIIIIIIZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIZIIIIIIIIIIIZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIZIIIIIIIIZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIZIIIIIZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIZIIIIZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIZIIIIIIIZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIZIIIIIIIIIIZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIZIIIIIIIIIIIIIZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIZIIIIIIIIIIIIZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIZIIIIIIIIIZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IZIIIIIIZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'ZIIIZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII'],\n",
" coeffs=[1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j,\n",
" 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j,\n",
" 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j,\n",
" 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j,\n",
" 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j,\n",
" 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j,\n",
" 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j,\n",
" 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j,\n",
" 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j,\n",
" 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j,\n",
" 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j,\n",
" 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j,\n",
" 1.+0.j, 1.+0.j, 1.+0.j])\n"
]
}
],
"source": [
"remapped_max_cut_paulis = build_max_cut_paulis(remapped_graph)\n",
"# define a qiskit SparsePauliOp from the list of paulis\n",
"remapped_cost_operator = SparsePauliOp.from_list(remapped_max_cut_paulis)\n",
"print(remapped_cost_operator)"
]
},
{
"cell_type": "markdown",
"id": "5ae531be-80eb-4acd-b84a-7d466fd872e7",
"metadata": {},
"source": [
"\n",
"\n",
"#### Erstellen Sie eine QAOA-Schaltung mit der SWAP-Strategie und der SAT-Abbildung\n",
"\n",
"Da wir die SWAP-Strategien nur auf die Kostenoperator-Ebene anwenden wollen, beginnen wir mit der Erstellung des isolierten Blocks, den wir später transformieren und an die endgültige QAOA-Schaltung anhängen werden.\n",
"\n",
"Dazu können wir die [`QAOAAnsatz`](/docs/api/qiskit/qiskit.circuit.library.QAOAAnsatz) Klasse aus Qiskit verwenden. Wir geben in die `initial_state` Felder und `mixer_operator` einen leeren Schaltkreis ein, um sicherzustellen, dass wir eine isolierte Kostenoperator-Schicht erstellen.\n",
"Wir definieren die `edge_coloring` Zuordnung zudem so, dass RZZ-Gatter neben SWAP-Gatter angeordnet sind. Diese strategische Positionierung ermöglicht es uns, Stornierungen bei der Formel 1 zu nutzen und die Rennstrecke für eine bessere Leistung zu optimieren.\n",
"Dieser Vorgang wird innerhalb der `create_qaoa_swap_circuit` Funktion ausgeführt.\n",
"\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "57d5eb53-9cda-4c38-a00b-26ed4b533bcd",
"metadata": {},
"outputs": [],
"source": [
"def make_meas_map(circuit: QuantumCircuit) -> dict:\n",
" \"\"\"Return a mapping from qubit index (the key) to classical bit (the value).\n",
"\n",
" This allows us to account for the swapping order introduced by the\n",
" SWAP strategy.\n",
" \"\"\"\n",
" creg = circuit.cregs[0]\n",
" qreg = circuit.qregs[0]\n",
"\n",
" meas_map = {}\n",
" for inst in circuit.data:\n",
" if inst.operation.name == \"measure\":\n",
" meas_map[qreg.index(inst.qubits[0])] = creg.index(inst.clbits[0])\n",
"\n",
" return meas_map\n",
"\n",
"\n",
"def apply_swap_strategy(\n",
" circuit: QuantumCircuit,\n",
" swap_strategy: SwapStrategy,\n",
" edge_coloring: dict[tuple[int, int], int] | None = None,\n",
") -> QuantumCircuit:\n",
" \"\"\"Transpile with a SWAP strategy.\n",
"\n",
" Returns:\n",
" A quantum circuit transpiled with the given swap strategy.\n",
" \"\"\"\n",
"\n",
" pm_pre = PassManager(\n",
" [\n",
" FindCommutingPauliEvolutions(),\n",
" Commuting2qGateRouter(\n",
" swap_strategy,\n",
" edge_coloring,\n",
" ),\n",
" ]\n",
" )\n",
" return pm_pre.run(circuit)\n",
"\n",
"\n",
"def apply_qaoa_layers(\n",
" cost_layer: QuantumCircuit,\n",
" meas_map: dict,\n",
" num_layers: int,\n",
" gamma: list[float] | ParameterVector = None,\n",
" beta: list[float] | ParameterVector = None,\n",
" initial_state: QuantumCircuit = None,\n",
" mixer: QuantumCircuit = None,\n",
"):\n",
" \"\"\"Applies QAOA layers to construct circuit.\n",
"\n",
" First, the initial state is applied. If `initial_state` is None, we begin in\n",
" the initial superposition state. Next, we alternate between layers of the\n",
" cost operator and the mixer. The cost operator is alternatively applied in\n",
" order and in reverse instruction order. This allows us to apply the swap\n",
" strategy on odd `p` layers and undo the swap strategy on even `p` layers.\n",
" \"\"\"\n",
"\n",
" num_qubits = cost_layer.num_qubits\n",
" new_circuit = QuantumCircuit(num_qubits, num_qubits)\n",
"\n",
" if initial_state is not None:\n",
" new_circuit.append(initial_state, range(num_qubits))\n",
" else:\n",
" # all h state by default\n",
" new_circuit.h(range(num_qubits))\n",
"\n",
" if gamma is None or beta is None:\n",
" gamma = ParameterVector(\"γ'\", num_layers)\n",
" if mixer is None or mixer.num_parameters == 0:\n",
" beta = ParameterVector(\"β'\", num_layers)\n",
" else:\n",
" beta = ParameterVector(\"β'\", num_layers * mixer.num_parameters)\n",
"\n",
" if mixer is not None:\n",
" mixer_layer = mixer\n",
" else:\n",
" mixer_layer = QuantumCircuit(num_qubits)\n",
" mixer_layer.rx(-2 * beta[0], range(num_qubits))\n",
"\n",
" for layer in range(num_layers):\n",
" bind_dict = {cost_layer.parameters[0]: gamma[layer]}\n",
" cost_layer_ = cost_layer.assign_parameters(bind_dict)\n",
" bind_dict = {\n",
" mixer_layer.parameters[i]: beta[layer + i]\n",
" for i in range(mixer_layer.num_parameters)\n",
" }\n",
" layer_mixer = mixer_layer.assign_parameters(bind_dict)\n",
"\n",
" if layer % 2 == 0:\n",
" new_circuit.append(cost_layer_, range(num_qubits))\n",
" else:\n",
" new_circuit.append(cost_layer_.reverse_ops(), range(num_qubits))\n",
"\n",
" new_circuit.append(layer_mixer, range(num_qubits))\n",
"\n",
" for qidx, cidx in meas_map.items():\n",
" new_circuit.measure(qidx, cidx)\n",
"\n",
" return new_circuit\n",
"\n",
"\n",
"def create_qaoa_swap_circuit(\n",
" cost_operator: SparsePauliOp,\n",
" swap_strategy: SwapStrategy,\n",
" edge_coloring: dict = None,\n",
" theta: list[float] = None,\n",
" qaoa_layers: int = 1,\n",
" initial_state: QuantumCircuit = None,\n",
" mixer: QuantumCircuit = None,\n",
"):\n",
" \"\"\"Create the circuit for QAOA.\n",
"\n",
" Notes: This circuit construction for QAOA works for quadratic terms in `Z`\n",
" and will be extended to first-order terms in `Z`.\n",
" Higher-orders are not supported.\n",
"\n",
" Args:\n",
" cost_operator: the cost operator.\n",
" swap_strategy: selected swap strategy\n",
" edge_coloring: A coloring of edges that should correspond to the\n",
" coupling map of the hardware. It defines the order in which\n",
" we apply the Rzz gates. This allows us to choose an ordering\n",
" such that `Rzz` gates will immediately precede SWAP gates\n",
" to leverage CNOT cancellation.\n",
" theta: The QAOA angles.\n",
" qaoa_layers: The number of layers of the cost operator and the\n",
" mixer operator.\n",
" initial_state: The initial state on which we apply layers of\n",
" cost operator and mixer.\n",
" mixer: The QAOA mixer. It will be applied as is onto the QAOA\n",
" circuit. Therefore, its output must have the same ordering\n",
" of qubits as its input.\n",
" \"\"\"\n",
"\n",
" num_qubits = cost_operator.num_qubits\n",
"\n",
" if theta is not None:\n",
" gamma = theta[: len(theta) // 2]\n",
" beta = theta[len(theta) // 2 :]\n",
" qaoa_layers = len(theta) // 2\n",
" else:\n",
" gamma = beta = None\n",
"\n",
" # First, create the ansatz of one layer of QAOA without mixer\n",
" cost_layer = QAOAAnsatz(\n",
" cost_operator,\n",
" reps=1,\n",
" initial_state=QuantumCircuit(num_qubits),\n",
" mixer_operator=QuantumCircuit(num_qubits),\n",
" ).decompose()\n",
"\n",
" # This will allow us to recover the permutation of the measurements\n",
" # that the swaps introduce.\n",
" cost_layer.measure_all()\n",
"\n",
" # Now, apply the swap strategy for commuting gates\n",
" cost_layer = apply_swap_strategy(cost_layer, swap_strategy, edge_coloring)\n",
"\n",
" # Compute the measurement map (qubit to classical bit).\n",
" # We will apply this for odd layers where the swaps were inserted.\n",
" if qaoa_layers % 2 == 1:\n",
" meas_map = make_meas_map(cost_layer)\n",
" else:\n",
" meas_map = {idx: idx for idx in range(num_qubits)}\n",
"\n",
" cost_layer.remove_final_measurements()\n",
"\n",
" # Finally, introduce the mixer circuit and add measurements\n",
" # following measurement map\n",
" circuit = apply_qaoa_layers(\n",
" cost_layer, meas_map, qaoa_layers, gamma, beta, initial_state, mixer\n",
" )\n",
"\n",
" return circuit"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "7793ef92-ce59-4fd7-b43f-48d4e3427e3a",
"metadata": {},
"outputs": [],
"source": [
"# We can define the edge_coloring map so that RZZ gates are positioned\n",
"# right before SWAP gates to exploit CX cancellations\n",
"# We use greedy edge coloring from rustworkx to color the edges of\n",
"# the graph. This coloring is used to order the RZZ gates\n",
"# in the circuit.\n",
"\n",
"edge_coloring_idx = rx.graph_greedy_edge_color(graph_100)\n",
"edge_coloring = {\n",
" edge: edge_coloring_idx[idx]\n",
" for idx, edge in enumerate(list(graph_100.edge_list()))\n",
"}\n",
"edge_coloring = {tuple(sorted(k)): v for k, v in edge_coloring.items()}"
]
},
{
"cell_type": "code",
"execution_count": 105,
"id": "82ae28b3-85eb-4487-8100-1e622e93cccf",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
""
]
},
"execution_count": 105,
"metadata": {},
"output_type": "execute_result"
}
],
"source": [
"qaoa_circ = create_qaoa_swap_circuit(\n",
" remapped_cost_operator,\n",
" swap_strategy,\n",
" edge_coloring=edge_coloring,\n",
" qaoa_layers=1,\n",
")\n",
"qaoa_circ.draw(output=\"mpl\", fold=False)"
]
},
{
"cell_type": "markdown",
"id": "e2afd1a7-0980-433b-a3a8-303d7e7718b1",
"metadata": {},
"source": [
"\n",
"\n",
"## Schritt 3: Ausführung mithilfe von „ IBM Quantum “-Primitiven\n",
"\n",
"Bereiten wir nun die Ausführung auf der Hardware vor. Unser erster Schritt wird darin bestehen, eine Kostenfunktion für den bedingten Value at Risk ( CVaR ) zu definieren, die in [\\[3\\]](#references) für den Einsatz im Rahmen des Paradigmas der variationalen Quantenoptimierungsalgorithmen eingeführt wurde.\n",
"\n",
"Die CVaR einer Zufallsvariablen $X$ für ein Konfidenzniveau $α ∈ (0, 1]$ ist definiert als $CVaR_{\\alpha}(X) = \\mathbb{E} \\lbrack X | X \\leq F_X^{-1}(\\alpha) \\rbrack$ wobei $F_X^{-1}(p)$ die inverse kumulative Verteilungsfunktion von $X$ ist. Mit anderen Worten: CVaR ist der Erwartungswert des unteren $\\alpha$ -Schwanzes der Verteilung von $X$.\n",
"\n"
]
},
{
"cell_type": "code",
"execution_count": 106,
"id": "172023f9-164e-43bd-bbc8-39d87628287e",
"metadata": {},
"outputs": [],
"source": [
"pass_manager = generate_preset_pass_manager(\n",
" backend=backend,\n",
" optimization_level=3,\n",
")\n",
"\n",
"transpiled_qaoa_circ = pass_manager.run(qaoa_circ)"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "e6794cf3-7fbe-46a5-bdc0-5faad1235365",
"metadata": {},
"outputs": [],
"source": [
"# Utility functions for the evaluation of the expectation value of a measured state\n",
"# In this code, for optimization, the measured state is converted into a bit string,\n",
"# and the sign of the value is determined by taking the exclusive OR of the bits\n",
"# corresponding to Pauli Z.\n",
"\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",
" \"\"\"Utility for the evaluation of the expectation value\n",
" of a measured state.\n",
"\n",
" Args:\n",
" state (int): The measured state.\n",
" observable (SparsePauliOp): The observable to evaluate the\n",
" expectation value for.\n",
"\n",
" Returns:\n",
" complex: The expectation value of the measured state.\n",
" \"\"\"\n",
" packed_uint8 = np.packbits(\n",
" observable.paulis.z, axis=1, bitorder=\"little\"\n",
" ) # convert observable to array with 8 bit integer\n",
" state_bytes = np.frombuffer(\n",
" state.to_bytes(packed_uint8.shape[1], \"little\"),\n",
" dtype=np.uint8, # convert bitstring to array with 8 bit integer\n",
" )\n",
" reduced = np.bitwise_xor.reduce(packed_uint8 & state_bytes, axis=1)\n",
" # take bitwise xor of the result of 'and' conditional on the\n",
" # above two, return 0 or 1\n",
" return np.sum(observable.coeffs * _PARITY[reduced])"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "c5e5f7a4-01f6-4a02-9114-3bb0e24be1a2",
"metadata": {},
"outputs": [],
"source": [
"def qaoa_sampler_cost_fun(\n",
" params, ansatz, hamiltonian, sampler, aggregation=None\n",
"):\n",
" \"\"\"Standard sampler-based QAOA cost function to be plugged into\n",
" optimizer routines.\n",
"\n",
" Args:\n",
" params (np.ndarray): Parameters for the ansatz.\n",
" ansatz (QuantumCircuit): Ansatz circuit.\n",
" hamiltonian (SparsePauliOp): Hamiltonian to be minimized.\n",
" sampler (QAOASampler): Sampler to be used.\n",
" aggregation (Callable | float | None): Aggregation function\n",
" to be applied to the sampled results. If None, the sum\n",
" of the expectation values is returned.\n",
" If float, the CVaR with the given alpha is used.\n",
" \"\"\"\n",
" # Run the circuit\n",
" job = sampler.run([(ansatz, params)])\n",
" sampler_result = job.result()\n",
" sampled_int_counts = sampler_result[\n",
" 0\n",
" ].data.c.get_int_counts() # bitstrings are stored as integers\n",
" shots = sum(sampled_int_counts.values())\n",
" int_count_distribution = {\n",
" key: val / shots for key, val in sampled_int_counts.items()\n",
" }\n",
"\n",
" # a dictionary containing: {state: (measurement probability, value)}\n",
" evaluated = {\n",
" state: (\n",
" probability,\n",
" np.real(evaluate_sparse_pauli(state, hamiltonian)),\n",
" )\n",
" for state, probability in int_count_distribution.items()\n",
" }\n",
"\n",
" # If aggregation is None, return the sum of the expectation values.\n",
" # If aggregation is a float, return the CVaR with the given alpha.\n",
" # Otherwise, use the aggregation function.\n",
" if aggregation is None:\n",
" result = sum(\n",
" probability * value for probability, value in evaluated.values()\n",
" )\n",
" elif isinstance(aggregation, float):\n",
" cvar_aggregation = _get_cvar_aggregation(aggregation)\n",
" result = cvar_aggregation(evaluated.values())\n",
" else:\n",
" result = aggregation(evaluated.values())\n",
"\n",
" global iter_counts, result_dict\n",
" iter_counts += 1\n",
" temp_dict = {}\n",
" temp_dict[\"params\"] = params.tolist()\n",
" temp_dict[\"cvar_fval\"] = result\n",
" temp_dict[\"fval\"] = sum(\n",
" probability * value for probability, value in evaluated.values()\n",
" )\n",
" temp_dict[\"distribution\"] = sampled_int_counts\n",
" temp_dict[\"evaluated\"] = evaluated\n",
" result_dict[iter_counts] = temp_dict\n",
" print(f\"Iteration {iter_counts}: {result}\")\n",
"\n",
" return result\n",
"\n",
"\n",
"def _get_cvar_aggregation(alpha: float | None) -> Callable:\n",
" \"\"\"Return the CVaR aggregation function with the given alpha.\n",
"\n",
" Args:\n",
" alpha (float | None): Alpha value for the CVaR aggregation.\n",
" If None, 1 is used by default.\n",
" Raises:\n",
" ValueError: If alpha is not in [0, 1].\n",
" \"\"\"\n",
" if alpha is None:\n",
" alpha = 1\n",
" elif not 0 <= alpha <= 1:\n",
" raise ValueError(f\"alpha must be in [0, 1], but {alpha} was given.\")\n",
"\n",
" def cvar_aggregation(\n",
" objective_dict: Iterable[tuple[float, float]],\n",
" ) -> float:\n",
" \"\"\"Return the CVaR of the given measurements.\n",
" Args:\n",
" objective_dict (Iterable[tuple[float, float]]): An iterable\n",
" of tuples containing the measured bit string and the\n",
" objective value based on the bit string.\n",
"\n",
" \"\"\"\n",
" sorted_measurements = sorted(objective_dict, key=lambda x: x[1])\n",
" # accumulate the probabilities until alpha is reached\n",
" accumulated_percent = 0.0\n",
" cvar = 0.0\n",
" for probability, value in sorted_measurements:\n",
" cvar += value * min(probability, alpha - accumulated_percent)\n",
" accumulated_percent += probability\n",
" if accumulated_percent >= alpha:\n",
" break\n",
" return cvar / alpha\n",
"\n",
" return cvar_aggregation"
]
},
{
"cell_type": "markdown",
"id": "63fa2ab4-5354-4022-ab46-e9bbf73870de",
"metadata": {},
"source": [
"Die „ CVaR “ kann, wie bereits erörtert [\\[4\\]](#references), als Methode zur Fehlerminderung eingesetzt werden. In diesem Beispiel bestimmen wir die Parameter „ $\\alpha$ “ und die Anzahl der Schüsse anhand des mit der Schaltung verbundenen [Fehlerwerts pro Schichtgatter](/docs/guides/qpu-information#2q-error-layered) (EPLG).\n",
"\n"
]
},
{
"cell_type": "code",
"execution_count": 109,
"id": "032bf312-4bf4-40f4-81f0-2ae8a719b98b",
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"layer fidelity 0.5454643821399414\n",
"\n",
"The corresponding CVaR aggregation value is: 0.2568730767702702\n",
"To mitigate the twirled noise, increase shots by a factor of 3.8929731857197782\n"
]
}
],
"source": [
"num_2q_ops = transpiled_qaoa_circ.count_ops()[\n",
" \"cz\"\n",
"] # the two qubit gates on our backend are cz's.\n",
"\n",
"for el in backend.properties().general:\n",
" if el.name[:2] == \"lf\" and el.name[3:] == str(\n",
" n\n",
" ): # pick out lf_100, lf of the best 100q chain\n",
" lf = el.value # layer fidelity\n",
" print(\"layer fidelity\", lf)\n",
" eplg = 1 - lf ** (1 / (n - 1)) # error per layered gate (EPLG)\n",
" fid_cz = 1 - eplg\n",
" gamma_cz = 1 / fid_cz**2\n",
" gamma_circ = gamma_cz**num_2q_ops\n",
"\n",
"cvar_aggregation = 1 / np.sqrt(gamma_circ)\n",
"print(\"\")\n",
"print(\"The corresponding CVaR aggregation value is: \", cvar_aggregation)\n",
"print(\n",
" \"To mitigate the twirled noise, increase shots by a factor of\",\n",
" np.sqrt(gamma_circ),\n",
")"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "382e8acd-d0d0-4302-99aa-b64e5dd31e17",
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Iteration 1: -13.227556797094595\n",
"Iteration 2: -13.181545294899571\n",
"Iteration 3: -13.149537293372594\n",
"Iteration 4: -3.305576300816324\n",
"Iteration 5: -12.647411769418035\n",
"Iteration 6: -13.443610807401718\n",
"Iteration 7: -12.475368761210511\n",
"Iteration 8: -15.905726329447413\n",
"Iteration 9: -18.011752834505565\n",
"Iteration 10: -14.125781339945583\n",
"Iteration 11: -19.693673319331744\n",
"Iteration 12: -21.175543794613695\n",
"Iteration 13: -21.805701324676196\n",
"Iteration 14: -22.121280244318488\n",
"Iteration 15: -20.02575633517435\n",
"Iteration 16: -22.399349757584158\n",
"Iteration 17: -22.569392265696226\n",
"Iteration 18: -21.877719328111898\n",
"Iteration 19: -22.79144777628963\n",
"Iteration 20: -22.437359259397432\n",
"Iteration 21: -23.021505287264777\n",
"Iteration 22: -22.69742427180412\n",
"Iteration 23: -23.12553129222746\n",
"Iteration 24: -22.893473281156922\n",
" message: Return from COBYLA because the trust region radius reaches its lower bound.\n",
" success: True\n",
" status: 0\n",
" fun: -23.12553129222746\n",
" x: [ 2.766e+00 1.080e+00]\n",
" nfev: 24\n",
" maxcv: 0.0\n"
]
}
],
"source": [
"iter_counts = 0\n",
"result_dict = {}\n",
"init_params = [np.pi, np.pi / 2]\n",
"\n",
"with Session(backend=backend) as session:\n",
" sampler = Sampler(mode=session)\n",
" sampler.options.default_shots = int(1000 / cvar_aggregation)\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.enable_measure = True\n",
" sampler.options.environment.job_tags = [\n",
" \"TUT_AQAOA\"\n",
" ] # add tag for your job execution\n",
"\n",
" result = minimize(\n",
" qaoa_sampler_cost_fun,\n",
" init_params,\n",
" args=(\n",
" transpiled_qaoa_circ,\n",
" remapped_cost_operator,\n",
" sampler,\n",
" cvar_aggregation,\n",
" ),\n",
" method=\"COBYLA\",\n",
" tol=1e-2,\n",
" )\n",
"print(result)"
]
},
{
"cell_type": "markdown",
"id": "1d190fa4-3bbe-412a-b296-6dddd3ad2b12",
"metadata": {},
"source": [
"\n",
"\n",
"## Schritt 4: Nachbearbeitung und Rückgabe des Ergebnisses im gewünschten klassischen Format\n",
"\n",
"Lassen Sie uns nun unsere Ergebnisse grafisch darstellen und anschließend nachbearbeiten, um den Wert des Schnitts zu ermitteln.\n",
"\n"
]
},
{
"cell_type": "code",
"execution_count": 111,
"id": "761821cb-9a0c-4efb-806b-75513302d34a",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
""
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"from matplotlib import pyplot as plt\n",
"\n",
"plt.figure(figsize=(12, 6))\n",
"plt.plot(\n",
" [result_dict[i][\"cvar_fval\"] for i in range(1, iter_counts + 1)],\n",
" label=\"CVaR\",\n",
")\n",
"plt.plot(\n",
" [result_dict[i][\"fval\"] for i in range(1, iter_counts + 1)],\n",
" label=\"Standard\",\n",
")\n",
"plt.legend()\n",
"plt.xlabel(\"Iteration\")\n",
"plt.ylabel(\"Cost\")\n",
"plt.show()"
]
},
{
"cell_type": "markdown",
"id": "38aadfcb-aec9-4dbb-a9d3-319239eae196",
"metadata": {},
"source": [
"Der folgende Code ermittelt die beste Lösung aus den Stichproben-Bitfolgen:\n",
"\n"
]
},
{
"cell_type": "code",
"execution_count": null,
"id": "7e8af29e-c99b-41f2-b6dd-2be471e1af21",
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"bitstring (int): 283561207335785714592526814041, probability: 0.00025693730729701953, objective value: -43.0\n"
]
}
],
"source": [
"# Sort the result_dict[iter_counts]['evaluated'] by the CVaR value\n",
"sorted_result_dict = [\n",
" (k, v)\n",
" for k, v in sorted(\n",
" result_dict[iter_counts][\"evaluated\"].items(),\n",
" key=lambda item: item[1][1],\n",
" )\n",
"]\n",
"print(\n",
" f\"bitstring (int): {sorted_result_dict[0][0]}, \"\n",
" f\"probability: {sorted_result_dict[0][1][0]}, \"\n",
" f\"objective value: {sorted_result_dict[0][1][1]}\"\n",
")"
]
},
{
"cell_type": "markdown",
"id": "9cbeacc1-ff99-4b3d-b38d-b293a19642e2",
"metadata": {},
"source": [
"Betrachten wir den Hamilton- $H_C$ en für das **Max-Cut** -Problem. Jeder Knoten des Graphen sei einem Qubit im Zustand $|0\\rangle$ oder $|1\\rangle$ zugeordnet, wobei der Wert die Menge bezeichnet, zu der der Knoten gehört. Das Ziel der Aufgabe besteht darin, die Anzahl der Kanten $(v_1, v_2)$ zu maximieren, für die $v_1 = |0\\rangle$ und $v_2 = |1\\rangle$ gilt, oder umgekehrt. Wenn wir jedem Qubit den Operator „ $Z$ “ zuordnen, wobei\n",
"\n",
"$$\n",
" Z|0\\rangle = |0\\rangle \\qquad Z|1\\rangle = -|1\\rangle,\n",
"$$\n",
"\n",
"Dann gehört eine Kante $(v_1, v_2)$ zum Schnitt, wenn der Eigenwert von $(Z_1|v_1\\rangle) \\cdot (Z_2|v_2\\rangle) = -1$ gilt; mit anderen Worten: Die mit $v_1$ und $v_2$ verbundenen Qubits sind unterschiedlich. Ebenso gehört $(v_1, v_2)$ nicht zur Schnittmenge, wenn der Eigenwert von $(Z_1|v_1\\rangle) \\cdot (Z_2|v_2\\rangle) = 1$ ist.\n",
"\n"
]
},
{
"cell_type": "code",
"execution_count": 113,
"id": "5ea9e6aa-4297-4687-b484-1695d415bad5",
"metadata": {},
"outputs": [
{
"name": "stdout",
"output_type": "stream",
"text": [
"Result bitstring (binary) : [1, 0, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 1, 1, 1, 0, 0]\n",
"The value of the cut is: 77\n"
]
}
],
"source": [
"from typing import Sequence\n",
"\n",
"\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",
"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])\n",
" + x[v]\n",
" * (\n",
" 1 - x[u]\n",
" ) # x[u] = x[v] if same cut, x[u] \\neq x[v] if different cuts\n",
" for u, v in list(graph.edge_list())\n",
" )\n",
"\n",
"\n",
"bitstring = to_bitstring(\n",
" sorted_result_dict[0][0], len(list(remapped_graph.nodes()))\n",
")\n",
"bitstring = bitstring[::-1]\n",
"print(f\"Result bitstring (binary) : {bitstring}\")\n",
"\n",
"cut_value = evaluate_sample(bitstring, remapped_graph)\n",
"print(f\"The value of the cut is: {cut_value}\")"
]
},
{
"cell_type": "markdown",
"id": "c5879546-35ab-4876-bed9-262b85f130cc",
"metadata": {},
"source": [
"Zeichnen wir nun ein Diagramm auf der Grundlage des Ergebnisses von CVaR.\n",
"Wir teilen die Knoten des Graphen auf der Grundlage des Ergebnisses von CVaR in zwei Gruppen auf.\n",
"Die Knoten der ersten Gruppe sind grau gefärbt, die Knoten der zweiten Gruppe lila.\n",
"Die Kanten zwischen den beiden Mengen sind die Kanten, die durch die Partitionierung geschnitten werden.\n",
"\n"
]
},
{
"cell_type": "code",
"execution_count": 124,
"id": "852dfeed-2871-4ca1-9754-15c95293198e",
"metadata": {},
"outputs": [
{
"data": {
"text/plain": [
""
]
},
"metadata": {},
"output_type": "display_data"
}
],
"source": [
"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,\n",
" node_color=colors,\n",
" node_size=150,\n",
" alpha=0.8,\n",
" pos=pos,\n",
" with_labels=True,\n",
" width=1,\n",
" )\n",
"\n",
"\n",
"plot_result(graph_100, to_bitstring(sorted_result_dict[0][0], 100)[::-1])"
]
},
{
"cell_type": "markdown",
"id": "82f5c13b-a141-4657-adfd-bb18e88ad9f2",
"metadata": {},
"source": [
"\n",
"\n",
"## Referenzen\n",
"\n",
"\\[1] Weidenfeller, J., Valor, L.C., Gacon, J., Tornow, C., Bello, L., Woerner, S., & Egger, D. J. (2022). Skalierung des Algorithmus zur approximativen Quantenoptimierung auf supraleitender Qubit-basierter Hardware. Quantum, 6, 870.\n",
"\n",
"\\[2] Matsuo, A., Yamashita, S., & Egger, D. J. (2023). Ein SAT-Ansatz für das anfängliche Zuordnungsproblem bei der SWAP-Gate-Insertion für kommutierende Gates. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, 106(11), 1424-1431.\n",
"\n",
"\\[3] Barkoutsos, P. K., Nannicini, G., Robert, A., Tavernelli, I., & Woerner, S. (2020). Verbesserung der variablen Quantenoptimierung mit CVaR. Quantum, 4, 256.\n",
"\n",
"\\[4] Barron, S. V., Egger, D. J., Pelofske, E., Bärtschi, A., Eidenbenz, S., Lehmkühler, M., & Woerner, S. (2023). Nachweisbare Schranken für rauschfreie Erwartungswerte, die aus verrauschten Stichproben berechnet werden. arXiv vorabdruck arXiv:2312.00733.\n",
"\n"
]
},
{
"cell_type": "markdown",
"id": "a6a5bbfe-a159-4dc1-9333-488737aff503",
"metadata": {},
"source": [
"\n",
"\n",
"## Nächste Schritte\n",
"\n",
"\n",
" Wenn Sie diese Arbeit interessant fanden, könnten Sie auch an folgenden Materialien interessiert sein:\n",
"\n",
" * [Der „unlösbare Zehnkampf](https://arxiv.org/pdf/2504.03832) “: eine Auflistung von 10 Optimierungsproblemen, die für klassische Optimierungsalgorithmen schwierig sind und sich gut als Anwendungsfälle eignen, um die in diesem Tutorial vorgestellten Techniken zu testen.\n",
" * [Ein Repository mit Best Practices für die Quantenoptimierung,](https://github.com/qiskit-community/qopt-best-practices) um die Ergebnisse Ihres QAOA-basierten Workflows weiter zu verbessern.\n",
"\n",
"\n"
]
},
{
"cell_type": "markdown",
"metadata": {},
"id": "a1b8767d",
"source": "© IBM Corp., 2017-2026"
}
],
"metadata": {
"hours": 1.5,
"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"
},
"qpuSeconds": 180
},
"nbformat": 4,
"nbformat_minor": 4
}