Trouver l'ensemble indépendant maximum avec l'Aqarios Constrained Quantum Optimizer

Remarque

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

Estimation d'utilisation : 30 secondes sur un processeur Heron r2. (REMARQUE : il s'agit seulement d'une estimation. Ton temps d'exécution peut varier.)

Contexte

Ce tutoriel montre comment trouver l'ensemble indépendant maximum d'un graphe à l'aide de l'Aqarios Constrained Quantum Optimizer [1], un problème d'optimisation combinatoire sous contraintes. Une instance de la bibliothèque de référence QOBLIB [2] est formulée comme un programme linéaire binaire et transmise à la fonction d'application de l'optimiseur. L'optimiseur gère en interne toute la reformulation, la synthèse de circuit, la transpilation et le démarrage à chaud itératif (voir [3] pour plus de détails).

Ce tutoriel couvre les étapes suivantes :

1. Définir le problème sous forme de programme linéaire à l'aide de OptimizationProblem de qiskit-addon-opt-mapper

2. Exécuter l'optimisation quantique à l'aide de l'Aqarios Constrained Quantum Optimizer

3. Récupérer et visualiser les résultats

Le problème de l'ensemble indépendant maximum

Le problème de l'ensemble indépendant maximum (MIS) est un défi fondamental en optimisation combinatoire. Formellement, étant donné un graphe $G(V, E)$, l'objectif est de trouver le plus grand sous-ensemble de sommets $V_I \subset V$ tel qu'aucune paire de sommets de $V_I$ ne soit reliée par une arête, comme dans $\nexists (u, v) \in E : v \in V_I \wedge u \in V_I$. À chaque sommet est associée une variable de décision binaire $x_i \in \{0, 1\}$, et une contrainte $x_u + x_v \leq 1$ est introduite pour chaque arête, garantissant qu'au plus une extrémité de chaque arête est sélectionnée. Le problème peut donc être formulé comme le problème de maximisation suivant :

$$\max_{x_i} \sum_{i \in V} x_i \qquad\text{(trouver le plus grand ensemble)}\\ \text{s.t.} \quad x_u + x_v \leq 1 \quad \forall (u, v) \in E.$$

Le MIS a un large éventail d'applications pratiques. Dans la planification de réseaux sans fil, un ensemble indépendant correspond à un groupe d'émetteurs pouvant tous diffuser simultanément sans interférence mutuelle. Dans l'ordonnancement, il modélise le plus grand ensemble de tâches pouvant s'exécuter simultanément compte tenu de conflits de ressources deux à deux. En biologie computationnelle, il capture des ensembles de protéines n'interagissant pas mutuellement au sein d'un réseau.

Malgré sa formulation intuitive, le MIS est NP-difficile, et même pour des graphes comportant quelques centaines de nœuds, certaines instances deviennent difficiles à résoudre exactement ou de manière heuristique [2]. Ce problème donne également lieu à des structures de contraintes creuses, particulièrement adaptées aux implémentations matérielles de l'optimisation quantique, ce qui en fait un banc d'essai attractif pour les dispositifs quantiques à court terme.

Aqarios Constrained Quantum Optimizer

L'approche standard pour intégrer un problème binaire sous contraintes dans l'optimisation quantique consiste à transformer le modèle en un format sans contraintes en ajoutant des termes de pénalité : chaque contrainte violée $x_u + x_v \leq 1$ contribue $2 x_u x_v$ à l'objectif de minimisation $-\sum_i x_i$. Cela est géré automatiquement par la fonction Qiskit Constrained Quantum Optimizer.

Au-delà de cette transformation standard, l'optimiseur identifie des cliques dans le graphe de contraintes. Une clique est un ensemble de nœuds $V_C$ où chaque paire de nœuds partage une arête. Par conséquent, les $\binom{|V_C|}{2}$ contraintes deux à deux $x_u + x_v \leq 1 \;\forall (u,v) \in E_C$ peuvent être remplacées par une seule contrainte plus stricte $\sum_{i \in V_C} x_i \leq 1$. L'introduction d'une variable d'écart $y$ transforme cela en une égalité $\sum_i x_i + y = 1$, qui prend la forme d'une contrainte one-hot pouvant être appliquée directement dans QAOA à l'aide de mixeurs XY [3]. Cela réduit l'espace de recherche et évite le besoin de termes de pénalité pour ces contraintes, améliorant ainsi la qualité de la solution.

De plus, les variables reliées à un seul voisin sont appelées nœuds pendants et sont fixées de manière déterministe par l'algorithme avant l'exécution quantique, réduisant encore la taille effective du problème.

Le Constrained Quantum Optimizer utilise une approche de démarrage à chaud itératif compatible avec les mixeurs XY [1], qui restreint progressivement l'espace de recherche en orientant la distribution de l'état quantique vers des régions de solution prometteuses au fil des itérations. Cela permet d'utiliser des paramètres QAOA à angle fixe, éliminant le besoin d'entraînement de paramètres variationnels. Les besoins totaux en ressources quantiques sont régis uniquement par le nombre d'itérations de démarrage à chaud, ce qui rend le coût quantique simple à contrôler.

Prérequis

Avant de commencer ce tutoriel, assure-toi d'avoir installé les prérequis suivants :

• Qiskit Runtime (pip install qiskit-ibm-runtime)

• Qiskit Functions Catalog IBM Client (pip install qiskit-ibm-catalog)

• Qiskit Addon Optimization Mapper (pip install qiskit-addon-opt-mapper)

• Numpy (pip install numpy)

• Matplotlib (pip install matplotlib)

• NetworkX (pip install networkx)

Facultativement, pour l'Annexe, tu dois installer

• Luna Model (pip install luna-model)

Configuration

Importe toutes les dépendances requises.

# Added by doQumentation — installs the packages this notebook needs if they are missing
import importlib.util

_needed = {"luna_model": "luna-model", "networkx": "networkx", "numpy": "numpy", "qiskit_addon_opt_mapper": "qiskit-addon-opt-mapper", "qiskit_ibm_catalog": "qiskit-ibm-catalog"}
_missing = [pip for module, pip in _needed.items()
            if importlib.util.find_spec(module) is None]
# One at a time, so a package that fails to install does not block the others
for _pip in _missing:
    %pip install -q {_pip}
if not _missing:
    print("\u2713 All required packages are installed")

import networkx as nx
import urllib.request

from qiskit_ibm_catalog import QiskitFunctionsCatalog

from qiskit_addon_opt_mapper import OptimizationProblem
from qiskit_addon_opt_mapper.applications import IndependentSet
from qiskit_addon_opt_mapper.translators import to_docplex_mp

Tout d'abord, authentifie-toi à l'aide de ta clé API IBM Quantum. Ensuite, sélectionne la fonction Qiskit comme suit. (Ce code suppose que tu as déjà enregistré ton compte dans ton environnement local.)

catalog = QiskitFunctionsCatalog(channel="ibm_quantum_platform")

# Verify that you have access to the function
catalog.list()

[QiskitFunction(aqarios/constrained-quantum-optimizer)]

# Load the function
optimizer = catalog.load("aqarios/constrained-quantum-optimizer")

# Check the list of backends you have access to
catalog.backends()

[<IBMBackend('ibm_pittsburgh')>,
 <IBMBackend('ibm_boston')>,
 <IBMBackend('ibm_phoenix')>,
 <IBMBackend('ibm_fez')>,
 <IBMBackend('ibm_miami')>,
 <IBMBackend('ibm_marrakesh')>,
 <IBMBackend('ibm_kingston')>]

# Select the backend you want to use
backend = catalog.backend("ibm_pittsburgh")

Étape 1 : associer les entrées classiques au problème quantique

Le problème est formulé sous la forme d'un fichier LP, un format courant pour les problèmes d'optimisation qui sert d'entrée à l'Aqarios Constrained Quantum Optimizer. Outre les fichiers LP, la fonction prend également en charge les fichiers MPS et les représentations natives Luna Model. Le fichier LP est généré selon les étapes suivantes :

1. Récupérer une instance de graphe depuis la QOBLIB [2]

2. Modéliser le problème d'optimisation

3. Générer le fichier LP

Charger le graphe de l'instance du problème

Les graphes sont spécifiés au format DIMACS .gph, un format ligne par ligne où les lignes commençant par e définissent des arêtes, les lignes commençant par p définissent l'en-tête du problème, et les lignes commençant par c sont des commentaires :

c some-comment
p edge 3 2
e 1 2
e 2 3
...

Le fichier .gph peut être téléchargé depuis le dépôt QOBLIB à l'aide de la fonction suivante, qui l'analyse également pour produire un graphe NetworkX. Note que le format DIMACS utilise un étiquetage des nœuds commençant à 1, qui est ici converti en indexation commençant à 0.

URL_BASE = "https://raw.githubusercontent.com/ZIB-AOPT/QOBLIB/refs/heads/main/07-independentset/instances/"

def fetch_qoblib_graph(name: str) -> nx.Graph:
    """Fetch and parse the QOBLIB graph file."""
    # Download the .gph file
    file, _ = urllib.request.urlretrieve(URL_BASE + f"{name}.gph")
    with open(file) as f:
        # Read the file contents
        lines = f.readlines()

    # Skip comments
    lines = [line for line in lines if not line.startswith("c")]

    # Read graph definition
    _, _, num_nodes, num_edges = lines[0].split()
    print(f"Loading graph with {num_nodes} nodes and {num_edges} edges.")

    # Parse edge information
    # The .gph format starts node labeling with 1; we need 0 here, so we subtract one.
    split_edges = (line.split() for line in lines[1:])
    edges = [(int(u) - 1, int(v) - 1) for _, u, v in split_edges]

    return nx.Graph(edges)

graph_name = "es60fst02"
graph = fetch_qoblib_graph(graph_name)

Loading graph with 186 nodes and 280 edges.

Cet exemple utilise l'instance es60fst02 de QOBLIB, un graphe comportant 186 nœuds et 280 arêtes. Grâce aux étapes de prétraitement employées par le Constrained Quantum Optimizer, cette instance peut être résolue sur des dispositifs Heron à 156 qubits. Le graphe peut être visualisé à l'aide de matplotlib :

# Keep layout for later reuse
layout = nx.spring_layout(graph, seed=1)
nx.draw(graph, layout, node_size=40)

Construire le problème d'optimisation

Le problème de l'ensemble indépendant maximum peut être formulé directement à l'aide de OptimizationProblem. Chaque nœud du graphe devient une variable de décision binaire, et chaque arête introduit une contrainte garantissant qu'au plus une de ses extrémités est sélectionnée :

# Create an OptimizationProblem instance
mis_problem = OptimizationProblem("MIS")

# Add a binary variable for each node
x = mis_problem.binary_var_list(graph.number_of_nodes())

# Maximize the sum of all node variables
mis_problem.maximize(linear={xi.name: 1 for xi in x})

# Add '<= 1' constraints for each edge
for u, v in graph.edges:
    mis_problem.linear_constraint({x[u].name: 1, x[v].name: 1}, "<=", 1)

Un raccourci

Le package qiskit-addon-opt-mapper fournit une classe d'application préimplémentée pour le problème de l'ensemble indépendant maximum, qui simplifie la formulation ci-dessus en un seul appel :

mis = IndependentSet(graph)
mis_problem = mis.to_optimization_problem()

Traduire le problème en fichier LP

OptimizationProblem lui-même ne prend pas en charge l'exportation en fichier LP, mais il est interopérable avec DOcplex, qui la prend en charge. La génération du contenu du fichier LP ne nécessite que deux lignes :

mp_model = to_docplex_mp(mis_problem)
lp_str = mp_model.export_as_lp_string()

print("\n".join(lp_str.split("\n")[:60]))
print("...")

\ This file has been generated by DOcplex
\ ENCODING=ISO-8859-1
\Problem name: Independent set

Maximize
 obj: x_0 + x_1 + x_2 + x_3 + x_4 + x_5 + x_6 + x_7 + x_8 + x_9 + x_10 + x_11
      + x_12 + x_13 + x_14 + x_15 + x_16 + x_17 + x_18 + x_19 + x_20 + x_21
      + x_22 + x_23 + x_24 + x_25 + x_26 + x_27 + x_28 + x_29 + x_30 + x_31
      + x_32 + x_33 + x_34 + x_35 + x_36 + x_37 + x_38 + x_39 + x_40 + x_41
      + x_42 + x_43 + x_44 + x_45 + x_46 + x_47 + x_48 + x_49 + x_50 + x_51
      + x_52 + x_53 + x_54 + x_55 + x_56 + x_57 + x_58 + x_59 + x_60 + x_61
      + x_62 + x_63 + x_64 + x_65 + x_66 + x_67 + x_68 + x_69 + x_70 + x_71
      + x_72 + x_73 + x_74 + x_75 + x_76 + x_77 + x_78 + x_79 + x_80 + x_81
      + x_82 + x_83 + x_84 + x_85 + x_86 + x_87 + x_88 + x_89 + x_90 + x_91
      + x_92 + x_93 + x_94 + x_95 + x_96 + x_97 + x_98 + x_99 + x_100 + x_101
      + x_102 + x_103 + x_104 + x_105 + x_106 + x_107 + x_108 + x_109 + x_110
      + x_111 + x_112 + x_113 + x_114 + x_115 + x_116 + x_117 + x_118 + x_119
      + x_120 + x_121 + x_122 + x_123 + x_124 + x_125 + x_126 + x_127 + x_128
      + x_129 + x_130 + x_131 + x_132 + x_133 + x_134 + x_135 + x_136 + x_137
      + x_138 + x_139 + x_140 + x_141 + x_142 + x_143 + x_144 + x_145 + x_146
      + x_147 + x_148 + x_149 + x_150 + x_151 + x_152 + x_153 + x_154 + x_155
      + x_156 + x_157 + x_158 + x_159 + x_160 + x_161 + x_162 + x_163 + x_164
      + x_165 + x_166 + x_167 + x_168 + x_169 + x_170 + x_171 + x_172 + x_173
      + x_174 + x_175 + x_176 + x_177 + x_178 + x_179 + x_180 + x_181 + x_182
      + x_183 + x_184 + x_185
Subject To
 c0: x_60 + x_61 <= 1
 c1: x_14 + x_60 <= 1
 c2: x_7 + x_60 <= 1
 c3: x_7 + x_61 <= 1
 c4: x_61 + x_62 <= 1
 c5: x_61 + x_64 <= 1
 c6: x_14 + x_62 <= 1
 c7: x_62 + x_65 <= 1
 c8: x_23 + x_63 <= 1
 c9: x_53 + x_63 <= 1
 c10: x_39 + x_63 <= 1
 c11: x_7 + x_68 <= 1
 c12: x_18 + x_68 <= 1
 c13: x_68 + x_69 <= 1
 c14: x_68 + x_72 <= 1
 c15: x_64 + x_65 <= 1
 c16: x_64 + x_69 <= 1
 c17: x_65 + x_66 <= 1
 c18: x_51 + x_53 <= 1
 c19: x_69 + x_73 <= 1
 c20: x_66 + x_67 <= 1
 c21: x_42 + x_66 <= 1
 c22: x_67 + x_75 <= 1
 c23: x_43 + x_67 <= 1
 c24: x_42 + x_75 <= 1
 c25: x_75 + x_83 <= 1
 c26: x_12 + x_51 <= 1
 c27: x_18 + x_70 <= 1
 c28: x_18 + x_26 <= 1
 c29: x_70 + x_71 <= 1
 c30: x_70 + x_76 <= 1
 c31: x_71 + x_72 <= 1
 c32: x_72 + x_73 <= 1
 c33: x_72 + x_78 <= 1
...

Ce format est pris en charge nativement par le Constrained Quantum Optimizer.

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

Toute la synthèse de circuit, l'optimisation et la transpilation sont gérées nativement par la fonction. Consulte la section des entrées de la référence API pour connaître les arguments avec lesquels appeler la fonction.

Pour ajuster finement le comportement de l'algorithme, consulte la liste des options de la référence API. Si tu veux que le mappage du circuit soit reproductible d'une exécution à l'autre, fixe l'option seed_transpiler.

Pour plus d'informations, consulte le guide Aqarios Constrained Quantum Optimizer et la référence API.

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

Le fichier LP peut maintenant être soumis à l'optimiseur :

job = optimizer.run(problem=lp_str, backend_name=backend.name)

print(f"Job ID: {job.job_id}")

Job ID: 87ec08b9-6275-40fa-be94-340a0a916bf1

En interne, l'algorithme se déroule selon les étapes suivantes :

1. Preprocessing:

   • Réduire les variables pouvant être fixées

   • Trouver les cliques

   • Identifier les types de contraintes

   • Évaluer les facteurs de pénalité pour les termes de pénalité

   • Appliquer les transformations de contraintes

   • Synthétiser le circuit avec des méthodes d'application des contraintes

   • Approximation du problème et transpilation

2. Chaînes parallèles de boucles itératives :

   • Échantillonner le circuit avec des paramètres fixes

   • Appliquer le post-traitement

   • Évaluer et définir de nouvelles probabilités de démarrage à chaud

3. Postprocessing:

   • Trouver les meilleurs échantillons et vérifier leur faisabilité par rapport au problème d'entrée

Suivre la progression

Consulte les sections suivantes de la page Prise en main de Qiskit Functions pour suivre la progression de ta tâche :

• Vérifier l'état de la tâche

• Récupérer les résultats

# Monitor the job status
job.status()

'QUEUED'

Étape 4 : post-traiter et renvoyer les résultats dans le format classique souhaité

Le résultat produit est un dictionnaire, dont les champs sont décrits dans la section des sorties de la référence API.

Lorsque la liste solutions contient plus d'une entrée, plusieurs optima dégénérés ont été trouvés. Seule la première solution est prise en compte ici, adressée par nom de variable. Les mêmes solutions sont également disponibles sous forme de chaînes de bits dans solution_bitstrings, où metadata.solver_info.variable_mapping donne la position de caractère de chaque variable.

# Retrieve the job result
result = job.result()

# Retrieve the first solution from the result
solution = result["solutions"][0]

print(f"The found maximum independent set of {graph_name} contains:", end=" ")
print(
    f"{int(result['objective_value'])} nodes and is {'feasible' if result['feasible'] else 'infeasible'}."
)
print("{" + " ".join(k[2:] for k, v in solution.items() if v == 1) + "}")

The found maximum independent set of es60fst02 contains: 88 nodes and is feasible.
{100 103 107 109 111 113 115 118 121 123 124 127 129 130 132 133 138 142 144 148 149 155 156 16 161 162 165 167 169 170 175 28 31 33 35 36 47 50 58 59 60 62 64 66 68 71 73 75 78 79 84 85 87 90 91 93 94 95 39 5 27 23 43 15 22 9 4 56 32 30 53 26 17 54 1 37 41 49 34 11 139 153 12 3 6 57 20 44}

Visualisation

L'ensemble indépendant identifié peut être visualisé en mettant en évidence les nœuds sélectionnés dans le graphe :

# Color all selected nodes in orange
node_map = {
    int(k.split("_")[1]): "tab:orange" if v else "tab:blue"
    for k, v in solution.items()
}
node_colors = [node_map[k] for k in graph.nodes]

# Draw with the same layout used before
nx.draw(graph, layout, node_size=40, node_color=node_colors)

Annexe : énoncé du problème avec Luna Model

En plus de l'approche qiskit-addon-opt-mapper présentée ci-dessus, la fonction Qiskit accepte également des modèles créés avec Luna Model [4], le SDK de modélisation d'Aqarios. Après installation du package PyPI luna-model, importe-le comme suit :

Setup:

from luna_model import Model, Sense
import numpy as np

Le modèle est ensuite construit à partir du graphe de la même manière qu'avec qiskit-addon-opt-mapper : Construire le modèle :

edges = np.array(graph.edges)

# Create the optimization model with a name
model = Model(name=f"MIS-{graph_name}", sense=Sense.MAX)
# Add binary variables
x = model.add_variables("x", graph.number_of_nodes())
# Set the objective
model.objective = x.sum()

# Use numpy like batch generation of constraints
model.add_constraints(x[edges].sum(axis=1) <= 1)

input_str = model.encode_b64()

# optimizer.run(problem=input_str, backend_name="ibm_fez")

Étapes suivantes

Recommandations

• Consulte le guide Aqarios Constrained Quantum Optimizer pour une présentation détaillée de toutes les fonctionnalités de la fonction.
• Explore la référence API pour la liste complète des paramètres d'entrée et des champs de sortie.
• Expérimente avec les options de l'algorithme (reps, num_parallel, shots, postprocessing_level) sur ton propre problème d'optimisation binaire sous contraintes pour évaluer leur impact sur la qualité de la solution et le temps d'exécution.

Références

1. IBM Quantum, Aqarios Constrained Quantum Optimizer Guide

2. Koch et al. (2026), The Quantum Optimization Benchmarking Library 10.1038/s43588-026-00991-1

3. Bucher et al. (2026), Constrained Quantum Optimization via Iterative Warm-Start XY-Mixers 10.1088/1367-2630/ae8ea2

4. Aqarios GmbH, Luna Model Docs