{
  "cells": [
    {
      "cell_type": "markdown",
      "id": "1a869c2d-ae51-47d3-8a41-bfcf5e505f59",
      "metadata": {},
      "source": [
        "---\n",
        "title: \"Techniques avancées pour le QAOA\"\n",
        "description: \"Ce cahier présente des techniques avancées visant à améliorer les performances de l'algorithme d'optimisation approximative quantique (QAOA) avec un grand nombre de qubits.\"\n",
        "---\n",
        "\n",
        "{/* cspell:ignore pysat, lbrack, frameon, IEICE  */}\n",
        "\n",
        "<span id=\"advanced-techniques-for-qaoa\" />\n",
        "\n",
        "# Techniques avancées pour le QAOA\n",
        "\n",
        "*Estimation de l'utilisation : 3 minutes sur un processeur r2 Heron (REMARQUE : il s'agit uniquement d'une estimation. Votre durée d'exécution peut varier.)*\n",
        "\n"
      ]
    },
    {
      "cell_type": "markdown",
      "id": "1a6bbeef-966f-45e1-89aa-e964ef891eeb",
      "metadata": {},
      "source": [
        "<span id=\"prerequisites\" />\n",
        "\n",
        "## Prérequis\n",
        "\n",
        "Les utilisateurs doivent connaître les principes fondamentaux de l'algorithme d'optimisation quantique approximative (QAOA). Consultez les ressources suivantes pour une introduction au QAOA :\n",
        "\n",
        "* Tutoriel sur [la résolution de problèmes d'optimisation quantique à grande échelle](/docs/tutorials/quantum-approximate-optimization-algorithm)\n",
        "* Le cours « [QAOA à l'échelle industrielle](/learning/courses/quantum-computing-in-practice/utility-scale-qaoa#utility-scale-qaoa) » (qui fait partie du cours «[ L'informatique quantique en pratique](/learning/courses/quantum-computing-in-practice) ») sur IBM Quantum® Learning\n",
        "\n",
        "<span id=\"learning-outcomes\" />\n",
        "\n",
        "## Résultats d'apprentissage\n",
        "\n",
        "À l'issue de ce tutoriel, les utilisateurs devraient être en mesure de :\n",
        "\n",
        "* Utiliser des techniques avancées qui contribuent à améliorer la compilation de QAOA et permettent d'optimiser ses performances\n",
        "\n",
        "Pour un guide détaillé du contenu de ce tutoriel, consultez cette [vidéo Qiskit](https://youtu.be/rBfK-l-qSNk?si=PC28gFAdu4JYSYdk).\n",
        "\n"
      ]
    },
    {
      "cell_type": "markdown",
      "id": "ea97567d-810f-4cca-8edf-a47d70ea870a",
      "metadata": {},
      "source": [
        "<span id=\"background\" />\n",
        "\n",
        "## Arrière-plan\n",
        "\n",
        "Ce tutoriel présente deux techniques avancées permettant d'améliorer les performances de **l** 'algorithme d'optimisation quantique approximative (QAOA) lorsqu'il est appliqué à un grand nombre de qubits.\n",
        "\n",
        "Les techniques avancées présentées dans ce cahier comprennent\n",
        "\n",
        "* **Stratégie SWAP avec mappage initial SAT** : il s'agit d'un passage de transcompilateur spécialement conçu pour le QAOA, qui combine une stratégie SWAP et un solveur SAT afin d'optimiser la sélection des qubits physiques à utiliser sur le QPU. La stratégie SWAP exploite la commutativité des opérateurs QAOA pour réorganiser les portes de manière à ce que des couches de portes SWAP puissent être exécutées simultanément, réduisant ainsi la profondeur du circuit [\\[1\\]](#references). Le solveur SAT sert à trouver une correspondance initiale qui minimise le nombre d'opérations SWAP nécessaires pour mettre en correspondance les qubits du circuit avec les qubits physiques du dispositif [\\[2\\]](#references).\n",
        "* **CVaR fonction de coût** : En général, on utilise la valeur attendue de l'hamiltonien de coût comme fonction de coût pour le QAOA, mais comme l'a montré [\\[3\\]](#references), le fait de se concentrer sur la queue de la distribution plutôt que sur la valeur attendue peut améliorer les performances du QAOA pour les problèmes d'optimisation combinatoire. C'est ce que permet l' CVaR. Pour un ensemble donné de tirages associés à des valeurs objectives du problème d'optimisation considéré, la valeur à risque conditionnelle ( CVaR ) avec un niveau de confiance de $\\alpha \\in [0, 1]$ est définie comme la moyenne des meilleurs tirages $\\alpha$ [\\[3\\]](#references).\n",
        "  Ainsi, $\\alpha = 1$ correspond à la valeur attendue standard, tandis que $\\alpha=0$ correspond à la valeur minimale parmi les prises de vue fournies, et $\\alpha \\in (0, 1)$ représente un compromis entre la recherche des meilleures prises de vue et l'application d'un lissage par moyennage afin d'uniformiser le paysage d'optimisation. De plus, l' CVaR e peut être utilisé comme technique d'atténuation des erreurs afin d'améliorer la qualité de l'estimation de la valeur objective [\\[4\\]](#references).\n",
        "\n",
        "À la fin de ce tutoriel, vous devriez être en mesure d'utiliser ces techniques pour obtenir les meilleurs résultats possibles en exécutant QAOA pour vos problèmes d'optimisation.\n",
        "\n"
      ]
    },
    {
      "cell_type": "markdown",
      "id": "40fb546e-85e0-450b-a5ea-5d08950d129f",
      "metadata": {},
      "source": [
        "<span id=\"requirements\" />\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 plus tard, avec prise en charge de [la visualisation](/docs/api/qiskit/visualization)\n",
        "* v0.43Qiskit Runtime ou plus tard (`pip install qiskit-ibm-runtime`)\n",
        "* Bibliothèque graphique Rustworkx (`pip install rustworkx`)\n",
        "* Python SAT (`pip install python-sat`)\n",
        "\n"
      ]
    },
    {
      "cell_type": "markdown",
      "id": "50285e5f-1a7b-471c-a223-1ae0af19d9ed",
      "metadata": {},
      "source": [
        "<span id=\"setup\" />\n",
        "\n",
        "## Configuration\n",
        "\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 91,
      "id": "d019ea68-61e0-4341-84c7-e612ca10dde7",
      "metadata": {},
      "outputs": [],
      "source": [
        "from __future__ import annotations\n",
        "\n",
        "import numpy as np\n",
        "import rustworkx as rx\n",
        "from dataclasses import dataclass\n",
        "from itertools import combinations\n",
        "from threading import Timer\n",
        "from collections.abc import Callable, Iterable\n",
        "from pysat.formula import CNF, IDPool\n",
        "from pysat.solvers import Solver\n",
        "from scipy.optimize import minimize\n",
        "from rustworkx.visualization import mpl_draw as draw_graph\n",
        "\n",
        "from qiskit.quantum_info import SparsePauliOp\n",
        "from qiskit.circuit.library import QAOAAnsatz\n",
        "from qiskit.circuit import QuantumCircuit, ParameterVector\n",
        "from qiskit.transpiler import CouplingMap, PassManager\n",
        "from qiskit.transpiler.preset_passmanagers import generate_preset_pass_manager\n",
        "from qiskit.transpiler.passes.routing.commuting_2q_gate_routing import (\n",
        "    SwapStrategy,\n",
        "    FindCommutingPauliEvolutions,\n",
        "    Commuting2qGateRouter,\n",
        ")\n",
        "\n",
        "from qiskit_ibm_runtime import QiskitRuntimeService, Session\n",
        "from qiskit_ibm_runtime import SamplerV2 as Sampler"
      ]
    },
    {
      "cell_type": "markdown",
      "id": "8b77b0c9-f5a6-476e-86b8-069ba14f9ab3",
      "metadata": {},
      "source": [
        "<span id=\"max-cut-problem\" />\n",
        "\n",
        "### Problème de coupe maximale\n",
        "\n",
        "Imaginons que nous cherchions à résoudre le problème **du coup maximal** sur un graphe de 100 nœuds à l'aide de l'algorithme QAOA.\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",
        "Dans cet exemple, nous utilisons un graphe de 100 nœuds basé sur une carte de couplage matériel.\n",
        "\n"
      ]
    },
    {
      "cell_type": "markdown",
      "id": "663d13f5-a5f7-4b67-a89b-26deb41224ec",
      "metadata": {},
      "source": [
        "<span id=\"small-scale-simulator-example\" />\n",
        "\n",
        "## Exemple de simulateur à petite échelle\n",
        "\n",
        "Étant donné que l'objectif de ce tutoriel est de montrer comment QAOA fonctionne à des échelles qui dépassent les capacités d'un simulateur, nous allons passer cette étape.\n",
        "\n",
        "Si vous souhaitez tester un workflow QAOA basé sur un simulateur, consultez le tutoriel consacré à [l'algorithme d'optimisation approximative quantique](/docs/tutorials/quantum-approximate-optimization-algorithm).\n",
        "\n"
      ]
    },
    {
      "cell_type": "markdown",
      "id": "6ca05a7c-5fde-4485-a3ad-c0ba02844e50",
      "metadata": {},
      "source": [
        "<span id=\"large-scale-hardware-example\" />\n",
        "\n",
        "## Exemple de matériel à grande échelle\n",
        "\n"
      ]
    },
    {
      "cell_type": "markdown",
      "id": "b825afbf-10fd-4926-bd65-05272044f107",
      "metadata": {},
      "source": [
        "<span id=\"step-1-map-classical-inputs-to-a-quantum-problem\" />\n",
        "\n",
        "### Étape 1 : Mettre en correspondance les entrées classiques avec un problème quantique\n",
        "\n",
        "<span id=\"graph-→-hamiltonian\" />\n",
        "\n",
        "#### Graphique → Hamiltonien\n",
        "\n",
        "Tout d'abord, transposez le problème en un circuit quantique adapté à l'approche QAOA. Vous trouverez plus de détails sur ce processus dans le [tutoriel d'introduction à QAOA](/docs/tutorials/quantum-approximate-optimization-algorithm).\n",
        "\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "id": "8c25db38-5f36-4a39-bdde-4f83616a6dde",
      "metadata": {},
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "<IBMBackend('ibm_fez')>\n"
          ]
        }
      ],
      "source": [
        "# Instantiate runtime to access backend\n",
        "service = QiskitRuntimeService()\n",
        "backend = service.least_busy(\n",
        "    min_num_qubits=100, operational=True, simulator=False\n",
        ")\n",
        "print(backend)"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "id": "e04ce982-8294-4ebe-8dcc-f74205938800",
      "metadata": {},
      "outputs": [
        {
          "data": {
            "text/plain": [
              "True"
            ]
          },
          "execution_count": 96,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "# Check if the coupling map is symmetric. We will add a conditional below\n",
        "# to avoid over-counting edges for symmetric/bi-directional coupling maps.\n",
        "\n",
        "backend.coupling_map.is_symmetric"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "id": "8b864d32-9483-45ea-831f-60488e330adb",
      "metadata": {},
      "outputs": [
        {
          "data": {
            "text/plain": [
              "<Image src=\"/docs/images/tutorials/advanced-techniques-for-qaoa/extracted-outputs/8b864d32-9483-45ea-831f-60488e330adb-0.avif\" alt=\"Output of the previous code cell\" />"
            ]
          },
          "metadata": {},
          "output_type": "display_data"
        }
      ],
      "source": [
        "n = 100\n",
        "graph_100 = rx.PyGraph()\n",
        "graph_100.add_nodes_from((np.arange(0, n, 1)))\n",
        "w = 1.0\n",
        "elist = []\n",
        "\n",
        "for edge in backend.coupling_map:\n",
        "    if (edge[0] < n) and (edge[1] < n):\n",
        "        # Conditional to avoid over-counting edges\n",
        "        if (\n",
        "            edge[1],\n",
        "            edge[0],\n",
        "            w,\n",
        "        ) not in elist:\n",
        "            elist.append((edge[0], edge[1], w))\n",
        "\n",
        "graph_100.add_edges_from(elist)\n",
        "draw_graph(graph_100, with_labels=True)"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 98,
      "id": "e39c4e42-ce97-4a04-8879-da4d33a684bc",
      "metadata": {},
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "Cost Function Hamiltonian: SparsePauliOp(['IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZ', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZI', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZIIIIIIIIIIIIZIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZIIIIIIIIIZIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZIIIIIIZIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZIIIZIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZIIIIIIZIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZIIIIIIIIIZIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZIIIIIIIIIIIIZIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZIIIIIIIIIIIIIIIZIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZIIIIIIIIIIIIIIZIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZIIIIIIIIIIIZIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZIIIIIIIIZIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZIIIIIZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZIIIIZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZIIIIIIIZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZIIIIIIIIIIZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZIIIIIIIIIIIIIZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZIIIIIIIIIIIIZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZIIIIIIIIIZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZIIIIIIZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZIIIZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZIIIIIIZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZIIIIIIIIIZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIZIIIIIIIIIIIIZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIZIIIIIIIIIIIIIIIZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIZIIIIIIIIIIIIIIZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIZIIIIIIIIIIIZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIZIIIIIIIIZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIZIIIIIZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIZIIIIZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIZIIIIIIIZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIZIIIIIIIIIIZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIZIIIIIIIIIIIIIZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIZIIIIIIIIIIIIZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIZIIIIIIIIIZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IZIIIIIIZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'ZIIIZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII'],\n",
            "              coeffs=[1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j,\n",
            " 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j,\n",
            " 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j,\n",
            " 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j,\n",
            " 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j,\n",
            " 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j,\n",
            " 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j,\n",
            " 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j,\n",
            " 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j,\n",
            " 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j,\n",
            " 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j,\n",
            " 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j,\n",
            " 1.+0.j, 1.+0.j, 1.+0.j])\n"
          ]
        }
      ],
      "source": [
        "# Construct cost hamiltonian\n",
        "\n",
        "\n",
        "def build_max_cut_paulis(graph: rx.PyGraph) -> list[tuple[str, float]]:\n",
        "    \"\"\"Convert the graph to Pauli list.\n",
        "\n",
        "    This function does the inverse of `build_max_cut_graph`\n",
        "    \"\"\"\n",
        "    pauli_list = []\n",
        "    for edge in list(graph.edge_list()):\n",
        "        paulis = [\"I\"] * len(graph)\n",
        "        paulis[edge[0]], paulis[edge[1]] = \"Z\", \"Z\"\n",
        "\n",
        "        weight = graph.get_edge_data(edge[0], edge[1])\n",
        "\n",
        "        pauli_list.append((\"\".join(paulis)[::-1], weight))\n",
        "\n",
        "    return pauli_list\n",
        "\n",
        "\n",
        "max_cut_paulis = build_max_cut_paulis(graph_100)\n",
        "\n",
        "cost_hamiltonian = SparsePauliOp.from_list(max_cut_paulis)\n",
        "print(\"Cost Function Hamiltonian:\", cost_hamiltonian)"
      ]
    },
    {
      "cell_type": "markdown",
      "id": "4e576068-53e7-4a06-a83b-87e95de141e9",
      "metadata": {},
      "source": [
        "<span id=\"step-2-optimize-problem-for-quantum-hardware-execution\" />\n",
        "\n",
        "### Étape 2 : Optimiser le problème pour l'exécution sur du matériel quantique\n",
        "\n",
        "<span id=\"swap-strategy-with-the-sat-initial-mapping\" />\n",
        "\n",
        "#### Stratégie SWAP avec cartographie initiale SAT\n",
        "\n",
        "Nous démontrerons comment construire et optimiser des circuits QAOA en utilisant **la stratégie SWAP avec SAT initial mapping**, une passe de transpilation spécialement conçue pour le QAOA appliqué aux problèmes quadratiques.\n",
        "\n",
        "Dans cet exemple, nous choisissons une stratégie d'insertion SWAP pour les blocs de portes à deux qubits commutatives, qui applique des couches de portes SWAP pouvant être exécutées simultanément sur la carte de couplage. Cette stratégie est présentée dans [\\[1\\]](#references) et est transmise à `Commuting2qGateRouter`, qui est exposée comme un passage de transcompilateur Qiskit standardisé (voir [`Commuting2qGateRouter`](/docs/api/qiskit/qiskit.transpiler.passes.Commuting2qGateRouter)). Dans cet exemple, nous utilisons une stratégie de permutation de lignes.\n",
        "\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 99,
      "id": "7c54402a-7696-4b0e-826a-6e0ac4c54395",
      "metadata": {},
      "outputs": [],
      "source": [
        "# Extract longest path with no repeated nodes\n",
        "nodes = rx.longest_simple_path(graph_100)\n",
        "\n",
        "# Collect even edges and odd edges\n",
        "even_edges = [\n",
        "    (nodes[i], nodes[i + 1])\n",
        "    if nodes[i] < nodes[i + 1]\n",
        "    else (nodes[i + 1], nodes[i])\n",
        "    for i in range(0, len(nodes) - 1, 2)\n",
        "]\n",
        "odd_edges = [\n",
        "    (nodes[i], nodes[i + 1])\n",
        "    if nodes[i] < nodes[i + 1]\n",
        "    else (nodes[i + 1], nodes[i])\n",
        "    for i in range(1, len(nodes) - 1, 2)\n",
        "]\n",
        "edge_list = [\n",
        "    (edge[0], edge[1]) if edge[0] < edge[1] else (edge[1], edge[0])\n",
        "    for edge in graph_100.edge_list()\n",
        "]\n",
        "\n",
        "swap_strategy = SwapStrategy(CouplingMap(edge_list), (even_edges, odd_edges))"
      ]
    },
    {
      "cell_type": "markdown",
      "id": "ba53fd1d-0d68-43e3-9102-4c6e64f04de7",
      "metadata": {},
      "source": [
        "<span id=\"remap-the-graph-using-a-sat-mapper\" />\n",
        "\n",
        "#### Remapper le graphe à l'aide d'un mappeur SAT\n",
        "\n",
        "Même lorsqu'un circuit est constitué de portes de commutation (c'est le cas du circuit QAOA, mais aussi des simulations de type Trotter des hamiltoniens d'Ising), trouver un bon mappage initial reste une tâche difficile. En utilisant l'approche basée sur le SAT présentée dans [\\[2\\]](#references), nous pouvons déterminer des mappages initiaux efficaces pour les circuits comportant des portes commutatives, ce qui permet de réduire considérablement le nombre de couches SWAP nécessaires. Il a été démontré que cette approche pouvait s'étendre jusqu'à *500 qubits*, comme l'illustre l'article.\n",
        "\n",
        "Le code suivant montre comment utiliser le site `SATMapper` de Matsuo et al. pour remapper le graphique. Ce processus permet de cartographier le problème dans un état initial plus optimal pour une stratégie SWAP donnée, ce qui entraîne une réduction significative du nombre de couches SWAP nécessaires à l'exécution du circuit.\n",
        "\n",
        "Dans `SATMapper`, le problème de la recherche d'une bonne cartographie initiale est formulé comme un problème SAT. Un solveur SAT est utilisé pour trouver une telle cartographie initiale pour le circuit QAOA. `python-sat` (`pysat` en abrégé) est une bibliothèque Python pour un solveur SAT, et nous l'utiliserons pour résoudre le problème SAT dans cet exemple.\n",
        "\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "id": "df9d861a-64e8-49ee-aed1-c41f437fa743",
      "metadata": {},
      "outputs": [],
      "source": [
        "\"\"\"A class to solve the SWAP gate insertion initial mapping problem\n",
        "using the SAT approach from https://arxiv.org/abs/2212.05666.\n",
        "\"\"\"\n",
        "\n",
        "\n",
        "@dataclass\n",
        "class SATResult:\n",
        "    \"\"\"A data class to hold the result of a SAT solver.\"\"\"\n",
        "\n",
        "    satisfiable: bool  # Satisfiable is True if the SAT model could be solved\n",
        "    # in a given time.\n",
        "    solution: dict  # The solution to the SAT problem if it is satisfiable.\n",
        "    mapping: list  # The mapping of nodes in the pattern graph to nodes in the\n",
        "    # target graph.\n",
        "    elapsed_time: float  # The time it took to solve the SAT model.\n",
        "\n",
        "\n",
        "class SATMapper:\n",
        "    r\"\"\"A class to introduce a SAT-approach to solve\n",
        "    the initial mapping problem in SWAP gate insertion for commuting gates.\n",
        "\n",
        "    When this pass is run on a DAG it will look for the first instance of\n",
        "    :class:`.Commuting2qBlock` and use the program graph :math:`P` of this block\n",
        "    of gates to find a layout for a given swap strategy. This layout is found\n",
        "    with a binary search over the layers :math:`l` of the swap strategy. At each\n",
        "    considered layer a subgraph isomorphism problem formulated as a SAT is solved\n",
        "    by a SAT solver. Each instance is whether it is possible to embed the program\n",
        "    graph :math:`P` into the effective connectivity graph :math:`C_l` that is\n",
        "    achieved by applying :math:`l` layers of the swap strategy to the coupling map\n",
        "    :math:`C_0` of the backend. Since solving SAT problems can be hard, a\n",
        "    ``time_out`` fixes the maximum time allotted to the SAT solver for each\n",
        "    instance. If this time is exceeded the considered problem is deemed\n",
        "    unsatisfiable and the binary search proceeds to the next number of swap\n",
        "    layers :math:``l``.\n",
        "    \"\"\"\n",
        "\n",
        "    def __init__(self, timeout: int = 60):\n",
        "        \"\"\"Initialize the SATMapping.\n",
        "\n",
        "        Args:\n",
        "            timeout: The allowed time in seconds for each iteration of the SAT\n",
        "                solver. This variable defaults to 60 seconds.\n",
        "        \"\"\"\n",
        "        self.timeout = timeout\n",
        "\n",
        "    def find_initial_mappings(\n",
        "        self,\n",
        "        program_graph: rx.Graph,\n",
        "        swap_strategy: SwapStrategy,\n",
        "        min_layers: int | None = None,\n",
        "        max_layers: int | None = None,\n",
        "    ) -> dict[int, SATResult]:\n",
        "        r\"\"\"Find an initial mapping for a given swap strategy. Perform a\n",
        "        binary search over the number of swap layers, and for each number\n",
        "        of swap layers solve a subgraph isomorphism problem formulated as\n",
        "        a SAT problem.\n",
        "\n",
        "        Args:\n",
        "            program_graph (rx.Graph): The program graph with commuting gates, where\n",
        "                                        each edge represents a two-qubit gate.\n",
        "            swap_strategy (SwapStrategy): The swap strategy to use to find the\n",
        "                                        initial mapping.\n",
        "            min_layers (int): The minimum number of swap layers to consider.\n",
        "                                        Defaults to the maximum degree of the\n",
        "                                        program graph - 2.\n",
        "            max_layers (int): The maximum number of swap layers to consider.\n",
        "                                        Defaults to the number of qubits in the\n",
        "                                        swap strategy - 2.\n",
        "\n",
        "        Returns:\n",
        "            dict[int, SATResult]: A dictionary containing the results of the SAT\n",
        "                                    solver for each number of swap layers.\n",
        "        \"\"\"\n",
        "        num_nodes_g1 = len(program_graph.nodes())\n",
        "        num_nodes_g2 = swap_strategy.distance_matrix.shape[0]\n",
        "        if num_nodes_g1 > num_nodes_g2:\n",
        "            return SATResult(False, [], [], 0)\n",
        "        if min_layers is None:\n",
        "            # use the maximum degree of the program graph - 2\n",
        "            # as the lower bound.\n",
        "            min_layers = max((d for _, d in program_graph.degree)) - 2\n",
        "        if max_layers is None:\n",
        "            max_layers = num_nodes_g2 - 1\n",
        "\n",
        "        variable_pool = IDPool(start_from=1)\n",
        "        variables = np.array(\n",
        "            [\n",
        "                [variable_pool.id(f\"v_{i}_{j}\") for j in range(num_nodes_g2)]\n",
        "                for i in range(num_nodes_g1)\n",
        "            ],\n",
        "            dtype=int,\n",
        "        )\n",
        "        vid2mapping = {v: idx for idx, v in np.ndenumerate(variables)}\n",
        "        binary_search_results = {}\n",
        "\n",
        "        def interrupt(solver):\n",
        "            # This function is called to interrupt the solver when the\n",
        "            # timeout is reached.\n",
        "            solver.interrupt()\n",
        "\n",
        "        # Make a cnf (conjunctive normal form) for the one-to-one\n",
        "        # mapping constraint\n",
        "        cnf1 = []\n",
        "        for i in range(num_nodes_g1):\n",
        "            clause = variables[i, :].tolist()\n",
        "            cnf1.append(clause)\n",
        "            for k, m in combinations(clause, 2):\n",
        "                cnf1.append([-1 * k, -1 * m])\n",
        "        for j in range(num_nodes_g2):\n",
        "            clause = variables[:, j].tolist()\n",
        "            for k, m in combinations(clause, 2):\n",
        "                cnf1.append([-1 * k, -1 * m])\n",
        "\n",
        "        # Perform a binary search over the number of swap layers to find the\n",
        "        # minimum number of swap layers that satisfies the subgraph isomorphism\n",
        "        # problem.\n",
        "        while min_layers < max_layers:\n",
        "            num_layers = (min_layers + max_layers) // 2\n",
        "\n",
        "            # Create the connectivity matrix. Note that if the swap strategy\n",
        "            # cannot reach full connectivity then its distance matrix will have\n",
        "            # entries with -1. These entries must be treated as False.\n",
        "            d_matrix = swap_strategy.distance_matrix\n",
        "            connectivity_matrix = (\n",
        "                (-1 < d_matrix) & (d_matrix <= num_layers)\n",
        "            ).astype(int)\n",
        "            # Make a cnf for the adjacency constraint\n",
        "            cnf2 = []\n",
        "            for e_0, e_1 in list(program_graph.edge_list()):\n",
        "                clause_matrix = np.multiply(\n",
        "                    connectivity_matrix, variables[e_1, :]\n",
        "                )\n",
        "                clause = np.concatenate(\n",
        "                    (\n",
        "                        [[-variables[e_0, i]] for i in range(num_nodes_g2)],\n",
        "                        clause_matrix,\n",
        "                    ),\n",
        "                    axis=1,\n",
        "                )\n",
        "                # Remove 0s from each clause\n",
        "                cnf2.extend([c[c != 0].tolist() for c in clause])\n",
        "\n",
        "            cnf = CNF(from_clauses=cnf1 + cnf2)\n",
        "\n",
        "            with Solver(bootstrap_with=cnf, use_timer=True) as solver:\n",
        "                # Solve the SAT problem with a timeout.\n",
        "                # Timer is used to interrupt the solver when the\n",
        "                # timeout is reached.\n",
        "                timer = Timer(self.timeout, interrupt, [solver])\n",
        "                timer.start()\n",
        "                status = solver.solve_limited(expect_interrupt=True)\n",
        "                timer.cancel()\n",
        "                # Get the solution and the elapsed time.\n",
        "                sol = solver.get_model()\n",
        "                e_time = solver.time()\n",
        "\n",
        "                print(\n",
        "                    f\"Layers: {num_layers}, Status: {status}, Time: {e_time}\"\n",
        "                )\n",
        "                if status:\n",
        "                    # If the SAT problem is satisfiable, convert the solution\n",
        "                    # to a mapping.\n",
        "                    mapping = [vid2mapping[idx] for idx in sol if idx > 0]\n",
        "                    binary_search_results[num_layers] = SATResult(\n",
        "                        status, sol, mapping, e_time\n",
        "                    )\n",
        "                    max_layers = num_layers\n",
        "                else:\n",
        "                    # If the SAT problem is unsatisfiable, return the last\n",
        "                    # satisfiable solution.\n",
        "                    binary_search_results[num_layers] = SATResult(\n",
        "                        status, sol, [], e_time\n",
        "                    )\n",
        "                    min_layers = num_layers + 1\n",
        "\n",
        "        return binary_search_results\n",
        "\n",
        "    def remap_graph_with_sat(\n",
        "        self, graph: rx.Graph, swap_strategy, max_layers\n",
        "    ):\n",
        "        \"\"\"Applies the SAT mapping.\n",
        "\n",
        "        Args:\n",
        "            graph (nx.Graph): The graph to remap.\n",
        "            swap_strategy (SwapStrategy): The swap strategy to use\n",
        "                                            to find the initial mapping.\n",
        "\n",
        "        Returns:\n",
        "            tuple: A tuple containing the remapped graph, the edge map, and the\n",
        "            number of layers of the swap strategy that was used to find the\n",
        "            initial mapping. If no solution is found then the tuple contains\n",
        "            None for each element. Note the returned edge map `{k: v}` means that\n",
        "            node `k` in the original graph gets mapped to node `v` in the\n",
        "            Pauli strings.\n",
        "        \"\"\"\n",
        "        num_nodes = len(graph.nodes())\n",
        "        results = self.find_initial_mappings(\n",
        "            graph, swap_strategy, 0, max_layers\n",
        "        )\n",
        "        solutions = [k for k, v in results.items() if v.satisfiable]\n",
        "\n",
        "        if len(solutions):\n",
        "            min_k = min(solutions)\n",
        "            edge_map = dict(results[min_k].mapping)\n",
        "            # Create the remapped graph\n",
        "            remapped_graph = rx.PyGraph()\n",
        "            remapped_graph.add_nodes_from(range(num_nodes))\n",
        "            mapping = dict(results[min_k].mapping)\n",
        "            for i, graph_edge in enumerate(list(graph.edge_list())):\n",
        "                remapped_edge = tuple(mapping[node] for node in graph_edge)\n",
        "                remapped_graph.add_edge(*remapped_edge, graph.edges()[i])\n",
        "            return remapped_graph, edge_map, min_k\n",
        "        else:\n",
        "            return None, None, None"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 101,
      "id": "e689e09e-6ca7-4154-8602-d1d954ebe80b",
      "metadata": {},
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "Layers: 0, Status: True, Time: 0.022812999999999306\n",
            "Map from old to new nodes:  {0: 0, 1: 1, 2: 2, 3: 3, 4: 4, 5: 5, 6: 6, 7: 7, 8: 8, 9: 9, 10: 10, 11: 11, 12: 12, 13: 13, 14: 14, 15: 15, 16: 16, 17: 17, 18: 18, 19: 19, 20: 20, 21: 21, 22: 22, 23: 23, 24: 24, 25: 25, 26: 26, 27: 27, 28: 28, 29: 29, 30: 30, 31: 31, 32: 32, 33: 33, 34: 34, 35: 35, 36: 36, 37: 37, 38: 38, 39: 39, 40: 40, 41: 41, 42: 42, 43: 43, 44: 44, 45: 45, 46: 46, 47: 47, 48: 48, 49: 49, 50: 50, 51: 51, 52: 52, 53: 53, 54: 54, 55: 55, 56: 56, 57: 57, 58: 58, 59: 59, 60: 60, 61: 61, 62: 62, 63: 63, 64: 64, 65: 65, 66: 66, 67: 67, 68: 68, 69: 69, 70: 70, 71: 71, 72: 72, 73: 73, 74: 74, 75: 75, 76: 76, 77: 77, 78: 78, 79: 79, 80: 80, 81: 81, 82: 82, 83: 83, 84: 84, 85: 85, 86: 86, 87: 87, 88: 88, 89: 89, 90: 90, 91: 91, 92: 92, 93: 93, 94: 94, 95: 95, 96: 96, 97: 97, 98: 98, 99: 99}\n",
            "Min SWAP layers: 0\n"
          ]
        },
        {
          "data": {
            "text/plain": [
              "<Image src=\"/docs/images/tutorials/advanced-techniques-for-qaoa/extracted-outputs/e689e09e-6ca7-4154-8602-d1d954ebe80b-1.avif\" alt=\"Output of the previous code cell\" />"
            ]
          },
          "metadata": {},
          "output_type": "display_data"
        }
      ],
      "source": [
        "sm = SATMapper(timeout=10)\n",
        "remapped_graph, edge_map, min_swap_layers = sm.remap_graph_with_sat(\n",
        "    graph=graph_100, swap_strategy=swap_strategy, max_layers=1\n",
        ")\n",
        "print(\"Map from old to new nodes: \", edge_map)\n",
        "print(\"Min SWAP layers:\", min_swap_layers)\n",
        "draw_graph(remapped_graph, node_size=200, with_labels=True, width=1)"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 102,
      "id": "ecf6e8c3-65c2-4430-8dd3-d67b8842045d",
      "metadata": {},
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "SparsePauliOp(['IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZ', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZI', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZIIIIIIIIIIIIZIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZIIIIIIIIIZIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZIIIIIIZIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZIIIZIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZIIIIIIZIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZIIIIIIIIIZIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZIIIIIIIIIIIIZIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZIIIIIIIIIIIIIIIZIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZIIIIIIIIIIIIIIZIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZIIIIIIIIIIIZIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZIIIIIIIIZIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZIIIIIZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZIIIIZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZIIIIIIIZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZIIIIIIIIIIZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZIIIIIIIIIIIIIZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZIIIIIIIIIIIIZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZIIIIIIIIIZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZIIIIIIZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZIIIZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZIIIIIIZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZIIIIIIIIIZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIZIIIIIIIIIIIIZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIZIIIIIIIIIIIIIIIZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIZIIIIIIIIIIIIIIZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIZIIIIIIIIIIIZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIZIIIIIIIIZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIZIIIIIZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIZIIIIZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIZIIIIIIIZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIZIIIIIIIIIIZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIZIIIIIIIIIIIIIZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIZIIIIIIIIIIIIZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIZIIIIIIIIIZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IZIIIIIIZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'IIIIZZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII', 'ZIIIZIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIIII'],\n",
            "              coeffs=[1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j,\n",
            " 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j,\n",
            " 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j,\n",
            " 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j,\n",
            " 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j,\n",
            " 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j,\n",
            " 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j,\n",
            " 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j,\n",
            " 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j,\n",
            " 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j,\n",
            " 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j,\n",
            " 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j, 1.+0.j,\n",
            " 1.+0.j, 1.+0.j, 1.+0.j])\n"
          ]
        }
      ],
      "source": [
        "remapped_max_cut_paulis = build_max_cut_paulis(remapped_graph)\n",
        "# define a qiskit SparsePauliOp from the list of paulis\n",
        "remapped_cost_operator = SparsePauliOp.from_list(remapped_max_cut_paulis)\n",
        "print(remapped_cost_operator)"
      ]
    },
    {
      "cell_type": "markdown",
      "id": "5ae531be-80eb-4acd-b84a-7d466fd872e7",
      "metadata": {},
      "source": [
        "<span id=\"build-a-qaoa-circuit-with-the-swap-strategy-and-the-sat-mapping\" />\n",
        "\n",
        "#### Construire un circuit QAOA avec la stratégie SWAP et le mappage SAT\n",
        "\n",
        "Nous ne voulons appliquer les stratégies SWAP qu'à la couche de l'opérateur de coûts, et nous commençons donc par créer le bloc isolé que nous transformerons et ajouterons plus tard au circuit QAOA final.\n",
        "\n",
        "Pour cela, nous pouvons utiliser la [`QAOAAnsatz`](/docs/api/qiskit/qiskit.circuit.library.QAOAAnsatz) classe de Qiskit. Nous saisissons un circuit vide dans les `initial_state` champs et `mixer_operator` afin de nous assurer que nous construisons une couche d'opérateurs de coût isolée.\n",
        "Nous définissons également la `edge_coloring` correspondance de manière à ce que les portes RZZ soient placées à côté des portes SWAP. Cet emplacement stratégique nous permet de tirer parti des annulations de vols CX, ce qui optimise le circuit et améliore les performances.\n",
        "Ce processus est exécuté au sein de la `create_qaoa_swap_circuit` fonction.\n",
        "\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "id": "57d5eb53-9cda-4c38-a00b-26ed4b533bcd",
      "metadata": {},
      "outputs": [],
      "source": [
        "def make_meas_map(circuit: QuantumCircuit) -> dict:\n",
        "    \"\"\"Return a mapping from qubit index (the key) to classical bit (the value).\n",
        "\n",
        "    This allows us to account for the swapping order introduced by the\n",
        "    SWAP strategy.\n",
        "    \"\"\"\n",
        "    creg = circuit.cregs[0]\n",
        "    qreg = circuit.qregs[0]\n",
        "\n",
        "    meas_map = {}\n",
        "    for inst in circuit.data:\n",
        "        if inst.operation.name == \"measure\":\n",
        "            meas_map[qreg.index(inst.qubits[0])] = creg.index(inst.clbits[0])\n",
        "\n",
        "    return meas_map\n",
        "\n",
        "\n",
        "def apply_swap_strategy(\n",
        "    circuit: QuantumCircuit,\n",
        "    swap_strategy: SwapStrategy,\n",
        "    edge_coloring: dict[tuple[int, int], int] | None = None,\n",
        ") -> QuantumCircuit:\n",
        "    \"\"\"Transpile with a SWAP strategy.\n",
        "\n",
        "    Returns:\n",
        "        A quantum circuit transpiled with the given swap strategy.\n",
        "    \"\"\"\n",
        "\n",
        "    pm_pre = PassManager(\n",
        "        [\n",
        "            FindCommutingPauliEvolutions(),\n",
        "            Commuting2qGateRouter(\n",
        "                swap_strategy,\n",
        "                edge_coloring,\n",
        "            ),\n",
        "        ]\n",
        "    )\n",
        "    return pm_pre.run(circuit)\n",
        "\n",
        "\n",
        "def apply_qaoa_layers(\n",
        "    cost_layer: QuantumCircuit,\n",
        "    meas_map: dict,\n",
        "    num_layers: int,\n",
        "    gamma: list[float] | ParameterVector = None,\n",
        "    beta: list[float] | ParameterVector = None,\n",
        "    initial_state: QuantumCircuit = None,\n",
        "    mixer: QuantumCircuit = None,\n",
        "):\n",
        "    \"\"\"Applies QAOA layers to construct circuit.\n",
        "\n",
        "    First, the initial state is applied. If `initial_state` is None, we begin in\n",
        "    the initial superposition state. Next, we alternate between layers of the\n",
        "    cost operator and the mixer. The cost operator is alternatively applied in\n",
        "    order and in reverse instruction order. This allows us to apply the swap\n",
        "    strategy on odd `p` layers and undo the swap strategy on even `p` layers.\n",
        "    \"\"\"\n",
        "\n",
        "    num_qubits = cost_layer.num_qubits\n",
        "    new_circuit = QuantumCircuit(num_qubits, num_qubits)\n",
        "\n",
        "    if initial_state is not None:\n",
        "        new_circuit.append(initial_state, range(num_qubits))\n",
        "    else:\n",
        "        # all h state by default\n",
        "        new_circuit.h(range(num_qubits))\n",
        "\n",
        "    if gamma is None or beta is None:\n",
        "        gamma = ParameterVector(\"γ'\", num_layers)\n",
        "        if mixer is None or mixer.num_parameters == 0:\n",
        "            beta = ParameterVector(\"β'\", num_layers)\n",
        "        else:\n",
        "            beta = ParameterVector(\"β'\", num_layers * mixer.num_parameters)\n",
        "\n",
        "    if mixer is not None:\n",
        "        mixer_layer = mixer\n",
        "    else:\n",
        "        mixer_layer = QuantumCircuit(num_qubits)\n",
        "        mixer_layer.rx(-2 * beta[0], range(num_qubits))\n",
        "\n",
        "    for layer in range(num_layers):\n",
        "        bind_dict = {cost_layer.parameters[0]: gamma[layer]}\n",
        "        cost_layer_ = cost_layer.assign_parameters(bind_dict)\n",
        "        bind_dict = {\n",
        "            mixer_layer.parameters[i]: beta[layer + i]\n",
        "            for i in range(mixer_layer.num_parameters)\n",
        "        }\n",
        "        layer_mixer = mixer_layer.assign_parameters(bind_dict)\n",
        "\n",
        "        if layer % 2 == 0:\n",
        "            new_circuit.append(cost_layer_, range(num_qubits))\n",
        "        else:\n",
        "            new_circuit.append(cost_layer_.reverse_ops(), range(num_qubits))\n",
        "\n",
        "        new_circuit.append(layer_mixer, range(num_qubits))\n",
        "\n",
        "    for qidx, cidx in meas_map.items():\n",
        "        new_circuit.measure(qidx, cidx)\n",
        "\n",
        "    return new_circuit\n",
        "\n",
        "\n",
        "def create_qaoa_swap_circuit(\n",
        "    cost_operator: SparsePauliOp,\n",
        "    swap_strategy: SwapStrategy,\n",
        "    edge_coloring: dict = None,\n",
        "    theta: list[float] = None,\n",
        "    qaoa_layers: int = 1,\n",
        "    initial_state: QuantumCircuit = None,\n",
        "    mixer: QuantumCircuit = None,\n",
        "):\n",
        "    \"\"\"Create the circuit for QAOA.\n",
        "\n",
        "    Notes: This circuit construction for QAOA works for quadratic terms in `Z`\n",
        "    and will be extended to first-order terms in `Z`.\n",
        "    Higher-orders are not supported.\n",
        "\n",
        "    Args:\n",
        "        cost_operator: the cost operator.\n",
        "        swap_strategy: selected swap strategy\n",
        "        edge_coloring: A coloring of edges that should correspond to the\n",
        "            coupling map of the hardware. It defines the order in which\n",
        "            we apply the Rzz gates. This allows us to choose an ordering\n",
        "            such that `Rzz` gates will immediately precede SWAP gates\n",
        "            to leverage CNOT cancellation.\n",
        "        theta: The QAOA angles.\n",
        "        qaoa_layers: The number of layers of the cost operator and the\n",
        "        mixer operator.\n",
        "        initial_state: The initial state on which we apply layers of\n",
        "            cost operator and mixer.\n",
        "        mixer: The QAOA mixer. It will be applied as is onto the QAOA\n",
        "            circuit. Therefore, its output must have the same ordering\n",
        "            of qubits as its input.\n",
        "    \"\"\"\n",
        "\n",
        "    num_qubits = cost_operator.num_qubits\n",
        "\n",
        "    if theta is not None:\n",
        "        gamma = theta[: len(theta) // 2]\n",
        "        beta = theta[len(theta) // 2 :]\n",
        "        qaoa_layers = len(theta) // 2\n",
        "    else:\n",
        "        gamma = beta = None\n",
        "\n",
        "    # First, create the ansatz of one layer of QAOA without mixer\n",
        "    cost_layer = QAOAAnsatz(\n",
        "        cost_operator,\n",
        "        reps=1,\n",
        "        initial_state=QuantumCircuit(num_qubits),\n",
        "        mixer_operator=QuantumCircuit(num_qubits),\n",
        "    ).decompose()\n",
        "\n",
        "    # This will allow us to recover the permutation of the measurements\n",
        "    # that the swaps introduce.\n",
        "    cost_layer.measure_all()\n",
        "\n",
        "    # Now, apply the swap strategy for commuting gates\n",
        "    cost_layer = apply_swap_strategy(cost_layer, swap_strategy, edge_coloring)\n",
        "\n",
        "    # Compute the measurement map (qubit to classical bit).\n",
        "    # We will apply this for odd layers where the swaps were inserted.\n",
        "    if qaoa_layers % 2 == 1:\n",
        "        meas_map = make_meas_map(cost_layer)\n",
        "    else:\n",
        "        meas_map = {idx: idx for idx in range(num_qubits)}\n",
        "\n",
        "    cost_layer.remove_final_measurements()\n",
        "\n",
        "    # Finally, introduce the mixer circuit and add measurements\n",
        "    # following measurement map\n",
        "    circuit = apply_qaoa_layers(\n",
        "        cost_layer, meas_map, qaoa_layers, gamma, beta, initial_state, mixer\n",
        "    )\n",
        "\n",
        "    return circuit"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "id": "7793ef92-ce59-4fd7-b43f-48d4e3427e3a",
      "metadata": {},
      "outputs": [],
      "source": [
        "# We can define the edge_coloring map so that RZZ gates are positioned\n",
        "# right before SWAP gates to exploit CX cancellations\n",
        "# We use greedy edge coloring from rustworkx to color the edges of\n",
        "# the graph. This coloring is used to order the RZZ gates\n",
        "# in the circuit.\n",
        "\n",
        "edge_coloring_idx = rx.graph_greedy_edge_color(graph_100)\n",
        "edge_coloring = {\n",
        "    edge: edge_coloring_idx[idx]\n",
        "    for idx, edge in enumerate(list(graph_100.edge_list()))\n",
        "}\n",
        "edge_coloring = {tuple(sorted(k)): v for k, v in edge_coloring.items()}"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 105,
      "id": "82ae28b3-85eb-4487-8100-1e622e93cccf",
      "metadata": {},
      "outputs": [
        {
          "data": {
            "text/plain": [
              "<Image src=\"/docs/images/tutorials/advanced-techniques-for-qaoa/extracted-outputs/82ae28b3-85eb-4487-8100-1e622e93cccf-1.avif\" alt=\"Output of the previous code cell\" />"
            ]
          },
          "execution_count": 105,
          "metadata": {},
          "output_type": "execute_result"
        }
      ],
      "source": [
        "qaoa_circ = create_qaoa_swap_circuit(\n",
        "    remapped_cost_operator,\n",
        "    swap_strategy,\n",
        "    edge_coloring=edge_coloring,\n",
        "    qaoa_layers=1,\n",
        ")\n",
        "qaoa_circ.draw(output=\"mpl\", fold=False)"
      ]
    },
    {
      "cell_type": "markdown",
      "id": "e2afd1a7-0980-433b-a3a8-303d7e7718b1",
      "metadata": {},
      "source": [
        "<span id=\"step-3-execute-using-ibm-quantum-primitives\" />\n",
        "\n",
        "## Étape 3 : Exécution à l'aide des primitives « IBM Quantum »\n",
        "\n",
        "Préparons-nous maintenant à l'exécution matérielle. Notre première étape consistera à définir une fonction de coût de la valeur à risque conditionnelle ( CVaR ), qui a été introduite dans [\\[3\\]](#references) en vue d'une utilisation dans le cadre des algorithmes d'optimisation quantique variationnelle.\n",
        "\n",
        "Le site CVaR d'une variable aléatoire $X$ pour un niveau de confiance $α ∈ (0, 1]$ est défini comme suit $CVaR_{\\alpha}(X) = \\mathbb{E} \\lbrack X | X \\leq F_X^{-1}(\\alpha) \\rbrack$ où $F_X^{-1}(p)$ est la fonction de distribution cumulative inverse de $X$. En d'autres termes, CVaR est la valeur attendue de la queue inférieure de $\\alpha$ de la distribution de $X$.\n",
        "\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 106,
      "id": "172023f9-164e-43bd-bbc8-39d87628287e",
      "metadata": {},
      "outputs": [],
      "source": [
        "pass_manager = generate_preset_pass_manager(\n",
        "    backend=backend,\n",
        "    optimization_level=3,\n",
        ")\n",
        "\n",
        "transpiled_qaoa_circ = pass_manager.run(qaoa_circ)"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "id": "e6794cf3-7fbe-46a5-bdc0-5faad1235365",
      "metadata": {},
      "outputs": [],
      "source": [
        "# Utility functions for the evaluation of the expectation value of a measured state\n",
        "# In this code, for optimization, the measured state is converted into a bit string,\n",
        "# and the sign of the value is determined by taking the exclusive OR of the bits\n",
        "# corresponding to Pauli Z.\n",
        "\n",
        "_PARITY = np.array(\n",
        "    [-1 if bin(i).count(\"1\") % 2 else 1 for i in range(256)],\n",
        "    dtype=np.complex128,\n",
        ")\n",
        "\n",
        "\n",
        "def evaluate_sparse_pauli(state: int, observable: SparsePauliOp) -> complex:\n",
        "    \"\"\"Utility for the evaluation of the expectation value\n",
        "        of a measured state.\n",
        "\n",
        "    Args:\n",
        "        state (int): The measured state.\n",
        "        observable (SparsePauliOp): The observable to evaluate the\n",
        "        expectation value for.\n",
        "\n",
        "    Returns:\n",
        "        complex: The expectation value of the measured state.\n",
        "    \"\"\"\n",
        "    packed_uint8 = np.packbits(\n",
        "        observable.paulis.z, axis=1, bitorder=\"little\"\n",
        "    )  # convert observable to array with 8 bit integer\n",
        "    state_bytes = np.frombuffer(\n",
        "        state.to_bytes(packed_uint8.shape[1], \"little\"),\n",
        "        dtype=np.uint8,  # convert bitstring to array with 8 bit integer\n",
        "    )\n",
        "    reduced = np.bitwise_xor.reduce(packed_uint8 & state_bytes, axis=1)\n",
        "    # take bitwise xor of the result of 'and' conditional on the\n",
        "    # above two, return 0 or 1\n",
        "    return np.sum(observable.coeffs * _PARITY[reduced])"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "id": "c5e5f7a4-01f6-4a02-9114-3bb0e24be1a2",
      "metadata": {},
      "outputs": [],
      "source": [
        "def qaoa_sampler_cost_fun(\n",
        "    params, ansatz, hamiltonian, sampler, aggregation=None\n",
        "):\n",
        "    \"\"\"Standard sampler-based QAOA cost function to be plugged into\n",
        "        optimizer routines.\n",
        "\n",
        "    Args:\n",
        "        params (np.ndarray): Parameters for the ansatz.\n",
        "        ansatz (QuantumCircuit): Ansatz circuit.\n",
        "        hamiltonian (SparsePauliOp): Hamiltonian to be minimized.\n",
        "        sampler (QAOASampler): Sampler to be used.\n",
        "        aggregation (Callable | float | None): Aggregation function\n",
        "            to be applied to the sampled results. If None, the sum\n",
        "            of the expectation values is returned.\n",
        "            If float, the CVaR with the given alpha is used.\n",
        "    \"\"\"\n",
        "    # Run the circuit\n",
        "    job = sampler.run([(ansatz, params)])\n",
        "    sampler_result = job.result()\n",
        "    sampled_int_counts = sampler_result[\n",
        "        0\n",
        "    ].data.c.get_int_counts()  # bitstrings are stored as integers\n",
        "    shots = sum(sampled_int_counts.values())\n",
        "    int_count_distribution = {\n",
        "        key: val / shots for key, val in sampled_int_counts.items()\n",
        "    }\n",
        "\n",
        "    # a dictionary containing: {state: (measurement probability, value)}\n",
        "    evaluated = {\n",
        "        state: (\n",
        "            probability,\n",
        "            np.real(evaluate_sparse_pauli(state, hamiltonian)),\n",
        "        )\n",
        "        for state, probability in int_count_distribution.items()\n",
        "    }\n",
        "\n",
        "    # If aggregation is None, return the sum of the expectation values.\n",
        "    # If aggregation is a float, return the CVaR with the given alpha.\n",
        "    # Otherwise, use the aggregation function.\n",
        "    if aggregation is None:\n",
        "        result = sum(\n",
        "            probability * value for probability, value in evaluated.values()\n",
        "        )\n",
        "    elif isinstance(aggregation, float):\n",
        "        cvar_aggregation = _get_cvar_aggregation(aggregation)\n",
        "        result = cvar_aggregation(evaluated.values())\n",
        "    else:\n",
        "        result = aggregation(evaluated.values())\n",
        "\n",
        "    global iter_counts, result_dict\n",
        "    iter_counts += 1\n",
        "    temp_dict = {}\n",
        "    temp_dict[\"params\"] = params.tolist()\n",
        "    temp_dict[\"cvar_fval\"] = result\n",
        "    temp_dict[\"fval\"] = sum(\n",
        "        probability * value for probability, value in evaluated.values()\n",
        "    )\n",
        "    temp_dict[\"distribution\"] = sampled_int_counts\n",
        "    temp_dict[\"evaluated\"] = evaluated\n",
        "    result_dict[iter_counts] = temp_dict\n",
        "    print(f\"Iteration {iter_counts}: {result}\")\n",
        "\n",
        "    return result\n",
        "\n",
        "\n",
        "def _get_cvar_aggregation(alpha: float | None) -> Callable:\n",
        "    \"\"\"Return the CVaR aggregation function with the given alpha.\n",
        "\n",
        "    Args:\n",
        "        alpha (float | None): Alpha value for the CVaR aggregation.\n",
        "            If None, 1 is used by default.\n",
        "    Raises:\n",
        "        ValueError: If alpha is not in [0, 1].\n",
        "    \"\"\"\n",
        "    if alpha is None:\n",
        "        alpha = 1\n",
        "    elif not 0 <= alpha <= 1:\n",
        "        raise ValueError(f\"alpha must be in [0, 1], but {alpha} was given.\")\n",
        "\n",
        "    def cvar_aggregation(\n",
        "        objective_dict: Iterable[tuple[float, float]],\n",
        "    ) -> float:\n",
        "        \"\"\"Return the CVaR of the given measurements.\n",
        "        Args:\n",
        "            objective_dict (Iterable[tuple[float, float]]): An iterable\n",
        "                of tuples containing the measured bit string and the\n",
        "                objective value based on the bit string.\n",
        "\n",
        "        \"\"\"\n",
        "        sorted_measurements = sorted(objective_dict, key=lambda x: x[1])\n",
        "        # accumulate the probabilities until alpha is reached\n",
        "        accumulated_percent = 0.0\n",
        "        cvar = 0.0\n",
        "        for probability, value in sorted_measurements:\n",
        "            cvar += value * min(probability, alpha - accumulated_percent)\n",
        "            accumulated_percent += probability\n",
        "            if accumulated_percent >= alpha:\n",
        "                break\n",
        "        return cvar / alpha\n",
        "\n",
        "    return cvar_aggregation"
      ]
    },
    {
      "cell_type": "markdown",
      "id": "63fa2ab4-5354-4022-ab46-e9bbf73870de",
      "metadata": {},
      "source": [
        "L' CVaR e peut être utilisé comme technique d'atténuation des erreurs, comme nous l'avons vu précédemment [\\[4\\]](#references). Dans cet exemple, nous déterminons l' $\\alpha$ e et le nombre de passes en fonction de [l](/docs/guides/qpu-information#2q-error-layered) 'erreur par porte en couches (EPLG) associée au circuit.\n",
        "\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 109,
      "id": "032bf312-4bf4-40f4-81f0-2ae8a719b98b",
      "metadata": {},
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "layer fidelity 0.5454643821399414\n",
            "\n",
            "The corresponding CVaR aggregation value is:  0.2568730767702702\n",
            "To mitigate the twirled noise, increase shots by a factor of 3.8929731857197782\n"
          ]
        }
      ],
      "source": [
        "num_2q_ops = transpiled_qaoa_circ.count_ops()[\n",
        "    \"cz\"\n",
        "]  # the two qubit gates on our backend are cz's.\n",
        "\n",
        "for el in backend.properties().general:\n",
        "    if el.name[:2] == \"lf\" and el.name[3:] == str(\n",
        "        n\n",
        "    ):  # pick out lf_100, lf of the best 100q chain\n",
        "        lf = el.value  # layer fidelity\n",
        "        print(\"layer fidelity\", lf)\n",
        "        eplg = 1 - lf ** (1 / (n - 1))  # error per layered gate (EPLG)\n",
        "        fid_cz = 1 - eplg\n",
        "        gamma_cz = 1 / fid_cz**2\n",
        "        gamma_circ = gamma_cz**num_2q_ops\n",
        "\n",
        "cvar_aggregation = 1 / np.sqrt(gamma_circ)\n",
        "print(\"\")\n",
        "print(\"The corresponding CVaR aggregation value is: \", cvar_aggregation)\n",
        "print(\n",
        "    \"To mitigate the twirled noise, increase shots by a factor of\",\n",
        "    np.sqrt(gamma_circ),\n",
        ")"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "id": "382e8acd-d0d0-4302-99aa-b64e5dd31e17",
      "metadata": {},
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "Iteration 1: -13.227556797094595\n",
            "Iteration 2: -13.181545294899571\n",
            "Iteration 3: -13.149537293372594\n",
            "Iteration 4: -3.305576300816324\n",
            "Iteration 5: -12.647411769418035\n",
            "Iteration 6: -13.443610807401718\n",
            "Iteration 7: -12.475368761210511\n",
            "Iteration 8: -15.905726329447413\n",
            "Iteration 9: -18.011752834505565\n",
            "Iteration 10: -14.125781339945583\n",
            "Iteration 11: -19.693673319331744\n",
            "Iteration 12: -21.175543794613695\n",
            "Iteration 13: -21.805701324676196\n",
            "Iteration 14: -22.121280244318488\n",
            "Iteration 15: -20.02575633517435\n",
            "Iteration 16: -22.399349757584158\n",
            "Iteration 17: -22.569392265696226\n",
            "Iteration 18: -21.877719328111898\n",
            "Iteration 19: -22.79144777628963\n",
            "Iteration 20: -22.437359259397432\n",
            "Iteration 21: -23.021505287264777\n",
            "Iteration 22: -22.69742427180412\n",
            "Iteration 23: -23.12553129222746\n",
            "Iteration 24: -22.893473281156922\n",
            " message: Return from COBYLA because the trust region radius reaches its lower bound.\n",
            " success: True\n",
            "  status: 0\n",
            "     fun: -23.12553129222746\n",
            "       x: [ 2.766e+00  1.080e+00]\n",
            "    nfev: 24\n",
            "   maxcv: 0.0\n"
          ]
        }
      ],
      "source": [
        "iter_counts = 0\n",
        "result_dict = {}\n",
        "init_params = [np.pi, np.pi / 2]\n",
        "\n",
        "with Session(backend=backend) as session:\n",
        "    sampler = Sampler(mode=session)\n",
        "    sampler.options.default_shots = int(1000 / cvar_aggregation)\n",
        "    sampler.options.dynamical_decoupling.enable = True\n",
        "    sampler.options.dynamical_decoupling.sequence_type = \"XY4\"\n",
        "    sampler.options.twirling.enable_gates = True\n",
        "    sampler.options.twirling.enable_measure = True\n",
        "    sampler.options.environment.job_tags = [\n",
        "        \"TUT_AQAOA\"\n",
        "    ]  # add tag for your job execution\n",
        "\n",
        "    result = minimize(\n",
        "        qaoa_sampler_cost_fun,\n",
        "        init_params,\n",
        "        args=(\n",
        "            transpiled_qaoa_circ,\n",
        "            remapped_cost_operator,\n",
        "            sampler,\n",
        "            cvar_aggregation,\n",
        "        ),\n",
        "        method=\"COBYLA\",\n",
        "        tol=1e-2,\n",
        "    )\n",
        "print(result)"
      ]
    },
    {
      "cell_type": "markdown",
      "id": "1d190fa4-3bbe-412a-b296-6dddd3ad2b12",
      "metadata": {},
      "source": [
        "<span id=\"step-4-post-process-and-return-result-in-desired-classical-format\" />\n",
        "\n",
        "## Étape 4 : Post-traitement et restitution du résultat dans le format classique souhaité\n",
        "\n",
        "Visualisons maintenant nos résultats, puis traitons-les pour déterminer la valeur de la coupe.\n",
        "\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 111,
      "id": "761821cb-9a0c-4efb-806b-75513302d34a",
      "metadata": {},
      "outputs": [
        {
          "data": {
            "text/plain": [
              "<Image src=\"/docs/images/tutorials/advanced-techniques-for-qaoa/extracted-outputs/761821cb-9a0c-4efb-806b-75513302d34a-0.avif\" alt=\"Output of the previous code cell\" />"
            ]
          },
          "metadata": {},
          "output_type": "display_data"
        }
      ],
      "source": [
        "from matplotlib import pyplot as plt\n",
        "\n",
        "plt.figure(figsize=(12, 6))\n",
        "plt.plot(\n",
        "    [result_dict[i][\"cvar_fval\"] for i in range(1, iter_counts + 1)],\n",
        "    label=\"CVaR\",\n",
        ")\n",
        "plt.plot(\n",
        "    [result_dict[i][\"fval\"] for i in range(1, iter_counts + 1)],\n",
        "    label=\"Standard\",\n",
        ")\n",
        "plt.legend()\n",
        "plt.xlabel(\"Iteration\")\n",
        "plt.ylabel(\"Cost\")\n",
        "plt.show()"
      ]
    },
    {
      "cell_type": "markdown",
      "id": "38aadfcb-aec9-4dbb-a9d3-319239eae196",
      "metadata": {},
      "source": [
        "Le code suivant permet d'extraire la meilleure solution parmi les chaînes de bits échantillonnées :\n",
        "\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": null,
      "id": "7e8af29e-c99b-41f2-b6dd-2be471e1af21",
      "metadata": {},
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "bitstring (int): 283561207335785714592526814041, probability: 0.00025693730729701953, objective value: -43.0\n"
          ]
        }
      ],
      "source": [
        "# Sort the result_dict[iter_counts]['evaluated'] by the CVaR value\n",
        "sorted_result_dict = [\n",
        "    (k, v)\n",
        "    for k, v in sorted(\n",
        "        result_dict[iter_counts][\"evaluated\"].items(),\n",
        "        key=lambda item: item[1][1],\n",
        "    )\n",
        "]\n",
        "print(\n",
        "    f\"bitstring (int): {sorted_result_dict[0][0]}, \"\n",
        "    f\"probability: {sorted_result_dict[0][1][0]}, \"\n",
        "    f\"objective value: {sorted_result_dict[0][1][1]}\"\n",
        ")"
      ]
    },
    {
      "cell_type": "markdown",
      "id": "9cbeacc1-ff99-4b3d-b38d-b293a19642e2",
      "metadata": {},
      "source": [
        "Considérons l'hamiltonien $H_C$ pour le problème **du coupé maximal**. Associons chaque sommet du graphe à un qubit dans l'état $|0\\rangle$ ou $|1\\rangle$, où la valeur désigne l'ensemble auquel appartient le sommet. L'objectif de ce problème est de maximiser le nombre d'arêtes $(v_1, v_2)$ pour lesquelles $v_1 = |0\\rangle$ et $v_2 = |1\\rangle$, ou inversement. Si l'on associe l'opérateur d' $Z$ à chaque qubit, où\n",
        "\n",
        "$$\n",
        "    Z|0\\rangle = |0\\rangle \\qquad Z|1\\rangle = -|1\\rangle,\n",
        "$$\n",
        "\n",
        "alors une arête $(v_1, v_2)$ appartient à la coupure si la valeur propre de $(Z_1|v_1\\rangle) \\cdot (Z_2|v_2\\rangle) = -1$; en d'autres termes, les qubits associés à $v_1$ et $v_2$ sont différents. De même, $(v_1, v_2)$ n'appartient pas à la section si la valeur propre de $(Z_1|v_1\\rangle) \\cdot (Z_2|v_2\\rangle) = 1$.\n",
        "\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 113,
      "id": "5ea9e6aa-4297-4687-b484-1695d415bad5",
      "metadata": {},
      "outputs": [
        {
          "name": "stdout",
          "output_type": "stream",
          "text": [
            "Result bitstring (binary) : [1, 0, 0, 1, 1, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 1, 0, 1, 0, 0, 0, 1, 0, 1, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 1, 1, 1, 0, 0]\n",
            "The value of the cut is: 77\n"
          ]
        }
      ],
      "source": [
        "from typing import Sequence\n",
        "\n",
        "\n",
        "def to_bitstring(integer, num_bits):\n",
        "    result = np.binary_repr(integer, width=num_bits)\n",
        "    return [int(digit) for digit in result]\n",
        "\n",
        "\n",
        "def evaluate_sample(x: Sequence[int], graph: rx.PyGraph) -> float:\n",
        "    assert len(x) == len(\n",
        "        list(graph.nodes())\n",
        "    ), \"The length of x must coincide with the number of nodes in the graph.\"\n",
        "    return sum(\n",
        "        x[u] * (1 - x[v])\n",
        "        + x[v]\n",
        "        * (\n",
        "            1 - x[u]\n",
        "        )  # x[u] = x[v] if same cut, x[u] \\neq x[v] if different cuts\n",
        "        for u, v in list(graph.edge_list())\n",
        "    )\n",
        "\n",
        "\n",
        "bitstring = to_bitstring(\n",
        "    sorted_result_dict[0][0], len(list(remapped_graph.nodes()))\n",
        ")\n",
        "bitstring = bitstring[::-1]\n",
        "print(f\"Result bitstring (binary) : {bitstring}\")\n",
        "\n",
        "cut_value = evaluate_sample(bitstring, remapped_graph)\n",
        "print(f\"The value of the cut is: {cut_value}\")"
      ]
    },
    {
      "cell_type": "markdown",
      "id": "c5879546-35ab-4876-bed9-262b85f130cc",
      "metadata": {},
      "source": [
        "Enfin, dessinons un graphique basé sur le résultat de CVaR.\n",
        "Nous divisons les nœuds du graphique en deux ensembles sur la base du résultat de CVaR.\n",
        "Les nœuds du premier ensemble sont colorés en gris et les nœuds du second ensemble sont colorés en violet.\n",
        "Les arêtes entre les deux ensembles sont les arêtes qui sont coupées par le partitionnement.\n",
        "\n"
      ]
    },
    {
      "cell_type": "code",
      "execution_count": 124,
      "id": "852dfeed-2871-4ca1-9754-15c95293198e",
      "metadata": {},
      "outputs": [
        {
          "data": {
            "text/plain": [
              "<Image src=\"/docs/images/tutorials/advanced-techniques-for-qaoa/extracted-outputs/852dfeed-2871-4ca1-9754-15c95293198e-0.avif\" alt=\"Output of the previous code cell\" />"
            ]
          },
          "metadata": {},
          "output_type": "display_data"
        }
      ],
      "source": [
        "def plot_result(G, x):\n",
        "    colors = [\"tab:grey\" if i == 0 else \"tab:purple\" for i in x]\n",
        "    pos, _default_axes = rx.spring_layout(G), plt.axes(frameon=True)\n",
        "    rx.visualization.mpl_draw(\n",
        "        G,\n",
        "        node_color=colors,\n",
        "        node_size=150,\n",
        "        alpha=0.8,\n",
        "        pos=pos,\n",
        "        with_labels=True,\n",
        "        width=1,\n",
        "    )\n",
        "\n",
        "\n",
        "plot_result(graph_100, to_bitstring(sorted_result_dict[0][0], 100)[::-1])"
      ]
    },
    {
      "cell_type": "markdown",
      "id": "82f5c13b-a141-4657-adfd-bb18e88ad9f2",
      "metadata": {},
      "source": [
        "<span id=\"references\" />\n",
        "\n",
        "## Références\n",
        "\n",
        "\\[1] Weidenfeller, J., Valor, L. C., Gacon, J., Tornow, C., Bello, L., Woerner, S., & Egger, D. J. (2022). Mise à l'échelle de l'algorithme d'optimisation approximative quantique sur du matériel basé sur des qubits supraconducteurs. Quantum, 6, 870.\n",
        "\n",
        "\\[2] Matsuo, A., Yamashita, S., et Egger, D. J. (2023). Une approche SAT du problème de cartographie initiale dans l'insertion de portes SWAP pour les portes commutatives. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, 106(11), 1424-1431.\n",
        "\n",
        "\\[3] Barkoutsos, P. K., Nannicini, G., Robert, A., Tavernelli, I. et Woerner, S. (2020). Amélioration de l'optimisation quantique variationnelle à l'aide de CVaR. Quantum, 4, 256.\n",
        "\n",
        "\\[4] Barron, S. V., Egger, D. J., Pelofske, E., Bärtschi, A., Eidenbenz, S., Lehmkuehler, M. et Woerner, S. (2023). Limites prévisibles pour les valeurs d'espérance sans bruit calculées à partir d'échantillons bruyants. arXiv preprint arXiv:2312.00733.\n",
        "\n"
      ]
    },
    {
      "cell_type": "markdown",
      "id": "a6a5bbfe-a159-4dc1-9333-488737aff503",
      "metadata": {},
      "source": [
        "<span id=\"next-steps\" />\n",
        "\n",
        "## Etapes suivantes\n",
        "\n",
        "<Admonition type=\"tip\" title=\"Recommandations\">\n",
        "  Si ce travail vous a paru intéressant, les documents suivants pourraient vous intéresser :\n",
        "\n",
        "  * [Le « décathlon » des problèmes d'optimisation](https://arxiv.org/pdf/2504.03832) : une liste de 10 problèmes d'optimisation qui posent des difficultés aux algorithmes d'optimisation classiques et qui pourraient constituer de bons cas d'utilisation pour tester les techniques présentées dans ce tutoriel.\n",
        "  * [Un dépôt contenant les meilleures pratiques en matière d'optimisation quantique,](https://github.com/qiskit-community/qopt-best-practices) destiné à améliorer encore les résultats de votre flux de travail basé sur le QAOA.\n",
        "</Admonition>\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": 180
  },
  "nbformat": 4,
  "nbformat_minor": 4
}