Trova l'insieme indipendente massimo con l'ottimizzatore quantistico vincolato Aqarios

Nota

Le Qiskit Functions sono una funzionalità sperimentale disponibile solo per gli utenti dei piani IBM Quantum® Premium Plan, Flex Plan e On-Prem (tramite IBM Quantum Platform API). Sono in stato di rilascio in anteprima e soggette a modifiche.

Stima di utilizzo: 30 secondi su un processore Heron r2. (NOTA: questa è solo una stima. Il tuo runtime potrebbe variare.)

Contesto

Questo tutorial mostra come trovare l'insieme indipendente massimo di un grafo utilizzando l'ottimizzatore quantistico vincolato Aqarios [1], un problema di ottimizzazione combinatoria vincolata. Un'istanza dalla libreria di benchmark QOBLIB [2] viene formulata come programma lineare binario e passata alla Optimizer Application Function. L'ottimizzatore gestisce internamente tutta la riformulazione, la sintesi del circuito, la transpilazione e il warm-start iterativo (vedi [3] per i dettagli).

Il tutorial copre i seguenti passaggi:

1. Definire il problema come programma lineare usando OptimizationProblem da qiskit-addon-opt-mapper

2. Eseguire l'ottimizzazione quantistica usando l'ottimizzatore quantistico vincolato Aqarios

3. Recuperare e visualizzare i risultati

Il problema dell'insieme indipendente massimo

Il problema dell'insieme indipendente massimo (MIS) è una sfida fondamentale nell'ottimizzazione combinatoria. Formalmente, dato un grafo $G(V, E)$, l'obiettivo è trovare il più grande sottoinsieme di vertici $V_I \subset V$ tale che nessuna coppia di vertici in $V_I$ sia connessa da un arco, come in $\nexists (u, v) \in E : v \in V_I \wedge u \in V_I$. A ogni vertice viene assegnata una variabile decisionale binaria $x_i \in \{0, 1\}$, e un vincolo $x_u + x_v \leq 1$ viene introdotto per ogni arco, garantendo che al massimo un estremo di ogni arco sia selezionato. Il problema può quindi essere formulato come il seguente problema di massimizzazione:

$$\max_{x_i} \sum_{i \in V} x_i \qquad\text{(trova l'insieme più grande)}\\ \text{s.t.} \quad x_u + x_v \leq 1 \quad \forall (u, v) \in E.$$

Il MIS ha un'ampia gamma di applicazioni pratiche. Nella pianificazione delle reti wireless, un insieme indipendente corrisponde a un gruppo di trasmettitori che possono trasmettere tutti simultaneamente senza interferenza reciproca. Nella pianificazione (scheduling), modella la più grande collezione di attività che possono essere eseguite contemporaneamente dati conflitti di risorse a coppie. In biologia computazionale, cattura insiemi di proteine che non interagiscono reciprocamente in una rete.

Nonostante la sua formulazione intuitiva, il MIS è NP-hard, e anche per grafi con poche centinaia di nodi alcune istanze specifiche diventano difficili da risolvere esattamente o euristicamente [2]. Il problema dà anche origine a strutture di vincoli sparse ben adatte per implementazioni hardware dell'ottimizzazione quantistica, rendendolo un benchmark interessante per i dispositivi quantistici a breve termine.

Ottimizzatore quantistico vincolato Aqarios

L'approccio standard per incorporare un problema binario vincolato nell'ottimizzazione quantistica trasforma il modello in un formato non vincolato aggiungendo termini di penalità: ogni vincolo violato $x_u + x_v \leq 1$ contribuisce con $2 x_u x_v$ all'obiettivo di minimizzazione $-\sum_i x_i$. Questo viene gestito automaticamente dalla Constrained Quantum Optimizer Qiskit Function.

Oltre a questa trasformazione standard, l'ottimizzatore identifica le cricche nel grafo dei vincoli. Una cricca è un insieme di nodi $V_C$ in cui ogni coppia di nodi condivide un arco. Di conseguenza, i $\binom{|V_C|}{2}$ vincoli a coppie $x_u + x_v \leq 1 \;\forall (u,v) \in E_C$ possono essere sostituiti da un unico vincolo più stretto $\sum_{i \in V_C} x_i \leq 1$. Introducendo una variabile di slack $y$ questo diventa un'uguaglianza $\sum_i x_i + y = 1$, che assume la forma di un vincolo one-hot che può essere imposto direttamente nel QAOA usando gli XY-mixer [3]. Questo riduce lo spazio di ricerca ed evita la necessità di termini di penalità per quei vincoli, migliorando la qualità della soluzione.

Inoltre, le variabili connesse a un solo vicino sono chiamate nodi pendant e vengono fissate deterministicamente dall'algoritmo prima dell'esecuzione quantistica, riducendo ulteriormente la dimensione effettiva del problema.

L'ottimizzatore quantistico vincolato impiega un approccio di warm-start iterativo compatibile con gli XY-mixer [1], che restringe progressivamente lo spazio di ricerca orientando la distribuzione dello stato quantistico verso regioni di soluzione promettenti attraverso le iterazioni. Questo consente l'uso di parametri QAOA ad angolo fisso, eliminando la necessità di addestramento dei parametri variazionali. I requisiti totali di risorse quantistiche sono governati unicamente dal numero di iterazioni di warm-start, il che rende il costo quantistico semplice da controllare.

Requisiti

Prima di iniziare questo tutorial, assicurati di aver installato i seguenti requisiti:

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

Facoltativamente, per l'Appendice devi installare

• Luna Model (pip install luna-model)

Configurazione

Importa tutte le dipendenze richieste.

# 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

Innanzitutto, autenticati usando la tua chiave API di IBM Quantum. Poi, seleziona la Qiskit Function come segue. (Questo codice presume che tu abbia già salvato il tuo account nel tuo ambiente locale.)

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

Passo 1: Mappare gli input classici nel problema quantistico

Il problema viene formulato come un file LP, un formato comune per i problemi di ottimizzazione che funge da input per l'ottimizzatore quantistico vincolato Aqarios. Oltre ai file LP, la funzione supporta anche i file MPS e le rappresentazioni native di Luna Model. Il file LP viene generato attraverso i seguenti passaggi:

1. Recuperare un'istanza di grafo dal QOBLIB [2]

2. Modellare il problema di ottimizzazione

3. Generare il file LP

Caricare il grafo dell'istanza del problema

I grafi sono specificati nel formato DIMACS .gph, un formato basato su righe in cui le righe che iniziano con e definiscono gli archi, le righe che iniziano con p definiscono l'intestazione del problema, e le righe che iniziano con c sono commenti:

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

Il file .gph può essere scaricato dal repository QOBLIB usando la seguente funzione, che lo analizza anche in un grafo NetworkX. Nota che il formato DIMACS usa un'etichettatura dei nodi a base 1, che qui viene convertita in indicizzazione a base 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.

Questo esempio usa l'istanza es60fst02 da QOBLIB, un grafo con 186 nodi e 280 archi. Grazie ai passaggi di preprocessing impiegati dall'ottimizzatore quantistico vincolato, questa istanza è risolvibile su dispositivi Heron a 156 qubit. Il grafo può essere visualizzato usando matplotlib:

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

Costruire il problema di ottimizzazione

Il problema dell'insieme indipendente massimo può essere formulato direttamente usando OptimizationProblem. Ogni nodo del grafo diventa una variabile decisionale binaria, e ogni arco introduce un vincolo che garantisce che al massimo uno dei suoi estremi sia selezionato:

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

Una scorciatoia

Il pacchetto qiskit-addon-opt-mapper fornisce una classe applicativa pre-implementata per il problema dell'insieme indipendente massimo, che semplifica la formulazione precedente in un'unica chiamata:

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

Tradurre il problema in un file LP

L'OptimizationProblem di per sé non supporta l'esportazione in file LP, ma è interoperabile con DOcplex, che lo supporta. Generare il contenuto del file LP richiede solo due righe:

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

Questo formato è nativo dell'ottimizzatore quantistico vincolato.

Step 2: Ottimizzare il problema per l'esecuzione su hardware quantistico

Tutta la sintesi del circuito, l'ottimizzazione e la transpilazione sono gestite nativamente dalla funzione. Consulta la sezione input nel riferimento API per gli argomenti con cui chiamare la funzione.

Per mettere a punto il comportamento dell'algoritmo, consulta l'elenco delle opzioni nel riferimento API. Se vuoi che il mapping del circuito sia riproducibile tra le esecuzioni, fissa l'opzione seed_transpiler.

Per maggiori informazioni, consulta la guida all'ottimizzatore quantistico vincolato Aqarios e il riferimento API.

Passo 3: Eseguire usando le primitive Qiskit

Il file LP può ora essere inviato all'ottimizzatore:

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, l'algoritmo procede attraverso le seguenti fasi:

1. Preprocessing:

   • Ridurre le variabili fissabili

   • Trovare le cricche

   • Identificare i tipi di vincolo

   • Valutare i fattori di penalità per i termini di penalità

   • Applicare le trasformazioni dei vincoli

   • Sintetizzare il circuito con metodi di imposizione dei vincoli

   • Approssimazione del problema e transpilazione

2. Catene parallele di cicli iterativi:

   • Campionare dal circuito con parametri fissi

   • Applicare il postprocessing

   • Valutare e impostare nuove probabilità di warm-start

3. Postprocessing:

   • Trovare i migliori campioni e verificare la fattibilità rispetto al problema di input

Monitorare l'avanzamento

Consulta le seguenti sezioni nella pagina Guida introduttiva alle Qiskit Functions per monitorare l'avanzamento del tuo job:

• Controlla lo stato del job

• Recupera i risultati

# Monitor the job status
job.status()

'QUEUED'

Passo 4: Post-elaborare e restituire i risultati nel formato classico desiderato

Il risultato in output è un dizionario, i cui campi sono descritti nella sezione Output del riferimento API.

Quando l'elenco solutions contiene più di una voce, sono stati trovati più ottimi degeneri. Qui viene considerata solo la prima soluzione, indirizzata per nome di variabile. Le stesse soluzioni sono disponibili anche come stringhe di bit in solution_bitstrings, dove metadata.solver_info.variable_mapping fornisce la posizione di carattere di ogni variabile.

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

Visualizzazione

L'insieme indipendente identificato può essere visualizzato evidenziando i nodi selezionati nel 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)

Appendice: enunciato del problema con Luna Model

Oltre all'approccio con qiskit-addon-opt-mapper mostrato sopra, la Qiskit Function accetta anche modelli creati con Luna Model [4], l'SDK di modellazione di Aqarios. Dopo l'installazione del pacchetto PyPI luna-model, importalo come segue:

Setup:

from luna_model import Model, Sense
import numpy as np

Il modello viene quindi costruito dal grafo nello stesso modo di qiskit-addon-opt-mapper: Costruisci il modello:

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

Prossimi passi

Raccomandazioni

• Consulta la guida all'ottimizzatore quantistico vincolato Aqarios per una descrizione dettagliata di tutte le funzionalità della funzione.
• Esplora il riferimento API per l'elenco completo dei parametri di input e dei campi di output.
• Sperimenta con le opzioni dell'algoritmo (reps, num_parallel, shots, postprocessing_level) sul tuo problema di ottimizzazione binaria vincolata per valutarne l'impatto sulla qualità della soluzione e sul tempo di esecuzione.

Riferimenti

1. IBM Quantum, Guida all'ottimizzatore quantistico vincolato Aqarios

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