{ "cells": [ { "cell_type": "markdown", "id": "2114652b-8f1f-4ba1-817b-48e98e3c6053", "metadata": {}, "source": [ "---\n", "title: \"Codage par corrélation de Pauli pour réduire les contraintes de coupe maximale\"\n", "description: \"Utiliser le codage par corrélation de Pauli pour coder les problèmes d'optimisation en qubits, ce qui permet d'améliorer l'efficacité du calcul quantique.\"\n", "---\n", "\n", "{/* cspell:ignore lbrack setminus coloneqq rbrack binom rhobeg nfev PCEFQ */}\n", "\n", "\n", "\n", "# Codage par corrélation de Pauli pour réduire les contraintes de coupe maximale\n", "\n", "*Durée estimée : 35 minutes sur un processeur Eagle r3 (REMARQUE : il s'agit uniquement d'une estimation.) (Votre temps d'exécution peut varier.)*\n", "\n" ] }, { "cell_type": "markdown", "id": "7239458e-d833-490e-8462-eaf2b5a115d4", "metadata": {}, "source": [ "\n", "\n", "## Résultats d'apprentissage\n", "\n", "À l'issue de ce tutoriel, les utilisateurs devraient obtenir les résultats suivants :\n", "\n", "* Comprendre les principes théoriques qui sous-tendent le codage par corrélation de Pauli (PCE), notamment comment les chaînes de Pauli à plusieurs corps permettent une compression polynomiale des problèmes d'optimisation classiques.\n", "* Mettre en œuvre le PCE dans la pratique pour coder et résoudre des problèmes d'optimisation à grande échelle sur du matériel quantique de prochaine génération.\n", "\n", "\n", "\n", "## Prérequis\n", "\n", "Nous vous recommandons de vous familiariser avec les sujets suivants avant de suivre ce tutoriel :\n", "\n", "* [Algorithmes quantiques variationnels](/learning/courses/variational-algorithm-design)\n", "* [QAOA et max-cut](/docs/tutorials/quantum-approximate-optimization-algorithm)\n", "\n" ] }, { "cell_type": "markdown", "id": "8a343d18-ab46-431f-899d-0664c2f99cc0", "metadata": {}, "source": [ "\n", "\n", "## Arrière-plan\n", "\n", "Ce tutoriel présente le *codage par corrélation de Pauli* (PCE) [\\[1\\]](#references), une approche conçue pour coder les problèmes d'optimisation dans des qubits avec une plus grande efficacité pour l'informatique quantique. Le PCE fait correspondre les variables classiques des problèmes d'optimisation aux corrélations de la matrice de Pauli à plusieurs corps, ce qui permet une compression polynomiale de l'espace requis pour le problème. L'utilisation du PCE permet de réduire le nombre de qubits nécessaires à l'encodage, ce qui le rend particulièrement avantageux pour les dispositifs quantiques à court terme dont les ressources en qubits sont limitées. En outre, il est démontré analytiquement que l'ECP atténue intrinsèquement les plateaux stériles, offrant une résilience super-polynomiale contre ce phénomène. Cette fonctionnalité intégrée permet d'obtenir des performances sans précédent dans les solveurs d'optimisation quantique.\n", "\n" ] }, { "cell_type": "markdown", "id": "c133831c-1eff-4913-aff6-8c0d82df9d61", "metadata": {}, "source": [ "\n", "\n", "### Aperçu\n", "\n", "L'approche PCE comprend trois étapes principales, comme l'illustre la figure 1 tirée de [\\[1\\]](#references) ci-dessous :\n", "\n", "1. Encodage du problème d'optimisation dans un espace de corrélation de Pauli.\n", "2. Résolution du problème à l'aide d'un solveur d'optimisation quantique-classique.\n", "3. Décodage de la solution dans l'espace d'optimisation d'origine.\n", " L'approche PCE est adaptable à tout solveur d'optimisation quantique capable de traiter les matrices de corrélation de Pauli.\n", "\n" ] }, { "attachments": {}, "cell_type": "markdown", "id": "40a636a3-c0c0-42ba-a68a-2abcb8a7187b", "metadata": {}, "source": [ "![Présentation du 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": [ "Dans la figure 1 tirée de [\\[1\\]](#references), le problème [de la coupe maximale](/docs/tutorials/quantum-approximate-optimization-algorithm) sert d'exemple pour illustrer l'approche PCE. Le problème de coupe maximale avec des nœuds de type « $m=9$ » est codé dans un espace de corrélation de Pauli, qui représente le problème d'optimisation sous la forme d'une matrice de corrélation — plus précisément, des corrélations de matrice de Pauli à deux corps entre les qubits de type « $n=3$ » $(Q_1, Q_2, Q_3)$. Les couleurs des nœuds indiquent la chaîne de Pauli utilisée pour chaque nœud codé.\n", "Par exemple, le nœud 1, qui correspond à la variable binaire $x_1$, est codé par la valeur attendue de $Z_1 \\otimes Z_2 \\otimes I_3$, tandis que $x_8$ est codé par $I_1 \\otimes Y_2 \\otimes Y_3$.\n", "Cela revient à compresser les variables d' $m$ s du problème en $ n = O(m^{1/2})$ qubits. Plus généralement, les corrélations à n corps d’ $k $ s permettent des compressions polynomiales d’ordre $k$, avec $k>1$. L’ensemble de Pauli choisi comprend trois sous-ensembles de chaînes de Pauli commutant entre elles, ce qui permet d’estimer expérimentalement toutes les corrélations d’ $m$ s à l’aide de seulement trois configurations de mesure.\n", "\n", "On construit une fonction de perte $\\mathcal{L}$ e des valeurs attendues de Pauli qui imite la fonction objective d'origine du max-cut. La fonction de perte est ensuite optimisée à l'aide d'un solveur d'optimisation quantique-classique, tel que le [Variational Quantum Eigensolver (VQE)](/learning/courses/quantum-diagonalization-algorithms/vqe).\n", "\n", "Une fois l'optimisation terminée, la solution est recodée dans l'espace d'optimisation d'origine, ce qui permet d'obtenir la solution optimale du problème de coupe maximale.\n", "\n", "\n", "\n", "## Exigences\n", "\n", "Avant de commencer ce tutoriel, assurez-vous que les éléments suivants sont installés :\n", "\n", "* Qiskit SDK v1.0 ou plus tard, avec prise en charge de [la visualisation](/docs/api/qiskit/visualization)\n", "* Qiskit Runtime v0.22 ou plus tard (`pip install qiskit-ibm-runtime`)\n", "\n" ] }, { "cell_type": "markdown", "id": "adfa1c9b-0dd3-42d0-afd9-bce648cf668e", "metadata": {}, "source": [ "\n", "\n", "## Configuration\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", "## Exemple de simulateur à petite échelle\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", "### Étape 1 : Mettre en correspondance les entrées classiques avec un problème quantique\n", "\n", "\n", "\n", "#### Le problème du découpage optimal\n", "\n", "Le problème du « max-cut » est un problème d'optimisation combinatoire défini sur un graphe $G = (V, E)$, où $V$ est l'ensemble des sommets et $E$ l'ensemble des arêtes. L'objectif est de répartir les sommets en deux ensembles, $S$ et $V \\setminus S$, de manière à maximiser le nombre d'arêtes entre ces deux ensembles.\n", "Pour une description détaillée du problème « max-cut », veuillez vous reporter au tutoriel sur [l'algorithme d'optimisation approximative quantique](/docs/tutorials/quantum-approximate-optimization-algorithm).\n", "Le problème du « max-cut » est également utilisé comme exemple dans le tutoriel «[ Techniques avancées pour le QAOA](/docs/tutorials/advanced-techniques-for-qaoa) ».\n", "Dans ces tutoriels, l'algorithme QAOA est utilisé pour résoudre le problème du coupé maximal.\n", "\n", "-hamiltonian\" />\n", "\n", "#### Graphique -> Hamiltonien\n", "\n", "Considérons tout d'abord un graphe aléatoire comportant 100 nœuds.\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": [ "Nous codons le graphe de 100 nœuds sous forme de corrélations de matrices de Pauli à deux corps sur neuf qubits (voir l'explication ci-dessous). Le graphe est représenté sous la forme d'une matrice de corrélation, dans laquelle chaque nœud est codé par une chaîne de Pauli. Le signe de la valeur attendue de la chaîne de Pauli indique la partition du nœud. Par exemple, le nœud 0 est codé par une chaîne de Pauli, $\\prod_0 = I_{8} \\otimes ... I_2 \\otimes X_1 \\otimes X_0$. Le signe de la valeur attendue de cette chaîne de Pauli indique la partition du nœud 0. Nous définissons un *codage par corrélation de Pauli* (PCE) par rapport à l' $\\prod$ e comme suit :\n", "\n", "$x_i \\coloneqq \\textit{sgn}(\\langle\\prod_i \\rangle),$\n", "\n", "où $x_i$ est la partition du nœud $i$ et $\\langle \\prod_i \\rangle \\coloneqq \\langle \\psi |\\prod_i| \\psi \\rangle $ est la valeur d'espérance de la chaîne de Pauli codant le nœud $i$ sur un état quantique $|\\psi \\rangle$.\n", "\n" ] }, { "cell_type": "markdown", "id": "678e00fb-5bb9-450e-8229-0eab5676057a", "metadata": {}, "source": [ "Encodons maintenant le graphe dans un hamiltonien à l'aide de PCE.\n", "Nous divisons les nœuds en trois ensembles : $S_1$ $S_2$, et $S_3$. Ensuite, nous codons les nœuds de chaque ensemble en utilisant les chaînes de Pauli avec $X$, $Y$, et $Z$, respectivement.\n", "\n" ] }, { "cell_type": "markdown", "id": "4d5d48e5-ebe8-4b36-9496-288f40174a7b", "metadata": {}, "source": [ "Nous devons déterminer la relation entre le nombre de nœuds et le nombre de qubits nécessaires pour coder tous ces nœuds. En utilisant toutes les permutations possibles pour le codage, on obtient :\n", "\n", "$$\n", "m=3\\binom{n}{k}.\n", "$$\n", "\n", "Dans cet exemple, nous considérons qu' $k=2$; par conséquent,\n", "\n", "$$\n", "m = \\frac{3}{2} n(n-1).\n", "$$\n", "\n", "Par conséquent, le nombre de qubits $n$ nécessaire pour représenter un certain nombre de nœuds $m$ s'écrit comme suit :\n", "\n", "$$\n", "n = \\left\\lceil \\frac{1 + \\sqrt{1 + \\tfrac{8}{3}m}}{2} \\right\\rceil.\n", "$$\n", "\n", "*Notez que le symbole $\\lceil \\cdot \\rceil$ désigne la fonction plafond, qui arrondit tout nombre réel à l'entier supérieur. Cela garantit que le nombre de qubits est un nombre entier.*\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", "### Étape 2 : Optimiser le problème pour l'exécution sur du matériel quantique\n", "\n", "\n", "\n", "#### Circuit quantique\n", "\n", "Ici, l'état $|\\psi \\rangle$ est paramétré avec $\\mathbf{\\theta}$, et nous optimisons ces paramètres $\\mathbf{\\theta}$ en utilisant une approche variationnelle.\n", "Ce tutoriel utilise l'ansatz `efficient_su2` pour notre algorithme variationnel en raison de ses capacités expressives et de sa facilité de mise en œuvre.\n", "Nous utilisons également la fonction de perte relaxée, qui sera présentée plus loin dans ce tutoriel.\n", "Par conséquent, nous pouvons résoudre des problèmes à grande échelle avec moins de qubits et des circuits moins profonds.\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", "#### Fonction de perte\n", "\n", "Pour la fonction de perte $\\mathcal{L}$, nous utilisons une relaxation de la fonction objective du max-cut telle que décrite dans [\\[1\\]](#references), qui est définie comme suit : $\\mathcal{V}(\\mathbf{x}) \\coloneqq \\sum_{(i, j) \\in E} W_{i, j}(1-x_i x_j)$. Ici, $W_{i, j}$ désigne le poids de l'arête $(i, j)$, et $x_i$ représente la partition du nœud $i$.\n", "La fonction de perte $\\mathcal{L}$ est donnée par :\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", "où la fonction objectif max-cut est remplacée par les tangentes hyperboliques lissées des valeurs attendues des chaînes de Pauli codant les nœuds. Le terme de régularisation $\\mathcal{L}^{(\\text{reg})}$ et le facteur de mise à l'échelle $\\alpha$, proportionnels au nombre de qubits, sont introduits afin d'améliorer les performances du solveur.\n", "\n", "Le terme de régularisation est défini comme suit :\n", "\n", "$\\mathcal{L}^{(\\text{reg})}$ est défini comme suit $\\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", "où $\\beta=1/2$, $\\nu = |E|/2 + (m -1) /4$, $|E|$ représente le nombre d'arêtes, et $m$ le nombre de nœuds du graphe.\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", "### Étape 3 : Exécutez à l'aide d' Qiskit primitives\n", "\n" ] }, { "cell_type": "markdown", "id": "583ba786-e2e9-4593-bf75-00723b589d78", "metadata": {}, "source": [ "Dans ce tutoriel, nous avons défini `max_iter=50` dans la boucle d'optimisation à des fins de démonstration. Si nous augmentons le nombre d'itérations, nous pouvons nous attendre à de meilleurs résultats.\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", "### Étape 4 : Post-traitement et restitution du résultat dans le format classique souhaité\n", "\n", "Les partitions des nœuds sont déterminées en évaluant le signe des valeurs d'espérance des chaînes de Pauli qui codent les nœuds.\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": [ "Nous pouvons calculer la taille de la coupe dans le problème de la coupe maximale à l'aide des partitions du nœud.\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": [ "Une fois l'apprentissage terminé, nous effectuons un tour de recherche par permutation d'un seul bit afin d'améliorer la solution dans le cadre d'une étape classique de post-traitement.\n", "Dans ce processus, nous échangeons les partitions de deux nœuds et évaluons la taille de la coupe. Si la taille de la coupe est améliorée, nous conservons l'échange. Nous répétons ce processus pour toutes les paires possibles de nœuds connectés par une arête.\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", "# Exemple de matériel à grande échelle\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", "## Etapes suivantes\n", "\n", "\n", " Si ce travail vous a paru intéressant, les ressources suivantes pourraient vous intéresser :\n", "\n", " * [Techniques avancées pour le QAOA](/docs/tutorials/advanced-techniques-for-qaoa)\n", " * [Combiner les options d'atténuation des erreurs avec la primitive Estimator](/docs/tutorials/combine-error-mitigation-techniques)\n", "\n", "\n" ] }, { "cell_type": "markdown", "id": "99f8259d-fb92-4fae-ab68-96b1e50929a0", "metadata": {}, "source": [ "\n", "\n", "## Références\n", "\n", "\\[1] Sciorilli, M., Borges, L., Patti, T. L., García-Martín, D., Camilo, G., Anandkumar, A., & Aolita, L. (2024). Vers des solveurs d'optimisation quantique à grande échelle utilisant un petit nombre de qubits. arXiv Prépublication [arXiv:2401.09421](https://arxiv.org/abs/2401.09421).\n", "\n" ] }, { "cell_type": "markdown", "id": "a4d97730-3c7f-4ce9-8bb9-e4e1c3801c10", "metadata": {}, "source": [ "\n", "\n", "## Enquête tutorielle\n", "\n", "Veuillez répondre à cette courte enquête pour nous faire part de vos commentaires sur ce didacticiel. Vos commentaires nous aideront à améliorer nos offres de contenu et l'expérience des utilisateurs.\n", "\n", "[Lien vers l'enquête](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 }