Résoudre le problème de Market Split avec l'Iskay Quantum Optimizer de Kipu Quantum

Remarque

Les Qiskit Functions sont une fonctionnalité expérimentale disponible uniquement pour les utilisateurs des plans IBM Quantum® Premium, Flex et On-Prem (via l'API IBM Quantum Platform). Elles sont en version préliminaire et sont susceptibles d'être modifiées.

Estimation d'utilisation : 20 secondes sur un processeur Heron r2. (REMARQUE : Il s'agit d'une estimation uniquement. Votre temps d'exécution peut varier.)

Contexte

Ce tutoriel montre comment résoudre le problème de Market Split à l'aide de l'optimiseur quantique Iskay de Kipu Quantum [1]. Le problème de Market Split représente un défi réel d'allocation de ressources où les marchés doivent être répartis en régions de vente équilibrées pour répondre à des objectifs de demande précis.

Le défi du Market Split

Le problème de Market Split présente un défi d'allocation de ressources d'apparence simple mais redoutablement complexe sur le plan computationnel. Considérons une entreprise avec $m$ produits vendus sur $n$ marchés différents, où chaque marché achète un ensemble spécifique de produits (représenté par les colonnes de la matrice $A$). L'objectif commercial est de répartir 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.

Formulation mathématique :

Nous cherchons un vecteur d'affectation binaire $x$, où :

• $x_j = 1$ affecte le marché $j$ à la Région A
• $x_j = 0$ affecte le marché $j$ à la Région B
• La contrainte $Ax = b$ doit être satisfaite, où $b$ représente les ventes cibles (typiquement la moitié de la demande totale par produit)

Fonction de coût :

Pour résoudre ce problème, nous minimisons la violation quadratique des contraintes :

$C(x) = ||Ax - b||^2 = \sum_{i=1}^{m} \left(\sum_{j=1}^{n} A_{ij}x_j - b_i\right)^2$

où :

• $A_{ij}$ représente les ventes du produit $i$ sur le marché $j$
• $x_j \in \{0,1\}$ est l'affectation binaire du marché $j$
• $b_i$ est l'objectif de ventes pour le produit $i$ dans chaque région
• Le coût est nul précisément lorsque toutes les contraintes sont satisfaites

Chaque terme de la somme représente l'écart quadratique par rapport aux ventes cibles pour un produit donné. En développant cette fonction de coût, nous obtenons :

$C(x) = x^T A^T A x - 2b^T A x + b^T b$

Puisque $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).

Complexité computationnelle :

Malgré son interprétation commerciale directe, ce problème présente une intractabilité computationnelle remarquable :

• Échec à petite échelle : les solveurs conventionnels de programmation mixte en nombres entiers échouent sur des instances avec aussi peu que sept produits dans un délai d'une heure [4]
• Croissance exponentielle : l'espace des solutions croît de manière exponentielle ($2^n$ affectations possibles), rendant les approches par force brute irréalisables

Cette barrière computationnelle sévère, combinée à sa pertinence pratique pour la planification territoriale et l'allocation de ressources, fait du problème de Market Split un banc d'essai idéal pour les algorithmes d'optimisation quantique [4].

Qu'est-ce qui rend l'approche d'Iskay unique ?

L'optimiseur Iskay utilise l'algorithme bf-DCQO (bias-field digitized counterdiabatic quantum optimization) [1], qui représente une avancée significative en optimisation quantique :

Efficacité des circuits : l'algorithme bf-DCQO atteint une réduction remarquable du nombre de portes [1] :

• Jusqu'à 10 fois moins de portes intriquantes que le Digital Quantum Annealing (DQA)
• Des circuits significativement moins profonds permettent :
  • Moins d'accumulation d'erreurs lors de l'exécution quantique
  • La capacité de traiter des problèmes plus importants sur le matériel quantique actuel
  • Aucun besoin de techniques d'atténuation d'erreurs

Conception non variationnelle : contrairement aux algorithmes variationnels nécessitant environ 100 itérations, bf-DCQO n'a généralement besoin que d'environ 10 itérations [1]. Cela est obtenu grâce à :

• Des calculs intelligents de champ de biais à partir des distributions d'états mesurés
• Le démarrage de chaque itération à partir d'un état d'énergie proche de la solution précédente
• Un post-traitement classique intégré avec recherche locale

Protocoles contreadiabatiques : l'algorithme incorpore des termes contreadiabatiques qui suppriment les excitations quantiques indésirables pendant les temps d'évolution courts, permettant au système de rester proche de l'état fondamental même lors de transitions rapides [1].

Prérequis

Avant de commencer ce tutoriel, assurez-vous d'avoir installé les éléments suivants :

• Qiskit IBM Runtime (pip install qiskit-ibm-runtime)
• Qiskit Functions (pip install qiskit-ibm-catalog)
• NumPy (pip install numpy)
• Requests (pip install requests)
• Opt Mapper Qiskit addon (pip install qiskit-addon-opt-mapper)

Vous devrez également obtenir l'accès à la fonction Iskay Quantum Optimizer depuis le catalogue Qiskit Functions.

Configuration

Commencez par importer tous les paquets requis pour ce tutoriel.

# Added by doQumentation — installs packages not in the Binder environment
%pip install -q qiskit-addon-opt-mapper

import os
import tempfile
import time
from typing import Tuple, Optional

import numpy as np
import requests

from qiskit_ibm_catalog import QiskitFunctionsCatalog

from qiskit_addon_opt_mapper import OptimizationProblem
from qiskit_addon_opt_mapper.converters import OptimizationProblemToQubo

print("All required libraries imported successfully")

Configurer les identifiants IBM Quantum

Définissez vos identifiants IBM Quantum® Platform. Vous aurez besoin de :

• Jeton API : votre clé API de 44 caractères depuis IBM Quantum Platform
• CRN de l'instance : l'identifiant de votre instance IBM Cloud®

token = "<YOUR_API_KEY>"
instance = "<YOUR_INSTANCE_CRN>"

Étape 1 : Transposer les entrées classiques en un problème quantique

Nous commençons par transposer notre problème classique en une représentation compatible avec le quantique. Cette étape comprend :

1. La connexion à l'Iskay Quantum Optimizer
2. Le chargement et la formulation du problème de Market Split
3. La compréhension de l'algorithme bf-DCQO qui le résoudra

Se connecter à l'Iskay Quantum Optimizer

Nous commençons par établir une connexion au catalogue Qiskit Functions et charger l'Iskay Quantum Optimizer. L'optimiseur Iskay est une fonction quantique fournie par Kipu Quantum qui implémente l'algorithme bf-DCQO pour résoudre des problèmes d'optimisation sur du matériel quantique.

catalog = QiskitFunctionsCatalog(token=token, instance=instance)
iskay_solver = catalog.load("kipu-quantum/iskay-quantum-optimizer")

print("Iskay optimizer loaded successfully")
print("Ready to solve optimization problems using bf-DCQO algorithm")

Charger et formuler le problème

Comprendre le format des données du problème

Les instances de problèmes provenant de QOBLIB (Quantum Optimization Benchmarking Library) [2] sont stockées dans un format texte simple. Examinons le contenu réel de notre instance cible ms_03_200_177.dat :

3 20
60   92  161   53   97    2   75   81    6  139  132   45  108  112  181   93  152  200  164   51 1002
176  196   41  143    2   88    0   79   10   71   75  148   82  135   34  187   33  155   58   46  879
68   68  179  173  127  163   48   49   99   78   44   52  173  131   73  198   84  109  180   95 1040

Structure du format :

• Première ligne : 3 20

  • 3 = nombre de produits (contraintes/lignes dans la matrice $A$)
  • 20 = nombre de marchés (variables/colonnes dans la matrice $A$)

• 3 lignes suivantes : Matrice de coefficients $A$ et vecteur cible $b$

  • Chaque ligne contient 21 nombres : les 20 premiers sont les coefficients de la ligne, le dernier est la cible
  • Ligne 2 : 60 92 161 ... 51 | 1002
    • Les 20 premiers nombres : quantité du Produit 1 vendue par chacun des 20 marchés
    • Dernier nombre (1002) : ventes cibles pour le Produit 1 dans une région
  • Ligne 3 : 176 196 41 ... 46 | 879
    • Ventes du Produit 2 par marché et cible (879)
  • Ligne 4 : 68 68 179 ... 95 | 1040
    • Ventes du Produit 3 par marché et cible (1040)

Interprétation commerciale :

• Le Marché 0 vend : 60 unités du Produit 1, 176 unités du Produit 2, 68 unités du Produit 3
• Le Marché 1 vend : 92 unités du Produit 1, 196 unités du Produit 2, 68 unités du Produit 3
• Et ainsi de suite pour les 20 marchés...
• Objectif : Répartir ces 20 marchés en deux régions où chaque région obtient exactement 1002 unités du Produit 1, 879 unités du Produit 2 et 1040 unités du Produit 3

Transformation QUBO

Des contraintes au QUBO : la transformation mathématique

La puissance de l'optimisation quantique réside dans la transformation de problèmes contraints en formes quadratiques non contraintes [4]. Pour le problème de Market Split, nous convertissons les contraintes d'égalité

$Ax = b$

où $x ∈ \{0,1\}^n$, en un QUBO en pénalisant les violations de contraintes.

La méthode de pénalité : Puisque nous avons besoin que $Ax = b$ soit exactement respecté, nous minimisons la violation quadratique : $f(x) = ||Ax - b||^2$

Celle-ci est nulle précisément lorsque toutes les contraintes sont satisfaites. En développant algébriquement : $f(x) = (Ax - b)^T(Ax - b) = x^T A^T A x - 2b^T A x + b^T b$

Objectif 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$

Point clé : Cette transformation est exacte, pas approximative. Les contraintes d'égalité se mettent naturellement au carré sous forme quadratique sans nécessiter de variables auxiliaires ni de paramètres de pénalité — ce qui rend cette formulation mathématiquement élégante et computationnellement efficace pour les solveurs quantiques [4]. Nous utiliserons la classe OptimizationProblem pour définir notre problème contraint, puis le convertirons au format QUBO à l'aide de OptimizationProblemToQubo, les deux provenant du paquet qiskit_addon_opt_mapper. Cela gère automatiquement la transformation basée sur les pénalités.

Implémenter les fonctions de chargement des données et de conversion QUBO

Nous définissons maintenant trois fonctions utilitaires :

1. parse_marketsplit_dat() - Analyse le format de fichier .dat et extrait les matrices $A$ et $b$
2. fetch_marketsplit_data() - Télécharge les instances de problèmes directement depuis le dépôt QOBLIB

def parse_marketsplit_dat(filename: str) -> Tuple[np.ndarray, np.ndarray]:
    """
    Parse a market split problem from a .dat file format.

    Parameters
    ----------
    filename : str
        Path to the .dat file containing the market split problem data.

    Returns
    -------
    A : np.ndarray
        Coefficient matrix of shape (m, n) where m is the number of products
        and n is the number of markets.
    b : np.ndarray
        Target vector of shape (m,) containing the target sales per product.
    """
    with open(filename, "r", encoding="utf-8") as f:
        lines = [
            line.strip()
            for line in f
            if line.strip() and not line.startswith("#")
        ]

    if not lines:
        raise ValueError("Empty or invalid .dat file")

    # First line: m n (number of products and markets)
    m, n = map(int, lines[0].split())

    # Next m lines: each row of A followed by corresponding element of b
    A, b = [], []
    for i in range(1, m + 1):
        values = list(map(int, lines[i].split()))
        A.append(values[:-1])  # First n values: product sales per market
        b.append(values[-1])  # Last value: target sales for this product

    return np.array(A, dtype=np.int32), np.array(b, dtype=np.int32)

def fetch_marketsplit_data(
    instance_name: str = "ms_03_200_177.dat",
) -> Tuple[Optional[np.ndarray], Optional[np.ndarray]]:
    """
    Fetch market split data directly from the QOBLIB repository.

    Parameters
    ----------
    instance_name : str
        Name of the .dat file to fetch (default: "ms_03_200_177.dat").

    Returns
    -------
    A : np.ndarray or None
        Coefficient matrix if successful, None if failed.
    b : np.ndarray or None
        Target vector if successful, None if failed.
    """
    url = f"https://git.zib.de/qopt/qoblib-quantum-optimization-benchmarking-library/-/raw/main/01-marketsplit/instances/{instance_name}"

    try:
        response = requests.get(url, timeout=30)
        response.raise_for_status()

        with tempfile.NamedTemporaryFile(
            mode="w", suffix=".dat", delete=False, encoding="utf-8"
        ) as f:
            f.write(response.text)
            temp_path = f.name

        try:
            return parse_marketsplit_dat(temp_path)
        finally:
            os.unlink(temp_path)
    except Exception as e:
        print(f"Error: {e}")
        return None, None

Charger l'instance du problème

Nous chargeons maintenant l'instance de problème spécifique ms_03_200_177.dat depuis QOBLIB [2]. Cette instance possède :

• 3 produits (contraintes)
• 20 marchés (variables de décision binaires)
• Plus d'un million d'affectations de marchés possibles à explorer ($2^{20} = 1\,048\,576$)

# Load the problem instance
instance_name = "ms_03_200_177.dat"
A, b = fetch_marketsplit_data(instance_name=instance_name)

if A is not None:
    print("Successfully loaded problem instance from QOBLIB")
    print("\nProblem Instance Analysis:")
    print("=" * 50)
    print(f"Coefficient Matrix A: {A.shape[0]} × {A.shape[1]}")
    print(f"   → {A.shape[0]} products (constraints)")
    print(f"   → {A.shape[1]} markets (decision variables)")
    print(f"Target Vector b: {b}")
    print("   → Target sales per product for each region")
    print(
        f"Solution Space: 2^{A.shape[1]} = {2**A.shape[1]:,} possible assignments"
    )

Convertir au format QUBO

Nous transformons maintenant le problème d'optimisation contraint au format QUBO :

# Create optimization problem
ms = OptimizationProblem(instance_name.replace(".dat", ""))

# Add binary variables (one for each market)
ms.binary_var_list(A.shape[1])

# Add equality constraints (one for each product)
for idx, rhs in enumerate(b):
    ms.linear_constraint(A[idx, :], sense="==", rhs=rhs)

# Convert to QUBO with penalty parameter
qubo = OptimizationProblemToQubo(penalty=1).convert(ms)

print("QUBO Conversion Complete:")
print("=" * 50)
print(f"Number of variables: {qubo.get_num_vars()}")
print(f"Constant term: {qubo.objective.constant}")
print(f"Linear terms: {len(qubo.objective.linear.to_dict())}")
print(f"Quadratic terms: {len(qubo.objective.quadratic.to_dict())}")

Convertir le QUBO au format Iskay

Nous devons maintenant convertir l'objet QUBO dans le format dictionnaire requis par l'optimiseur Iskay de Kipu Quantum.

Les arguments problem et problem_type encodent un problème d'optimisation de la forme

$$\begin{align} \min_{(x_1, x_2, \ldots, x_n) \in D} C(x_1, x_2, \ldots, x_n) \nonumber \end{align}$$

où

$$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}$$

• En choisissant problem_type = "binary", vous spécifiez que la fonction de coût est au format binary, ce qui signifie que $D = \{0, 1\}^{n}$, c'est-à-dire que la fonction de coût est écrite sous forme QUBO/HUBO.
• D'autre part, en choisissant problem_type = "spin", la fonction de coût est écrite sous forme Ising, où $D = \{-1, 1\}^{n}$.

Les coefficients du problème doivent être encodés dans un dictionnaire comme suit :

$$\begin{align} \nonumber &\texttt{\{} \\ \nonumber &\texttt{"()"}&: \quad &a, \\ \nonumber &\texttt{"(i,)"}&: \quad &b_i, \\ \nonumber &\texttt{"(i, j)"}&: \quad &c_{i, j}, \quad (i \neq j) \\ \nonumber &\quad \vdots \\ \nonumber &\texttt{"(} k_1, ..., k_m \texttt{)"}&: \quad &g_{k_1, ..., k_m}, \quad (k_1 \neq k_2 \neq \dots \neq k_m) \\ \nonumber &\texttt{\}} \end{align}$$

Notez que les clés du dictionnaire doivent être des chaînes de caractères contenant un tuple valide d'entiers non répétés. Pour les problèmes binaires, nous savons que :

$$x_i^2 = x_i$$

pour $i=j$ (puisque $x_i \in \{0,1\}$ implique $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 :

Coefficient linéaire total pour la variable $x_i$ : $b_i + c_{i,i}$

Cela signifie :

• Les termes linéaires comme "(i, )" contiennent : le coefficient linéaire original + le coefficient quadratique diagonal
• Les termes quadratiques diagonaux comme "(i, i)" ne doivent PAS apparaître dans le dictionnaire final
• Seuls les termes quadratiques hors diagonale comme "(i, j)" où $i \neq j$ doivent être inclus comme entrées séparées

Exemple : Si votre QUBO contient $3x_1 + 2x_1^2 + 4x_1 x_2$, le dictionnaire Iskay doit contenir :

• "(0, )" : 5.0 (combinaison de $3 + 2 = 5$)
• "(0, 1)" : 4.0 (terme hors diagonale)

Et NON des entrées séparées pour "(0, )" : 3.0 et "(0, 0)" : 2.0.

# Convert QUBO to Iskay dictionary format:

# Create empty Iskay input dictionary
iskay_input_problem = {}

# Convert QUBO to Iskay dictionary format
iskay_input_problem = {"()": qubo.objective.constant}

for i in range(qubo.get_num_vars()):
    for j in range(i, qubo.get_num_vars()):
        if i == j:
            # Add linear term (including diagonal quadratic contribution)
            iskay_input_problem[f"({i}, )"] = float(
                qubo.objective.linear.to_dict().get(i)
            ) + float(qubo.objective.quadratic.to_dict().get((i, i)))
        else:
            # Add off-diagonal quadratic term
            iskay_input_problem[f"({i}, {j})"] = float(
                qubo.objective.quadratic.to_dict().get((i, j))
            )

# Display Iskay dictionary summary
print("Iskay Dictionary Format:")
print("=" * 50)
print(f"Total coefficients: {len(iskay_input_problem)}")
print(f"  • Constant term: {iskay_input_problem['()']}")
print(
    f"  • Linear terms: {sum(1 for k in iskay_input_problem.keys() if k != '()' and ', )' in k)}"
)
print(
    f"  • Quadratic terms: {sum(1 for k in iskay_input_problem.keys() if k != '()' and ', )' not in k)}"
)
print("\nSample coefficients:")

# Get first 10 and last 5 items properly
items = list(iskay_input_problem.items())
first_10 = list(enumerate(items[:10]))
last_5 = list(enumerate(items[-5:], start=len(items) - 5))

for i, (key, value) in first_10 + last_5:
    coeff_type = (
        "constant"
        if key == "()"
        else "linear"
        if ", )" in key
        else "quadratic"
    )
    print(f"  {key}: {value} ({coeff_type})")
print("  ...")
print("\n✓ Problem ready for Iskay optimizer!")

Comprendre l'algorithme bf-DCQO

Avant de lancer l'optimisation, comprenons l'algorithme quantique sophistiqué qui alimente Iskay : bf-DCQO (bias-field digitized counterdiabatic quantum optimization) [1].

Qu'est-ce que bf-DCQO ?

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) du Hamiltonien quantique final [1]. L'algorithme répond à un défi fondamental de l'optimisation quantique :

Le défi : le calcul quantique adiabatique traditionnel 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, entraînant davantage d'opérations de portes et d'erreurs accumulées.

La solution : bf-DCQO utilise des protocoles contreadiabatiques pour permettre une évolution rapide tout en maintenant la fidélité de l'état fondamental, réduisant considérablement la profondeur des circuits.

Cadre mathématique

L'algorithme minimise une fonction de coût de la forme :

$\min_{(x_1,x_2,...,x_n) \in D} C(x_1,x_2,...,x_n)$

où $D = \{0,1\}^n$ pour les variables binaires et :

$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}$

Pour notre problème de Market Split, la fonction de coût est :

$C(x) = ||Ax - b||^2 = x^T A^T A x - 2 b^T A x + b^T b$

Le rôle des termes contreadiabatiques

Les termes contreadiabatiques sont des termes supplémentaires introduits dans le Hamiltonien dépendant du temps qui suppriment les excitations indésirables pendant l'évolution quantique. Voici pourquoi ils sont essentiels :

En optimisation quantique adiabatique, nous faisons évoluer le système selon un Hamiltonien dépendant du temps :

$H(t) = \left(1 - \frac{t}{T}\right) H_{\text{initial}} + \frac{t}{T} H_{\text{problem}}$

où $H_{\text{problem}}$ encode notre problème d'optimisation. Pour maintenir l'état fondamental lors d'une évolution rapide, nous ajoutons des termes contreadiabatiques :

$H_{\text{CD}}(t) = H(t) + H_{\text{counter}}(t)$

Ces termes contreadiabatiques ont les effets suivants :

1. Suppression des transitions indésirables : empêchent l'état quantique de sauter vers des états excités lors d'une évolution rapide
2. Temps d'évolution plus courts : permettent d'atteindre l'état final beaucoup plus rapidement sans violer l'adiabaticité
3. Réduction de la profondeur des circuits : une évolution plus courte conduit à moins de portes et moins d'erreurs

L'impact pratique est spectaculaire : bf-DCQO utilise jusqu'à 10 fois moins de portes intriquantes que le Digital Quantum Annealing [1], le rendant praticable sur le matériel quantique bruyant d'aujourd'hui.

Optimisation itérative par champ de biais

Contrairement aux algorithmes variationnels qui optimisent les paramètres du circuit à travers de nombreuses itérations, bf-DCQO utilise une approche guidée par champ de biais qui converge en environ 10 itérations [1] :

Processus itératif :

1. Évolution quantique initiale : démarrer avec un circuit quantique implémentant le protocole d'évolution contreadiabatique

2. Mesure : mesurer l'état quantique pour obtenir une distribution de probabilité sur les chaînes de bits

3. Calcul du champ de biais : analyser les statistiques de mesure et calculer un champ de biais optimal $h_i$ pour chaque Qubit : $h_i = \text{f}(\text{measurement statistics}, \text{previous solutions})$

4. Itération suivante : le champ de biais modifie le Hamiltonien pour l'itération suivante : $H_{\text{next}} = H_{\text{problem}} + \sum_i h_i \sigma_i^z$

   Cela permet de démarrer près de la bonne solution trouvée précédemment, effectuant ainsi une forme de « recherche locale quantique »

5. Convergence : répéter jusqu'à ce que la qualité de la solution se stabilise ou qu'un nombre maximal d'itérations soit atteint

Avantage clé : chaque itération apporte une progression 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.

Post-traitement classique intégré

Après la convergence de l'optimisation quantique, Iskay effectue un post-traitement classique de recherche locale :

• Exploration par inversion de bits : inverser systématiquement ou aléatoirement des bits dans la meilleure solution mesurée
• Évaluation de l'énergie : calculer $C(x)$ pour chaque solution modifiée
• Sélection gloutonne : accepter les améliorations qui diminuent la fonction de coût
• Passes multiples : effectuer plusieurs passes (contrôlées par postprocessing_level)

Cette approche hybride compense les erreurs d'inversion de bits dues aux imperfections matérielles et aux erreurs de lecture, garantissant des solutions de haute qualité même sur des dispositifs quantiques bruyants.

Pourquoi bf-DCQO excelle sur le matériel actuel

L'algorithme bf-DCQO est spécifiquement conçu pour exceller sur les dispositifs quantiques actuels à échelle intermédiaire bruyante (NISQ) [1] :

1. Résilience aux erreurs : moins de portes (réduction de 10 fois) signifie considérablement moins d'accumulation d'erreurs
2. Aucune atténuation d'erreurs requise : l'efficacité inhérente de l'algorithme élimine le besoin de techniques coûteuses d'atténuation d'erreurs [1]
3. Évolutivité : peut traiter des problèmes jusqu'à 156 Qubits (156 variables binaires) avec un mappage direct des Qubits [1]
4. Performance prouvée : atteint des ratios d'approximation de 100 % sur les instances de référence MaxCut et HUBO [1]

Voyons maintenant cet algorithme puissant en action sur notre problème de Market Split !

Étape 2 : Optimiser le problème pour l'exécution sur matériel quantique

L'algorithme bf-DCQO gère automatiquement l'optimisation des circuits, créant des circuits quantiques peu profonds avec des termes contreadiabatiques spécifiquement conçus pour le Backend cible.

Configurer l'optimisation

L'optimiseur Iskay nécessite 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 :

Paramètres requis

Paramètre	Type	Description	Exemple
problem	Dict[str, float]	Coefficients QUBO au format clé-chaîne	{"()": -21.0, "(0,4)": 0.5, "(0,1)": 0.5}
problem_type	str	Spécification du format : "binary" pour QUBO ou "spin" pour Ising	"binary"
backend_name	str	Dispositif quantique cible	"ibm_fez"

Concepts essentiels

• Format du problème : nous utilisons "binary" puisque nos variables sont binaires (0/1), représentant les affectations de marchés.
• Sélection du Backend : choisissez parmi les QPU disponibles (par exemple, "ibm_fez") en fonction de vos besoins et de votre instance de ressources de calcul.
• Structure QUBO : notre dictionnaire de problème contient les coefficients exacts issus de la transformation mathématique.

Options avancées (optionnelles)

Iskay fournit des capacités d'ajustement fin via des paramètres optionnels. Bien que les valeurs par défaut fonctionnent bien pour la plupart des problèmes, vous pouvez personnaliser le comportement pour des exigences spécifiques :

Paramètre	Type	Par défaut	Description
shots	int	10000	Mesures quantiques par itération (plus élevé = plus précis)
num_iterations	int	10	Itérations de l'algorithme (plus d'itérations peuvent améliorer la qualité de la solution)
use_session	bool	True	Utiliser les sessions IBM pour des temps d'attente réduits
seed_transpiler	int	None	Définir pour une compilation reproductible des circuits quantiques
direct_qubit_mapping	bool	False	Mapper les Qubits virtuels directement sur les Qubits physiques
job_tags	List[str]	None	Tags personnalisés pour le suivi des tâches
preprocessing_level	int	0	Intensité du prétraitement du problème (0-3) - voir les détails ci-dessous
postprocessing_level	int	2	Niveau de raffinement de la solution (0-2) - voir les détails ci-dessous
transpilation_level	int	0	Essais d'optimisation du Transpiler (0-5) - voir les détails ci-dessous
transpile_only	bool	False	Analyser l'optimisation du circuit sans exécuter l'ensemble du processus

Niveaux de prétraitement (0-3) : particulièrement importants pour les problèmes plus importants qui ne peuvent actuellement pas tenir dans les temps de cohérence du matériel. Des niveaux de prétraitement plus élevés atteignent des profondeurs de circuit plus faibles par des approximations dans la transpilation du problème :

• Niveau 0 : exact, circuits plus longs
• Niveau 1 : bon équilibre entre précision et approximation, éliminant uniquement les portes avec des angles dans le 10e percentile le plus bas
• Niveau 2 : approximation légèrement plus élevée, éliminant les portes avec des angles dans le 20e percentile le plus bas et utilisant approximation_degree=0.95 dans la transpilation
• Niveau 3 : niveau d'approximation maximal, éliminant les portes dans le 30e percentile le plus bas et utilisant approximation_degree=0.90 dans la transpilation

Niveaux de transpilation (0-5) : contrôlent les essais avancés d'optimisation du Transpiler pour la compilation des circuits quantiques. Cela peut entraîner une augmentation de la surcharge classique, et dans certains cas, cela peut 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.

• Niveau 0 : optimisation du circuit DCQO décomposé (placement, routage, ordonnancement)
• Niveau 1 : optimisation de PauliEvolutionGate puis du circuit DCQO décomposé (max_trials=10)
• Niveau 2 : optimisation de PauliEvolutionGate puis du circuit DCQO décomposé (max_trials=15)
• Niveau 3 : optimisation de PauliEvolutionGate puis du circuit DCQO décomposé (max_trials=20)
• Niveau 4 : optimisation de PauliEvolutionGate puis du circuit DCQO décomposé (max_trials=25)
• Niveau 5 : optimisation de PauliEvolutionGate puis du circuit DCQO décomposé (max_trials=50)

Niveaux de post-traitement (0-2) : contrôlent la quantité d'optimisation classique, compensant les erreurs d'inversion de bits avec un nombre différent de passes gloutonnes d'une recherche locale :

• Niveau 0 : 1 passe
• Niveau 1 : 2 passes
• Niveau 2 : 3 passes

Mode transpilation seule : désormais disponible pour les utilisateurs qui souhaitent analyser l'optimisation des circuits sans exécuter l'algorithme quantique complet.

Exemple de configuration personnalisée

Voici comment vous pourriez configurer Iskay avec différents paramètres :

custom_options = {
    "shots": 15_000,                                        # Higher shot count for better statistics
    "num_iterations": 12,                                   # More iterations for solution refinement
    "preprocessing_level": 1,                               # Light preprocessing for problem simplification
    "postprocessing_level": 2,                              # Maximum postprocessing for solution quality
    "transpilation_level": 3,                               # Using higher transpilation level for circuit optimization
    "seed_transpiler": 42,                                  # Fixed seed for reproducible results
    "job_tags": ["market_split"]                            # Custom tracking tags
}

Pour ce tutoriel, nous conserverons la plupart des paramètres par défaut et ne modifierons que le nombre d'itérations de champ de biais :

# Specify the target backend
backend_name = "ibm_fez"

# Set the number of bias-field iterations and set a tag to identify the jobs
options = {
    "num_iterations": 3,  # Change number of bias-field iterations
    "job_tags": ["market_split_example"],  # Tag to identify jobs
}

# Configure Iskay optimizer
iskay_input = {
    "problem": iskay_input_problem,
    "problem_type": "binary",
    "backend_name": backend_name,
    "options": options,
}

print("Iskay Optimizer Configuration:")
print("=" * 40)
print(f"  Backend: {backend_name}")
print(f"  Problem: {len(iskay_input['problem'])} terms")
print("  Algorithm: bf-DCQO")

Étape 3 : Exécuter à l'aide des primitives Qiskit

Nous soumettons maintenant notre problème pour exécution sur le matériel IBM Quantum. L'algorithme bf-DCQO va :

1. Construire des circuits quantiques peu profonds avec des termes contreadiabatiques
2. Exécuter environ 10 itérations avec optimisation par champ de biais
3. Effectuer un post-traitement classique avec recherche locale
4. Retourner l'affectation optimale des marchés

# Submit the optimization job
print("Submitting optimization job to Kipu Quantum...")
print(
    f"Problem size: {A.shape[1]} variables, {len(iskay_input['problem'])} terms"
)
print(
    "Algorithm: bf-DCQO (bias-field digitized counterdiabatic quantum optimization)"
)

job = iskay_solver.run(**iskay_input)

print("\nJob successfully submitted!")
print(f"Job ID: {job.job_id}")
print("Optimization in progress...")
print(
    f"The bf-DCQO algorithm will efficiently explore {2**A.shape[1]:,} possible assignments"
)

Surveiller l'état de la tâche

Vous pouvez vérifier l'état actuel de votre tâche d'optimisation. Les états possibles sont :

• QUEUED : la tâche est en attente dans la file
• RUNNING : la tâche est en cours d'exécution sur le matériel quantique
• DONE : la tâche s'est terminée avec succès
• CANCELED : la tâche a été annulée
• ERROR : la tâche a rencontré une erreur

# Check job status
print(f"Job status: {job.status()}")

Attendre la fin de l'exécution

Cette cellule va bloquer jusqu'à ce que la tâche soit terminée. Le processus d'optimisation comprend :

• Le temps d'attente en file (attente de l'accès au matériel quantique)
• Le temps d'exécution (exécution de l'algorithme bf-DCQO avec environ 10 itérations)
• Le temps de post-traitement (recherche locale classique)

Les temps de complétion typiques varient de quelques minutes à plusieurs dizaines de minutes selon les conditions de la file d'attente.

# Wait for job completion
while True:
    status = job.status()
    print(
        f"Waiting for job {job.job_id} to complete... (status: {status})",
        end="\r",
        flush=True,
    )
    if status in ["DONE", "CANCELED", "ERROR"]:
        print(
            f"\nJob {job.job_id} completed with status: {status}" + " " * 20
        )
        break
    time.sleep(30)

# Retrieve the optimization results
result = job.result()
print("\nOptimization complete!")

Étape 4 : Post-traiter et retourner le résultat au format classique souhaité

Nous procédons maintenant au post-traitement des résultats de l'exécution quantique. Cela comprend :

• L'analyse de la structure de la solution
• La validation de la satisfaction des contraintes
• Le benchmarking par rapport aux approches classiques

Analyser les résultats

Comprendre la structure du résultat

Iskay retourne un dictionnaire de résultats complet contenant :

• solution : un dictionnaire associant les indices des variables à leurs valeurs optimales (0 ou 1)
• solution_info : des informations détaillées incluant :
  • bitstring : l'affectation optimale sous forme de chaîne binaire
  • cost : la valeur de la fonction objectif (devrait être 0 pour une satisfaction parfaite des contraintes)
  • mapping : comment les positions de la chaîne de bits correspondent aux variables du problème
  • seed_transpiler : la graine utilisée pour la reproductibilité
• prob_type : si la solution est au format binaire ou spin

Examinons la solution retournée par l'optimiseur quantique.

# Display the optimization results
print("Optimization Results")
print("=" * 50)
print(f"Problem Type: {result['prob_type']}")
print("\nSolution Info:")
print(f"  Bitstring: {result['solution_info']['bitstring']}")
print(f"  Cost: {result['solution_info']['cost']}")
print("\nSolution (first 10 variables):")
for i, (var, val) in enumerate(list(result["solution"].items())[:10]):
    print(f"  {var}: {val}")
print("  ...")

Validation de la solution

Nous validons maintenant si la solution quantique satisfait les contraintes du Market Split. Le processus de validation vérifie :

Qu'est-ce qu'une violation de contrainte ?

• Pour chaque produit $i$, nous calculons les ventes réelles dans la Région A : $(Ax)_i$
• Nous comparons cela aux ventes cibles $b_i$
• La violation est la différence absolue : $|(Ax)_i - b_i|$
• Une solution réalisable présente zéro violation pour tous les produits

Ce que nous attendons :

• Cas idéal : violation totale = 0 (toutes les contraintes parfaitement satisfaites)
  • 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
  • La Région B reçoit les unités restantes (également 1002, 879 et 1040 respectivement)
• Bon cas : la violation totale est faible (solution quasi optimale)
• Mauvais cas : des violations importantes indiquent que la solution ne satisfait pas les exigences commerciales

La fonction de validation calculera :

1. Les ventes réelles par produit dans chaque région
2. Les violations de contraintes pour chaque produit
3. La répartition des marchés entre les régions

def validate_solution(A, b, solution):
    """Validate market split solution."""
    x = np.array(solution)
    region_a = A @ x
    region_b = A @ (1 - x)
    violations = np.abs(region_a - b)

    return {
        "target": b,
        "region_a": region_a,
        "region_b": region_b,
        "violations": violations,
        "total_violation": np.sum(violations),
        "is_feasible": np.sum(violations) == 0,
        "region_a_markets": int(np.sum(x)),
        "region_b_markets": len(x) - int(np.sum(x)),
    }

# Convert bitstring to list of integers and validate
optimal_assignment = [
    int(bit) for bit in result["solution_info"]["bitstring"]
]
validation = validate_solution(A, b, optimal_assignment)

Interpréter les résultats de validation

Les résultats de validation montrent si l'optimiseur quantique a trouvé une solution réalisable. Examinons les éléments suivants :

Vérification de la faisabilité :

• is_feasible = True signifie que la solution satisfait parfaitement toutes les contraintes (violation totale = 0)
• is_feasible = False signifie que certaines contraintes sont violées

Analyse des ventes :

• Comparez les ventes cibles par rapport aux ventes réelles pour chaque produit
• Pour une solution parfaite : Réel = Cible pour tous les produits dans les deux régions
• La différence indique à quel point nous sommes proches de la répartition souhaitée des marchés

Répartition des marchés :

• Montre combien de marchés sont affectés à chaque région
• Il n'est pas nécessaire d'avoir un nombre égal de marchés, seuls les objectifs de ventes doivent être atteints

print("Solution Validation")
print("=" * 50)
print(f"Feasible solution: {validation['is_feasible']}")
print(f"Total constraint violation: {validation['total_violation']}")

print("\nSales Analysis (Target vs Actual):")
for i, (target, actual_a, actual_b) in enumerate(
    zip(validation["target"], validation["region_a"], validation["region_b"])
):
    violation_a = abs(actual_a - target)
    violation_b = abs(actual_b - target)
    print(f"  Product {i+1}:")
    print(f"    Target: {target}")
    print(f"    Region A: {actual_a} (violation: {violation_a})")
    print(f"    Region B: {actual_b} (violation: {violation_b})")

print("\nMarket Distribution:")
print(f"  Region A: {validation['region_a_markets']} markets")
print(f"  Region B: {validation['region_b_markets']} markets")

Évaluation de la qualité de la solution

Sur la base des résultats de validation ci-dessus, nous pouvons évaluer la qualité de la solution quantique :

Si is_feasible = True (violation totale = 0) :

• L'optimiseur quantique a trouvé avec succès une solution optimale
• Toutes les contraintes commerciales sont parfaitement satisfaites
• Cela démontre un avantage quantique sur un problème où les solveurs classiques rencontrent des difficultés [4]

Si is_feasible = False (violation totale > 0) :

• La solution est quasi optimale mais pas parfaite
• De petites violations peuvent être acceptables en pratique
• Envisagez d'ajuster les paramètres de l'optimiseur :
  • Augmentez num_iterations pour plus de passes d'optimisation
  • Augmentez postprocessing_level pour plus de raffinement classique
  • Augmentez shots pour de meilleures statistiques de mesure

Interprétation de la fonction de coût :

• La valeur cost de solution_info est égale à $||Ax - b||^2$
• Un coût = 0 indique une satisfaction parfaite des contraintes
• Des valeurs de coût plus élevées indiquent des violations de contraintes plus importantes

Conclusion

Ce que nous avons accompli

Dans ce tutoriel, nous avons réussi à :

1. Charger un véritable problème d'optimisation : obtenu une instance difficile de Market Split à partir de la bibliothèque de référence QOBLIB [2]
2. Transformer au format QUBO : converti le problème contraint en une formulation quadratique non contrainte [3]
3. Exploiter des algorithmes quantiques avancés : utilisé l'algorithme bf-DCQO de Kipu Quantum avec des termes contreadiabatiques [1]
4. Obtenir des solutions optimales : trouvé des solutions réalisables satisfaisant toutes les contraintes

Points clés à retenir

Innovation algorithmique : l'algorithme bf-DCQO représente une avancée significative [1] :

• 10 fois moins de portes que le Digital Quantum Annealing
• Environ 10 itérations au lieu d'environ 100 pour les méthodes variationnelles
• Résilience intégrée aux erreurs grâce à l'efficacité des circuits

Termes contreadiabatiques : permettent une évolution quantique rapide tout en maintenant la fidélité de l'état fondamental, rendant l'optimisation quantique praticable sur le matériel bruyant d'aujourd'hui [1].

Guidage par champ de biais : l'approche itérative par champ de biais permet à chaque itération de démarrer près des bonnes solutions trouvées précédemment, fournissant une forme de recherche locale améliorée par le quantique [1].

Prochaines étapes

Pour approfondir votre compréhension et explorer davantage :

1. Essayer différentes instances : expérimentez avec d'autres instances QOBLIB de tailles variées
2. Ajuster les paramètres : modifiez num_iterations, preprocessing_level, postprocessing_level
3. Comparer avec le classique : évaluez les performances par rapport aux solveurs d'optimisation classiques
4. Essayer différentes stratégies : essayez de trouver un meilleur encodage pour le problème ou formulez-le en HUBO (si possible)
5. Appliquer à votre domaine : adaptez les techniques de formulation QUBO/HUBO à vos propres problèmes d'optimisation

Références

[1] IBM Quantum. "Kipu Quantum Optimization." IBM Quantum Documentation.

[2] QOBLIB - Quantum Optimization Benchmarking Library. Zuse Institute Berlin (ZIB). https://git.zib.de/qopt/qoblib-quantum-optimization-benchmarking-library

[3] Glover, F., Kochenberger, G., & 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.

[4] Lodi, A., Tramontani, A., & Weninger, K. (2023). "The Intractable Decathlon: Benchmarking Hard Combinatorial Problems." INFORMS Journal on Computing.