{ "cells": [ { "cell_type": "markdown", "id": "2114652b-8f1f-4ba1-817b-48e98e3c6053", "metadata": {}, "source": [ "---\n", "title: \"Pauli-Korrelationskodierung zur Reduzierung der Anforderungen an den Max-Cut\"\n", "description: \"Verwende die Pauli-Korrelationskodierung, um Optimierungsprobleme effizienter in Qubits zu kodieren und so die Quantencomputering zu verbessern.\"\n", "---\n", "\n", "{/* cspell:ignore lbrack setminus coloneqq rbrack binom rhobeg nfev PCEFQ */}\n", "\n", "\n", "\n", "# Pauli-Korrelationskodierung zur Reduzierung der Anforderungen an den Max-Cut\n", "\n", "*Geschätzte Laufzeit: 35 Minuten auf einem Eagle- r3 -Prozessor (HINWEIS: Dies ist nur eine Schätzung. (Die Laufzeit kann variieren.)*\n", "\n" ] }, { "cell_type": "markdown", "id": "7239458e-d833-490e-8462-eaf2b5a115d4", "metadata": {}, "source": [ "\n", "\n", "## Lernziele\n", "\n", "* Verstehen Sie die theoretischen Grundlagen der Pauli-Korrelationskodierung (PCE), einschließlich der Frage, wie Mehrkörper-Pauli-Strings eine polynomiale Komprimierung klassischer Optimierungsprobleme ermöglichen.\n", "* PCE in der Praxis einsetzen, um groß angelegte Optimierungsaufgaben auf der in Kürze verfügbaren Quantenhardware zu formulieren und zu lösen.\n", "\n", "\n", "\n", "## Voraussetzungen\n", "\n", "* [Variationale Quantenalgorithmen](/learning/courses/variational-algorithm-design)\n", "* [QAOA und Max-Cut](/docs/tutorials/quantum-approximate-optimization-algorithm)\n", "\n" ] }, { "cell_type": "markdown", "id": "8a343d18-ab46-431f-899d-0664c2f99cc0", "metadata": {}, "source": [ "\n", "\n", "## Hintergrund\n", "\n", "In diesem Tutorium wird die *Pauli-Korrelationskodierung* (PCE) [\\[1\\]](#references) vorgestellt, ein Ansatz, der darauf abzielt, Optimierungsprobleme in Qubits zu kodieren, um die Effizienz von Quantenberechnungen zu erhöhen. PCE bildet klassische Variablen in Optimierungsproblemen auf Mehrkörper-Pauli-Matrix-Korrelationen ab, was zu einer polynomialen Kompression des Platzbedarfs des Problems führt. Durch den Einsatz von PCE wird die Anzahl der für die Kodierung benötigten Qubits reduziert, was besonders vorteilhaft für Quantengeräte mit begrenzten Qubit-Ressourcen ist. Darüber hinaus wird analytisch nachgewiesen, dass PCE inhärent unfruchtbare Plateaus abschwächt und eine super-polynomiale Widerstandsfähigkeit gegen dieses Phänomen bietet. Diese eingebaute Funktion ermöglicht eine noch nie dagewesene Leistung von Quantenoptimierungslösern.\n", "\n" ] }, { "cell_type": "markdown", "id": "c133831c-1eff-4913-aff6-8c0d82df9d61", "metadata": {}, "source": [ "\n", "\n", "### Übersicht\n", "\n", "Der PCE-Ansatz umfasst drei Hauptschritte, wie in Abbildung 1 aus [\\[1\\]](#references) unten dargestellt:\n", "\n", "1. Kodierung des Optimierungsproblems in einem Pauli-Korrelationsraum.\n", "2. Lösung des Problems mit einem quantenklassischen Optimierungslöser.\n", "3. Dekodierung der Lösung zurück in den ursprünglichen Optimierungsraum.\n", " Der PCE-Ansatz ist an jeden Quantenoptimierungslöser anpassbar, der Pauli-Korrelationsmatrizen verarbeiten kann.\n", "\n" ] }, { "attachments": {}, "cell_type": "markdown", "id": "40a636a3-c0c0-42ba-a68a-2abcb8a7187b", "metadata": {}, "source": [ "![Überblick über PCE.](https://quantum.cloud.ibm.com/docs/images/tutorials/solving-maxcut-with-reduced-qubit-requirements-using-pauli-correlation-encoding/af2cb835-88db-4a3d-9c86-51424b1a4bd3.avif)\n", "\n" ] }, { "cell_type": "markdown", "id": "1f28c0b3-b6dd-4627-90e6-db70b9114cd0", "metadata": {}, "source": [ "In Abbildung 1 aus [\\[1\\]](#references) wird das [Max-Cut-](/docs/tutorials/quantum-approximate-optimization-algorithm) Problem als Beispiel herangezogen, um den PCE-Ansatz zu veranschaulichen. Das Max-Cut-Problem mit $m=9$ Knoten wird in einen Pauli-Korrelationsraum kodiert, wobei das Optimierungsproblem als Korrelationsmatrix dargestellt wird – genauer gesagt als Zwei-Körper-Pauli-Matrix-Korrelationen zwischen $n=3$ Qubits $(Q_1, Q_2, Q_3)$. Die Farben der Knoten geben die Pauli-Zeichenfolge an, die für den jeweiligen kodierten Knoten verwendet wird.\n", "Beispielsweise wird Knoten 1, der der binären Variablen $x_1$ entspricht, durch den Erwartungswert von $Z_1 \\otimes Z_2 \\otimes I_3$ kodiert, während $x_8$ durch $I_1 \\otimes Y_2 \\otimes Y_3$ kodiert wird.\n", "Dies entspricht einer Komprimierung der $m$ Variablen des Problems in $ n = O(m^{1/2})$ Qubits. Allgemeiner gesagt ermöglichen Korrelationen vom Typ „ $k $ “ eine polynomiale Kompression der Ordnung „ $k$ “, wobei „ $k>1$ “ gilt. Die gewählte Pauli-Menge umfasst drei Teilmengen von Pauli-Strings, die untereinander kommutieren, wodurch alle „ $m$ “-Korrelationen mit nur drei Messkonfigurationen experimentell bestimmt werden können.\n", "\n", "Es wird eine Verlustfunktion $\\mathcal{L}$ aus Pauli-Erwartungswerten konstruiert, die die ursprüngliche Max-Cut-Zielfunktion nachbildet. Die Verlustfunktion wird anschließend mithilfe eines quantenklassischen Optimierungslösers, wie beispielsweise dem [Variational Quantum Eigensolver (VQE)](/learning/courses/quantum-diagonalization-algorithms/vqe), optimiert.\n", "\n", "Sobald die Optimierung abgeschlossen ist, wird die Lösung zurück in den ursprünglichen Optimierungsraum dekodiert, wodurch die optimale Max-Cut-Lösung ermittelt wird.\n", "\n", "\n", "\n", "## Anforderungen\n", "\n", "Bevor Sie mit diesem Tutorial beginnen, sollten Sie sicherstellen, dass Sie Folgendes installiert haben:\n", "\n", "* Qiskit SDK v1.0 oder später, mit [Visual](/docs/api/qiskit/visualization) isierungsunterstützung\n", "* Qiskit Runtime v0.22 oder später (`pip install qiskit-ibm-runtime`)\n", "\n" ] }, { "cell_type": "markdown", "id": "adfa1c9b-0dd3-42d0-afd9-bce648cf668e", "metadata": {}, "source": [ "\n", "\n", "## Einrichtung\n", "\n" ] }, { "cell_type": "code", "execution_count": null, "id": "5abb33b8-080d-4375-ac16-7788f2f1516a", "metadata": {}, "outputs": [], "source": [ "from itertools import combinations\n", "\n", "import numpy as np\n", "import rustworkx as rx\n", "import networkx as nx\n", "\n", "from scipy.optimize import minimize, OptimizeResult\n", "\n", "from qiskit.circuit.library import efficient_su2\n", "from qiskit.transpiler.preset_passmanagers import generate_preset_pass_manager\n", "from qiskit.quantum_info import SparsePauliOp\n", "from qiskit_ibm_runtime import EstimatorV2 as Estimator\n", "from qiskit_ibm_runtime import QiskitRuntimeService\n", "from qiskit_ibm_runtime import Session\n", "from rustworkx.visualization import mpl_draw\n", "from qiskit_aer import AerSimulator" ] }, { "cell_type": "code", "execution_count": 2, "id": "89c2999b-d309-4cf4-820e-9ef8a5cd5807", "metadata": {}, "outputs": [], "source": [ "def calc_cut_size(graph, partition0, partition1):\n", " \"\"\"Calculate the cut size of the given partitions of the graph.\"\"\"\n", "\n", " cut_size = 0\n", " for edge0, edge1 in graph.edge_list():\n", " if edge0 in partition0 and edge1 in partition1:\n", " cut_size += 1\n", " elif edge0 in partition1 and edge1 in partition0:\n", " cut_size += 1\n", " return cut_size" ] }, { "cell_type": "markdown", "id": "19cc2e86-204f-4ebf-b1a3-942025cc7015", "metadata": {}, "source": [ "\n", "\n", "## Beispiel für einen Simulator im kleinen Maßstab\n", "\n" ] }, { "cell_type": "code", "execution_count": 3, "id": "af0c1db0-3b69-459c-8013-5149ede620c2", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "We are using the aer_simulator_from(ibm_pittsburgh)\n" ] } ], "source": [ "service = QiskitRuntimeService()\n", "real_backend = service.least_busy(\n", " operational=True, simulator=False, min_num_qubits=156\n", ")\n", "backend = AerSimulator.from_backend(real_backend)\n", "print(f\"We are using the {backend.name}\")" ] }, { "cell_type": "markdown", "id": "c8084430-5386-4788-97c3-c6e4fb7cb191", "metadata": {}, "source": [ "\n", "\n", "### Schritt 1: Klassische Eingaben einem Quantenproblem zuordnen\n", "\n", "\n", "\n", "#### Das Max-Cut-Problem\n", "\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", "Eine ausführliche Beschreibung des Max-Cut-Problems finden Sie im Tutorial [zum algorithmischen Ansatz](/docs/tutorials/quantum-approximate-optimization-algorithm) der approximativen Quantenoptimierung.\n", "Das Max-Cut-Problem wird auch im Tutorial [„Fortgeschrittene Techniken für QAOA“](/docs/tutorials/advanced-techniques-for-qaoa) als Beispiel herangezogen.\n", "In diesen Tutorials wird der QAOA-Algorithmus zur Lösung des Max-Cut-Problems verwendet.\n", "\n", "-hamiltonian\" />\n", "\n", "#### Grafik -> Hamilton-Funktion\n", "\n", "Betrachten wir zunächst einen Zufallsgraphen mit 100 Knoten.\n", "\n" ] }, { "cell_type": "code", "execution_count": 4, "id": "37edb718-2bab-49d7-ad66-5f2f67d2aeff", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "\"Output" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "num_nodes = 100 # Number of nodes in graph\n", "seed = 42\n", "graph = rx.undirected_gnp_random_graph(num_nodes, 0.1, seed=seed)\n", "mpl_draw(graph)" ] }, { "cell_type": "code", "execution_count": null, "id": "eb7a80dc-74ea-472b-a13f-11cb8d4c0ca9", "metadata": {}, "outputs": [], "source": [ "nx_graph = nx.Graph()\n", "nx_graph.add_nodes_from(range(num_nodes))" ] }, { "cell_type": "code", "execution_count": 6, "id": "63451877-908a-4e80-9e11-23eb0d288bfc", "metadata": {}, "outputs": [], "source": [ "for edge in graph.edge_list():\n", " nx_graph.add_edge(edge[0], edge[1])" ] }, { "cell_type": "code", "execution_count": 7, "id": "515e7220-586f-4e2a-82b6-3885e3e38566", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Initial cut size: 345\n" ] } ], "source": [ "curr_cut_size, partition = nx.approximation.one_exchange(nx_graph, seed=1)\n", "print(f\"Initial cut size: {curr_cut_size}\")" ] }, { "cell_type": "markdown", "id": "57e3804e-61ae-45c5-9d94-3665cf01784b", "metadata": {}, "source": [ "Wir kodieren den Graphen mit 100 Knoten in Zwei-Körper-Pauli-Matrix-Korrelationen über neun Qubits (siehe die Erläuterung unten). Der Graph wird als Korrelationsmatrix dargestellt, wobei jeder Knoten durch eine Pauli-Zeichenkette kodiert ist. Das Vorzeichen des Erwartungswerts der Pauli-String-Funktion gibt die Partition des Knotens an. Beispielsweise wird Knoten 0 durch eine Pauli-Kette kodiert: „ $\\prod_0 = I_{8} \\otimes ... I_2 \\otimes X_1 \\otimes X_0$ “. Das Vorzeichen des Erwartungswerts dieser Pauli-Kette gibt die Partition von Knoten 0 an. Wir definieren eine *Pauli-Korrelationskodierung* (PCE) in Bezug auf „ $\\prod$ “ wie folgt:\n", "\n", "$x_i \\coloneqq \\textit{sgn}(\\langle\\prod_i \\rangle),$\n", "\n", "wobei $x_i$ die Partition des Knotens $i$ und $\\langle \\prod_i \\rangle \\coloneqq \\langle \\psi |\\prod_i| \\psi \\rangle $ der Erwartungswert des Pauli-Strings ist, der den Knoten $i$ über einen Quantenzustand $|\\psi \\rangle$ kodiert.\n", "\n" ] }, { "cell_type": "markdown", "id": "678e00fb-5bb9-450e-8229-0eab5676057a", "metadata": {}, "source": [ "Nun wollen wir den Graphen mit PCE in einen Hamiltonian kodieren.\n", "Wir teilen die Knotenpunkte in drei Gruppen ein: $S_1$, $S_2$, und $S_3$. Dann kodieren wir die Knoten in jeder Gruppe mit den Pauli-Strings $X$, $Y$ bzw. $Z$.\n", "\n" ] }, { "cell_type": "markdown", "id": "4d5d48e5-ebe8-4b36-9496-288f40174a7b", "metadata": {}, "source": [ "Wir müssen einen Zusammenhang zwischen der Anzahl der Knoten und der Anzahl der Qubits herleiten, die wir benötigen, um alle Knoten zu kodieren. Die Verwendung aller möglichen Permutationen für die Kodierung ergibt:\n", "\n", "$$\n", "m=3\\binom{n}{k}.\n", "$$\n", "\n", "In diesem Beispiel betrachten wir $k=2$, daher gilt:\n", "\n", "$$\n", "m = \\frac{3}{2} n(n-1).\n", "$$\n", "\n", "Daher lautet die Anzahl der Qubits $n$, die benötigt werden, um eine bestimmte Anzahl von Knoten $m$ darzustellen, wie folgt:\n", "\n", "$$\n", "n = \\left\\lceil \\frac{1 + \\sqrt{1 + \\tfrac{8}{3}m}}{2} \\right\\rceil.\n", "$$\n", "\n", "*Beachte, dass das Symbol „ $\\lceil \\cdot \\rceil$ “ die Ceiling-Funktion darstellt, die jede reelle Zahl auf die nächste ganze Zahl aufrundet. Dadurch wird sichergestellt, dass die Anzahl der Qubits eine ganze Zahl ist.*\n", "\n" ] }, { "cell_type": "code", "execution_count": 13, "id": "8ea1f545-3e9f-4620-bde8-755178ad3ec9", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Number of qubits: 9\n", "List 1: [0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30, 31, 32]\n", "List 2: [33, 34, 35, 36, 37, 38, 39, 40, 41, 42, 43, 44, 45, 46, 47, 48, 49, 50, 51, 52, 53, 54, 55, 56, 57, 58, 59, 60, 61, 62, 63, 64, 65]\n", "List 3: [66, 67, 68, 69, 70, 71, 72, 73, 74, 75, 76, 77, 78, 79, 80, 81, 82, 83, 84, 85, 86, 87, 88, 89, 90, 91, 92, 93, 94, 95, 96, 97, 98, 99]\n" ] } ], "source": [ "num_qubits = int(np.ceil((1 + np.sqrt(1 + (8 / 3) * num_nodes)) / 2))\n", "\n", "list_size = num_nodes // 3\n", "node_x = [i for i in range(list_size)]\n", "node_y = [i for i in range(list_size, 2 * list_size)]\n", "node_z = [i for i in range(2 * list_size, num_nodes)]\n", "\n", "print(f\"Number of qubits: {num_qubits}\")\n", "print(\"List 1:\", node_x)\n", "print(\"List 2:\", node_y)\n", "print(\"List 3:\", node_z)" ] }, { "cell_type": "code", "execution_count": 14, "id": "d2649acb-7857-4cf4-88dc-4ef381a8552f", "metadata": {}, "outputs": [], "source": [ "def build_pauli_correlation_encoding(pauli, node_list, n, k=2):\n", " pauli_correlation_encoding = []\n", " for idx, c in enumerate(combinations(range(n), k)):\n", " if idx >= len(node_list):\n", " break\n", " paulis = [\"I\"] * n\n", " paulis[c[0]], paulis[c[1]] = pauli, pauli\n", " pauli_correlation_encoding.append((\"\".join(paulis)[::-1], 1))\n", "\n", " hamiltonian = []\n", " for pauli, weight in pauli_correlation_encoding:\n", " hamiltonian.append(SparsePauliOp.from_list([(pauli, weight)]))\n", "\n", " return hamiltonian\n", "\n", "\n", "pauli_correlation_encoding_x = build_pauli_correlation_encoding(\n", " \"X\", node_x, num_qubits\n", ")\n", "pauli_correlation_encoding_y = build_pauli_correlation_encoding(\n", " \"Y\", node_y, num_qubits\n", ")\n", "pauli_correlation_encoding_z = build_pauli_correlation_encoding(\n", " \"Z\", node_z, num_qubits\n", ")" ] }, { "cell_type": "markdown", "id": "4ce84c90-8b64-4959-a315-2380482801ad", "metadata": {}, "source": [ "\n", "\n", "### Schritt 2: Optimierung des Problems für die Ausführung auf Quantenhardware\n", "\n", "\n", "\n", "#### Quantenschaltung\n", "\n", "Hier wird der Zustand $|\\psi \\rangle$ mit $\\mathbf{\\theta}$ parametrisiert, und wir optimieren diese Parameter $\\mathbf{\\theta}$ mit einem Variationsansatz.\n", "In diesem Tutorial wird der `efficient_su2` -Ansatz für unseren Variationsalgorithmus verwendet, da er sehr aussagekräftig und einfach zu implementieren ist.\n", "Wir verwenden auch die entspannte Verlustfunktion, die später in diesem Tutorium vorgestellt wird.\n", "Infolgedessen können wir große Probleme mit weniger Qubits und geringerer Schaltungstiefe lösen.\n", "\n" ] }, { "cell_type": "code", "execution_count": 15, "id": "035f6b4a-4de0-452a-b60f-7260f9e3103a", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "\"Output" ] }, "execution_count": 15, "metadata": {}, "output_type": "execute_result" } ], "source": [ "# Build the quantum circuit\n", "qc = efficient_su2(num_qubits, su2_gates=[\"ry\", \"rz\"], reps=2)\n", "qc.draw(\"mpl\")" ] }, { "cell_type": "code", "execution_count": 16, "id": "162f1384-98f5-406e-b5ae-0e12d0ad4b59", "metadata": {}, "outputs": [], "source": [ "# Optimize the circuit\n", "\n", "pm = generate_preset_pass_manager(optimization_level=3, backend=backend)\n", "qc = pm.run(qc)" ] }, { "cell_type": "markdown", "id": "644c9317-7988-427e-979a-975c0a616f52", "metadata": {}, "source": [ "\n", "\n", "#### Verlustfunktion\n", "\n", "Für die Verlustfunktion $\\mathcal{L}$ verwenden wir eine Relaxation der Max-Cut-Zielfunktion, wie in [\\[1\\]](#references) beschrieben, die wie folgt definiert ist: $\\mathcal{V}(\\mathbf{x}) \\coloneqq \\sum_{(i, j) \\in E} W_{i, j}(1-x_i x_j)$. Dabei bezeichnet $W_{i, j}$ das Gewicht der Kante $(i, j)$ und $x_i$ die Partition des Knotens $i$.\n", "Die Verlustfunktion $\\mathcal{L}$ ist wie folgt gegeben:\n", "\n", "$\\mathcal{L}\\coloneqq \\sum_{(i, j) \\in E} W_{i, j} \\text{tanh} (\\alpha \\langle\\prod_i \\rangle) \\text{tanh} (\\alpha \\langle\\prod_j \\rangle) + \\mathcal{L}^{(\\text{reg})}$,\n", "\n", "wobei die Max-Cut-Zielfunktion durch die glatten hyperbolischen Tangenten der Erwartungswerte der Pauli-Strings ersetzt wird, die die Knoten kodieren. Zur Verbesserung der Leistungsfähigkeit des Lösers werden der Regularisierungsterm $\\mathcal{L}^{(\\text{reg})}$ und der Skalierungsfaktor $\\alpha$ eingeführt, die proportional zur Anzahl der Qubits sind.\n", "\n", "Der Regularisierungsterm ist definiert als:\n", "\n", "$\\mathcal{L}^{(\\text{reg})}$ ist definiert als $\\mathcal{L}^{(\\text{reg})} \\coloneqq \\beta \\nu \\lbrack \\frac{1}{m} \\sum_{i \\in V} \\text{tanh} (\\alpha \\langle\\prod_i \\rangle)^2 \\rbrack ^2$\n", "\n", "wobei $\\beta=1/2$, $\\nu = |E|/2 + (m -1) /4$, $|E|$ die Anzahl der Kanten und $m$ die Anzahl der Knoten im Graphen ist.\n", "\n" ] }, { "cell_type": "code", "execution_count": null, "id": "fe608e6a-08ce-493d-9b0a-eb9d6e0028ff", "metadata": {}, "outputs": [], "source": [ "def loss_func_estimator(x, ansatz, hamiltonian, estimator, graph):\n", " \"\"\"\n", " Calculates the specified loss function for the given ansatz, Hamiltonian,\n", " and graph.\n", "\n", " The expectation values of each Pauli string in the Hamiltonian are first\n", " obtained by running the ansatz on the quantum backend. These\n", " expectation values are then passed through the nonlinear function\n", " tanh(alpha * prod_i). The loss function is\n", " subsequently computed from these transformed values.\n", " \"\"\"\n", " job = estimator.run(\n", " [\n", " (ansatz, hamiltonian[0], x),\n", " (ansatz, hamiltonian[1], x),\n", " (ansatz, hamiltonian[2], x),\n", " ]\n", " )\n", " result = job.result()\n", "\n", " # calculate the loss function\n", " node_exp_map = {}\n", " idx = 0\n", " for r in result:\n", " for ev in r.data.evs:\n", " node_exp_map[idx] = ev\n", " idx += 1\n", "\n", " loss = 0\n", " alpha = num_qubits\n", " for edge0, edge1 in graph.edge_list():\n", " loss += np.tanh(alpha * node_exp_map[edge0]) * np.tanh(\n", " alpha * node_exp_map[edge1]\n", " )\n", "\n", " regulation_term = 0\n", " for i in range(len(graph.nodes())):\n", " regulation_term += np.tanh(alpha * node_exp_map[i]) ** 2\n", " regulation_term = regulation_term / len(graph.nodes())\n", " regulation_term = regulation_term**2\n", " beta = 1 / 2\n", " v = len(graph.edges()) / 2 + (len(graph.nodes()) - 1) / 4\n", " regulation_term = beta * v * regulation_term\n", "\n", " loss = loss + regulation_term\n", "\n", " global experiment_result\n", " print(f\"Iter {len(experiment_result)}: {loss}\")\n", " experiment_result.append({\"loss\": loss, \"exp_map\": node_exp_map})\n", " return loss" ] }, { "cell_type": "markdown", "id": "49943596-7f90-4226-a900-d5890deefbd9", "metadata": {}, "source": [ "\n", "\n", "### Schritt 3: Mit „ Qiskit primitives “ ausführen\n", "\n" ] }, { "cell_type": "markdown", "id": "583ba786-e2e9-4593-bf75-00723b589d78", "metadata": {}, "source": [ "In diesem Tutorial setzen `max_iter=50` wir zu Demonstrationszwecken in der Optimierungsschleife. Wenn wir die Anzahl der Iterationen erhöhen, können wir bessere Ergebnisse erwarten.\n", "\n" ] }, { "cell_type": "code", "execution_count": 18, "id": "8d203dd5-8b72-4b78-a36e-c10fdef3ebc3", "metadata": {}, "outputs": [], "source": [ "pce = []\n", "pce.append(\n", " [op.apply_layout(qc.layout) for op in pauli_correlation_encoding_x]\n", ")\n", "pce.append(\n", " [op.apply_layout(qc.layout) for op in pauli_correlation_encoding_y]\n", ")\n", "pce.append(\n", " [op.apply_layout(qc.layout) for op in pauli_correlation_encoding_z]\n", ")" ] }, { "cell_type": "code", "execution_count": null, "id": "8d9d6313-9bcd-4ffb-b40c-361d18c68afe", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Iter 0: 159.88755362682548\n", "Iter 1: 113.46202580636677\n", "Iter 2: 56.76494226400048\n", "Iter 3: 32.63357946896002\n", "Iter 4: 21.517837239610117\n", "Iter 5: 30.96034960483569\n", "Iter 6: 20.780475923938027\n", "Iter 7: 24.54251816279811\n", "Iter 8: 27.834486461763042\n", "Iter 9: 16.705460776812693\n", "Iter 10: 18.020587887236864\n", "Iter 11: 12.252379762741352\n", "Iter 12: 5.253885750886939\n", "Iter 13: 6.985984759592262\n", "Iter 14: 6.908717244584757\n", "Iter 15: 12.915466016863858\n", "Iter 16: 4.105776920457279\n", "Iter 17: 11.707504530740305\n", "Iter 18: 7.154360511076546\n", "Iter 19: 10.3890865704735\n", "Iter 20: 10.376147647857252\n", "Iter 21: 2.533430195296697\n", "Iter 22: 3.8612421907795462\n", "Iter 23: 6.103735057461906\n", "Iter 24: -1.1190368234312347\n", "Iter 25: 6.125915279494738\n", "Iter 26: 11.086280445482455\n", "Iter 27: 10.102569882302827\n", "Iter 28: -0.02664415648133822\n", "Iter 29: 7.621887727398785\n", "Iter 30: 5.967346615554497\n", "Iter 31: 3.85345716014828\n", "Iter 32: 4.5494846149011\n", "Iter 33: 10.006668112637232\n", "Iter 34: -3.1927138938527877\n", "Iter 35: 2.8829882366285116\n", "Iter 36: 3.3130087521654144\n", "Iter 37: -4.907566569808272\n", "Iter 38: -4.980134722109894\n", "Iter 39: -2.990457463896541\n", "Iter 40: -5.938401817344579\n", "Iter 41: -2.1807712386469724\n", "Iter 42: -1.0945774380342126\n", "Iter 43: -4.7548102593556685\n", "Iter 44: -3.8762362299208144\n", "Iter 45: -4.9348321021624\n", "Iter 46: -6.487722842864011\n", "Iter 47: 0.7064210113389331\n", "Iter 48: -2.3428323031772216\n", "Iter 49: -2.626032270380895\n", " message: Return from COBYLA because the objective function has been evaluated 50 times.\n", " success: False\n", " status: 3\n", " fun: -2.626032270380895\n", " x: [ 1.375e+00 1.951e+00 ... 9.395e-01 8.948e-01]\n", " nfev: 50\n" ] } ], "source": [ "max_iter = 50\n", "counter = {\"i\": 0}\n", "last_x = {\"value\": None}\n", "last_fun = {\"value\": None}\n", "\n", "with Session(backend=backend) as session:\n", " estimator = Estimator(mode=session)\n", "\n", " experiment_result = []\n", "\n", " def loss_func(x):\n", " last_x[\"value\"] = x.copy()\n", " if counter[\"i\"] + 1 > max_iter:\n", " return last_fun[\"value\"]\n", " counter[\"i\"] += 1\n", " val = loss_func_estimator(\n", " x, qc, [pce[0], pce[1], pce[2]], estimator, graph\n", " )\n", " last_fun[\"value\"] = val\n", " return val\n", "\n", " np.random.seed(seed)\n", " initial_params = np.random.rand(qc.num_parameters)\n", "\n", " result = minimize(\n", " loss_func, initial_params, method=\"COBYLA\", options={\"rhobeg\": 1.0}\n", " )\n", "\n", " if counter[\"i\"] >= max_iter:\n", " result = OptimizeResult(\n", " message=f\"Return from COBYLA because the objective function \"\n", " f\"has been evaluated {max_iter} times.\",\n", " success=False,\n", " status=3,\n", " fun=last_fun[\"value\"],\n", " x=last_x[\"value\"],\n", " nfev=counter[\"i\"],\n", " )\n", "\n", "print(result)" ] }, { "cell_type": "markdown", "id": "5c9dd9f8-ed15-4008-8841-e44caf11cf99", "metadata": {}, "source": [ "\n", "\n", "### Schritt 4: Nachbearbeitung und Rückgabe des Ergebnisses im gewünschten klassischen Format\n", "\n", "Die Partitionen der Knoten werden durch Auswertung der Vorzeichen der Erwartungswerte der Pauli-Strings, die die Knoten kodieren, bestimmt.\n", "\n" ] }, { "cell_type": "code", "execution_count": 20, "id": "fa2db108-754b-4036-af98-87f5390a9c11", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "{0, 2, 3, 8, 9, 11, 12, 13, 17, 18, 20, 22, 23, 24, 25, 26, 27, 30, 35, 37, 38, 40, 43, 46, 48, 49, 50, 51, 53, 57, 61, 62, 63, 66, 67, 68, 70, 71, 74, 77, 81, 82, 83, 84, 87, 88, 94, 96, 99} {1, 4, 5, 6, 7, 10, 14, 15, 16, 19, 21, 28, 29, 31, 32, 33, 34, 36, 39, 41, 42, 44, 45, 47, 52, 54, 55, 56, 58, 59, 60, 64, 65, 69, 72, 73, 75, 76, 78, 79, 80, 85, 86, 89, 90, 91, 92, 93, 95, 97, 98}\n" ] } ], "source": [ "# Calculate the partitions based on the final expectation values\n", "# If the expectation value is positive, the node belongs to partition 0 (par0)\n", "# Otherwise, the node belongs to partition 1 (par1)\n", "def get_partitions(experiment_result):\n", " par0, par1 = set(), set()\n", " best_index = min(\n", " range(len(experiment_result)),\n", " key=lambda i: experiment_result[i][\"loss\"],\n", " )\n", " for i in experiment_result[best_index][\"exp_map\"]:\n", " if experiment_result[best_index][\"exp_map\"][i] >= 0:\n", " par0.add(i)\n", " else:\n", " par1.add(i)\n", " return par0, par1, best_index\n", "\n", "\n", "par0, par1, best_index = get_partitions(experiment_result)\n", "print(par0, par1)" ] }, { "cell_type": "markdown", "id": "6f82e256-36f1-4ac1-badb-abdc98a26b23", "metadata": {}, "source": [ "Wir können die Schnittgröße des Max-Cut-Problems anhand der Partitionen des Knotens berechnen.\n", "\n" ] }, { "cell_type": "code", "execution_count": 21, "id": "bd85ceae-ef8b-4e21-b447-e92ca92e06eb", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Cut size: 268\n" ] } ], "source": [ "cut_size = calc_cut_size(graph, par0, par1)\n", "print(f\"Cut size: {cut_size}\")" ] }, { "cell_type": "markdown", "id": "ef94b209-ea19-4292-aedc-f77edf77a2eb", "metadata": {}, "source": [ "Sobald das Training abgeschlossen ist, führen wir eine Runde Single-Bit-Swap-Suche durch, um die Lösung in einem klassischen Nachbearbeitungsschritt zu verbessern.\n", "Dabei tauschen wir die Partitionen von zwei Knoten aus und bewerten die Schnittgröße. Wenn die Schnittgröße verbessert wird, behalten wir den Tausch bei. Wir wiederholen diesen Vorgang für alle möglichen Knotenpaare, die durch eine Kante verbunden sind.\n", "\n" ] }, { "cell_type": "code", "execution_count": 22, "id": "b0df38ef-98d0-4d8c-bbdf-75d14e4680f7", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "[1, 0, 1, 1, 0, 0, 0, 0, 1, 1, 0, 1, 1, 1, 0, 0, 0, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 1, 1, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 1]\n" ] } ], "source": [ "cur_bits = []\n", "\n", "for i in experiment_result[best_index][\"exp_map\"]:\n", " if experiment_result[best_index][\"exp_map\"][i] >= 0:\n", " cur_bits.append(1)\n", " else:\n", " cur_bits.append(0)\n", "print(cur_bits)" ] }, { "cell_type": "code", "execution_count": 23, "id": "232658b0-a86b-4cb5-aff8-c8f2423491b6", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "279 [1, 0, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 1, 0, 0, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 1]\n" ] } ], "source": [ "# Swap the partitions and calculate the cut size\n", "\n", "\n", "def swap_partitions(graph, cur_bits):\n", " best_cut = 0\n", " best_bits = []\n", " for edge0, edge1 in graph.edge_list():\n", " swapped_bits = cur_bits.copy()\n", " swapped_bits[edge0], swapped_bits[edge1] = (\n", " swapped_bits[edge1],\n", " swapped_bits[edge0],\n", " )\n", "\n", " cur_partition = [set(), set()]\n", " for i, bit in enumerate(swapped_bits):\n", " if bit > 0:\n", " cur_partition[0].add(i)\n", " else:\n", " cur_partition[1].add(i)\n", " cut_size = calc_cut_size(graph, cur_partition[0], cur_partition[1])\n", " if best_cut < cut_size:\n", " best_cut = cut_size\n", " best_bits = swapped_bits\n", " return best_cut, best_bits\n", "\n", "\n", "best_cut, best_bits = swap_partitions(graph, cur_bits)\n", "print(best_cut, best_bits)" ] }, { "cell_type": "markdown", "id": "5142e8d0-ef6f-4abb-974e-ed25e5bfe692", "metadata": {}, "source": [ "\n", "\n", "# Beispiel für groß angelegte Hardware\n", "\n" ] }, { "cell_type": "code", "execution_count": null, "id": "d91c4ac2-3c5b-4afb-aa2c-42d1b50fa674", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "We are using 33 qubits\n", "We are using the ibm_pittsburgh\n", "Iter 0: 57399.57543902076\n", "Iter 1: 56458.787143794\n", "Iter 2: 40778.45608998947\n", "Iter 3: 35571.58511146131\n", "Iter 4: 33861.6835761173\n", "Iter 5: 39697.22637736274\n", "Iter 6: 34984.77893767163\n", "Iter 7: 32051.882157096858\n", "Iter 8: 26134.153216063707\n", "Iter 9: 24914.322627065787\n", "Iter 10: 24030.21227315425\n", "Iter 11: 23047.463945514\n", "Iter 12: 22629.42866110748\n", "Iter 13: 17374.859132614685\n", "Iter 14: 18020.11637762458\n", "Iter 15: 17924.7066364044\n", "Iter 16: 15825.1992250984\n", "Iter 17: 16553.346711978447\n", "Iter 18: 12393.565736512377\n", "Iter 19: 11994.021456089155\n", "Iter 20: 11199.994322735669\n", "Iter 21: 9624.895532927634\n", "Iter 22: 9073.811130188606\n", "Iter 23: 9836.721241931278\n", "Iter 24: 10555.925186133794\n", "Iter 25: 9179.1179493286\n", "Iter 26: 8495.394826965305\n", "Iter 27: 8913.688189840399\n", "Iter 28: 7830.448471810181\n", "Iter 29: 7757.430542422075\n", "Iter 30: 6796.187594518731\n", "Iter 31: 7307.985913766867\n", "Iter 32: 7340.225833330675\n", "Iter 33: 7064.731899380469\n", "Iter 34: 7632.270657372515\n", "Iter 35: 7049.154710767935\n", "Iter 36: 7486.118442084411\n", "Iter 37: 6302.12602219333\n", "Iter 38: 6244.934230209166\n", "Iter 39: 7154.9748739261395\n", "Iter 40: 6482.109600054041\n", "Iter 41: 5718.475169152395\n", "Iter 42: 5693.008457857462\n", "Iter 43: 4869.782667921923\n", "Iter 44: 4957.625304450959\n", "Iter 45: 5582.240637063214\n", "Iter 46: 4983.90082772116\n", "Iter 47: 5416.268575648202\n", "Iter 48: 4809.98398457807\n", "Iter 49: 5092.527306646118\n", " message: Return from COBYLA because the objective function has been evaluated 50 times.\n", " success: False\n", " status: 3\n", " fun: 5092.527306646118\n", " x: [ 1.375e+00 1.951e+00 ... 7.259e-01 8.971e-01]\n", " nfev: 50\n", "Cut size: 56152\n", "The best max-cut value achieved for a graph with 1500 nodes on 33 qubits is 56219\n", "and the specific partition we obtained is [1, 0, 0, 0, 1, 1, 0, 1, 1, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 0, 1, 0, 0, 1, 1, 1, 0, 1, 1, 0, 1, 0, 1, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 1, 0, 1, 1, 1, 1, 0, 1, 0, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 1, 1, 1, 1, 1, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 1, 1, 1, 0, 1, 0, 1, 0, 0, 1, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 1, 0, 1, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 0, 1, 0, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 1, 1, 0, 0, 1, 1, 1, 1, 0, 1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 0, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 1, 0, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 1, 0, 1, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 1, 0, 0, 1, 0, 1, 1, 1, 1, 0, 1, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 1, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 0, 0, 1, 1, 1, 0, 0, 1, 0, 0, 1, 0, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 1, 1, 0, 1, 1, 1, 1, 0, 0, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 1, 1, 0, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 1, 1, 1, 0, 0, 1, 0, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 0, 1, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 1, 1, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 1, 0, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 0, 1, 0, 1, 1, 0, 0, 1, 0, 0, 1, 1, 0, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 0, 0, 0, 1, 0, 0, 1, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 1, 0, 0, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 1, 1, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 1, 1, 0, 1, 0, 1, 0, 1, 0, 0, 1, 1, 0, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 0, 1, 0, 1, 1, 1, 1, 0, 1, 0, 1, 1, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 0, 0, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 0, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 1, 0, 1, 1, 0, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 1, 1, 0, 0, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 0, 1, 1, 1, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1]\n" ] } ], "source": [ "# -------------------------Step 1-------------------------\n", "\n", "num_nodes = 1500 # Number of nodes in graph\n", "graph = rx.undirected_gnp_random_graph(num_nodes, 0.1, seed=seed)\n", "nx_graph = nx.Graph()\n", "nx_graph.add_nodes_from(range(num_nodes))\n", "for edge in graph.edge_list():\n", " nx_graph.add_edge(edge[0], edge[1])\n", "\n", "num_qubits = int(np.ceil((1 + np.sqrt(1 + (8 / 3) * num_nodes)) / 2))\n", "\n", "list_size = num_nodes // 3\n", "node_x = [i for i in range(list_size)]\n", "node_y = [i for i in range(list_size, 2 * list_size)]\n", "node_z = [i for i in range(2 * list_size, num_nodes)]\n", "\n", "pauli_correlation_encoding_x = build_pauli_correlation_encoding(\n", " \"X\", node_x, num_qubits\n", ")\n", "pauli_correlation_encoding_y = build_pauli_correlation_encoding(\n", " \"Y\", node_y, num_qubits\n", ")\n", "pauli_correlation_encoding_z = build_pauli_correlation_encoding(\n", " \"Z\", node_z, num_qubits\n", ")\n", "print(f\"We are using {num_qubits} qubits\")\n", "\n", "# -------------------------Step 2-------------------------\n", "backend = real_backend\n", "print(f\"We are using the {backend.name}\")\n", "qc = efficient_su2(num_qubits, [\"ry\", \"rz\"], reps=2)\n", "pm = generate_preset_pass_manager(optimization_level=3, backend=backend)\n", "qc = pm.run(qc)\n", "# -------------------------Step 3-------------------------\n", "pce = []\n", "pce.append(\n", " [op.apply_layout(qc.layout) for op in pauli_correlation_encoding_x]\n", ")\n", "pce.append(\n", " [op.apply_layout(qc.layout) for op in pauli_correlation_encoding_y]\n", ")\n", "pce.append(\n", " [op.apply_layout(qc.layout) for op in pauli_correlation_encoding_z]\n", ")\n", "\n", "# Run the optimization using a session.\n", "max_iter = 50\n", "counter = {\"i\": 0}\n", "with Session(backend=backend) as session:\n", " estimator = Estimator(mode=session)\n", " estimator.options.environment.job_tags = [\"TUT_PCEFQ\"]\n", " experiment_result = []\n", "\n", " def loss_func(x):\n", " last_x[\"value\"] = x.copy()\n", " if counter[\"i\"] + 1 > max_iter:\n", " return last_fun[\"value\"]\n", " counter[\"i\"] += 1\n", " val = loss_func_estimator(\n", " x, qc, [pce[0], pce[1], pce[2]], estimator, graph\n", " )\n", " last_fun[\"value\"] = val\n", " return val\n", "\n", " np.random.seed(seed)\n", " initial_params = np.random.rand(qc.num_parameters)\n", " result = minimize(\n", " loss_func, initial_params, method=\"COBYLA\", options={\"rhobeg\": 1.0}\n", " )\n", " if counter[\"i\"] >= max_iter:\n", " result = OptimizeResult(\n", " message=\"Return from COBYLA because the objective function \"\n", " \"has been evaluated {max_iter} times.\",\n", " success=False,\n", " status=3,\n", " fun=last_fun[\"value\"],\n", " x=last_x[\"value\"],\n", " nfev=counter[\"i\"],\n", " )\n", "print(result)\n", "\n", "# -------------------------Step 4-------------------------\n", "\n", "par0, par1, best_index = get_partitions(experiment_result)\n", "cut_size = calc_cut_size(graph, par0, par1)\n", "print(f\"Cut size: {cut_size}\")\n", "\n", "best_bits = []\n", "cur_bits = []\n", "for i in experiment_result[best_index][\"exp_map\"]:\n", " if experiment_result[best_index][\"exp_map\"][i] >= 0:\n", " cur_bits.append(1)\n", " else:\n", " cur_bits.append(0)\n", "best_cut, best_bits = swap_partitions(graph, cur_bits)\n", "# Print final solution\n", "\n", "print(\n", " f\"The best max-cut value achieved for a graph with {num_nodes} nodes \"\n", " f\"on {num_qubits} qubits is {best_cut}\"\n", ")\n", "print(f\"and the specific partition we obtained is {best_bits}\")" ] }, { "cell_type": "markdown", "id": "9d68b120-bf43-4070-b897-013652c824d7", "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", " * [Fortgeschrittene Techniken für QAOA](/docs/tutorials/advanced-techniques-for-qaoa)\n", " * [Fehlerreduktionsoptionen mit dem Schätz-Basiselement kombinieren](/docs/tutorials/combine-error-mitigation-techniques)\n", "\n", "\n" ] }, { "cell_type": "markdown", "id": "99f8259d-fb92-4fae-ab68-96b1e50929a0", "metadata": {}, "source": [ "\n", "\n", "## Referenzen\n", "\n", "\\[1] Sciorilli, M., Borges, L., Patti, T. L., García-Martín, D., Camilo, G., Anandkumar, A., & Aolita, L. (2024). Auf dem Weg zu groß angelegten Quantenoptimierungslösern mit wenigen Qubits. arXiv Vorabdruck [arXiv:2401.09421](https://arxiv.org/abs/2401.09421).\n", "\n" ] }, { "cell_type": "markdown", "id": "a4d97730-3c7f-4ce9-8bb9-e4e1c3801c10", "metadata": {}, "source": [ "\n", "\n", "## Tutorial-Umfrage\n", "\n", "Bitte nehmen Sie an dieser kurzen Umfrage teil, um uns Ihr Feedback zu diesem Lernprogramm zu geben. Ihre Erkenntnisse helfen uns, unser Inhaltsangebot und unsere Nutzererfahrung zu verbessern.\n", "\n", "[Link zur Umfrage](https://your.feedback.ibm.com/jfe/form/SV_8ANZAlsKSFf6DA2)\n", "\n" ] }, { "cell_type": "markdown", "id": "0c934e9b-2864-4292-94c9-7fa9b5bce007", "metadata": {}, "source": [ "© IBM Corp. 2024–2026\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.5, "qpuSeconds": 2100 }, "nbformat": 4, "nbformat_minor": 4 }