Encuentra el conjunto independiente máximo con el optimizador cuántico con restricciones de Aqarios

Tiempo de ejecución estimado: 30 segundos en un procesador Heron r2. (NOTA: Se trata únicamente de una estimación. (El tiempo de ejecución puede variar.)

En segundo plano

Este tutorial muestra cómo hallar el conjunto independiente máximo de un grafo utilizando el optimizador cuántico con restricciones Aqarios [1], lo que constituye un problema de optimización combinatoria con restricciones. Se formula una instancia de la biblioteca de pruebas QOBLIB [2] como un problema de programación lineal binaria y se pasa a la función de aplicación del optimizador. El optimizador se encarga internamente de todas las operaciones de reformulación, síntesis de circuitos, transpilación y arranque en caliente iterativo (véase [3] para más detalles).

El tutorial abarca los siguientes pasos:

1. Define el problema como un programa lineal utilizando el OptimizationProblem de qiskit-addon-opt-mapper
2. Ejecuta la optimización cuántica utilizando el optimizador cuántico con restricciones de Aqarios
3. Recuperar y visualizar los resultados

El problema del conjunto independiente máximo

El problema del conjunto independiente máximo (MIS) es un reto fundamental en la optimización combinatoria. Formalmente, dado un grafo $G(V, E)$, el objetivo es encontrar el mayor subconjunto de vértices $V_I \subset V$ tal que no haya dos vértices en $V_I$ conectados por un arco, como se muestra 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 arco, lo que garantiza que se seleccione como máximo un extremo de cada arco. Por lo tanto, el problema puede formularse como el siguiente problema de maximización:

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 emitir simultáneamente sin interferir entre sí. En la planificación, modela el conjunto más amplio de tareas que pueden ejecutarse simultáneamente, teniendo en cuenta los conflictos de recursos entre pares. En biología computacional, se utiliza para identificar conjuntos de proteínas que no interactúan entre sí en una red.

A pesar de su formulación intuitiva, el MIS es un problema NP-difícil, e incluso en el caso de grafos con unos pocos cientos de nodos, algunas instancias concretas resultan difíciles de resolver, ya sea de forma exacta o heurística [2]. El problema da lugar además a estructuras de restricciones dispersas que resultan muy adecuadas para las implementaciones en hardware de la optimización cuántica, lo que lo convierte en un punto de referencia atractivo para los dispositivos cuánticos a corto plazo.

Optimizador cuántico con restricciones Aqarios

El enfoque estándar para integrar un problema binario con restricciones en la optimización cuántica consiste en transformar 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 lo gestiona automáticamente la función «Constrained Quantum Optimizer» de Qiskit.

Más allá de esta transformación estándar, el optimizador identifica cliques en el grafo de restricciones. Un clúster es un conjunto de nodos $V_C$ en el que cada par de nodos comparte un arco. En consecuencia, las restricciones por pares de « $\binom{|V_C|}{2}$ » $x_u + x_v \leq 1 \;\forall (u,v) \in E_C$ pueden sustituirse 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 adopta la forma de una restricción «one-hot» que puede aplicarse directamente en QAOA utilizando mezcladores XY [3]. Esto reduce el espacio de búsqueda y evita la necesidad de aplicar términos de penalización para esas restricciones, lo que mejora la calidad de la solución.

Además, las variables conectadas únicamente a un único vecino se denominan «nodos 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 optimizador cuántico con restricciones emplea un enfoque iterativo de «arranque en caliente» compatible con los mezcladores XY [1], que reduce progresivamente el espacio de búsqueda al orientar la distribución del estado cuántico hacia regiones de solución prometedoras a lo largo de las iteraciones. Esto permite utilizar parámetros QAOA de ángulo fijo, lo que elimina la necesidad de un entrenamiento variacional de los parámetros. Los requisitos totales de recursos cuánticos dependen exclusivamente del número de iteraciones de «arranque en caliente», lo que significa que el coste cuántico es fácil 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 Cliente (pip install qiskit-ibm-catalog)
• Mapeador de optimización de complementos de Qiskit (pip install qiskit-addon-opt-mapper)
• Numpy (pip install numpy)
• Matplotlib (pip install matplotlib)
• NetworkX (pip install networkx)

Si lo deseas, para el Apéndice debes instalar

• Modelo Luna (pip install luna-model)

Configuración

Importa todas las dependencias necesarias.

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

En primer lugar, inicia sesión con tu clave API de IBM Quantum. A continuación, selecciona la función de Qiskit de la siguiente manera. (Este código da por hecho 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()

Output:

[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()

Output:

[<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: Asignar entradas clásicas a un problema cuántico

El problema se formula como un archivo LP, un formato habitual para problemas de optimización que sirve como entrada para el optimizador cuántico con restricciones Aqarios. Además de los archivos LP, la función también es compatible con archivos MPS y representaciones nativas de Luna Model. El archivo LP se genera siguiendo estos pasos:

1. Obtener una instancia de grafo de la biblioteca QOBLIB [2]
2. Formular el problema de optimización
3. Generar el archivo LP

Cargar el grafo de la instancia del problema

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

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

El archivo .gph se puede descargar del repositorio QOBLIB mediante la siguiente función, que además lo analiza para convertirlo en un gráfico de « NetworkX ». Ten en cuenta que el formato DIMACS utiliza una numeración de nodos que empieza por 1, que aquí se convierte a una indexación que empieza por 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)

Output:

Loading graph with 186 nodes and 280 edges.

En este ejemplo se utiliza la instancia es60fst02 de QOBLIB, un grafo con 186 nodos y 280 aristas. Gracias a los pasos de preprocesamiento empleados por el Optimizador Cuántico con Restricciones, esta instancia puede resolverse en dispositivos Heron de 156 qubits. El gráfico se puede visualizar utilizando matplotlib:

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

Output:

Formular 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 se seleccione como máximo 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 ya implementada para el problema del conjunto independiente máximo, lo que simplifica la formulación anterior a una sola llamada:

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

Convierte el problema en un archivo LP

El programa en sí OptimizationProblem no admite la exportación de archivos LP, pero es compatible con DOcplex, que sí lo hace. Para generar el contenido del archivo LP solo se necesitan 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("...")

Output:

\ 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 optimizador cuántico con restricciones.

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

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

Para ajustar el comportamiento del algoritmo, consulta la lista de opciones en la referencia de la API.

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

Paso 3: Ejecutar con el comando « Qiskit primitives »

Ahora se puede enviar el archivo LP al optimizador:

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

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

Output:

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

A nivel interno, el algoritmo sigue las siguientes etapas:

1. Preprocesamiento :
   • Reducir las variables que se pueden modificar
   • Encuentra grupos de amigos
   • Identificar los tipos de restricciones
   • Evaluar los factores de penalización para los términos de penalización
   • Aplicar transformaciones con restricciones
   • Sintetizar circuitos mediante métodos que garantizan el cumplimiento de las restricciones
   • Formulación aproximada del problema y transpilación
2. Cadenas paralelas de bucles iterativos :
   • Muestra de un circuito con parámetros fijos
   • Aplicar el posprocesamiento
   • Evaluar y establecer nuevas probabilidades de arranque en caliente
3. Posprocesamiento :
   • Busca las mejores muestras y comprueba su viabilidad en relación con el problema planteado

Hacer un seguimiento del progreso

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

• Comprobar estado de trabajo
• Obtener resultados

# Monitor the job status
job.status()

Output:

'QUEUED'

Paso 4: Realizar el posprocesamiento y presentar los resultados en el formato clásico deseado

El resultado es un diccionario cuyos campos se describen en la sección «Salidas» de la referencia de la API.

Cuando la lista solutions contiene más de una entrada, se han encontrado varios óptimos degenerados. Aquí solo se tiene en cuenta la primera solución:

# 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['obj_value'])} nodes and is {'feasible' if result['feasible'] else 'infeasible'}."
)
print("{" + " ".join(k[2:] for k, v in solution.items() if v == 1) + "}")

Output:

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 gráfico:

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

Output:

Apéndice: Planteamiento del problema con el modelo Luna

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

Configuración:

from luna_model import Model, Sense
import numpy as np

A continuación, el modelo se construye a partir del gráfico de la misma forma que en el caso de qiskit-addon-opt-mapper:

Crea 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(model=input_str, backend_name="ibm_fez")

Pasos siguientes

Referencias

1. IBM Quantum : Guía del optimizador cuántico con restricciones de Aqarios
2. Koch et al. (2026), «The Quantum Optimization Benchmarking Library» 10.1038/s43588-026-00991-1
3. Bucher et al. (2026), «Optimización cuántica con restricciones mediante mezcladores XY iterativos con inicio en caliente » 10.1088/1367-2630/ae8ea2
4. Documentación del modelo Luna de Aqarios GmbH,