{ "cells": [ { "cell_type": "markdown", "id": "title", "metadata": {}, "source": [ "---\n", "title: \"Résolvez le problème de fragmentation du marché grâce à l'optimiseur Iskay Quantum de Kipu Quantum\"\n", "description: \"Découvrez comment résoudre le problème de la division du marché à l'aide de l'optimiseur quantique Iskay et de l'algorithme bf-DCQO sur le matériel d' IBM Quantum\"\n", "---\n", "\n", "\n", "\n", "# Résolvez le problème de fragmentation du marché grâce à l'optimiseur Iskay Quantum de Kipu Quantum\n", "\n", "{/* cspell:ignore adiabaticity, HUBO, bitflip, metaheuristic, fontweight, fontsize, QOBLIB, Zuse, Kochenberger, Tramontani, Weninger, edgecolor, nonumber */}\n", "\n" ] }, { "cell_type": "markdown", "id": "note", "metadata": {}, "source": [ "\n", " Qiskit Functions sont une fonctionnalité expérimentale disponible uniquement pour les utilisateurs des plans IBM Quantum® Premium Plan, Flex et On-Prem (via IBM Quantum Platform API). Elles sont en cours de publication et peuvent être modifiées.\n", "\n", "\n", "*Estimation d'utilisation : 20 secondes sur un processeur Heron r2. (NOTE : Il s'agit uniquement d'une estimation. Votre durée d'exécution peut varier.)*\n", "\n" ] }, { "cell_type": "markdown", "id": "background", "metadata": {}, "source": [ "\n", "\n", "## Arrière-plan\n", "\n", "Ce tutoriel montre comment résoudre le problème de la division du marché en utilisant [l'optimiseur quantique Iskay de Kipu Quantum](/docs/guides/kipu-optimization) [\\[1\\].](#references) Le problème de la division du marché représente un défi réel d'allocation des ressources où les marchés doivent être divisés en régions de vente équilibrées pour atteindre des objectifs de demande précis.\n", "\n", "\n", "\n", "### Le défi de la division du marché\n", "\n", "Le problème de la répartition du marché est un défi d'une simplicité trompeuse, mais d'une puissance de calcul redoutable, en matière d'allocation des ressources. Considérons une entreprise dont les produits $m$ sont vendus sur $n$ marchés différents, chaque marché achetant un ensemble spécifique de produits (représenté par les colonnes de la matrice $A$ ). L'objectif de l'entreprise est de diviser ces marchés en deux régions de vente équilibrées, de sorte que chaque région reçoive exactement la moitié de la demande totale pour chaque produit.\n", "\n", "**Formulation mathématique :**\n", "\n", "Nous recherchons un vecteur d'affectation binaire $x$, où :\n", "\n", "* $x_j = 1$ attribue le marché $j$ à la région A\n", "* $x_j = 0$ attribue le marché $j$ à la région B\n", "* La contrainte $Ax = b$ doit être satisfaite, où $b$ représente les ventes cibles (généralement la moitié de la demande totale par produit)\n", "\n", "**Fonction de coût :**\n", "\n", "Pour résoudre ce problème, nous minimisons le carré de la violation de la contrainte :\n", "\n", "$C(x) = ||Ax - b||^2 = \\sum_{i=1}^{m} \\left(\\sum_{j=1}^{n} A_{ij}x_j - b_i\\right)^2$\n", "\n", "où :\n", "\n", "* $A_{ij}$ représente les ventes du produit $i$ sur le marché $j$\n", "* $x_j \\in \\{0,1\\}$ est l'affectation binaire du marché $j$\n", "* $b_i$ est l'objectif de vente du produit $i$ dans chaque région\n", "* Le coût est égal à zéro précisément lorsque toutes les contraintes sont satisfaites\n", "\n", "Chaque terme de la somme représente l'écart au carré par rapport aux ventes cibles pour un produit particulier. Lorsque nous développons cette fonction de coût, nous obtenons :\n", "\n", "$C(x) = x^T A^T A x - 2b^T A x + b^T b$\n", "\n", "Comme $b^T b$ est une constante, minimiser $C(x)$ revient à minimiser la fonction quadratique $x^T A^T A x - 2b^T A x$, ce qui est exactement un problème QUBO (Quadratic Unconstrained Binary Optimization).\n", "\n", "**Complexité informatique :**\n", "\n", "En dépit de son interprétation commerciale simple, ce problème présente une difficulté de calcul remarquable :\n", "\n", "* **Échec à petite échelle** : Les solveurs conventionnels de programmation en nombres entiers mixtes échouent sur des instances comportant aussi peu que sept produits dans un délai d'une heure [\\[4\\]](#references)\n", "* **Croissance exponentielle** : L'espace de solution croît de manière exponentielle ( $2^n$ affectations possibles), ce qui rend les approches par force brute infaisables\n", "\n", "Cet obstacle informatique important, combiné à sa pertinence pratique pour l'aménagement du territoire et l'allocation des ressources, fait du problème de la division du marché une référence idéale pour les algorithmes d'optimisation quantique [\\[4\\].](#references)\n", "\n", "\n", "\n", "### Qu'est-ce qui rend l'approche d'Iskay unique?\n", "\n", "L'optimiseur d'Iskay utilise l'algorithme **bf-DCQO (bias-field digitized counterdiabatic quantum optimization)** [\\[1\\]](#references), qui représente une avancée significative dans le domaine de l'optimisation quantique :\n", "\n", "**Efficacité du circuit** : L'algorithme bf-DCQO permet une réduction remarquable du nombre de portes [\\[1\\] :](#references)\n", "\n", "* Jusqu'à **10 fois moins de portes d'intrication** que le recuit quantique numérique (DQA)\n", "* Des circuits nettement moins profonds permettent :\n", " * Moins d'accumulation d'erreurs pendant l'exécution quantique\n", " * Capacité à résoudre des problèmes plus importants avec le matériel quantique actuel\n", " * Pas besoin de techniques d'atténuation des erreurs\n", "\n", "**Conception non variationnelle** : Contrairement aux algorithmes variationnels qui nécessitent environ 100 itérations, bf-DCQO n'en nécessite généralement qu'une **dizaine** [\\[1\\].](#references) Pour ce faire, il faut\n", "\n", "* Calculs intelligents du champ de polarisation à partir de distributions d'états mesurées\n", "* Commencer chaque itération à partir d'un état énergétique proche de la solution précédente\n", "* Post-traitement classique intégré avec recherche locale\n", "\n", "**Protocoles contrediabatiques** : L'algorithme incorpore des termes contrediabatiques qui suppriment les excitations quantiques indésirables pendant les temps d'évolution courts, ce qui permet au système de rester proche de l'état fondamental même en cas de transitions rapides [\\[1\\].](#references)\n", "\n" ] }, { "cell_type": "markdown", "id": "requirements", "metadata": {}, "source": [ "\n", "\n", "## Exigences\n", "\n", "Avant de commencer ce tutoriel, assurez-vous que les éléments suivants sont installés :\n", "\n", "* Qiskit IBM Runtime (`pip install qiskit-ibm-runtime`)\n", "* Qiskit Functions (`pip install qiskit-ibm-catalog`)\n", "* NumPy (`pip install numpy`)\n", "* Demandes (`pip install requests`)\n", "* Opt Mapper Qiskit addon (`pip install qiskit-addon-opt-mapper`)\n", "\n", "Vous devrez également obtenir l'accès à la [fonction Iskay Quantum Optimizer](/functions?id=kipu-quantum-iskay-quantum-optimizer) sur le site Qiskit Functions Catalog.\n", "\n" ] }, { "cell_type": "markdown", "id": "setup", "metadata": {}, "source": [ "\n", "\n", "## Configuration\n", "\n", "Tout d'abord, importez tous les paquets nécessaires pour ce tutoriel.\n", "\n" ] }, { "cell_type": "code", "execution_count": null, "id": "imports", "metadata": {}, "outputs": [], "source": [ "import os\n", "import tempfile\n", "import time\n", "from typing import Tuple, Optional\n", "\n", "import numpy as np\n", "import requests\n", "\n", "from qiskit_ibm_catalog import QiskitFunctionsCatalog\n", "\n", "from qiskit_addon_opt_mapper import OptimizationProblem\n", "from qiskit_addon_opt_mapper.converters import OptimizationProblemToQubo\n", "\n", "print(\"All required libraries imported successfully\")" ] }, { "cell_type": "markdown", "id": "credentials", "metadata": {}, "source": [ "\n", "\n", "### Configurer les informations d'identification d' IBM Quantum\n", "\n", "Définissez vos [IBM Quantum® Platform](/) compétences. Eléments nécessaires :\n", "\n", "* **Jeton API** : Votre clé API de 44 caractères provenant de IBM Quantum Platform\n", "* **Instance CRN** : Votre identifiant d'instance IBM Cloud®\n", "\n" ] }, { "cell_type": "code", "execution_count": null, "id": "creds", "metadata": {}, "outputs": [], "source": [ "token = \"\"\n", "instance = \"\"" ] }, { "cell_type": "markdown", "id": "step1", "metadata": {}, "source": [ "\n", "\n", "## Étape 1 : Mettre en correspondance les entrées classiques avec un problème quantique\n", "\n", "Nous commençons par transposer notre problème classique dans une représentation compatible avec le système quantique. Cette étape implique :\n", "\n", "1. Connexion à l'optimiseur quantique Iskay\n", "2. Chargement et formulation du problème de la répartition du marché\n", "3. Comprendre l'algorithme bf-DCQO qui le résoudra\n", "\n", "\n", "\n", "### Se connecter à Iskay Quantum Optimizer\n", "\n", "Nous commençons par établir une connexion avec le site Qiskit Functions Catalog et par charger l'optimiseur quantique Iskay. L'optimiseur Iskay est une fonction quantique fournie par Kipu Quantum qui met en œuvre l'algorithme bf-DCQO pour résoudre des problèmes d'optimisation sur du matériel quantique.\n", "\n" ] }, { "cell_type": "code", "execution_count": null, "id": "load_solver", "metadata": {}, "outputs": [], "source": [ "catalog = QiskitFunctionsCatalog(token=token, instance=instance)\n", "iskay_solver = catalog.load(\"kipu-quantum/iskay-quantum-optimizer\")\n", "\n", "print(\"Iskay optimizer loaded successfully\")\n", "print(\"Ready to solve optimization problems using bf-DCQO algorithm\")" ] }, { "cell_type": "markdown", "id": "step2", "metadata": {}, "source": [ "\n", "\n", "### Charger et formuler le problème\n", "\n", "\n", "\n", "#### Comprendre le format des données problématiques\n", "\n", "Les instances de problèmes de QOBLIB (Quantum Optimization Benchmarking Library) [\\[2\\]](#references) sont stockées dans un format texte simple. Examinons le contenu réel de notre instance cible `ms_03_200_177.dat`:\n", "\n", "```text\n", "3 20\n", "60 92 161 53 97 2 75 81 6 139 132 45 108 112 181 93 152 200 164 51 1002\n", "176 196 41 143 2 88 0 79 10 71 75 148 82 135 34 187 33 155 58 46 879\n", "68 68 179 173 127 163 48 49 99 78 44 52 173 131 73 198 84 109 180 95 1040\n", "```\n", "\n", "**Structure du format :**\n", "\n", "* **Première ligne :** `3 20`\n", " * `3` = nombre de produits (contraintes/rangées de la matrice $A$ )\n", " * `20` = nombre de marchés (variables/colonnes de la matrice $A$ )\n", "\n", "* **3 lignes suivantes :** Matrice des coefficients $A$ et vecteur cible $b$\n", " * Chaque ligne comporte 21 nombres : les 20 premiers sont les coefficients de ligne, le dernier est la cible\n", " * Ligne 2 : `60 92 161 ... 51 | 1002`\n", " * Les 20 premiers chiffres : Quelle quantité de produit 1 chacun des 20 marchés vend-il?\n", " * Dernier chiffre (1002) : Objectif de vente pour le produit 1 dans une région\n", " * Ligne 3 : `176 196 41 ... 46 | 879`\n", " * Ventes du produit 2 par marché et par cible (879)\n", " * Ligne 4 : `68 68 179 ... 95 | 1040`\n", " * Ventes du produit 3 par marché et par cible (1040)\n", "\n", "**Interprétation commerciale :**\n", "\n", "* Le marché 0 vend : 60 unités du produit 1, 176 unités du produit 2, 68 unités du produit 3\n", "* Le marché 1 vend : 92 unités du produit 1, 196 unités du produit 2, 68 unités du produit 3\n", "* Et ainsi de suite pour les 20 marchés...\n", "* **Objectif** : diviser ces 20 marchés en deux régions où chaque région reçoit exactement 1002 unités du produit 1, 879 unités du produit 2 et 1040 unités du produit 3\n", "\n", "\n", "\n", "#### Transformation QUBO\n", "\n", "\n", "\n", "## Des contraintes au QUBO : la transformation mathématique\n", "\n", "La puissance de l'optimisation quantique réside dans la transformation de problèmes contraints en formes quadratiques sans contrainte [\\[4\\].](#references) Pour le problème de la répartition du marché, nous convertissons les contraintes d'égalité\n", "\n", "$Ax = b$\n", "\n", "où $x ∈ \\{0,1\\}^n$, en une QUBO en pénalisant les violations de contraintes.\n", "\n", "**La méthode de la pénalité :** Puisque nous avons besoin que $Ax = b$ tienne exactement, nous minimisons le carré de la violation : $f(x) = ||Ax - b||^2$\n", "\n", "Elle est égale à zéro précisément lorsque toutes les contraintes sont satisfaites. Développement algébrique : $f(x) = (Ax - b)^T(Ax - b) = x^T A^T A x - 2b^T A x + b^T b$\n", "\n", "**Objectif de QUBO :** Puisque $b^T b$ est constant, notre optimisation devient : $\\text{minimize} \\quad Q(x) = x^T(A^T A)x - 2(A^T b)^T x$\n", "\n", "**Aperçu principal :** Cette transformation est exacte et non approximative. Les contraintes d'égalité se transforment naturellement en forme quadratique sans nécessiter de variables auxiliaires ou de paramètres de pénalité, ce qui rend cette formulation mathématiquement élégante et informatiquement efficace pour les solveurs quantiques [\\[4\\].](#references) Nous utiliserons la classe `OptimizationProblem` pour définir notre problème contraint, puis nous le convertirons au format QUBO à l'aide de `OptimizationProblemToQubo`, tous deux issus du package **qiskit\\_addon\\_opt\\_mapper**. Cela permet de gérer automatiquement la transformation basée sur la pénalité.\n", "\n" ] }, { "cell_type": "markdown", "id": "functions_intro", "metadata": {}, "source": [ "\n", "\n", "### Mettre en œuvre les fonctions de chargement des données et de conversion QUBO\n", "\n", "Nous définissons maintenant trois fonctions d'utilité :\n", "\n", "1. `parse_marketsplit_dat()` - Analyse le format de fichier `.dat` et extrait les matrices $A$ et $b$\n", "2. `fetch_marketsplit_data()` - Téléchargement d'instances de problèmes directement à partir du référentiel QOBLIB\n", "\n" ] }, { "cell_type": "code", "execution_count": null, "id": "functions", "metadata": {}, "outputs": [], "source": [ "def parse_marketsplit_dat(filename: str) -> Tuple[np.ndarray, np.ndarray]:\n", " \"\"\"\n", " Parse a market split problem from a .dat file format.\n", "\n", " Parameters\n", " ----------\n", " filename : str\n", " Path to the .dat file containing the market split problem data.\n", "\n", " Returns\n", " -------\n", " A : np.ndarray\n", " Coefficient matrix of shape (m, n) where m is the number of products\n", " and n is the number of markets.\n", " b : np.ndarray\n", " Target vector of shape (m,) containing the target sales per product.\n", " \"\"\"\n", " with open(filename, \"r\", encoding=\"utf-8\") as f:\n", " lines = [\n", " line.strip()\n", " for line in f\n", " if line.strip() and not line.startswith(\"#\")\n", " ]\n", "\n", " if not lines:\n", " raise ValueError(\"Empty or invalid .dat file\")\n", "\n", " # First line: m n (number of products and markets)\n", " m, n = map(int, lines[0].split())\n", "\n", " # Next m lines: each row of A followed by corresponding element of b\n", " A, b = [], []\n", " for i in range(1, m + 1):\n", " values = list(map(int, lines[i].split()))\n", " A.append(values[:-1]) # First n values: product sales per market\n", " b.append(values[-1]) # Last value: target sales for this product\n", "\n", " return np.array(A, dtype=np.int32), np.array(b, dtype=np.int32)\n", "\n", "\n", "def fetch_marketsplit_data(\n", " instance_name: str = \"ms_03_200_177.dat\",\n", ") -> Tuple[Optional[np.ndarray], Optional[np.ndarray]]:\n", " \"\"\"\n", " Fetch market split data directly from the QOBLIB repository.\n", "\n", " Parameters\n", " ----------\n", " instance_name : str\n", " Name of the .dat file to fetch (default: \"ms_03_200_177.dat\").\n", "\n", " Returns\n", " -------\n", " A : np.ndarray or None\n", " Coefficient matrix if successful, None if failed.\n", " b : np.ndarray or None\n", " Target vector if successful, None if failed.\n", " \"\"\"\n", " url = f\"https://git.zib.de/qopt/qoblib-quantum-optimization-benchmarking-library/-/raw/main/01-marketsplit/instances/{instance_name}\"\n", "\n", " try:\n", " response = requests.get(url, timeout=30)\n", " response.raise_for_status()\n", "\n", " with tempfile.NamedTemporaryFile(\n", " mode=\"w\", suffix=\".dat\", delete=False, encoding=\"utf-8\"\n", " ) as f:\n", " f.write(response.text)\n", " temp_path = f.name\n", "\n", " try:\n", " return parse_marketsplit_dat(temp_path)\n", " finally:\n", " os.unlink(temp_path)\n", " except Exception as e:\n", " print(f\"Error: {e}\")\n", " return None, None" ] }, { "cell_type": "markdown", "id": "load_intro", "metadata": {}, "source": [ "\n", "\n", "### Charger l'instance du problème\n", "\n", "Nous chargeons maintenant l'instance de problème spécifique `ms_03_200_177.dat` à partir de la QOBLIB \\[2.] Cette instance a :\n", "\n", "* 3 produits (contraintes)\n", "* 20 marchés (variables de décision binaires)\n", "* Plus d'un million de marchés possibles à explorer ( $2^{20} = 1,048,576$ )\n", "\n" ] }, { "cell_type": "code", "execution_count": null, "id": "load", "metadata": {}, "outputs": [], "source": [ "# Load the problem instance\n", "instance_name = \"ms_03_200_177.dat\"\n", "A, b = fetch_marketsplit_data(instance_name=instance_name)\n", "\n", "if A is not None:\n", " print(\"Successfully loaded problem instance from QOBLIB\")\n", " print(\"\\nProblem Instance Analysis:\")\n", " print(\"=\" * 50)\n", " print(f\"Coefficient Matrix A: {A.shape[0]} × {A.shape[1]}\")\n", " print(f\" → {A.shape[0]} products (constraints)\")\n", " print(f\" → {A.shape[1]} markets (decision variables)\")\n", " print(f\"Target Vector b: {b}\")\n", " print(\" → Target sales per product for each region\")\n", " print(\n", " f\"Solution Space: \"\n", " f\"2^{A.shape[1]} = {2**A.shape[1]:,} possible assignments\"\n", " )" ] }, { "cell_type": "markdown", "id": "convert_intro", "metadata": {}, "source": [ "\n", "\n", "### Convertir au format QUBO\n", "\n", "Nous transformons maintenant le problème d'optimisation contraint en format QUBO :\n", "\n" ] }, { "cell_type": "code", "execution_count": null, "id": "convert", "metadata": {}, "outputs": [], "source": [ "# Create optimization problem\n", "ms = OptimizationProblem(instance_name.replace(\".dat\", \"\"))\n", "\n", "# Add binary variables (one for each market)\n", "ms.binary_var_list(A.shape[1])\n", "\n", "# Add equality constraints (one for each product)\n", "for idx, rhs in enumerate(b):\n", " ms.linear_constraint(A[idx, :], sense=\"==\", rhs=rhs)\n", "\n", "# Convert to QUBO with penalty parameter\n", "qubo = OptimizationProblemToQubo(penalty=1).convert(ms)\n", "\n", "print(\"QUBO Conversion Complete:\")\n", "print(\"=\" * 50)\n", "print(f\"Number of variables: {qubo.get_num_vars()}\")\n", "print(f\"Constant term: {qubo.objective.constant}\")\n", "print(f\"Linear terms: {len(qubo.objective.linear.to_dict())}\")\n", "print(f\"Quadratic terms: {len(qubo.objective.quadratic.to_dict())}\")" ] }, { "cell_type": "markdown", "id": "1d307072", "metadata": {}, "source": [ "\n", "\n", "### Convertir QUBO au format Iskay\n", "\n", "Nous devons maintenant convertir l'objet QUBO dans le format de dictionnaire requis par l'optimiseur Iskay de Kipu Quantum.\n", "\n", "Les arguments `problem` et `problem_type` codent un problème d'optimisation de la forme\n", "\n", "$$\n", "\\begin{align}\n", "\\min_{(x_1, x_2, \\ldots, x_n) \\in D} C(x_1, x_2, \\ldots, x_n) \\nonumber\n", "\\end{align}\n", "$$\n", "\n", "où\n", "\n", "$$\n", "C(x_1, ... , x_n) = a + \\sum_{i} b_i x_i + \\sum_{i, j} c_{i, j} x_i x_j + ... + \\sum_{k_1, ..., k_m} g_{k_1, ..., k_m} x_{k_1} ... x_{k_m}\n", "$$\n", "\n", "* En choisissant `problem_type = \"binary\"`, vous indiquez que la fonction de coût est au format `binary` , ce qui signifie que $D = \\{0, 1\\}^{n}$, comme dans, la fonction de coût est écrite dans la formulation QUBO/HUBO.\n", "* D'autre part, en choisissant `problem_type = \"spin\"`, la fonction de coût s'écrit dans la formulation d'Ising, où $D = \\{-1, 1\\}^{n}$.\n", "\n", "Les coefficients du problème doivent être encodés dans un dictionnaire comme suit :\n", "\n", "$$\n", "\\begin{align} \\nonumber\n", "&\\texttt{\\{} \\\\ \\nonumber\n", "&\\texttt{\"()\"}&: \\quad &a, \\\\ \\nonumber\n", "&\\texttt{\"(i,)\"}&: \\quad &b_i, \\\\ \\nonumber\n", "&\\texttt{\"(i, j)\"}&: \\quad &c_{i, j}, \\quad (i \\neq j) \\\\ \\nonumber\n", "&\\quad \\vdots \\\\ \\nonumber\n", "&\\texttt{\"(} k_1, ..., k_m \\texttt{)\"}&: \\quad &g_{k_1, ..., k_m}, \\quad (k_1 \\neq k_2 \\neq \\dots \\neq k_m) \\\\ \\nonumber\n", "&\\texttt{\\}}\n", "\\end{align}\n", "$$\n", "\n", "Notez que les clés du dictionnaire doivent être des chaînes de caractères contenant un tuple valide d'entiers non répétitifs. Pour les problèmes binaires, nous savons que\n", "\n", "$$\n", "x_i^2 = x_i\n", "$$\n", "\n", "pour $i=j$ (puisque $x_i \\in \\{0,1\\}$ signifie $x_i \\cdot x_i = x_i$ ). Ainsi, dans votre formulation QUBO, si vous avez à la fois des contributions linéaires $b_i x_i$ et des contributions quadratiques diagonales $c_{i,i} x_i^2$, ces termes doivent être combinés en un seul coefficient linéaire :\n", "\n", "**Coefficient linéaire total pour la variable $x_i$** : $b_i + c_{i,i}$\n", "\n", "Ce qui signifie :\n", "\n", "* Les termes linéaires tels que `\"(i, )\"` contiennent : le coefficient linéaire d'origine + le coefficient quadratique diagonal\n", "* Les termes quadratiques diagonaux comme `\"(i, i)\"` ne devrait **PAS** apparaître dans le dictionnaire final\n", "* Seuls les termes quadratiques hors diagonale tels que `\"(i, j)\"` où $i \\neq j$ doivent être inclus en tant qu'entrées séparées\n", "\n", "**Exemple :** Si votre QUBO a $3x_1 + 2x_1^2 + 4x_1 x_2$, le dictionnaire Iskay devrait contenir :\n", "\n", "* `\"(0, )\"`: `5.0` (combinant $3 + 2 = 5$ )\n", "* `\"(0, 1)\"`: `4.0` (terme hors diagonale)\n", "\n", "**PAS d'** entrées séparées pour `\"(0, )\"`: `3.0` et `\"(0, 0)\"`: `2.0`.\n", "\n" ] }, { "cell_type": "code", "execution_count": null, "id": "57eda6fd", "metadata": {}, "outputs": [], "source": [ "# Convert QUBO to Iskay dictionary format:\n", "\n", "# Create empty Iskay input dictionary\n", "iskay_input_problem = {}\n", "\n", "# Convert QUBO to Iskay dictionary format\n", "iskay_input_problem = {\"()\": qubo.objective.constant}\n", "\n", "for i in range(qubo.get_num_vars()):\n", " for j in range(i, qubo.get_num_vars()):\n", " if i == j:\n", " # Add linear term (including diagonal quadratic contribution)\n", " iskay_input_problem[f\"({i}, )\"] = float(\n", " qubo.objective.linear.to_dict().get(i)\n", " ) + float(qubo.objective.quadratic.to_dict().get((i, i)))\n", " else:\n", " # Add off-diagonal quadratic term\n", " iskay_input_problem[f\"({i}, {j})\"] = float(\n", " qubo.objective.quadratic.to_dict().get((i, j))\n", " )\n", "\n", "# Display Iskay dictionary summary\n", "print(\"Iskay Dictionary Format:\")\n", "print(\"=\" * 50)\n", "print(f\"Total coefficients: {len(iskay_input_problem)}\")\n", "print(f\" • Constant term: {iskay_input_problem['()']}\")\n", "print(\n", " f\" • Linear terms: \"\n", " f\"{sum(1 for k in iskay_input_problem.keys() if k != '()' and ', )' in k)}\"\n", ")\n", "print(\n", " f\" • Quadratic terms: \"\n", " f\"{sum(1 for k in iskay_input_problem.keys() if k != '()' and ', )' not in k)}\"\n", ")\n", "print(\"\\nSample coefficients:\")\n", "\n", "# Get first 10 and last 5 items properly\n", "items = list(iskay_input_problem.items())\n", "first_10 = list(enumerate(items[:10]))\n", "last_5 = list(enumerate(items[-5:], start=len(items) - 5))\n", "\n", "for i, (key, value) in first_10 + last_5:\n", " coeff_type = (\n", " \"constant\"\n", " if key == \"()\"\n", " else \"linear\"\n", " if \", )\" in key\n", " else \"quadratic\"\n", " )\n", " print(f\" {key}: {value} ({coeff_type})\")\n", "print(\" ...\")\n", "print(\"\\n✓ Problem ready for Iskay optimizer!\")" ] }, { "cell_type": "markdown", "id": "step3", "metadata": {}, "source": [ "\n", "\n", "### Comprendre l'algorithme bf-DCQO\n", "\n", "Avant de lancer l'optimisation, il convient de comprendre l'algorithme quantique sophistiqué qui alimente Iskay : **bf-DCQO (bias-field digitized counterdiabatic quantum optimization)** [\\[1\\].](#references)\n", "\n", "\n", "\n", "#### Qu'est-ce que le bf-DCQO?\n", "\n", "bf-DCQO est basé sur l'évolution temporelle d'un système quantique où la solution du problème est encodée dans l' **état fondamental** (état d'énergie le plus bas) de l'hamiltonien quantique final [\\[1\\].](#references) L'algorithme relève un défi fondamental en matière d'optimisation quantique :\n", "\n", "**Le défi** : l'informatique quantique adiabatique traditionnelle nécessite une évolution très lente pour maintenir les conditions de l'état fondamental conformément au théorème adiabatique. Cela exige des circuits quantiques de plus en plus profonds à mesure que la complexité du problème augmente, ce qui entraîne davantage d'opérations de porte et d'erreurs accumulées.\n", "\n", "**La solution** : bf-DCQO utilise des protocoles contrediabatiques pour permettre une évolution rapide tout en maintenant la fidélité de l'état fondamental, ce qui réduit considérablement la profondeur du circuit.\n", "\n", "\n", "\n", "#### Cadre mathématique\n", "\n", "L'algorithme minimise une fonction de coût de la forme :\n", "\n", "$\\min_{(x_1,x_2,...,x_n) \\in D} C(x_1,x_2,...,x_n)$\n", "\n", "où $D = \\{0,1\\}^n$ pour les variables binaires et :\n", "\n", "$C(x) = a + \\sum_i b_i x_i + \\sum_{i,j} c_{ij} x_i x_j + ... + \\sum g_{k_1,...,k_m} x_{k_1}...x_{k_m}$\n", "\n", "Pour notre problème de division du marché, la fonction de coût est la suivante :\n", "\n", "$C(x) = ||Ax - b||^2 = x^T A^T A x - 2 b^T A x + b^T b$\n", "\n", "\n", "\n", "#### Le rôle des termes contre-diabétiques\n", "\n", "Les **termes contrediabatiques** sont des termes supplémentaires introduits dans le hamiltonien dépendant du temps qui suppriment les excitations indésirables au cours de l'évolution quantique. Voici pourquoi ils sont essentiels :\n", "\n", "Dans l'optimisation quantique adiabatique, nous faisons évoluer le système en fonction d'un hamiltonien dépendant du temps :\n", "\n", "$H(t) = \\left(1 - \\frac{t}{T}\\right) H_{\\text{initial}} + \\frac{t}{T} H_{\\text{problem}}$\n", "\n", "où $H_{\\text{problem}}$ code notre problème d'optimisation. Pour maintenir l'état fondamental pendant l'évolution rapide, nous ajoutons des termes contrediabatiques :\n", "\n", "$H_{\\text{CD}}(t) = H(t) + H_{\\text{counter}}(t)$\n", "\n", "Ces termes contrediabatiques ont les effets suivants :\n", "\n", "1. **Supprimer les transitions indésirables** : Empêcher l'état quantique de passer à des états excités au cours d'une évolution rapide\n", "2. **Permettre des temps d'évolution plus courts** : Permet d'atteindre l'état final beaucoup plus rapidement sans violer l'adiabaticité\n", "3. **Réduire la profondeur des circuits** : Une évolution plus courte permet de réduire le nombre de portes et d'erreurs\n", "\n", "L'impact pratique est spectaculaire : bf-DCQO utilise jusqu'à **10 fois moins de portes d'enchevêtrement** que Digital Quantum Annealing [\\[1\\]](#references), ce qui le rend pratique pour le matériel quantique bruyant d'aujourd'hui.\n", "\n", "\n", "\n", "#### Optimisation itérative par champ de biais\n", "\n", "Contrairement aux algorithmes variationnels qui optimisent les paramètres du circuit par de nombreuses itérations, bf-DCQO utilise une **approche guidée par le champ de polarisation** qui converge en 10 itérations environ \\[1 :]\n", "\n", "**Processus d'itération :**\n", "\n", "1. **Evolution quantique initiale** : Commencez par un circuit quantique mettant en œuvre le protocole d'évolution contrediabatique\n", "\n", "2. **Mesure** : Mesurer l'état quantique pour obtenir une distribution de probabilité sur des chaînes de bits\n", "\n", "3. **Calcul du champ de polarisation** : Analyse des statistiques de mesure et calcul d'un champ de polarisation optimal $h_i$ pour chaque qubit : $h_i = \\text{f}(\\text{measurement statistics}, \\text{previous solutions})$\n", "\n", "4. **Itération suivante** : Le champ de polarisation modifie l'hamiltonien pour l'itération suivante : $H_{\\text{next}} = H_{\\text{problem}} + \\sum_i h_i \\sigma_i^z$\n", "\n", " Cela permet de commencer à proximité de la bonne solution trouvée précédemment, en effectuant une forme de \"recherche locale quantique\"\n", "\n", "5. **Convergence** : Répéter l'opération jusqu'à ce que la qualité de la solution se stabilise ou qu'un nombre maximal d'itérations soit atteint\n", "\n", "**Principal avantage** : Chaque itération permet de progresser de manière significative vers la solution optimale en incorporant les informations des mesures précédentes, contrairement aux méthodes variationnelles qui doivent explorer l'espace des paramètres à l'aveugle.\n", "\n", "\n", "\n", "#### Post-traitement classique intégré\n", "\n", "Après la convergence de l'optimisation quantique, Iskay effectue un post-traitement classique de **recherche locale** :\n", "\n", "* **Exploration par retournement de bits** : Inversion systématique ou aléatoire des bits dans la meilleure solution mesurée\n", "* **Évaluation de l'énergie** : Calculer $C(x)$ pour chaque solution modifiée\n", "* **Sélection avide** : Accepter les améliorations qui réduisent la fonction de coût\n", "* **Passes multiples** : Effectuer plusieurs passes (contrôlées par `postprocessing_level`)\n", "\n", "Cette approche hybride compense les erreurs de basculement des bits dues aux imperfections du matériel et aux erreurs de lecture, garantissant des solutions de haute qualité même sur des dispositifs quantiques bruyants.\n", "\n", "\n", "\n", "#### Pourquoi bf-DCQO excelle sur le matériel actuel\n", "\n", "L'algorithme bf-DCQO est spécialement conçu pour exceller sur les dispositifs quantiques bruyants à échelle intermédiaire (NISQ) d'aujourd'hui [\\[1\\] :](#references)\n", "\n", "1. **Résistance aux erreurs** : Moins de portes (réduction de 10 fois) signifie moins d'accumulation d'erreurs\n", "2. **Aucune réduction d'erreur n'est nécessaire** : L'efficacité inhérente de l'algorithme élimine la nécessité de recourir à des techniques coûteuses d'atténuation des erreurs [\\[1\\]](#references)\n", "3. **Évolutivité** : Peut traiter des problèmes comportant jusqu'à 156 qubits (156 variables binaires) avec une mise en correspondance directe des qubits [\\[1\\]](#references)\n", "4. **Performances prouvées** : Taux d'approximation de 100 % sur les instances de référence MaxCut et HUBO [\\[1\\]](#references)\n", "\n", "Voyons maintenant ce puissant algorithme en action sur notre problème de division du marché!\n", "\n" ] }, { "cell_type": "markdown", "id": "step4", "metadata": {}, "source": [ "\n", "\n", "## Étape 2 : Optimiser le problème pour l'exécution sur du matériel quantique\n", "\n", "L'algorithme bf-DCQO gère automatiquement l'optimisation des circuits, en créant des circuits quantiques peu profonds avec des termes contrediabatiques spécifiquement conçus pour le backend cible.\n", "\n", "\n", "\n", "### Configurer l'optimisation\n", "\n", "L'Optimiseur Iskay a besoin de plusieurs paramètres clés pour résoudre efficacement votre problème d'optimisation. Examinons chaque paramètre et son rôle dans le processus d'optimisation quantique :\n", "\n", "\n", "\n", "#### Paramètres obligatoires\n", "\n", "| Paramètre | Type | Description | Exemple |\n", "| -------------------- | ------------------ | --------------------------------------------------------------------- | ------------------------------------------- |\n", "| **problème métier** | `Dict[str, float]` | Coefficients QUBO au format string-key | `{\"()\": -21.0, \"(0,4)\": 0.5, \"(0,1)\": 0.5}` |\n", "| **type de problème** | `str` | Spécification du format : `\"binary\"` pour QUBO ou `\"spin\"` pour Ising | `\"binary\"` |\n", "| **nom du backend** | `str` | Dispositif quantique cible | `\"ibm_fez\"` |\n", "\n", "\n", "\n", "#### Concepts essentiels\n", "\n", "* **Format du problème** : Nous utilisons `\"binary\"` car nos variables sont binaires (0/1), représentant des affectations de marché.\n", "* **Sélection du backend** : Choisissez parmi les QPU disponibles (par exemple, `\"ibm_fez\"`) en fonction de vos besoins et de l'instance de ressources de calcul.\n", "* **Structure QUBO** : Notre dictionnaire de problèmes contient les coefficients exacts de la transformation mathématique.\n", "\n", "\n", "\n", "#### Options avancées (facultatif)\n", "\n", "Iskay offre des possibilités de réglage fin grâce à des paramètres optionnels. Bien que les valeurs par défaut conviennent à la plupart des problèmes, vous pouvez personnaliser le comportement pour répondre à des besoins spécifiques :\n", "\n", "| Paramètre | Type | Par défaut | Description |\n", "| --------------------------- | ----------- | ---------- | ------------------------------------------------------------------------------------------------------- |\n", "| **Tentatives** | `int` | 10 000 | Mesures quantiques par itération (plus élevées = plus précises) |\n", "| **nombre d'itérations** | `int` | 10 | Itérations de l'algorithme (un plus grand nombre d'itérations peut améliorer la qualité de la solution) |\n", "| **session d'utilisation** | `bool` | Oui | Utiliser les sessions IBM pour réduire les temps d'attente |\n", "| **semence\\_transpiler** | `int` | Aucun | Ensemble pour la compilation reproductible de circuits quantiques |\n", "| **cartographie directe** | `bool` | Faux | Cartographier les qubits virtuels directement en qubits physiques |\n", "| **étiquettes\\_emploi** | `List[str]` | Aucun | Étiquettes personnalisées pour le suivi des emplois |\n", "| **prétraitement Niveau** | `int` | 0 | Intensité du prétraitement du problème (0-3) - voir détails ci-dessous |\n", "| **post-traitement\\_niveau** | `int` | 2 | Niveau de raffinement de la solution (0-2) - voir détails ci-dessous |\n", "| **transpilation\\_level** | `int` | 0 | Essais d'optimisation du transpondeur (0-5) - voir détails ci-dessous |\n", "| **transpile\\_only** | `bool` | Faux | Analyse de l'optimisation des circuits sans exécution complète |\n", "\n", "**Niveaux de prétraitement (0-3)** : Particulièrement important pour les problèmes plus importants qui ne peuvent actuellement pas tenir sur les temps de cohérence du matériel. Des niveaux de prétraitement plus élevés permettent d'obtenir des circuits moins profonds grâce à des approximations dans la transpilation du problème :\n", "\n", "* **Niveau 0** : Circuits exacts et plus longs\n", "* **Niveau 1** : Bon équilibre entre la précision et l'approximation, en n'éliminant que les portes dont les angles se situent dans les 10 percentiles les plus bas\n", "* **Niveau 2** : Approximation légèrement plus élevée, en supprimant les portes dont les angles se situent dans le 20e centile le plus bas et en utilisant `approximation_degree=0.95` dans la transpilation\n", "* **Niveau 3** : Niveau d'approximation maximale, en éliminant les portes situées dans le 30e centile inférieur et en utilisant `approximation_degree=0.90` pour la transpilation\n", "\n", "**Niveaux de transpilation (0-5)** : Contrôle les essais d'optimisation avancés du transpileur pour la compilation de circuits quantiques. Cela peut entraîner une augmentation de la charge classique et, dans certains cas, ne pas modifier la profondeur du circuit. La valeur par défaut `2` conduit généralement au circuit le plus petit et est relativement rapide.\n", "\n", "* **Niveau 0** : Optimisation du circuit DCQO décomposé (layout, routing, scheduling)\n", "* **Niveau 1** : Optimisation de `PauliEvolutionGate` puis du circuit DCQO décomposé ( max\\_trials=10 )\n", "* **Niveau 2** : Optimisation de `PauliEvolutionGate` puis du circuit DCQO décomposé ( max\\_trials=15 )\n", "* **Niveau 3** : Optimisation de `PauliEvolutionGate` puis du circuit DCQO décomposé ( max\\_trials=20 )\n", "* **Niveau 4** : Optimisation de `PauliEvolutionGate` puis du circuit DCQO décomposé ( max\\_trials=25 )\n", "* **Niveau 5** : Optimisation de `PauliEvolutionGate` puis du circuit DCQO décomposé ( max\\_trials=50 )\n", "\n", "**Niveaux de post-traitement (0-2)** : Contrôlez le degré d'optimisation classique, en compensant les erreurs d'inversion de bits par un nombre différent de passages gourmands d'une recherche locale :\n", "\n", "* **Niveau 0** : 1 réussite\n", "* **Niveau 1** : 2 passages\n", "* **Niveau 2** : 3 réussites\n", "\n", "**Mode transpile uniquement** : Désormais disponible pour les utilisateurs qui souhaitent analyser l'optimisation des circuits sans exécuter l'algorithme quantique complet.\n", "\n", "\n", "\n", "#### Exemple de configuration personnalisée\n", "\n", "Voici comment vous pourriez configurer Iskay avec différents paramètres :\n", "\n", "```python\n", "custom_options = {\n", " # Higher shot count for better statistics\n", " \"shots\": 15_000,\n", "\n", " # More iterations for solution refinement\n", " \"num_iterations\": 12,\n", "\n", " # Light preprocessing for problem simplification\n", " \"preprocessing_level\": 1,\n", "\n", " # Maximum postprocessing for solution quality\n", " \"postprocessing_level\": 2,\n", "\n", " # Using higher transpilation level for circuit optimization\n", " \"transpilation_level\": 3,\n", "\n", " # Fixed seed for reproducible results\n", " \"seed_transpiler\": 42,\n", "\n", " # Custom tracking tags\n", " \"job_tags\": [\"market_split\"]\n", "}\n", "```\n", "\n" ] }, { "cell_type": "markdown", "id": "86e2b10d", "metadata": {}, "source": [ "Pour ce tutoriel, nous conserverons la plupart des paramètres par défaut et nous ne modifierons que le nombre d'itérations du champ de polarisation :\n", "\n" ] }, { "cell_type": "code", "execution_count": null, "id": "config", "metadata": {}, "outputs": [], "source": [ "# Specify the target backend\n", "backend_name = \"ibm_fez\"\n", "\n", "# Set the number of bias-field iterations and set a tag to identify the jobs\n", "options = {\n", " \"num_iterations\": 3, # Change number of bias-field iterations\n", " \"job_tags\": [\"market_split_example\"], # Tag to identify jobs\n", "}\n", "\n", "# Configure Iskay optimizer\n", "iskay_input = {\n", " \"problem\": iskay_input_problem,\n", " \"problem_type\": \"binary\",\n", " \"backend_name\": backend_name,\n", " \"options\": options,\n", "}\n", "\n", "print(\"Iskay Optimizer Configuration:\")\n", "print(\"=\" * 40)\n", "print(f\" Backend: {backend_name}\")\n", "print(f\" Problem: {len(iskay_input['problem'])} terms\")\n", "print(\" Algorithm: bf-DCQO\")" ] }, { "cell_type": "markdown", "id": "submit_intro", "metadata": {}, "source": [ "\n", "\n", "## Étape 3 : Exécutez à l'aide d' Qiskit primitives\n", "\n", "Nous soumettons maintenant notre problème pour qu'il soit exécuté sur le matériel IBM Quantum. L'algorithme bf-DCQO :\n", "\n", "1. Construire des circuits quantiques peu profonds avec des termes contrediabatiques\n", "2. Exécution d'environ 10 itérations avec optimisation du champ de polarisation\n", "3. Effectuer un post-traitement classique avec recherche locale\n", "4. Renvoyer l'affectation optimale du marché\n", "\n" ] }, { "cell_type": "code", "execution_count": null, "id": "run", "metadata": {}, "outputs": [], "source": [ "# Submit the optimization job\n", "print(\"Submitting optimization job to Kipu Quantum...\")\n", "print(\n", " f\"Problem size: {A.shape[1]} variables, {len(iskay_input['problem'])} terms\"\n", ")\n", "print(\n", " \"Algorithm: bf-DCQO (bias-field digitized counterdiabatic quantum optimization)\"\n", ")\n", "\n", "job = iskay_solver.run(**iskay_input)\n", "\n", "print(\"\\nJob successfully submitted!\")\n", "print(f\"Job ID: {job.job_id}\")\n", "print(\"Optimization in progress...\")\n", "print(\n", " f\"The bf-DCQO algorithm will efficiently explore \"\n", " f\"{2**A.shape[1]:,} possible assignments\"\n", ")" ] }, { "cell_type": "markdown", "id": "status_intro", "metadata": {}, "source": [ "\n", "\n", "### Surveiller l'état des tâches\n", "\n", "Vous pouvez vérifier l'état actuel de votre travail d'optimisation. Les statuts possibles sont les suivants :\n", "\n", "* `QUEUED`: Le travail est en attente dans la file d'attente\n", "* `RUNNING`: Le travail est en cours d'exécution sur le matériel quantique\n", "* `DONE`: Travail terminé avec succès\n", "* `CANCELED`: Le travail a été annulé\n", "* `ERROR`: Le travail a rencontré une erreur\n", "\n" ] }, { "cell_type": "code", "execution_count": null, "id": "status", "metadata": {}, "outputs": [], "source": [ "# Check job status\n", "print(f\"Job status: {job.status()}\")" ] }, { "cell_type": "markdown", "id": "wait_intro", "metadata": {}, "source": [ "\n", "\n", "### Attendez la fin\n", "\n", "Cette cellule se bloquera jusqu'à ce que le travail soit terminé. Le processus d'optimisation comprend\n", "\n", "* Temps d'attente (attente de l'accès au matériel quantique)\n", "* Temps d'exécution (exécution de l'algorithme bf-DCQO avec environ 10 itérations)\n", "* Temps de post-traitement (recherche locale classique)\n", "\n", "Les délais d'exécution typiques varient de quelques minutes à quelques dizaines de minutes en fonction des conditions de la file d'attente.\n", "\n" ] }, { "cell_type": "code", "execution_count": null, "id": "wait", "metadata": {}, "outputs": [], "source": [ "# Wait for job completion\n", "while True:\n", " status = job.status()\n", " print(\n", " f\"Waiting for job {job.job_id} to complete... (status: {status})\",\n", " end=\"\\r\",\n", " flush=True,\n", " )\n", " if status in [\"DONE\", \"CANCELED\", \"ERROR\"]:\n", " print(\n", " f\"\\nJob {job.job_id} completed with status: {status}\" + \" \" * 20\n", " )\n", " break\n", " time.sleep(30)\n", "\n", "# Retrieve the optimization results\n", "result = job.result()\n", "print(\"\\nOptimization complete!\")" ] }, { "cell_type": "markdown", "id": "step5", "metadata": {}, "source": [ "\n", "\n", "## Étape 4 : Post-traitement et restitution du résultat dans le format classique souhaité\n", "\n", "Nous procédons maintenant au post-traitement des résultats de l'exécution quantique. Comprend :\n", "\n", "* Analyse de la structure de la solution\n", "* Validation de la satisfaction des contraintes\n", "* Comparaison avec les approches classiques\n", "\n", "\n", "\n", "### Analyser les résultats\n", "\n", "\n", "\n", "#### Comprendre la structure des résultats\n", "\n", "Iskay renvoie un dictionnaire de résultats complet contenant :\n", "\n", "* **`solution`**: Un dictionnaire associant les indices des variables à leurs valeurs optimales (0 ou 1)\n", "* **`solution_info`**: Informations détaillées, y compris :\n", " * `bitstring`: L'affectation optimale sous forme de chaîne binaire\n", " * `cost`: La valeur de la fonction objective (devrait être 0 pour une satisfaction parfaite des contraintes)\n", " * `mapping`: Comment les positions des chaînes de bits correspondent aux variables du problème\n", " * `seed_transpiler`: Semence utilisée pour la reproductibilité\n", "* **`prob_type`**: Si la solution est en format binaire ou en format spin\n", "\n", "Examinons la solution renvoyée par l'optimiseur quantique.\n", "\n" ] }, { "cell_type": "code", "execution_count": null, "id": "results", "metadata": {}, "outputs": [], "source": [ "# Display the optimization results\n", "print(\"Optimization Results\")\n", "print(\"=\" * 50)\n", "print(f\"Problem Type: {result['prob_type']}\")\n", "print(\"\\nSolution Info:\")\n", "print(f\" Bitstring: {result['solution_info']['bitstring']}\")\n", "print(f\" Cost: {result['solution_info']['cost']}\")\n", "print(\"\\nSolution (first 10 variables):\")\n", "for i, (var, val) in enumerate(list(result[\"solution\"].items())[:10]):\n", " print(f\" {var}: {val}\")\n", "print(\" ...\")" ] }, { "cell_type": "markdown", "id": "validation_intro", "metadata": {}, "source": [ "\n", "\n", "#### Validation de la solution\n", "\n", "Nous vérifions maintenant si la solution quantique satisfait aux contraintes du fractionnement du marché. Le processus de validation vérifie :\n", "\n", "**Qu'est-ce qu'une violation de contrainte?**\n", "\n", "* Pour chaque produit $i$, nous calculons les ventes réelles dans la région A : $(Ax)_i$\n", "* Nous comparons ce chiffre à l'objectif de vente $b_i$\n", "* La **violation** est la différence absolue : $|(Ax)_i - b_i|$\n", "* Une **solution réalisable** ne comporte aucune violation pour tous les produits\n", "\n", "**Ce que nous attendons :**\n", "\n", "* **Cas idéal** : Violation totale = 0 (toutes les contraintes sont parfaitement satisfaites)\n", " * La région A reçoit exactement 1002 unités du produit 1, 879 unités du produit 2 et 1040 unités du produit 3\n", " * La région B reçoit les unités restantes (également 1002, 879 et 1040 respectivement)\n", "* **Bon cas** : La violation totale est faible (solution quasi-optimale)\n", "* **Mauvais cas** : Les violations importantes indiquent que la solution ne répond pas aux exigences de l'entreprise\n", "\n", "La fonction de validation calcule :\n", "\n", "1. Ventes réelles par produit dans chaque région\n", "2. Violations des contraintes pour chaque produit\n", "3. Répartition du marché entre les régions\n", "\n" ] }, { "cell_type": "code", "execution_count": null, "id": "validate", "metadata": {}, "outputs": [], "source": [ "def validate_solution(A, b, solution):\n", " \"\"\"Validate market split solution.\"\"\"\n", " x = np.array(solution)\n", " region_a = A @ x\n", " region_b = A @ (1 - x)\n", " violations = np.abs(region_a - b)\n", "\n", " return {\n", " \"target\": b,\n", " \"region_a\": region_a,\n", " \"region_b\": region_b,\n", " \"violations\": violations,\n", " \"total_violation\": np.sum(violations),\n", " \"is_feasible\": np.sum(violations) == 0,\n", " \"region_a_markets\": int(np.sum(x)),\n", " \"region_b_markets\": len(x) - int(np.sum(x)),\n", " }\n", "\n", "\n", "# Convert bitstring to list of integers and validate\n", "optimal_assignment = [\n", " int(bit) for bit in result[\"solution_info\"][\"bitstring\"]\n", "]\n", "validation = validate_solution(A, b, optimal_assignment)" ] }, { "cell_type": "markdown", "id": "validation_results_intro", "metadata": {}, "source": [ "\n", "\n", "#### Interpréter les résultats de la validation\n", "\n", "Les résultats de la validation indiquent si l'optimiseur quantique a trouvé une solution réalisable. Examinons les points suivants :\n", "\n", "**Contrôle de faisabilité :**\n", "\n", "* **`is_feasible = True`** signifie que la solution satisfait parfaitement toutes les contraintes (violation totale = 0)\n", "* **`is_feasible = False`** signifie que certaines contraintes sont violées\n", "\n", "**Analyse des ventes :**\n", "\n", "* Comparer les ventes cibles et les ventes réelles pour chaque produit\n", "* Pour une solution parfaite : Réel = Objectif pour tous les produits dans les deux régions\n", "* La différence indique à quel point nous sommes proches de la répartition souhaitée du marché\n", "\n", "**Répartition du marché :**\n", "\n", "* Indique le nombre de marchés attribués à chaque région\n", "* Il n'est pas nécessaire d'avoir un nombre égal de marchés, mais seulement d'atteindre les objectifs de vente\n", "\n" ] }, { "cell_type": "code", "execution_count": null, "id": "display_validation", "metadata": {}, "outputs": [], "source": [ "print(\"Solution Validation\")\n", "print(\"=\" * 50)\n", "print(f\"Feasible solution: {validation['is_feasible']}\")\n", "print(f\"Total constraint violation: {validation['total_violation']}\")\n", "\n", "print(\"\\nSales Analysis (Target vs Actual):\")\n", "for i, (target, actual_a, actual_b) in enumerate(\n", " zip(validation[\"target\"], validation[\"region_a\"], validation[\"region_b\"])\n", "):\n", " violation_a = abs(actual_a - target)\n", " violation_b = abs(actual_b - target)\n", " print(f\" Product {i+1}:\")\n", " print(f\" Target: {target}\")\n", " print(f\" Region A: {actual_a} (violation: {violation_a})\")\n", " print(f\" Region B: {actual_b} (violation: {violation_b})\")\n", "\n", "print(\"\\nMarket Distribution:\")\n", "print(f\" Region A: {validation['region_a_markets']} markets\")\n", "print(f\" Region B: {validation['region_b_markets']} markets\")" ] }, { "cell_type": "markdown", "id": "interpretation", "metadata": {}, "source": [ "\n", "\n", "#### Évaluation de la qualité de la solution\n", "\n", "Sur la base des résultats de validation ci-dessus, nous pouvons évaluer la qualité de la solution quantique :\n", "\n", "**Si `is_feasible = True` (violation totale = 0) :**\n", "\n", "* L'optimiseur quantique a trouvé une solution optimale\n", "* Toutes les contraintes de l'entreprise sont parfaitement satisfaites\n", "* Cela démontre l'avantage quantique sur un problème pour lequel les solveurs classiques ont des difficultés [\\[4\\]](#references)\n", "\n", "**Si `is_feasible = False` (violation totale > 0) :**\n", "\n", "* La solution est quasi-optimale mais pas parfaite\n", "* De petites violations peuvent être acceptables dans la pratique\n", "* Envisager d'ajuster les paramètres de l'optimiseur :\n", " * Augmenter `num_iterations` pour plus de passes d'optimisation\n", " * Augmenter `postprocessing_level` pour un raffinement plus classique\n", " * Augmenter `shots` pour de meilleures statistiques de mesure\n", "\n", "**Interprétation de la fonction de coût :**\n", "\n", "* La valeur `cost` de `solution_info` est égale à $||Ax - b||^2$\n", "* Le coût = 0 indique une satisfaction parfaite des contraintes\n", "* Des valeurs de coût plus élevées indiquent des violations de contraintes plus importantes\n", "\n" ] }, { "cell_type": "markdown", "id": "conclusion", "metadata": {}, "source": [ "\n", "\n", "## Conclusion\n", "\n", "\n", "\n", "### Ce que nous avons accompli\n", "\n", "Dans ce tutoriel, nous avons réussi :\n", "\n", "1. **Chargement d'un problème d'optimisation réel** : obtention d'une instance difficile de Market Split à partir de la bibliothèque de référence QOBLIB \\[2]\n", "2. **Transformé au format QUBO** : Conversion du problème contraint en une formulation quadratique sans contrainte \\[3]\n", "3. **Exploitation d'algorithmes quantiques avancés** : Utilisation de l'algorithme bf-DCQO de Kipu Quantum avec des termes contrediabatiques \\[1]\n", "4. **Obtention de solutions optimales** : Recherche de solutions réalisables satisfaisant toutes les contraintes\n", "\n", "\n", "\n", "### Points essentiels à retenir\n", "\n", "**Innovation algorithmique** : L'algorithme bf-DCQO représente une avancée significative [\\[1\\] :](#references)\n", "\n", "* **10 fois moins de portes** que le recuit quantique numérique\n", "* **Environ 10 itérations** au lieu d'environ 100 pour les méthodes variationnelles\n", "* **Résistance aux erreurs intégrée** grâce à l'efficacité du circuit\n", "\n", "**Termes contrediabatiques** : Permettent une évolution quantique rapide tout en maintenant la fidélité de l'état fondamental, rendant l'optimisation quantique pratique sur le matériel bruyant d'aujourd'hui [\\[1\\].](#references)\n", "\n", "**Guidage par champ de biais** : L'approche itérative du champ de biais permet à chaque itération de commencer à proximité de bonnes solutions trouvées précédemment, ce qui constitue une forme de recherche locale améliorée sur le plan quantique [\\[1\\].](#references)\n", "\n", "\n", "\n", "### Etapes suivantes\n", "\n", "Pour approfondir votre compréhension et explorer davantage :\n", "\n", "1. **Essayez différentes instances** : Expérimentez d'autres instances QOBLIB de tailles différentes\n", "2. **Régler les paramètres** : Ajuster `num_iterations`, `preprocessing_level`, `postprocessing_level`\n", "3. **Comparaison avec les** solutions classiques : comparaison avec les solveurs d'optimisation classiques\n", "4. **Essayez différentes stratégies** : Essayer de trouver un meilleur encodage pour le problème ou le formuler comme HUBO (si possible)\n", "5. **Appliquer à votre domaine** : Adapter les techniques de formulation QUBO/HUBO à vos propres problèmes d'optimisation\n", "\n", "\n", "\n", "### Références\n", "\n", "\\[1] IBM Quantum. \" [Optimisation quantique de Kipu](/docs/guides/kipu-optimization) \" *IBM Quantum Documentation*.\n", "\n", "\\[2] QOBLIB - Quantum Optimization Benchmarking Library (bibliothèque d'évaluation comparative de l'optimisation quantique). Institut Zuse de Berlin (ZIB). [https://git.zib.de/qopt/qoblib-quantum-optimization-benchmarking-library](https://git.zib.de/qopt/qoblib-quantum-optimization-benchmarking-library)\n", "\n", "\\[3] Glover, F., Kochenberger, G. et Du, Y. (2019). \"Quantum bridge analytics I : a tutorial on formulating and using QUBO models\" *4OR: A Quarterly Journal of Operations Research*, 17(4), 335-371.\n", "\n", "\\[4] Lodi, A., Tramontani, A. et Weninger, K. (2023). \"The Intractable Decathlon : Benchmarking Hard Combinatorial Problems\" *INFORMS Journal on Computing*.\n", "\n" ] }, { "cell_type": "markdown", "metadata": {}, "id": "a1b8767d", "source": "© IBM Corp., 2017-2026" } ], "metadata": { "kernelspec": { "display_name": "Python 3", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3" }, "hours": 1, "qpuSeconds": 20 }, "nbformat": 4, "nbformat_minor": 5 }