{ "cells": [ { "cell_type": "markdown", "id": "bc51e7bf-e582-49ba-93f8-035624d56ccf", "metadata": {}, "source": [ "---\n", "title: \"Algorithme d'optimisation approximative quantique\"\n", "description: \"Résoudre le problème du « max-cut » à l'aide de l'algorithme QAOA avec un modèle Qiskit à l'échelle industrielle.\"\n", "---\n", "\n", "{/* cspell:ignore frameon popcount fval */}\n", "\n", "\n", "\n", "# Algorithme d'optimisation approximative quantique\n", "\n", "*Estimation de l'utilisation : 22 minutes sur un processeur Heron r3 (REMARQUE : il s'agit uniquement d'une estimation). Votre durée d'exécution peut varier.)*\n", "\n" ] }, { "cell_type": "markdown", "id": "learning-outcomes-prereqs", "metadata": {}, "source": [ "\n", "\n", "## Résultats d'apprentissage\n", "\n", "À l'issue de ce tutoriel, vous devriez être en mesure de comprendre les points suivants :\n", "\n", "* Comment transposer un problème classique d'optimisation combinatoire (coupe maximale) en un hamiltonien quantique\n", "* Comment implémenter et exécuter l'algorithme d'optimisation quantique approximative (QAOA) à l'aide de sessions du service de calcul d' IBM Quantum\n", "* Comment faire évoluer un workflow QAOA, depuis un exemple sur petit simulateur jusqu'à une exécution sur du matériel à l'échelle industrielle\n", "\n", "\n", "\n", "## Prérequis\n", "\n", "Nous vous recommandons de vous familiariser avec les sujets suivants :\n", "\n", "* [Les bases des circuits quantiques](/learning/courses/basics-of-quantum-information)\n", "* [Algorithmes variationnels](/learning/courses/variational-algorithm-design)\n", "* [QAOA en détail](/learning/courses/quantum-computing-in-practice/utility-scale-qaoa) — pour une présentation exhaustive de l'algorithme QAOA et de son application à l'échelle industrielle\n", "\n" ] }, { "cell_type": "markdown", "id": "de201dbb", "metadata": {}, "source": [ "\n", "\n", "## Arrière-plan\n", "\n", "**L** 'algorithme d'optimisation approximative quantique (QAOA) est une méthode itérative hybride quantique-classique permettant de résoudre des problèmes d'optimisation combinatoire. Dans ce tutoriel, vous utiliserez QAOA pour résoudre le problème **de la coupe maximale (max-cut)** — un problème d'optimisation NP-difficile qui trouve des applications dans le regroupement de données, la science des réseaux et la physique statistique. Étant donné un graphe composé de nœuds reliés par des arêtes, l'objectif est de partitionner les nœuds en deux ensembles de manière à maximiser le nombre d'arêtes traversant la partition.\n", "\n", "![Illustration d'un problème de coupe maximale](https://quantum.cloud.ibm.com/docs/images/tutorials/quantum-approximate-optimization-algorithm/maxcut-illustration.avif)\n", "\n", "\n", "\n", "### De l'optimisation classique aux circuits quantiques\n", "\n", "Le problème de Max-cut peut être formulé comme un problème d'optimisation binaire classique. À chaque nœud est attribuée une variable binaire $x_i \\in \\{0, 1\\}$ indiquant à quel ensemble il appartient. L'objectif est de maximiser le nombre d'arêtes dont les extrémités appartiennent à des ensembles différents :\n", "\n", "$$\n", "\\max_{x \\in \\{0,1\\}^n} \\sum_{(i,j)} x_i + x_j - 2x_ix_j.\n", "$$\n", "\n", "Cela revient à un problème **d'optimisation binaire quadratique sans contrainte (QUBO)** de la forme $\\min_x\\, x^T Q x$. Grâce à une substitution de variables standard ( $x_i \\to (1 - Z_i)/2$ ), le problème QUBO peut être réécrit sous la forme d'un **hamiltonien de coût** dont l'état fondamental code la solution optimale. En général, cet hamiltonien comporte à la fois des termes quadratiques et linéaires :\n", "\n", "$$\n", "H_C = \\sum_{ij} Q_{ij} \\, Z_i Z_j + \\sum_i b_i \\, Z_i.\n", "$$\n", "\n", "Pour le problème de coupe maximale non pondérée considéré ici, les coefficients linéaires s'annulent ( $b_i = 0$ ) et $Q_{ij} = 1$ pour chaque arête, ce qui donne la forme simplifiée $H_C = \\sum_{(i,j) \\in E} Z_i Z_j$ que vous allez implémenter dans le code ci-dessous. La forme plus générale ci-dessus est celle dont vous aurez besoin pour adapter ce workflow aux graphes pondérés ou à d'autres problèmes pouvant être formulés sous forme de QUBO.\n", "\n", "\n", "\n", "### Comment fonctionne le QAOA\n", "\n", "La méthode QAOA élabore des solutions candidates en appliquant des couches alternées de deux opérateurs à un état de superposition initial $H^{\\otimes n}|0\\rangle$ : l' **opérateur** de coût $e^{-i\\gamma_k H_C}$ et un **opérateur de mélange** $e^{-i\\beta_k H_m}$. Les angles $\\gamma_k$ et $\\beta_k$ sont optimisés dans une boucle de rétroaction classique; l'ordinateur quantique évalue la fonction de coût, et un optimiseur classique met à jour les paramètres jusqu'à convergence. Cette boucle itérative s'exécute au sein d'une **session** de calcul quantique, ce qui permet de maintenir le dispositif quantique réservé d'une itération à l'autre afin de réduire la latence.\n", "\n", "![Schéma de circuit avec couches QAOA](https://quantum.cloud.ibm.com/docs/images/tutorials/quantum-approximate-optimization-algorithm/circuit-diagram.svg)\n", "\n", "Pour une étude plus approfondie de la théorie QAOA, y compris la déduction complète du modèle QUBO vers l'hamiltonien, consultez le [module de cours sur la QAOA](/learning/courses/utility-scale-quantum-computing/variational-quantum-algorithms#1-introduction).\n", "\n", "Dans ce tutoriel, vous allez d'abord résoudre le problème du « max-cut » sur un petit graphe à cinq nœuds, puis adapter ce même processus à un problème à grande échelle portant sur 100 nœuds, sur du matériel réel. *Remarque concernant l'accès aux formules :* ce tutoriel utilise [des sessions](/docs/guides/execution-modes#session-mode) Quantum Compute, qui ne sont disponibles que dans la formule Premium. Si vous utilisez le plan « Open Plan », vous ne pouvez pas suivre ce tutoriel tel quel; vous devrez plutôt passer en `Session` [mode « job »](/docs/guides/execution-modes#job-mode) (c'est-à-dire soumettre chaque itération sous forme de tâche indépendante plutôt que d'encapsuler la boucle d'optimisation dans `Session(...)`). Le workflow continue de s'exécuter, mais chaque itération subit la latence totale de la file d'attente au lieu de réutiliser un périphérique réservé. Pour plus d'informations, consultez la rubrique « [Présentation des formules disponibles](/docs/guides/plans-overview) ».\n", "\n" ] }, { "cell_type": "markdown", "id": "381800e5", "metadata": {}, "source": [ "\n", "\n", "## Exigences\n", "\n", "Avant de commencer ce tutoriel, assurez-vous que les éléments suivants sont installés :\n", "\n", "* Qiskit SDK v2.0 ou version ultérieure, 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", "De plus, vous devrez disposer d'un accès à une instance sur [IBM Quantum® Platform](/docs/guides/cloud-setup).\n", "\n" ] }, { "cell_type": "markdown", "id": "f5307376", "metadata": {}, "source": [ "\n", "\n", "## Configuration\n", "\n" ] }, { "cell_type": "code", "execution_count": 1, "id": "37b3acfc", "metadata": {}, "outputs": [], "source": [ "import matplotlib.pyplot as plt\n", "import rustworkx as rx\n", "from rustworkx.visualization import mpl_draw as draw_graph\n", "import numpy as np\n", "from scipy.optimize import minimize\n", "from collections import defaultdict\n", "from typing import Sequence\n", "\n", "\n", "from qiskit.quantum_info import SparsePauliOp\n", "from qiskit.circuit.library import QAOAAnsatz\n", "from qiskit.transpiler.preset_passmanagers import generate_preset_pass_manager\n", "\n", "from qiskit_ibm_runtime import QiskitRuntimeService\n", "from qiskit_ibm_runtime import Session, EstimatorV2 as Estimator\n", "from qiskit_ibm_runtime import SamplerV2 as Sampler" ] }, { "cell_type": "markdown", "id": "68fd0b4f-baa4-45dc-9f4c-d9cdff01a651", "metadata": {}, "source": [ "\n", "\n", "## Exemple à petite échelle\n", "\n", "Cette section présente étape par étape le déroulement du processus QAOA sur une petite instance de problème de coupe maximale à cinq nœuds. Même s'il est qualifié de « petite échelle », cet exemple s'exécute tout de même sur du matériel d' IBM Quantum s réel : le code sélectionne un backend comportant au moins 127 qubits et y exécute le circuit.\n", "\n" ] }, { "cell_type": "markdown", "id": "0cbca6cb", "metadata": {}, "source": [ "Initialisez votre problème en créant un graphe avec $n=5$ nœuds.\n", "\n" ] }, { "cell_type": "code", "execution_count": 2, "id": "6ced6bea", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "\"Output" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "n_small = 5\n", "\n", "graph = rx.PyGraph()\n", "graph.add_nodes_from(np.arange(0, n_small, 1))\n", "edge_list = [\n", " (0, 1, 1.0),\n", " (0, 2, 1.0),\n", " (0, 4, 1.0),\n", " (1, 2, 1.0),\n", " (2, 3, 1.0),\n", " (3, 4, 1.0),\n", "]\n", "graph.add_edges_from(edge_list)\n", "draw_graph(graph, node_size=600, with_labels=True)" ] }, { "cell_type": "markdown", "id": "a06e4386-d7bd-4914-9baa-36a5cc60e3ab", "metadata": {}, "source": [ "\n", "\n", "### Étape 1 : Mettre en correspondance les entrées classiques avec un problème quantique\n", "\n", "Représentez le graphe classique sous forme de **circuits** quantiques et **d'opérateurs**. Comme indiqué dans la [section « Contexte »](#background), pour le problème du « max-cut » non pondéré, l'hamiltonien de coût se réduit à $H_C = \\sum_{(i,j) \\in E} Z_i Z_j$, et la méthode QAOA utilise un circuit d'ansatz paramétré pour préparer des états fondamentaux candidats de $H_C$.\n", "\n" ] }, { "cell_type": "markdown", "id": "a5b9e551-38a1-4543-b9f1-caaefb0ef3a9", "metadata": {}, "source": [ "\n", "\n", "#### Construire l'hamiltonien des coûts\n", "\n", "Convertissez les arêtes du graphe en termes Pauli $Z_iZ_j$ pour construire $H_C$ (voir [Contexte](#background) pour la dérivation).\n", "\n" ] }, { "cell_type": "code", "execution_count": 3, "id": "52d1ba92", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Cost Function Hamiltonian: SparsePauliOp(['IIIZZ', 'IIZIZ', 'ZIIIZ', 'IIZZI', 'IZZII', 'ZZIII'],\n", " coeffs=[1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j])\n" ] } ], "source": [ "def build_max_cut_paulis(\n", " graph: rx.PyGraph,\n", ") -> list[tuple[str, list[int], float]]:\n", " \"\"\"Convert graph edges to a list of ZZ Pauli terms.\n", "\n", " The returned list is in the sparse format expected by\n", " ``SparsePauliOp.from_sparse_list``: each element is\n", " ``(pauli_string, qubit_indices, coefficient)``.\n", " \"\"\"\n", " pauli_list = []\n", " for edge in list(graph.edge_list()):\n", " weight = graph.get_edge_data(edge[0], edge[1])\n", " pauli_list.append((\"ZZ\", [edge[0], edge[1]], weight))\n", " return pauli_list\n", "\n", "\n", "max_cut_paulis = build_max_cut_paulis(graph)\n", "cost_hamiltonian = SparsePauliOp.from_sparse_list(max_cut_paulis, n_small)\n", "print(\"Cost Function Hamiltonian:\", cost_hamiltonian)" ] }, { "cell_type": "markdown", "id": "33f71b0d-4a2a-4082-8c1a-ce9d2b769048", "metadata": {}, "source": [ "\n", "\n", "#### Construire le circuit de l'approche QAOA\n", "\n" ] }, { "cell_type": "markdown", "id": "00431c46-30c2-40f9-99df-40baf8da98f6", "metadata": {}, "source": [ "Utilisez `QAOAAnsatz` pour construire le circuit QAOA paramétré à partir de l'hamiltonien de coût. Nous utilisons `reps=2` ici (deux couches QAOA, quatre paramètres : $\\beta_0, \\beta_1, \\gamma_0, \\gamma_1$ ).\n", "\n" ] }, { "cell_type": "code", "execution_count": 4, "id": "7bd8c6d4-f40f-4a11-a440-0b26d9021b53", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "\"Output" ] }, "execution_count": 4, "metadata": {}, "output_type": "execute_result" } ], "source": [ "circuit = QAOAAnsatz(cost_operator=cost_hamiltonian, reps=2)\n", "circuit.measure_all()\n", "\n", "circuit.draw(\"mpl\")" ] }, { "cell_type": "code", "execution_count": 5, "id": "315c495a", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "ParameterView([ParameterVectorElement(β[0]), ParameterVectorElement(β[1]), ParameterVectorElement(γ[0]), ParameterVectorElement(γ[1])])" ] }, "execution_count": 5, "metadata": {}, "output_type": "execute_result" } ], "source": [ "circuit.parameters" ] }, { "cell_type": "markdown", "id": "82f70daa-ff68-447a-8064-8b7df7a646cf", "metadata": {}, "source": [ "\n", "\n", "### Étape 2 : Optimiser le problème pour l'exécution sur du matériel quantique\n", "\n" ] }, { "cell_type": "markdown", "id": "c08be444-e3ed-4178-a10b-414069b1b411", "metadata": {}, "source": [ "Convertir le circuit abstrait en instructions natives du matériel. Cette étape gère le mappage des qubits, la décomposition des portes, le routage et la suppression des erreurs. Pour plus d'informations, consultez la [documentation](/docs/guides/transpile) sur la transpilation.\n", "\n" ] }, { "cell_type": "code", "execution_count": 6, "id": "3f28a422-805c-4d3d-b5f6-62539e9133bd", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "\n" ] }, { "data": { "text/plain": [ "\"Output" ] }, "execution_count": 6, "metadata": {}, "output_type": "execute_result" } ], "source": [ "service = QiskitRuntimeService()\n", "backend = service.least_busy(\n", " operational=True, simulator=False, min_num_qubits=127\n", ")\n", "print(backend)\n", "\n", "# Create pass manager for transpilation. Level 3 is the most aggressive\n", "# preset: slower to transpile, but produces shorter circuits that are\n", "# more robust to hardware noise.\n", "pm = generate_preset_pass_manager(optimization_level=3, backend=backend)\n", "\n", "candidate_circuit = pm.run(circuit)\n", "candidate_circuit.draw(\"mpl\", fold=False, idle_wires=False)" ] }, { "cell_type": "markdown", "id": "4e75cad7-f599-4937-b5fe-f4d01f53423c", "metadata": {}, "source": [ "\n", "\n", "### Étape 3 : Exécutez à l'aide d' Qiskit primitives\n", "\n" ] }, { "cell_type": "markdown", "id": "9b99ce67-f121-4244-b62a-536be38fea86", "metadata": {}, "source": [ "La boucle d'optimisation QAOA s'exécute au sein d'une [session](/docs/guides/execution-modes) Quantum Compute afin de garantir que le périphérique reste réservé d'une itération à l'autre. Un estimateur évalue l' $\\langle H_C \\rangle$ e à chaque étape, et un optimiseur classique (COBYLA) met à jour les paramètres jusqu'à convergence.\n", "\n", "![Illustration montrant le comportement des modes d'exécution Single job, Batch et Session.](https://quantum.cloud.ibm.com/docs/images/tutorials/quantum-approximate-optimization-algorithm/runtime-modes.avif)\n", "\n" ] }, { "cell_type": "markdown", "id": "00b2b0f1-9bad-4ad3-b93e-5cbf40395dbf", "metadata": {}, "source": [ "Définissez les paramètres initiaux et lancez la boucle d'optimisation :\n", "\n" ] }, { "cell_type": "code", "execution_count": 7, "id": "afa5747f-44dc-4e41-a875-7b6f896f13e2", "metadata": {}, "outputs": [], "source": [ "# QAOA doesn't prescribe principled default angles — any bounded choice\n", "# works as a warm start for problems this small. beta and gamma are\n", "# periodic (beta in [0, pi] and gamma in [0, 2*pi] modulo the underlying\n", "# Pauli-rotation periods), and pi/2 and pi are just midpoints of those\n", "# ranges. For harder problems you would typically warm start from known\n", "# good angles or transfer parameters from smaller instances.\n", "initial_gamma = np.pi\n", "initial_beta = np.pi / 2\n", "init_params = [initial_beta, initial_beta, initial_gamma, initial_gamma]" ] }, { "cell_type": "code", "execution_count": 8, "id": "3e64a862", "metadata": {}, "outputs": [], "source": [ "def cost_func_estimator(params, ansatz, hamiltonian, estimator):\n", " # transform the observable defined on virtual qubits to\n", " # an observable defined on all physical qubits\n", " isa_hamiltonian = hamiltonian.apply_layout(ansatz.layout)\n", "\n", " pub = (ansatz, isa_hamiltonian, params)\n", " job = estimator.run([pub])\n", "\n", " results = job.result()[0]\n", " cost = results.data.evs\n", "\n", " objective_func_vals.append(cost)\n", "\n", " return cost" ] }, { "cell_type": "code", "execution_count": 9, "id": "2df241a9", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ " message: Return from COBYLA because the trust region radius reaches its lower bound.\n", " success: True\n", " status: 0\n", " fun: -2.0402211719947774\n", " x: [ 3.041e+00 1.212e+00 2.081e+00 4.471e+00]\n", " nfev: 36\n", " maxcv: 0.0\n" ] } ], "source": [ "objective_func_vals = [] # Global variable\n", "with Session(backend=backend) as session:\n", " # If using qiskit-ibm-runtime<0.24.0, change `mode=` to `session=`\n", " estimator = Estimator(mode=session)\n", " estimator.options.default_shots = 1000\n", "\n", " # Set simple error suppression/mitigation options\n", " estimator.options.dynamical_decoupling.enable = True\n", " estimator.options.dynamical_decoupling.sequence_type = \"XY4\"\n", " estimator.options.twirling.enable_gates = True\n", " estimator.options.twirling.num_randomizations = \"auto\"\n", " estimator.options.environment.job_tags = [\"TUT_QAOA\"]\n", "\n", " result = minimize(\n", " cost_func_estimator,\n", " init_params,\n", " args=(candidate_circuit, cost_hamiltonian, estimator),\n", " method=\"COBYLA\",\n", " tol=1e-2,\n", " )\n", " print(result)" ] }, { "cell_type": "markdown", "id": "01d6b81c", "metadata": {}, "source": [ "L'optimiseur a permis de réduire le coût et de trouver de meilleurs paramètres pour le circuit.\n", "\n", "Une courbe qui diminue progressivement avant de se stabiliser est le signe d'une convergence. Une courbe bruyante et non monotone indique généralement qu'il faut se pencher sur un problème en amont; les causes courantes sont un nombre insuffisant d'itérations par évaluation (variance élevée de l'estimateur), des paramètres initiaux inadéquats ou un circuit dont la profondeur est dominée par le bruit matériel. COBYLA ne fait appel à aucun dérivé et résiste assez bien à un bruit modéré, mais lorsque le bruit l'emporte sur les gains réels de coût par itération, son modèle d'approximation linéaire ne parvient plus à distinguer la descente réelle des fluctuations aléatoires, et l'optimiseur s'égare.\n", "\n" ] }, { "cell_type": "code", "execution_count": 10, "id": "e14ecc92", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "\"Output" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "plt.figure(figsize=(12, 6))\n", "plt.plot(objective_func_vals)\n", "plt.xlabel(\"Iteration\")\n", "plt.ylabel(\"Cost\")\n", "plt.show()" ] }, { "cell_type": "markdown", "id": "1f9c8a9c", "metadata": {}, "source": [ "Attribuez les paramètres optimisés et échantillonnez la distribution finale à l'aide de la primitive Sampler.\n", "\n" ] }, { "cell_type": "code", "execution_count": 11, "id": "2989e76e-4296-4dd8-b065-2b8fced064cf", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "\"Output" ] }, "execution_count": 11, "metadata": {}, "output_type": "execute_result" } ], "source": [ "optimized_circuit = candidate_circuit.assign_parameters(result.x)\n", "optimized_circuit.draw(\"mpl\", fold=False, idle_wires=False)" ] }, { "cell_type": "code", "execution_count": 12, "id": "d8f0e302", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "{18: 0.039, 5: 0.0665, 20: 0.0973, 29: 0.0063, 9: 0.0899, 13: 0.0379, 2: 0.0047, 1: 0.0153, 11: 0.0932, 14: 0.0327, 12: 0.0314, 25: 0.0193, 21: 0.0398, 6: 0.0224, 4: 0.0197, 10: 0.0387, 3: 0.0181, 26: 0.07, 17: 0.0327, 19: 0.0332, 22: 0.0914, 24: 0.007, 0: 0.0033, 8: 0.0066, 30: 0.0158, 28: 0.0169, 27: 0.0222, 16: 0.0073, 7: 0.0057, 23: 0.0062, 15: 0.0054, 31: 0.0041}\n" ] } ], "source": [ "# If using qiskit-ibm-runtime<0.24.0, change `mode=` to `backend=`\n", "sampler = Sampler(mode=backend)\n", "sampler.options.default_shots = 10000\n", "\n", "# Set simple error suppression/mitigation options\n", "sampler.options.dynamical_decoupling.enable = True\n", "sampler.options.dynamical_decoupling.sequence_type = \"XY4\"\n", "sampler.options.twirling.enable_gates = True\n", "sampler.options.twirling.num_randomizations = \"auto\"\n", "\n", "sampler.options.environment.job_tags = [\"TUT_QAOA\"]\n", "\n", "pub = (optimized_circuit,)\n", "job = sampler.run([pub], shots=int(1e4))\n", "counts_int = job.result()[0].data.meas.get_int_counts()\n", "counts_bin = job.result()[0].data.meas.get_counts()\n", "shots = sum(counts_int.values())\n", "final_distribution_int = {key: val / shots for key, val in counts_int.items()}\n", "final_distribution_bin = {key: val / shots for key, val in counts_bin.items()}\n", "print(final_distribution_int)" ] }, { "cell_type": "markdown", "id": "dace5fed-5555-4f1c-9109-7f5a31832d04", "metadata": {}, "source": [ "\n", "\n", "### Étape 4 : Post-traitement et restitution du résultat dans le format classique souhaité\n", "\n", "Extraire la chaîne binaire la plus probable de la distribution échantillonnée. Il s'agit de la meilleure version trouvée par QAOA.\n", "\n" ] }, { "cell_type": "code", "execution_count": 13, "id": "d4f7fc70-883f-4b6b-8e92-2fc4afbbea46", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Result bitstring: [0, 0, 1, 0, 1]\n" ] } ], "source": [ "# auxiliary functions to sample most likely bitstring\n", "def to_bitstring(integer, num_bits):\n", " result = np.binary_repr(integer, width=num_bits)\n", " return [int(digit) for digit in result]\n", "\n", "\n", "keys = list(final_distribution_int.keys())\n", "values = list(final_distribution_int.values())\n", "most_likely = keys[np.argmax(np.abs(values))]\n", "most_likely_bitstring = to_bitstring(most_likely, len(graph))\n", "most_likely_bitstring.reverse()\n", "\n", "print(\"Result bitstring:\", most_likely_bitstring)" ] }, { "cell_type": "code", "execution_count": 14, "id": "650875e9-adbc-43bd-9505-556be2566278", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "\"Output" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "plt.rcParams.update({\"font.size\": 10})\n", "final_bits = final_distribution_bin\n", "values = np.abs(list(final_bits.values()))\n", "top_4_values = sorted(values, reverse=True)[:4]\n", "positions = []\n", "for value in top_4_values:\n", " positions.append(np.where(values == value)[0])\n", "fig = plt.figure(figsize=(11, 6))\n", "ax = fig.add_subplot(1, 1, 1)\n", "plt.xticks(rotation=45)\n", "plt.title(\"Result Distribution\")\n", "plt.xlabel(\"Bitstrings (reversed)\")\n", "plt.ylabel(\"Probability\")\n", "ax.bar(list(final_bits.keys()), list(final_bits.values()), color=\"tab:grey\")\n", "for p in positions:\n", " ax.get_children()[int(p[0])].set_color(\"tab:purple\")\n", "plt.show()" ] }, { "cell_type": "markdown", "id": "207443f2-34d9-424a-a6d7-44707ef1488b", "metadata": {}, "source": [ "\n", "\n", "#### Visualiser la meilleure coupe\n", "\n", "À partir de la chaîne binaire optimale, vous pouvez ensuite visualiser cette découpe sur le graphe d'origine.\n", "\n" ] }, { "cell_type": "code", "execution_count": 15, "id": "33135970-8bc4-4fb2-ab87-08726a432ce4", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "\"Output" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "# auxiliary function to plot graphs\n", "def plot_result(G, x):\n", " colors = [\"tab:grey\" if i == 0 else \"tab:purple\" for i in x]\n", " pos, _default_axes = rx.spring_layout(G), plt.axes(frameon=True)\n", " rx.visualization.mpl_draw(\n", " G, node_color=colors, node_size=100, alpha=0.8, pos=pos\n", " )\n", "\n", "\n", "plot_result(graph, most_likely_bitstring)" ] }, { "cell_type": "markdown", "id": "2119575f-f3cf-45bc-ae2b-93c046391eb6", "metadata": {}, "source": [ "Calculez maintenant la valeur de la découpe :\n", "\n" ] }, { "cell_type": "code", "execution_count": 16, "id": "2f6a73c4-f5ae-4647-a0dd-d77a13f66388", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "The value of the cut is: 5\n" ] } ], "source": [ "def evaluate_sample(x: Sequence[int], graph: rx.PyGraph) -> float:\n", " assert len(x) == len(\n", " list(graph.nodes())\n", " ), \"The length of x must coincide with the number of nodes in the graph.\"\n", " return sum(\n", " x[u] * (1 - x[v]) + x[v] * (1 - x[u])\n", " for u, v in list(graph.edge_list())\n", " )\n", "\n", "\n", "cut_value = evaluate_sample(most_likely_bitstring, graph)\n", "print(\"The value of the cut is:\", cut_value)" ] }, { "cell_type": "markdown", "id": "76a7241e", "metadata": {}, "source": [ "Pour un graphe aussi petit, il est facile de trouver le véritable optimum par force brute; vous pouvez donc vérifier les résultats en comparant le résultat obtenu par l'algorithme QAOA à la réponse exacte.\n", "\n" ] }, { "cell_type": "code", "execution_count": 17, "id": "0a3b5267", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Classical optimum (brute force): 5\n", "QAOA cut value: 5\n" ] } ], "source": [ "# Classical baseline: enumerate all 2**n_small bitstrings and take the best cut.\n", "def brute_force_max_cut(graph: rx.PyGraph) -> tuple[int, list[int]]:\n", " n = len(list(graph.nodes()))\n", " best_cut = -1\n", " best_x: list[int] = []\n", " for i in range(2**n):\n", " x = [(i >> k) & 1 for k in range(n)]\n", " cut = evaluate_sample(x, graph)\n", " if cut > best_cut:\n", " best_cut = int(cut)\n", " best_x = x\n", " return best_cut, best_x\n", "\n", "\n", "classical_best, classical_x = brute_force_max_cut(graph)\n", "print(f\"Classical optimum (brute force): {classical_best}\")\n", "print(f\"QAOA cut value: {cut_value}\")" ] }, { "cell_type": "markdown", "id": "large-scale-header", "metadata": {}, "source": [ "\n", "\n", "## Exemple de matériel à grande échelle\n", "\n", "Sur IBM Quantum Platform, vous avez accès à de nombreux appareils dotés de plus de 100 qubits. Choisissez-en un sur lequel résoudre le problème du « max-cut » sur un graphe pondéré de 100 nœuds. Il s'agit d'un problème à « grande échelle ». Le processus suit les mêmes étapes que celles décrites ci-dessus, mais s'applique à un graphe beaucoup plus vaste.\n", "\n" ] }, { "cell_type": "markdown", "id": "large-scale-steps-intro", "metadata": {}, "source": [ "\n", "\n", "### Flux de travail de bout en bout à l'échelle industrielle\n", "\n", "Les quatre étapes sont présentées ci-dessous, appliquées au graphe de 100 nœuds. La structure est la même que celle de la démonstration à petite échelle : création de la carte, compilation, exécution, post-traitement — mais avec un problème plus complexe, réparti entre les quatre cellules ci-dessous pour plus de clarté.\n", "\n" ] }, { "cell_type": "code", "execution_count": null, "id": "large-scale-helpers", "metadata": {}, "outputs": [], "source": [ "# Precomputed parity lookup table: _PARITY[b] = +1 if popcount(b) is even, else -1.\n", "# We use this to vectorize expectation-value evaluation across all Pauli terms.\n", "_PARITY = np.array(\n", " [-1 if bin(i).count(\"1\") % 2 else 1 for i in range(256)],\n", " dtype=np.complex128,\n", ")\n", "\n", "\n", "def evaluate_sparse_pauli(state: int, observable: SparsePauliOp) -> complex:\n", " \"\"\"Expectation value of a SparsePauliOp on a single computational-basis state.\n", "\n", " For a Z-only observable (which QAOA cost Hamiltonians are, after the\n", " QUBO-to-Hamiltonian mapping), the eigenvalue of each Pauli term on a\n", " computational-basis state is simply (-1)**popcount(z_mask AND state),\n", " i.e., the parity of the bitwise-AND of the term's Z-support and the\n", " measured bitstring.\n", "\n", " This routine packs the Z-support of every Pauli term into bytes, ANDs\n", " them against the measured state in a single vectorized op, and looks up\n", " the parity in _PARITY. For a 100-qubit / ~hundreds-of-terms Hamiltonian\n", " over 10_000 samples, this is dramatically faster than calling\n", " SparsePauliOp.expectation_value per sample.\n", " \"\"\"\n", " packed_uint8 = np.packbits(observable.paulis.z, axis=1, bitorder=\"little\")\n", " state_bytes = np.frombuffer(\n", " state.to_bytes(packed_uint8.shape[1], \"little\"), dtype=np.uint8\n", " )\n", " reduced = np.bitwise_xor.reduce(packed_uint8 & state_bytes, axis=1)\n", " return np.sum(observable.coeffs * _PARITY[reduced])\n", "\n", "\n", "def best_solution(samples, hamiltonian):\n", " \"\"\"Return the sampled bitstring (as int) with the lowest Hamiltonian cost.\"\"\"\n", " min_cost = float(\"inf\")\n", " min_sol = None\n", " for bit_str in samples.keys():\n", " candidate_sol = int(bit_str)\n", " fval = evaluate_sparse_pauli(candidate_sol, hamiltonian).real\n", " if fval <= min_cost:\n", " min_cost = fval\n", " min_sol = candidate_sol\n", " return min_sol\n", "\n", "\n", "def _plot_cdf(objective_values: dict, ax, color):\n", " x_vals = sorted(objective_values.keys(), reverse=True)\n", " y_vals = np.cumsum([objective_values[x] for x in x_vals])\n", " ax.plot(x_vals, y_vals, color=color)\n", "\n", "\n", "def plot_cdf(dist, ax, title):\n", " _plot_cdf(dist, ax, \"C1\")\n", " ax.vlines(min(list(dist.keys())), 0, 1, \"C1\", linestyle=\"--\")\n", " ax.set_title(title)\n", " ax.set_xlabel(\"Objective function value\")\n", " ax.set_ylabel(\"Cumulative distribution function\")\n", " ax.grid(alpha=0.3)\n", "\n", "\n", "def samples_to_objective_values(samples, hamiltonian):\n", " \"\"\"Convert the samples to values of the objective function.\"\"\"\n", " objective_values = defaultdict(float)\n", " for bit_str, prob in samples.items():\n", " candidate_sol = int(bit_str)\n", " fval = evaluate_sparse_pauli(candidate_sol, hamiltonian).real\n", " objective_values[fval] += prob\n", " return objective_values" ] }, { "cell_type": "markdown", "id": "4dc0c8ff", "metadata": {}, "source": [ "**Étape 1** : Construire le graphe, l'hamiltonien de coût et l'ansatz.\n", "\n" ] }, { "cell_type": "code", "execution_count": 19, "id": "94190344", "metadata": {}, "outputs": [], "source": [ "# Step 1: build the 100-node graph, cost Hamiltonian, and QAOA ansatz.\n", "n_large = 100\n", "graph_100 = rx.PyGraph()\n", "graph_100.add_nodes_from(np.arange(0, n_large, 1))\n", "elist = []\n", "for edge in backend.coupling_map:\n", " if edge[0] < n_large and edge[1] < n_large:\n", " elist.append((edge[0], edge[1], 1.0))\n", "graph_100.add_edges_from(elist)\n", "\n", "max_cut_paulis_100 = build_max_cut_paulis(graph_100)\n", "cost_hamiltonian_100 = SparsePauliOp.from_sparse_list(\n", " max_cut_paulis_100, n_large\n", ")\n", "\n", "circuit_100 = QAOAAnsatz(cost_operator=cost_hamiltonian_100, reps=1)\n", "circuit_100.measure_all()" ] }, { "cell_type": "markdown", "id": "c91f0c16", "metadata": {}, "source": [ "**Étape 2** : Transpiler pour le backend matériel sélectionné.\n", "\n" ] }, { "cell_type": "code", "execution_count": 20, "id": "2b59da0e", "metadata": {}, "outputs": [], "source": [ "# Step 2: transpile for hardware.\n", "pm = generate_preset_pass_manager(optimization_level=3, backend=backend)\n", "candidate_circuit_100 = pm.run(circuit_100)" ] }, { "cell_type": "markdown", "id": "eb2c4d66", "metadata": {}, "source": [ "**Étape 3** : Exécutez la boucle d'optimisation QAOA au sein d'une session, puis effectuez un échantillonnage.\n", "\n" ] }, { "cell_type": "code", "execution_count": 21, "id": "e5aceab3", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ " message: Return from COBYLA because the trust region radius reaches its lower bound.\n", " success: True\n", " status: 0\n", " fun: -17.172689238986344\n", " x: [ 2.574e+00 4.166e+00]\n", " nfev: 28\n", " maxcv: 0.0\n" ] } ], "source": [ "# Step 3: run the QAOA optimization loop on the device, then sample the\n", "# final distribution with the optimized parameters.\n", "initial_gamma = np.pi\n", "initial_beta = np.pi / 2\n", "init_params = [initial_beta, initial_gamma]\n", "\n", "objective_func_vals = [] # Global variable\n", "with Session(backend=backend) as session:\n", " estimator = Estimator(mode=session)\n", " estimator.options.default_shots = 1000\n", "\n", " # Set simple error suppression/mitigation options\n", " estimator.options.dynamical_decoupling.enable = True\n", " estimator.options.dynamical_decoupling.sequence_type = \"XY4\"\n", " estimator.options.twirling.enable_gates = True\n", " estimator.options.twirling.num_randomizations = \"auto\"\n", " estimator.options.environment.job_tags = [\"TUT_QAOA\"]\n", "\n", " result = minimize(\n", " cost_func_estimator,\n", " init_params,\n", " args=(candidate_circuit_100, cost_hamiltonian_100, estimator),\n", " method=\"COBYLA\",\n", " )\n", " print(result)\n", "\n", "# Assign optimal parameters and sample the final distribution.\n", "optimized_circuit_100 = candidate_circuit_100.assign_parameters(result.x)\n", "\n", "sampler = Sampler(mode=backend)\n", "sampler.options.default_shots = 10000\n", "\n", "# Set simple error suppression/mitigation options\n", "sampler.options.dynamical_decoupling.enable = True\n", "sampler.options.dynamical_decoupling.sequence_type = \"XY4\"\n", "sampler.options.twirling.enable_gates = True\n", "sampler.options.twirling.num_randomizations = \"auto\"\n", "\n", "# Add a unique tag to the job execution\n", "sampler.options.environment.job_tags = [\"TUT_QAOA\"]\n", "\n", "pub = (optimized_circuit_100,)\n", "job = sampler.run([pub], shots=int(1e4))\n", "\n", "counts_int = job.result()[0].data.meas.get_int_counts()\n", "shots = sum(counts_int.values())\n", "final_distribution_100_int = {\n", " key: val / shots for key, val in counts_int.items()\n", "}" ] }, { "cell_type": "markdown", "id": "7f0c5980", "metadata": {}, "source": [ "**Étape 4** : Traiter la distribution échantillonnée afin d'en extraire la meilleure coupure.\n", "\n" ] }, { "cell_type": "code", "execution_count": 22, "id": "010571f7", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Result bitstring: [1, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1, 1, 0, 0, 1, 0, 0, 1, 1, 0, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 0, 0, 0, 0, 1, 1, 0, 1, 0, 0, 0, 1, 0, 0, 1, 0, 1, 0, 0, 1, 1, 1, 1, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1, 1, 1, 0, 1, 0, 1, 0, 1, 1, 1, 0, 1, 1, 1, 0]\n", "The value of the cut is: 156\n" ] } ], "source": [ "# Step 4: find the best-cost sample and evaluate its cut value.\n", "best_sol_100 = best_solution(final_distribution_100_int, cost_hamiltonian_100)\n", "best_sol_bitstring_100 = to_bitstring(int(best_sol_100), len(graph_100))\n", "best_sol_bitstring_100.reverse()\n", "\n", "print(\"Result bitstring:\", best_sol_bitstring_100)\n", "\n", "cut_value_100 = evaluate_sample(best_sol_bitstring_100, graph_100)\n", "print(\"The value of the cut is:\", cut_value_100)" ] }, { "cell_type": "markdown", "id": "large-scale-convergence-md", "metadata": {}, "source": [ "Vérifiez que le coût minimisé dans la boucle d'optimisation a convergé, puis visualisez les résultats.\n", "\n" ] }, { "cell_type": "code", "execution_count": 23, "id": "large-scale-viz", "metadata": {}, "outputs": [ { "data": { "text/plain": [ "\"Output" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/plain": [ "\"Output" ] }, "metadata": {}, "output_type": "display_data" }, { "data": { "text/plain": [ "\"Output" ] }, "metadata": {}, "output_type": "display_data" } ], "source": [ "# Plot convergence\n", "plt.figure(figsize=(12, 6))\n", "plt.plot(objective_func_vals)\n", "plt.xlabel(\"Iteration\")\n", "plt.ylabel(\"Cost\")\n", "plt.show()\n", "\n", "# Visualize the cut\n", "plot_result(graph_100, best_sol_bitstring_100)\n", "\n", "# Plot cumulative distribution function\n", "result_dist = samples_to_objective_values(\n", " final_distribution_100_int, cost_hamiltonian_100\n", ")\n", "fig, ax = plt.subplots(1, 1, figsize=(8, 6))\n", "plot_cdf(result_dist, ax, backend.name)" ] }, { "cell_type": "markdown", "id": "69ebc85b-6a29-4671-8d16-1ac97f089607", "metadata": {}, "source": [ "\n", "\n", "## Etapes suivantes\n", "\n", "Si ce travail vous a paru intéressant, les ressources suivantes pourraient vous intéresser :\n", "\n", "\n", " * [Techniques avancées pour le QAOA](/docs/tutorials/advanced-techniques-for-qaoa) — exploration de stratégies avancées visant à améliorer les performances du QAOA\n", " * [Défi d'optimisation multi-objectifs](https://github.com/qiskit-community/qdc-challenges-2025/blob/main/challenges/Track_B/qmoo/qmoo_qdc25.ipynb) — mettez vos compétences à l'épreuve avec ce défi communautaire consacré à l'optimisation quantique multi-objectifs\n", " * [Documentation](/docs/guides/transpile) sur la transpilation pour l'optimisation fine des circuits\n", " * [Suppression et atténuation des erreurs](/docs/guides/error-mitigation-and-suppression-techniques) pour améliorer les résultats matériels\n", "\n", "\n" ] }, { "cell_type": "markdown", "metadata": {}, "id": "a1b8767d", "source": "© IBM Corp., 2017-2026" } ], "metadata": { "kernelspec": { "display_name": "Python 3", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3" }, "hours": 1, "qpuSeconds": 1320 }, "nbformat": 4, "nbformat_minor": 5 }