Resuelve un problema de conjunto independiente máximo con más variables que qubits usando SQOA Solver de JIJ

nota

Qiskit Functions es una función experimental disponible solo para los usuarios de los planes Premium, Flex y On-Prem (mediante la API de IBM Quantum Platform) de IBM Quantum®. Están en estado de versión preliminar y sujetas a cambios.

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

Antecedentes

Este tutorial muestra cómo usar SQOA Solver, una Qiskit Function de JIJ, para resolver un problema de conjunto independiente máximo (MIS) con más variables binarias que qubits tiene la QPU seleccionada. Los pasos básicos son cargar una instancia de MIS de la Quantum Optimization Benchmarking Library (QOBLIB) [1], formularla en forma de optimización binaria cuadrática sin restricciones (QUBO) con qiskit-addon-opt-mapper, enviarla a SQOA Solver para su ejecución en una QPU de IBM® y validar la solución devuelta.

El problema del conjunto independiente máximo

Un conjunto independiente es un subconjunto de nodos de un grafo tal que no hay dos nodos seleccionados que compartan una arista. Un conjunto independiente máximo (MIS) es un conjunto independiente con el mayor número posible de nodos. Las aplicaciones del MIS incluyen la planificación de horarios, la asignación de recursos y el diseño de redes.

El MIS es NP-difícil. En una búsqueda exhaustiva, cada nodo adicional duplica el número de subconjuntos a considerar, por lo que este enfoque es impracticable incluso para grafos de tamaño moderado. QOBLIB incluye el MIS como una de sus diez clases de problemas, por lo que es un benchmark útil para evaluar flujos de trabajo de optimización cuántica en hardware real.

Formulación matemática

Dado un grafo no dirigido $G = (V, E)$, asigna una variable binaria $x_v$ a cada nodo $v$:

• $x_v = 1$ si el nodo $v$ está seleccionado.

• $x_v = 0$ otherwise.

La formulación lineal binaria maximiza el número de nodos seleccionados e impide que ambos extremos de cualquier arista sean seleccionados:

$$\begin{aligned} \max_{x} \quad & \sum_{v \in V} x_v \\ \text{subject to} \quad & x_v + x_w \leq 1 && \forall (v,w) \in E, \\ & x_v \in \{0,1\} && \forall v \in V. \end{aligned}$$

El objetivo cuenta los nodos seleccionados. En conjunto, las restricciones de aristas garantizan que los nodos seleccionados formen un conjunto independiente.

Este tutorial usa la formulación binaria sin restricciones de QOBLIB, que reemplaza las restricciones de aristas por penalizaciones cuadráticas:

$$\max_{x \in \{0,1\}^{|V|}} \quad \sum_{v \in V} x_v - 2 \sum_{(v,w) \in E} x_v x_w.$$

Siempre que ambos extremos de una arista estén seleccionados, el segundo término resta dos del objetivo. Esta penalización hace que una selección conflictiva sea menos favorable que conservar solo uno de los extremos. El objetivo resultante es un QUBO, que es el formato de entrada que acepta SQOA Solver.

¿Por qué usar SQOA Solver?

Muchos enfoques de optimización cuántica asignan un qubit a cada variable binaria, de modo que la capacidad del hardware cuántico puede limitar directamente el tamaño del problema. SQOA Solver combina varias técnicas de reducción y de computación híbrida para aliviar esta restricción:

• Puede abordar problemas con más variables binarias que qubits tiene la QPU. El presolve aplica reglas de reducción que pueden fijar variables y simplificar el QUBO restante, preservando al menos una solución óptima. Empíricamente, el presolve también puede hacer más disperso el QUBO restante, lo que ayuda a la codificación basada en QRAC que lo sigue.

  Luego el solver usa una codificación basada en QRAC derivada de Quantum Random Access Optimization (QRAO) [3] para representar varias variables (hasta tres) sin interacción directa en el QUBO en el mismo qubit.

  Las reducciones del presolve y de la codificación dependen de la estructura del problema. Por ejemplo, en este tutorial, un problema de 200 variables usa solo 67 qubits.

• Puede ser menos sensible al ruido del hardware. La diagonalización cuántica basada en muestras [4], [5] usa la QPU para muestrear cadenas de bits pero realiza la diagonalización de forma clásica. Esto evita evaluaciones repetidas en la QPU para actualizar parámetros variacionales y puede reducir el impacto del ruido en el flujo de trabajo de optimización.

• Automatiza el flujo de trabajo desde el presolve hasta el posprocesamiento. Tú proporcionas una instancia QUBO con el formato correcto y seleccionas un backend. SQOA Solver ejecuta entonces todo el flujo de trabajo automáticamente. Aplica el presolve, asigna las variables clásicas a un problema cuántico relajado, construye y transpila los circuitos de muestreo, realiza el muestreo cuántico y la diagonalización clásica, redondea y refina la asignación, y reconstruye y evalúa la solución clásica.

Requisitos

Antes de comenzar este tutorial, asegúrate de tener instalados los siguientes paquetes:

• Cliente del catálogo de Qiskit Functions (pip install qiskit-ibm-catalog).

• Qiskit addon optimization mapper, usado para formular el problema (pip install qiskit-addon-opt-mapper).

• NetworkX y Matplotlib, usados para manejar y graficar el grafo (pip install networkx matplotlib).

También necesitas acceso a SQOA Solver desde el catálogo de Qiskit Functions. Completa el formulario para solicitar acceso a la función.

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

_needed = {"matplotlib": "matplotlib", "networkx": "networkx", "ommx": "ommx", "ommx_quantum_benchmarks": "ommx-quantum-benchmarks", "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")

# %pip install qiskit-ibm-catalog qiskit-addon-opt-mapper networkx matplotlib

Configuración

Primero, importa los paquetes y herramientas necesarios.

import urllib.request

import matplotlib.pyplot as plt
import networkx as nx
from qiskit_addon_opt_mapper import OptimizationProblem
from qiskit_addon_opt_mapper.converters import OptimizationProblemToQubo
from qiskit_ibm_catalog import QiskitFunctionsCatalog

SQOA Solver acepta un problema QUBO como un diccionario de coeficientes en el formato de tuplas-cadena usado por las funciones de optimización de IBM®. Define una función auxiliar que convierta el QUBO devuelto por OptimizationProblemToQubo a este formato.

El conversor siempre devuelve un problema de minimización, lo que coincide con la forma en que SQOA Solver trata un problema en forma de diccionario. Las claves usan los índices de variable del QUBO, y cada variable recibe una entrada lineal, incluso con coeficiente cero, para que la solución devuelta cubra todas las variables.

def to_problem_dict(qubo: OptimizationProblem) -> dict[str, float]:
    """Convert a QUBO from OptimizationProblemToQubo to the SQOA Solver dictionary format."""
    objective = qubo.objective
    payload = {"()": objective.constant}
    # Keep every variable in the problem, even with a zero linear coefficient.
    payload.update({f"({i},)": 0.0 for i in range(qubo.get_num_vars())})
    for i, coefficient in objective.linear.to_dict().items():
        payload[f"({i},)"] += coefficient
    for (i, j), coefficient in objective.quadratic.to_dict().items():
        # Fold a binary diagonal term x_i * x_i = x_i into the linear term.
        key = f"({i},)" if i == j else f"({i}, {j})"
        payload[key] = payload.get(key, 0.0) + coefficient
    return {key: float(value) for key, value in payload.items()}

Paso 1: Asignar entradas clásicas a un problema cuántico

SQOA Solver acepta un problema QUBO y realiza la asignación cuántica dentro de la función. En este tutorial, descargas una instancia de MIS de QOBLIB y la formulas como un QUBO con qiskit-addon-opt-mapper. Este paso abarca lo siguiente:

• Conectarse a SQOA Solver.

• Comprender el marco SQOA.

• Cargar la instancia del problema.

• Formular el QUBO y convertirlo para su envío.

Conectarse a SQOA Solver

Conéctate al catálogo de Qiskit Functions con tus credenciales de IBM Quantum Platform y luego carga SQOA Solver. El siguiente código supone que ya guardaste tu cuenta en tu entorno local.

Si la conexión falla, confirma que el administrador de tu cuenta de IBM Quantum Platform haya concedido a la instancia de servicio seleccionada acceso a SQOA Solver.

catalog = QiskitFunctionsCatalog(channel="ibm_quantum_platform")
solver = catalog.load("jij/sqoa-solver")

Comprender el marco SQOA

El Sampling-based Quantum Optimization Algorithm with Quantum Relaxation (SQOA-QR) [2] combina Quantum Random Access Optimization (QRAO) con la diagonalización cuántica basada en muestras:

1. Relajación cuántica y codificación: SQOA Solver convierte el QUBO en un objetivo de Ising de minimización de la forma $c + \sum_i h_i z_i + \sum_{i<j} J_{ij} z_i z_j$, donde $z_i \in \{-1, +1\}$. Luego QRAO [3] asigna cada variable de espín a un observable de Pauli. Para la codificación $(3,1)$-QRAC usada aquí, el hamiltoniano relajado es

   $$\widetilde{H} = cI + \sum_i \sqrt{k_i} h_i P_{f(i)} + \sum_{i<j} \sqrt{k_i k_j} J_{ij} P_{f(i)} P_{f(j)},$$

   donde $I$ es el operador identidad, $f(i)$ asigna la variable $i$ a un qubit y a uno de $X$, $Y$ o $Z$, y $k_i \in \{1,2,3\}$ es el número de variables asignadas al mismo qubit que $i$. Cuando los dos qubits relevantes contienen tres variables, los factores de escala lineal y cuadrático pasan a ser $\sqrt{3}$ y $3$, respectivamente.

   A las variables que comparten un qubit se les asignan observables de Pauli distintos que no conmutan. Las variables que interactúan en el QUBO se mantienen en qubits diferentes, mientras que las variables sin interacción directa en el QUBO pueden compartir un qubit. Por lo tanto, la reducción en el número de qubits depende de la estructura del problema.

2. Muestreo cuántico: Un procesador cuántico muestrea cadenas de bits a partir de circuitos diseñados para explorar estados de baja energía del hamiltoniano relajado.

3. Diagonalización basada en muestras: El solver proyecta el hamiltoniano relajado sobre el subespacio generado por los estados de la base obtenidos de las cadenas de bits muestreadas y diagonaliza el hamiltoniano proyectado de forma clásica [4], [5]. Para un conjunto fijo de cadenas de bits muestreadas, sea $\mathcal{S}_r$ el subespacio generado por $r$ estados de la base distintos, de modo que $\dim(\mathcal{S}_r) \leq r$. Su energía del estado fundamental estimada es:

   $$E_r = \min_{\substack{|\psi\rangle \in \mathcal{S}_r \\ \langle\psi|\psi\rangle=1}} \langle\psi|\widetilde{H}|\psi\rangle, \qquad \mathcal{S}_r \subseteq \mathcal{S}_{r'} \Longrightarrow E_{\mathrm{exact}} \leq E_{r'} \leq E_r \quad (r' \geq r),$$

   donde $E_{\mathrm{exact}}$ es la energía del estado fundamental del hamiltoniano relajado completo. Por lo tanto, un subespacio retenido más grande no puede aumentar la energía del estado fundamental estimada.

   Este orden supone el mismo resultado de muestreo y se refiere a la energía del hamiltoniano relajado antes del redondeo. No garantiza teóricamente una mejor solución clásica devuelta. Sin embargo, en QRAO se espera heurísticamente que un estado de menor energía proporcione una mejor solución clásica.

4. Redondeo: El estado relajado obtenido de la diagonalización se convierte en una asignación binaria clásica.

SQOA Solver rodea este marco con procesamiento clásico. Antes de la asignación cuántica, el presolve aplica reglas de reducción que pueden fijar variables y simplificar el QUBO restante, preservando al menos una solución óptima. Después de la diagonalización y el redondeo, una búsqueda local clásica refina la asignación, y OMMX reconstruye y evalúa la solución completa.

Cargar la instancia

QOBLIB distribuye cada instancia de MIS como un grafo en el formato DIMACS .gph, un formato basado en líneas en el que la línea que comienza con p indica el número de nodos y de aristas y cada línea que comienza con e define una arista.

QOBLIB también publica una solución de referencia óptima o la mejor conocida para cada instancia. Las siguientes funciones descargan ambas desde el repositorio de QOBLIB. DIMACS numera los nodos a partir de 1, por lo que el grafo se reetiqueta para comenzar desde 0.

Si prefieres partir de tu propio grafo, omite la descarga y formula el problema a partir de tu grafo de NetworkX de la misma manera.

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

def fetch_qoblib_graph(name: str) -> nx.Graph:
    """Download a QOBLIB independent-set instance as a NetworkX graph."""
    with urllib.request.urlopen(
        f"{QOBLIB_URL}/instances/{name}.gph"
    ) as response:
        lines = response.read().decode().splitlines()
    graph = nx.Graph()
    for fields in map(str.split, lines):
        if fields and fields[0] == "p":
            # Header: p edge <number of nodes> <number of edges>
            graph.add_nodes_from(range(int(fields[2])))
        elif fields and fields[0] == "e":
            # DIMACS labels nodes from 1; relabel them to start from 0.
            graph.add_edge(int(fields[1]) - 1, int(fields[2]) - 1)
    return graph

def fetch_reference_objective(name: str) -> float:
    """Read the objective value of the QOBLIB reference solution."""
    with urllib.request.urlopen(
        f"{QOBLIB_URL}/solutions/{name}.opt.sol"
    ) as response:
        for line in response.read().decode().splitlines():
            if line.startswith("# Objective value"):
                return float(line.split("=")[1])
    raise ValueError(f"No objective value found for {name}.")

INSTANCE_NAME = "gen200_p0-9_44"
G = fetch_qoblib_graph(INSTANCE_NAME)
reference_objective = fetch_reference_objective(INSTANCE_NAME)

Más adelante usas el valor objetivo de la solución de referencia para evaluar el resultado de SQOA Solver. Este tutorial resuelve este problema en un dispositivo con 156 qubits.

print(
    f"{INSTANCE_NAME}: {G.number_of_nodes()} nodes, {G.number_of_edges()} edges"
)
print(f"Reference objective: {reference_objective:g}")

gen200_p0-9_44: 200 nodes, 1990 edges
Reference objective: 44

Visualiza el grafo. Más adelante también lo usas para verificar que los nodos devueltos por SQOA Solver forman un conjunto independiente.

layout = nx.forceatlas2_layout(
    G, max_iter=500, scaling_ratio=3.0, gravity=1.0, seed=7
)
node_size = max(8, min(60, 4000 / max(G.number_of_nodes(), 1)))

fig, ax = plt.subplots(figsize=(9, 7))
nx.draw_networkx_edges(G, layout, ax=ax, alpha=0.2, width=0.6)
nx.draw_networkx_nodes(
    G, layout, node_size=node_size, node_color="lightgray", ax=ax
)
ax.set_title(
    f"{INSTANCE_NAME}: {G.number_of_nodes()} nodes, {G.number_of_edges()} edges"
)
ax.set_axis_off()
plt.show()

Formular el QUBO

Construye la formulación lineal binaria de la sección Antecedentes como un OptimizationProblem con una variable binaria por nodo, un objetivo que cuenta los nodos seleccionados y una restricción por arista. Luego conviértela con OptimizationProblemToQubo.

Con un peso de penalización de 2, el conversor reemplaza cada restricción de arista por el término de penalización $2 x_v x_w$ y convierte la maximización en una minimización, por lo que el problema convertido es la formulación binaria sin restricciones de QOBLIB con el signo invertido. Los índices de variable del QUBO son las etiquetas de nodo del grafo. La clase de aplicación IndependentSet en qiskit_addon_opt_mapper.applications construye el mismo modelo con restricciones con IndependentSet(G).to_optimization_problem().

Finalmente, convierte el QUBO al formato de diccionario con to_problem_dict(). Como el problema es un QUBO binario, la solicitud del Paso 2 declara su dominio de variables como "binary". La función realiza el presolve, la asignación cuántica y la construcción de circuitos después del envío.

mis = OptimizationProblem(INSTANCE_NAME)
mis.binary_var_list(G.number_of_nodes(), name="x")
mis.maximize(linear={v: 1 for v in G.nodes})
for u, v in G.edges:
    mis.linear_constraint({u: 1, v: 1}, "<=", 1)

converter = OptimizationProblemToQubo(penalty=2)
qubo = converter.convert(mis)
problem_dict = to_problem_dict(qubo)

print(f"QUBO variables: {qubo.get_num_vars()}")
print(f"Dictionary entries: {len(problem_dict)}")

QUBO variables: 200
Dictionary entries: 2191

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

SQOA Solver realiza la asignación cuántica y la preparación del hardware dentro de la función. Primero aplica el presolve al QUBO y luego asigna las variables restantes a un hamiltoniano relajado mediante una codificación basada en QRAC.

Para el muestreo cuántico, construye circuitos basados en el hamiltoniano relajado y los transpila para el backend seleccionado. Las reducciones del tamaño del problema y del número de qubits que logran el presolve y la codificación dependen del problema, así que configura el solver sin suponer un factor de reducción fijo.

Configurar las entradas del solver

SQOA Solver requiere dos entradas:

• problem, el diccionario del Paso 1.

• variable_type, que es "binary" para este QUBO.

También acepta dos entradas opcionales:

• backend_name selecciona la QPU. Cuando se omite o es None, la función selecciona la QPU operativa menos ocupada a la que tiene acceso tu instancia.

• options es un diccionario que controla el presupuesto de muestreo (shots), la semilla clásica (seed), el uso de sesión (session), la búsqueda local clásica (postprocessing_level) y las etiquetas del trabajo (job_tags). Si aumentas shots, las estadísticas de muestreo pueden mejorar.

Para conocer todas las entradas, sus valores predeterminados y las reglas de validación, consulta la referencia de la API.

Este tutorial indica el backend de forma explícita, usa los valores predeterminados de shots, session y postprocessing_level, y fija la semilla clásica. Reúne las entradas en un diccionario para poder pasarlas a solver.run() en el Paso 3.

# ibm_fez has 156 qubits
backend_name = (
    "ibm_fez"  # Omit this key or pass None for automatic selection.
)

sqoa_input = {
    "problem": problem_dict,
    "variable_type": "binary",
    "backend_name": backend_name,
}

sqoa_input["options"] = {
    "shots": 4096,
    "seed": 42,
    "session": False,
    "postprocessing_level": 1,
}

Paso 3: Ejecutar usando primitivas

Envía el trabajo con la conexión a SQOA Solver creada en el Paso 1. La función ejecuta la primitiva IBM Quantum Sampler en el backend seleccionado, recopila las cadenas de bits medidas y continúa con la diagonalización clásica y el posprocesamiento. Tú interactúas con un único trabajo de la función.

job = solver.run(**sqoa_input)
print(f"Job ID: {job.job_id}")

Job ID: dcee8e26-b8ac-4dd7-a76e-5adb5bc388e5

Para comprobar el estado de la carga de trabajo, consulta Comprobar el estado del trabajo. Internamente, la función pasa por las fases de asignación, optimización para el hardware, espera en cola, ejecución en la QPU y posprocesamiento.

job.status()

'INITIALIZING'

job.result() se bloquea hasta que el trabajo se completa y devuelve un diccionario con la solución, su valor objetivo y su factibilidad, y metadatos que contienen información del solver y del uso de recursos. Para ver la definición completa de las entradas y salidas, consulta la referencia de la API.

result = job.result()

Paso 4: Posprocesar el resultado y convertirlo a un formato clásico

Inspecciona la salida completa de la función, asigna la asignación devuelta de vuelta al grafo, verifica los nodos seleccionados y visualiza el resultado.

Inspeccionar el resultado

El diccionario de resultados contiene cuatro campos de nivel superior:

• solution es la asignación completa de variables, con claves x_i, donde i es el índice de la variable (por ejemplo, x_17). En este tutorial, el índice de la variable es la etiqueta del nodo.

• objective_value es el objetivo de esa asignación evaluado sobre el diccionario enviado, es decir, sobre el QUBO de minimización.

• feasible se refiere únicamente al dominio de las variables, porque el diccionario no tiene restricciones.

• metadata contiene solver_info y resource_usage. solver_info registra la seed efectiva de la ejecución. Si se ejecutó la búsqueda local clásica, solver_info también registra en solution_before_postprocessing la asignación redondeada previa a ese refinamiento.

solver_info = result["metadata"]["solver_info"]

print(f"Result fields: {list(result)}")
print(f"Solution entries: {len(result['solution'])}")
print(f"First entries: {dict(list(result['solution'].items())[:3])}")
print(f"Objective value: {result['objective_value']}")
print(f"Feasible: {result['feasible']}")
print(f"Solver-info fields: {list(solver_info)}")
print(f"Effective seed: {solver_info['seed']}")
print(f"Resource-usage phases: {list(result['metadata']['resource_usage'])}")

Result fields: ['solution', 'objective_value', 'feasible', 'metadata']
Solution entries: 200
First entries: {'x_0': 0.0, 'x_1': 0.0, 'x_2': 1.0}
Objective value: -35.0
Feasible: True
Solver-info fields: ['seed', 'solution_before_postprocessing']
Effective seed: 42
Resource-usage phases: ['RUNNING: MAPPING', 'RUNNING: OPTIMIZING_FOR_HARDWARE', 'RUNNING: WAITING_FOR_QPU', 'RUNNING: EXECUTING_QPU', 'RUNNING: POST_PROCESSING']

Asignar la solución al grafo

Reúne los valores devueltos en el orden de los índices de las variables y asígnalos de vuelta a las variables del problema original con interpret(). Los nodos seleccionados son las variables con valor 1, y is_feasible() comprueba la asignación contra las restricciones de aristas del problema original.

x_qubo = [result["solution"][f"x_{i}"] for i in range(qubo.get_num_vars())]
x = converter.interpret(x_qubo)
selected_nodes = [node for node, value in enumerate(x) if value > 0.5]

print(f"Selected nodes: {len(selected_nodes)}")
print(f"Satisfies every edge constraint: {mis.is_feasible(x)}")

Selected nodes: 35
Satisfies every edge constraint: True

Comparar con la solución antes del posprocesamiento

Como postprocessing_level es 1, solver_info también registra en solution_before_postprocessing la asignación redondeada previa a la búsqueda local clásica. Usa las mismas claves que solution.

Evalúala sobre el QUBO para ver cuánto mejoró el refinamiento el resultado. Ambos valores son objetivos del QUBO de minimización enviado, por lo que un valor menor es mejor. El campo se omite cuando la búsqueda local no se ejecuta, por ejemplo, cuando el presolve fija todas las variables.

before = solver_info.get("solution_before_postprocessing")
if before is None:
    print("The classical local search did not run for this problem.")
else:
    x_before = [before[f"x_{i}"] for i in range(qubo.get_num_vars())]
    changed = sum(
        before[key] != value for key, value in result["solution"].items()
    )
    print(
        f"Objective before local search: {qubo.objective.evaluate(x_before)}"
    )
    print(f"Objective after local search: {result['objective_value']}")
    print(f"Variables changed by local search: {changed}")

Objective before local search: -12.0
Objective after local search: -35.0
Variables changed by local search: 19

Verificar la restricción de independencia

Como el QUBO representa la adyacencia mediante términos de penalización en lugar de restricciones explícitas, un resultado heurístico aún puede seleccionar nodos adyacentes. Comprueba los nodos devueltos directamente contra el grafo. Para la comparación y la visualización de las secciones siguientes, copia el conjunto devuelto y elimina de forma voraz uno de los extremos de cada conflicto detectado.

returned_set = set(selected_nodes)
conflicts = [
    (u, v) for u, v in G.edges if u in returned_set and v in returned_set
]
print(f"Conflicting edges in the returned set: {len(conflicts)}")

independent_set = returned_set.copy()
for u, v in conflicts:
    if u in independent_set and v in independent_set:
        # Drop the endpoint that has more selected neighbors.
        drop = max(
            (u, v),
            key=lambda node: sum(nb in independent_set for nb in G[node]),
        )
        independent_set.remove(drop)

assert all(
    not (u in independent_set and v in independent_set) for u, v in G.edges
)
print(f"Independent set size after repair: {len(independent_set)}")

Conflicting edges in the returned set: 0
Independent set size after repair: 35

Comparar con la solución de referencia

En el Paso 1, descargaste el valor objetivo de la solución de referencia de QOBLIB. Las soluciones de referencia de QOBLIB pueden ser óptimas o las mejores conocidas, así que compara con el objetivo de referencia sin suponer que siempre es un óptimo certificado.

Para este problema de maximización, una razón de 1.0 significa que el resultado reparado coincide con el objetivo de referencia.

ratio_to_reference = len(independent_set) / reference_objective

print(f"Reference objective: {reference_objective:g}")
print(f"Ratio to reference: {ratio_to_reference:.3f}")

Reference objective: 44
Ratio to reference: 0.795

Visualizar el resultado

Grafica de nuevo el grafo con el conjunto independiente reparado resaltado. Ningún par de nodos resaltados comparte una arista.

fig, ax = plt.subplots(figsize=(9, 7))
nx.draw_networkx_edges(G, layout, ax=ax, alpha=0.2, width=0.6)
nx.draw_networkx_nodes(
    G,
    layout,
    nodelist=[v for v in G if v not in independent_set],
    node_size=node_size,
    node_color="lightgray",
    ax=ax,
)
nx.draw_networkx_nodes(
    G,
    layout,
    nodelist=sorted(independent_set),
    node_size=node_size * 1.4,
    node_color="tab:blue",
    ax=ax,
)
ax.set_title(
    f"Independent set size: {len(independent_set)} "
    f"(reference: {reference_objective:g})"
)
ax.set_axis_off()
plt.show()

Leer el uso de recursos

Los metadatos del resultado informan CPU_TIME para las fases distintas de RUNNING: EXECUTING_QPU, cuando está disponible. La fase RUNNING: EXECUTING_QPU puede informar QPU_TIME, el uso de QPU devuelto por Quantum Compute, si el uso final está disponible para cada trabajo de Quantum Compute.

usage = result["metadata"]["resource_usage"]

for phase, metrics in usage.items():
    line = f"{phase:36s}"
    if "CPU_TIME" in metrics:
        line += f" CPU {metrics['CPU_TIME']:8.1f} s"
    if "QPU_TIME" in metrics:
        line += f" QPU {metrics['QPU_TIME']:8.1f} s"
    print(line)

RUNNING: MAPPING                     CPU     11.8 s
RUNNING: OPTIMIZING_FOR_HARDWARE     CPU     15.4 s
RUNNING: WAITING_FOR_QPU             CPU     16.5 s
RUNNING: EXECUTING_QPU               QPU      3.0 s
RUNNING: POST_PROCESSING             CPU     55.8 s

Conclusión

En este tutorial, descargaste una instancia MIS de QOBLIB, la formulaste como un QUBO con qiskit-addon-opt-mapper, te conectaste a SQOA Solver, configuraste y enviaste la carga de trabajo, asignaste de nuevo la asignación devuelta al grafo y comprobaste los nodos seleccionados con el grafo original.

También comparaste el resultado con la solución de referencia de QOBLIB, examinaste la contribución del posprocesamiento clásico e inspeccionaste el uso de recursos de cada fase de ejecución.

SQOA Solver combina presolve, QRAO con una codificación basada en QRAC, construcción de circuitos de muestreo, transpilación adaptada al hardware, diagonalización basada en muestras, redondeo y refinamiento clásico. Este flujo de trabajo puede asignar más variables binarias de las que permitiría una codificación de una variable por Qubit. La magnitud de la reducción gracias al presolve y a la codificación depende de la estructura del problema, y la calidad de la solución depende de las muestras obtenidas.

Los ajustes shots y postprocessing_level controlan, respectivamente, el presupuesto de muestreo cuántico y el refinamiento clásico, sin cambiar el flujo de trabajo de envío.

Apéndice: Envía el problema como una instancia OMMX

SQOA Solver también acepta un ommx.v1.Instance del SDK de OMMX. El paquete OMMX Quantum Benchmarks distribuye los problemas de QOBLIB como instancias OMMX junto con sus soluciones de referencia, de modo que puedes cargar el mismo QUBO sin tener que formularlo tú mismo.

Con una entrada OMMX, objective_value se evalúa en el sentido de la instancia, y el resultado también contiene la ommx.v1.Solution canónica. Instala el paquete, que también instala el SDK de OMMX:

# %pip install ommx-quantum-benchmarks

Carga el modelo binary_unconstrained de la misma instancia. El cargador del conjunto de datos imprime mensajes de progreso, por lo que el código los captura para mantener la salida compacta.

%%capture
from ommx_quantum_benchmarks.qoblib import IndependentSet

ommx_instance, _ = IndependentSet()("binary_unconstrained", INSTANCE_NAME)

SQOA Solver recibe una instancia OMMX como una cadena Base64 estándar con relleno y devuelve la solución canónica en el mismo formato. Define dos funciones auxiliares para esta conversión:

• to_problem_payload() serializa un ommx.v1.Instance en la cadena que pasas como problem.

• to_ommx_solution() decodifica la ommx.v1.Solution canónica del resultado.

import base64

from ommx.v1 import Instance, Solution

def to_problem_payload(instance: Instance) -> str:
    """Serialize an OMMX instance into the `problem` string for SQOA Solver."""
    return base64.b64encode(instance.to_bytes()).decode()

def to_ommx_solution(result: dict) -> Solution:
    """Decode the canonical OMMX solution from a SQOA Solver result."""
    payload = result["metadata"]["solver_info"]["ommx_solution"]
    return Solution.from_bytes(base64.b64decode(payload, validate=True))

Envía la instancia con las mismas entradas que antes, reemplazando solo problem. Luego decodifica la solución canónica y lee los nodos seleccionados por nombre de variable.

ommx_job = solver.run(
    **{**sqoa_input, "problem": to_problem_payload(ommx_instance)}
)
ommx_result = ommx_job.result()

ommx_solution = to_ommx_solution(ommx_result)
x_values = ommx_solution.extract_decision_variables("x")
ommx_nodes = sorted(
    node for (node,), value in x_values.items() if value > 0.5
)

print(f"Objective value: {ommx_result['objective_value']}")
print(f"Selected nodes: {len(ommx_nodes)}")

Objective value: 35.0
Selected nodes: 35

Próximos pasos

Recomendaciones

• Aplica el flujo de trabajo a tus propios problemas QUBO. Construye un OptimizationProblem como se muestra en la guía de SQOA Solver. Los pasos de conversión y envío siguen siendo los mismos, pero adapta la validación a la estructura de tu problema.
• Envía el problema como una instancia OMMX, como se muestra en el apéndice. Consulta la referencia de la API para ver los formatos de problema aceptados y los campos devueltos.
• Explora otras instancias de conjuntos independientes en el repositorio de QOBLIB o mediante OMMX Quantum Benchmarks.
• Aprende más sobre el modelado con qiskit-addon-opt-mapper o JijModeling y sobre el intercambio de problemas con OMMX.

Referencias

[1] Koch, T., Bernal Neira, D. E., Chen, Y., Cortiana, G., Egger, D. J., Heese, R., Hegade, N. N., Gomez Cadavid, A., Huang, R., Itoko, T., et al. (2026). Quantum optimization benchmarking library: The intractable decathlon. Nature Computational Science, 6, 653–671. DOI, arXiv:2504.03832

[2] Matsuyama, H., & Yamashiro, Y. (2025). Sampling-based quantum optimization algorithm with quantum relaxation. 2025 IEEE International Conference on Quantum Computing and Engineering (QCE), 1, 2323–2333. DOI, arXiv:2504.12629

[3] Fuller, B., Hadfield, C., Glick, J. R., Imamichi, T., Itoko, T., Thompson, R. J., Jiao, Y., Kagele, M. M., Blom-Schieber, A. W., Raymond, R., et al. (2024). Approximate solutions of combinatorial problems via quantum relaxations. IEEE Transactions on Quantum Engineering, 5, 1–15. DOI, arXiv:2111.03167

[4] Kanno, K., Kohda, M., Imai, R., Koh, S., Mitarai, K., Mizukami, W., & Nakagawa, Y. O. (2026). Quantum-selected configuration interaction: Classical diagonalization of Hamiltonians in subspaces selected by quantum computers. Physical Review Research, 8(2), 023268. DOI, arXiv:2302.11320

[5] Robledo-Moreno, J., Motta, M., Haas, H., Javadi-Abhari, A., Jurcevic, P., Kirby, W., et al. (2025). Chemistry beyond the scale of exact diagonalization on a quantum-centric supercomputer. Science Advances, 11(25), eadu9991. DOI, arXiv:2405.05068