Résolvez le problème de fragmentation du marché grâce à l'optimiseur Iskay Quantum de Kipu Quantum

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

Arrière-plan

Ce tutoriel montre comment résoudre le problème de la division du marché en utilisant l'optimiseur quantique Iskay de Kipu Quantum [1]. 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.

Le défi de la division du marché

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.

Formulation mathématique :

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

• $x_j = 1$ attribue le marché $j$ à la région A
• $x_j = 0$ attribue le marché $j$ à la région B
• 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)

Fonction de coût :

Pour résoudre ce problème, nous minimisons le carré de la violation de la contrainte :

$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 vente du produit $i$ dans chaque région
• Le coût est égal à zéro précisément lorsque toutes les contraintes sont satisfaites

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 :

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

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

Complexité informatique :

En dépit de son interprétation commerciale simple, ce problème présente une difficulté de calcul remarquable :

• É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]
• 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

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].

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

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

Efficacité du circuit : L'algorithme bf-DCQO permet une réduction remarquable du nombre de portes [1] :

• Jusqu'à 10 fois moins de portes d'intrication que le recuit quantique numérique (DQA)
• Des circuits nettement moins profonds permettent :
  • Moins d'accumulation d'erreurs pendant l'exécution quantique
  • Capacité à résoudre des problèmes plus importants avec le matériel quantique actuel
  • Pas besoin de techniques d'atténuation des erreurs

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]. Pour ce faire, il faut

• Calculs intelligents du champ de polarisation à partir de distributions d'états mesurées
• Commencer chaque itération à partir d'un état énergétique proche de la solution précédente
• Post-traitement classique intégré avec recherche locale

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].

Exigences

Avant de commencer ce tutoriel, assurez-vous que les éléments suivants sont installés :

• Qiskit IBM Runtime (pip install qiskit-ibm-runtime)
• Qiskit Functions (pip install qiskit-ibm-catalog)
• NumPy (pip install numpy)
• Demandes (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 sur le site Qiskit Functions Catalog.

Configuration

Tout d'abord, importez tous les paquets nécessaires pour ce tutoriel.

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 informations d'identification d' IBM Quantum

Définissez vos IBM Quantum® Platform compétences. Eléments nécessaires :

• Jeton API : Votre clé API de 44 caractères provenant de IBM Quantum Platform
• Instance CRN : Votre identifiant d'instance IBM Cloud®

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

Étape 1 : Mettre en correspondance les entrées classiques avec un problème quantique

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

1. Connexion à l'optimiseur quantique Iskay
2. Chargement et formulation du problème de la répartition du marché
3. Comprendre l'algorithme bf-DCQO qui le résoudra

Se connecter à Iskay Quantum Optimizer

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.

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 problématiques

Les instances de problèmes 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/rangées de la matrice $A$ )
  • 20 = nombre de marchés (variables/colonnes de la matrice $A$ )

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

  • Chaque ligne comporte 21 nombres : les 20 premiers sont les coefficients de ligne, le dernier est la cible
  • Ligne 2 : 60 92 161 ... 51 | 1002
    • Les 20 premiers chiffres : Quelle quantité de produit 1 chacun des 20 marchés vend-il?
    • Dernier chiffre (1002) : Objectif de vente pour le produit 1 dans une région
  • Ligne 3 : 176 196 41 ... 46 | 879
    • Ventes du produit 2 par marché et par cible (879)
  • Ligne 4 : 68 68 179 ... 95 | 1040
    • Ventes du produit 3 par marché et par 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 : 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

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 sans contrainte [4]. Pour le problème de la répartition du marché, nous convertissons les contraintes d'égalité

$Ax = b$

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

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$

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$

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$

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]. 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é.

Mettre en œuvre les fonctions de chargement des données et de conversion QUBO

Nous définissons maintenant trois fonctions d'utilité :

1. parse_marketsplit_dat() - Analyse le format de fichier .dat et extrait les matrices $A$ et $b$
2. fetch_marketsplit_data() - Téléchargement d'instances de problèmes directement à partir du référentiel 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 à partir de la QOBLIB [2.] Cette instance a :

• 3 produits (contraintes)
• 20 marchés (variables de décision binaires)
• Plus d'un million 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: "
        f"2^{A.shape[1]} = {2**A.shape[1]:,} possible assignments"
    )

Convertir au format QUBO

Nous transformons maintenant le problème d'optimisation contraint en 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 QUBO au format Iskay

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

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

où

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

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

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

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 :

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

Ce qui signifie :

• Les termes linéaires tels que "(i, )" contiennent : le coefficient linéaire d'origine + le coefficient quadratique diagonal
• Les termes quadratiques diagonaux comme "(i, i)" ne devrait PAS apparaître dans le dictionnaire final
• 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

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

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

PAS d' 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: "
    f"{sum(1 for k in iskay_input_problem.keys() if k != '()' and ', )' in k)}"
)
print(
    f"  • Quadratic terms: "
    f"{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, il convient de comprendre l'algorithme quantique sophistiqué qui alimente Iskay : bf-DCQO (bias-field digitized counterdiabatic quantum optimization) [1].

Qu'est-ce que le 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) de l'hamiltonien quantique final [1]. L'algorithme relève un défi fondamental en matière d'optimisation quantique :

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.

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.

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 division du marché, la fonction de coût est la suivante :

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

Le rôle des termes contre-diabétiques

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 :

Dans l'optimisation quantique adiabatique, nous faisons évoluer le système en fonction d'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}}$ code notre problème d'optimisation. Pour maintenir l'état fondamental pendant l'évolution rapide, nous ajoutons des termes contrediabatiques :

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

Ces termes contrediabatiques ont les effets suivants :

1. Supprimer les transitions indésirables : Empêcher l'état quantique de passer à des états excités au cours d'une évolution rapide
2. Permettre des temps d'évolution plus courts : Permet d'atteindre l'état final beaucoup plus rapidement sans violer l'adiabaticité
3. Réduire la profondeur des circuits : Une évolution plus courte permet de réduire le nombre de portes et d'erreurs

L'impact pratique est spectaculaire : bf-DCQO utilise jusqu'à 10 fois moins de portes d'enchevêtrement que Digital Quantum Annealing [1], ce qui le rend pratique pour 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 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 :]

Processus d'itération :

1. Evolution quantique initiale : Commencez par un circuit quantique mettant en œuvre le protocole d'évolution contrediabatique

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

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

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$

   Cela permet de commencer à proximité de la bonne solution trouvée précédemment, en effectuant une forme de "recherche locale quantique"

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

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.

Post-traitement classique intégré

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

• Exploration par retournement de bits : Inversion systématique ou aléatoire des bits dans la meilleure solution mesurée
• Évaluation de l'énergie : Calculer $C(x)$ pour chaque solution modifiée
• Sélection avide : Accepter les améliorations qui réduisent la fonction de coût
• Passes multiples : Effectuer plusieurs passes (contrôlées par postprocessing_level)

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.

Pourquoi bf-DCQO excelle sur le matériel actuel

L'algorithme bf-DCQO est spécialement conçu pour exceller sur les dispositifs quantiques bruyants à échelle intermédiaire (NISQ) d'aujourd'hui [1] :

1. Résistance aux erreurs : Moins de portes (réduction de 10 fois) signifie moins d'accumulation d'erreurs
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]
3. Évolutivité : Peut traiter des problèmes comportant jusqu'à 156 qubits (156 variables binaires) avec une mise en correspondance directe des qubits [1]
4. Performances prouvées : Taux d'approximation de 100 % sur les instances de référence MaxCut et HUBO [1]

Voyons maintenant ce puissant algorithme en action sur notre problème de division du marché!

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

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.

Configurer l'optimisation

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 :

Paramètres obligatoires

Concepts essentiels

• Format du problème : Nous utilisons "binary" car nos variables sont binaires (0/1), représentant des affectations de marché.
• 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.
• Structure QUBO : Notre dictionnaire de problèmes contient les coefficients exacts de la transformation mathématique.

Options avancées (facultatif)

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 :

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 :

• Niveau 0 : Circuits exacts et plus longs
• 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
• 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
• 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

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.

• Niveau 0 : Optimisation du circuit DCQO décomposé (layout, routing, scheduling)
• 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ô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 :

• Niveau 0 : 1 réussite
• Niveau 1 : 2 passages
• Niveau 2 : 3 réussites

Mode transpile uniquement : 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 = {
    # Higher shot count for better statistics
    "shots": 15_000,

    # More iterations for solution refinement
    "num_iterations": 12,

    # Light preprocessing for problem simplification
    "preprocessing_level": 1,

    # Maximum postprocessing for solution quality
    "postprocessing_level": 2,

    # Using higher transpilation level for circuit optimization
    "transpilation_level": 3,

    # Fixed seed for reproducible results
    "seed_transpiler": 42,

    # Custom tracking tags
    "job_tags": ["market_split"]
}

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 :

# 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écutez à l'aide d' Qiskit primitives

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

1. Construire des circuits quantiques peu profonds avec des termes contrediabatiques
2. Exécution d'environ 10 itérations avec optimisation du champ de polarisation
3. Effectuer un post-traitement classique avec recherche locale
4. Renvoyer l'affectation optimale du marché

# 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 "
    f"{2**A.shape[1]:,} possible assignments"
)

Surveiller l'état des tâches

Vous pouvez vérifier l'état actuel de votre travail d'optimisation. Les statuts possibles sont les suivants :

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

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

Attendez la fin

Cette cellule se bloquera jusqu'à ce que le travail soit terminé. Le processus d'optimisation comprend

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

Les délais d'exécution typiques varient de quelques minutes à quelques dizaines de minutes en fonction des 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-traitement et restitution du résultat dans le format classique souhaité

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

• Analyse de la structure de la solution
• Validation de la satisfaction des contraintes
• Comparaison avec les approches classiques

Analyser les résultats

Comprendre la structure des résultats

Iskay renvoie un dictionnaire de résultats complet contenant :

• solution: Un dictionnaire associant les indices des variables à leurs valeurs optimales (0 ou 1)
• solution_info: Informations détaillées, y compris :
  • bitstring: L'affectation optimale sous forme de chaîne binaire
  • cost: La valeur de la fonction objective (devrait être 0 pour une satisfaction parfaite des contraintes)
  • mapping: Comment les positions des chaînes de bits correspondent aux variables du problème
  • seed_transpiler: Semence utilisée pour la reproductibilité
• prob_type: Si la solution est en format binaire ou en format spin

Examinons la solution renvoyé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 vérifions maintenant si la solution quantique satisfait aux contraintes du fractionnement du marché. 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 ce chiffre à l'objectif de vente $b_i$
• La violation est la différence absolue : $|(Ax)_i - b_i|$
• Une solution réalisable ne comporte aucune violation pour tous les produits

Ce que nous attendons :

• Cas idéal : Violation totale = 0 (toutes les contraintes sont 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 : Les violations importantes indiquent que la solution ne répond pas aux exigences de l'entreprise

La fonction de validation calcule :

1. Ventes réelles par produit dans chaque région
2. Violations des contraintes pour chaque produit
3. Répartition du marché 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 la validation

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

Contrôle de 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 :

• Comparer les ventes cibles et les ventes réelles pour chaque produit
• Pour une solution parfaite : Réel = Objectif pour tous les produits dans les deux régions
• La différence indique à quel point nous sommes proches de la répartition souhaitée du marché

Répartition du marché :

• Indique le nombre de marchés attribués à chaque région
• Il n'est pas nécessaire d'avoir un nombre égal de marchés, mais seulement d'atteindre les objectifs de vente

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é une solution optimale
• Toutes les contraintes de l'entreprise sont parfaitement satisfaites
• Cela démontre l'avantage quantique sur un problème pour lequel les solveurs classiques ont 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 dans la pratique
• Envisager d'ajuster les paramètres de l'optimiseur :
  • Augmenter num_iterations pour plus de passes d'optimisation
  • Augmenter postprocessing_level pour un raffinement plus classique
  • Augmenter 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$
• Le 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. 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]
2. Transformé au format QUBO : Conversion du problème contraint en une formulation quadratique sans contrainte [3]
3. Exploitation d'algorithmes quantiques avancés : Utilisation de l'algorithme bf-DCQO de Kipu Quantum avec des termes contrediabatiques [1]
4. Obtention de solutions optimales : Recherche de solutions réalisables satisfaisant toutes les contraintes

Points essentiels à retenir

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

• 10 fois moins de portes que le recuit quantique numérique
• Environ 10 itérations au lieu d'environ 100 pour les méthodes variationnelles
• Résistance aux erreurs intégrée grâce à l'efficacité du circuit

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].

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].

Etapes suivantes

Pour approfondir votre compréhension et explorer davantage :

1. Essayez différentes instances : Expérimentez d'autres instances QOBLIB de tailles différentes
2. Régler les paramètres : Ajuster num_iterations, preprocessing_level, postprocessing_level
3. Comparaison avec les solutions classiques : comparaison avec les solveurs d'optimisation classiques
4. Essayez différentes stratégies : Essayer de trouver un meilleur encodage pour le problème ou le formuler comme HUBO (si possible)
5. Appliquer à votre domaine : Adapter les techniques de formulation QUBO/HUBO à vos propres problèmes d'optimisation

Références

[1] IBM Quantum. " Optimisation quantique de Kipu " IBM Quantum Documentation.

[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

[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.

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