Encuentra el conjunto independiente máximo con el Aqarios Constrained Quantum Optimizer

Nota

Qiskit Functions son una funcionalidad experimental disponible únicamente para los usuarios de los planes IBM Quantum® Premium Plan, Flex Plan y On-Prem (a través de la API de IBM Quantum Platform). Se encuentran en estado de lanzamiento preliminar (preview) y están sujetas a cambios.

Estimación de uso: 30 segundos en un procesador Heron r2. (NOTA: Esto es solo una estimación. Tu tiempo de ejecución puede variar.)

Contexto

Este tutorial muestra cómo encontrar el conjunto independiente máximo de un grafo utilizando el Aqarios Constrained Quantum Optimizer [1], un problema de optimización combinatoria con restricciones. Una instancia de la biblioteca de referencia QOBLIB [2] se formula como un programa lineal binario y se pasa a la función de aplicación del optimizador. El optimizador gestiona internamente toda la reformulación, la síntesis del circuito, la transpilación y el arranque en caliente iterativo (consulta [3] para más detalles).

El tutorial abarca los siguientes pasos:

1. Definir el problema como un programa lineal utilizando OptimizationProblem de qiskit-addon-opt-mapper

2. Ejecutar la optimización cuántica utilizando el Aqarios Constrained Quantum Optimizer

3. Recuperar y visualizar los resultados

El problema del conjunto independiente máximo

El problema del conjunto independiente máximo (MIS, por sus siglas en inglés) es un desafío fundamental en la optimización combinatoria. Formalmente, dado un grafo $G(V, E)$, el objetivo es encontrar el subconjunto más grande de vértices $V_I \subset V$ tal que no haya dos vértices en $V_I$ conectados por una arista, como en $\nexists (u, v) \in E : v \in V_I \wedge u \in V_I$. A cada vértice se le asigna una variable de decisión binaria $x_i \in \{0, 1\}$, y se introduce una restricción $x_u + x_v \leq 1$ para cada arista, garantizando que como máximo se seleccione uno de los extremos de cada arista. El problema puede plantearse entonces como el siguiente problema de maximización:

$$\max_{x_i} \sum_{i \in V} x_i \qquad\text{(encontrar el conjunto más grande)}\\ \text{s.a.} \quad x_u + x_v \leq 1 \quad \forall (u, v) \in E.$$

El MIS tiene una amplia gama de aplicaciones prácticas. En la planificación de redes inalámbricas, un conjunto independiente corresponde a un grupo de transmisores que pueden transmitir simultáneamente sin interferencia mutua. En la planificación de tareas, modela la mayor colección de tareas que pueden ejecutarse simultáneamente dados conflictos de recursos por pares. En biología computacional, captura conjuntos de proteínas que no interactúan entre sí en una red.

A pesar de su formulación intuitiva, el MIS es NP-difícil, e incluso para grafos con unos pocos cientos de nodos, ciertas instancias se vuelven difíciles de resolver de forma exacta o heurística [2]. El problema también da lugar a estructuras de restricciones dispersas que son muy adecuadas para implementaciones de hardware de optimización cuántica, lo que lo convierte en una referencia atractiva para los dispositivos cuánticos a corto plazo.

Aqarios Constrained Quantum Optimizer

El enfoque estándar para incorporar un problema binario con restricciones a la optimización cuántica transforma el modelo en un formato sin restricciones añadiendo términos de penalización: cada restricción incumplida $x_u + x_v \leq 1$ contribuye con $2 x_u x_v$ al objetivo de minimización $-\sum_i x_i$. Esto se gestiona automáticamente mediante la Qiskit Function Constrained Quantum Optimizer.

Más allá de esta transformación estándar, el optimizador identifica cliques en el grafo de restricciones. Una clique es un conjunto de nodos $V_C$ en el que cada par de nodos comparte una arista. Como consecuencia, las $\binom{|V_C|}{2}$ restricciones por pares $x_u + x_v \leq 1 \;\forall (u,v) \in E_C$ pueden reemplazarse por una única restricción más estricta $\sum_{i \in V_C} x_i \leq 1$. Al introducir una variable de holgura $y$, esto se convierte en una igualdad $\sum_i x_i + y = 1$, que toma la forma de una restricción one-hot que se puede imponer directamente en QAOA utilizando XY-mixers [3]. Esto reduce el espacio de búsqueda y evita la necesidad de términos de penalización para esas restricciones, mejorando la calidad de la solución.

Además, las variables conectadas a un único vecino se denominan nodos pendant (colgantes) y el algoritmo las fija de forma determinista antes de la ejecución cuántica, lo que reduce aún más el tamaño efectivo del problema.

El Constrained Quantum Optimizer emplea un enfoque de arranque en caliente iterativo compatible con XY-mixers [1], que reduce progresivamente el espacio de búsqueda sesgando la distribución del estado cuántico hacia regiones de solución prometedoras a lo largo de las iteraciones. Esto permite el uso de parámetros QAOA de ángulo fijo, eliminando la necesidad de entrenar parámetros variacionales. Los requisitos totales de recursos cuánticos están determinados únicamente por el número de iteraciones de arranque en caliente, lo que hace que el costo cuántico sea sencillo de controlar.

Requisitos

Antes de comenzar este tutorial, asegúrate de haber instalado los siguientes requisitos:

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

Opcionalmente, para el Apéndice necesitas instalar

• Luna Model (pip install luna-model)

Configuración

Importa todas las dependencias necesarias.

# 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

Primero, autentícate utilizando tu clave de API de IBM Quantum. Luego, selecciona la Qiskit Function de la siguiente manera. (Este código asume que ya has guardado tu cuenta en tu entorno 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")

Paso 1: Mapear las entradas clásicas al problema cuántico

El problema se formula como un archivo LP, un formato común para problemas de optimización que sirve como entrada para el Aqarios Constrained Quantum Optimizer. Además de los archivos LP, la función también admite archivos MPS y representaciones nativas de Luna Model. El archivo LP se genera mediante los siguientes pasos:

1. Obtener una instancia de grafo de QOBLIB [2]

2. Modelar el problema de optimización

3. Generar el archivo LP

Cargar el grafo de la instancia del problema

Los grafos se especifican en el formato DIMACS .gph, un formato basado en líneas donde las líneas que comienzan con e definen aristas, las líneas que comienzan con p definen el encabezado del problema y las líneas que comienzan con c son comentarios:

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

El archivo .gph se puede descargar del repositorio de QOBLIB utilizando la siguiente función, que además lo analiza y lo convierte en un grafo de NetworkX. Ten en cuenta que el formato DIMACS utiliza un etiquetado de nodos basado en 1, que aquí se convierte a una indexación basada en 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.

Este ejemplo utiliza la instancia es60fst02 de QOBLIB, un grafo con 186 nodos y 280 aristas. Gracias a los pasos de preprocesamiento empleados por el Constrained Quantum Optimizer, esta instancia se puede resolver en dispositivos Heron de 156 qubits. El grafo se puede visualizar utilizando matplotlib:

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

Construir el problema de optimización

El problema del conjunto independiente máximo se puede formular directamente utilizando OptimizationProblem. Cada nodo del grafo se convierte en una variable de decisión binaria, y cada arista introduce una restricción que garantiza que como máximo se seleccione uno de sus extremos:

# 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 atajo

El paquete qiskit-addon-opt-mapper proporciona una clase de aplicación preimplementada para el problema del conjunto independiente máximo, que simplifica la formulación anterior en una única llamada:

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

Traducir el problema a un archivo LP

El propio OptimizationProblem no admite la exportación a archivos LP, pero es interoperable con DOcplex, que sí lo hace. Generar el contenido del archivo LP requiere solo dos líneas:

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

Este formato es nativo del Constrained Quantum Optimizer.

Paso 2: Optimizar el problema para la ejecución en hardware cuántico

Toda la síntesis, optimización y transpilación del circuito se gestiona de forma nativa mediante la función. Consulta la sección de entradas en la referencia de la API para conocer los argumentos con los que llamar a la función.

Para ajustar con precisión el comportamiento del algoritmo, consulta la lista de opciones en la referencia de la API. Si quieres que el mapeo del circuito sea reproducible entre ejecuciones, fija la opción seed_transpiler.

Para obtener más información, consulta la guía del Aqarios Constrained Quantum Optimizer y la referencia de la API.

Paso 3: Ejecutar utilizando primitivas de Qiskit

Ahora el archivo LP se puede enviar al optimizador:

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

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

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

Internamente, el algoritmo avanza a través de las siguientes etapas:

1. Preprocessing:

   • Reducir las variables fijables

   • Encontrar cliques

   • Identificar los tipos de restricciones

   • Evaluar los factores de penalización para los términos de penalización

   • Aplicar transformaciones de restricciones

   • Sintetizar el circuito con métodos de imposición de restricciones

   • Aproximación del problema y transpilación

2. Cadenas paralelas de bucles iterativos:

   • Muestrear el circuito con parámetros fijos

   • Aplicar el posprocesamiento

   • Evaluar y establecer nuevas probabilidades de arranque en caliente

3. Postprocessing:

   • Encontrar las mejores muestras y verificar su factibilidad con respecto al problema de entrada

Supervisar el progreso

Consulta las siguientes secciones en la página Primeros pasos con Qiskit Functions para supervisar el progreso de tu trabajo:

• Comprobar el estado del trabajo

• Recuperar resultados

# Monitor the job status
job.status()

'QUEUED'

Paso 4: Posprocesar y devolver los resultados en el formato clásico deseado

El resultado de salida es un diccionario, cuyos campos se describen en la sección de salidas de la referencia de la API.

Cuando la lista solutions contiene más de una entrada, significa que se han encontrado múltiples óptimos degenerados. Aquí solo se considera la primera solución, indicada por el nombre de la variable. Las mismas soluciones también están disponibles como cadenas de bits en solution_bitstrings, donde metadata.solver_info.variable_mapping indica la posición de carácter de cada 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}

Visualización

El conjunto independiente identificado se puede visualizar resaltando los nodos seleccionados en el grafo:

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

Apéndice: Planteamiento del problema con Luna Model

Además del enfoque con qiskit-addon-opt-mapper mostrado anteriormente, la Qiskit Function también acepta modelos creados con Luna Model [4], el SDK de modelado de Aqarios. Después de instalar el paquete de PyPI luna-model, impórtalo de la siguiente manera:

Setup:

from luna_model import Model, Sense
import numpy as np

Luego, el modelo se construye a partir del grafo de la misma manera que con qiskit-addon-opt-mapper: Construir el modelo:

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

Próximos pasos

Recomendaciones

• Consulta la guía del Aqarios Constrained Quantum Optimizer para un recorrido detallado por todas las características de la función.
• Explora la referencia de la API para ver la lista completa de parámetros de entrada y campos de salida.
• Experimenta con las opciones del algoritmo (reps, num_parallel, shots, postprocessing_level) en tu propio problema de optimización binaria con restricciones para evaluar su impacto en la calidad de la solución y el tiempo de ejecución.

Referencias

1. IBM Quantum, Guía del Aqarios Constrained Quantum Optimizer

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, Documentación de Luna Model