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

Stima del tempo di esecuzione: 30 secondi su un processore Heron r2. (NOTA: Si tratta solo di una stima. (La durata potrebbe variare.)

Sfondo

Questo tutorial illustra come individuare l'insieme indipendente massimo di un grafo utilizzando l'Aqarios Constrained Quantum Optimizer [1], un problema di ottimizzazione combinatoria con vincoli. Un'istanza della libreria di benchmark QOBLIB [2] viene formulata come un programma lineare binario e trasmessa alla funzione applicativa dell'ottimizzatore. L'ottimizzatore gestisce internamente tutte le operazioni di riformulazione, sintesi dei circuiti, transpilazione e avvio a caldo iterativo (per ulteriori dettagli, si veda [3] ).

Il tutorial illustra i seguenti passaggi:

1. Definire il problema come un programma lineare utilizzando il OptimizationProblem di qiskit-addon-opt-mapper
2. Eseguire l'ottimizzazione quantistica utilizzando l'ottimizzatore quantistico con vincoli di Aqarios
3. Recuperare e visualizzare i risultati

Il problema dell'insieme indipendente massimo

Il problema dell'insieme indipendente massimo (MIS) rappresenta 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 non vi siano due vertici in $V_I$ collegati da un arco, come illustrato in $\nexists (u, v) \in E : v \in V_I \wedge u \in V_I$. A ciascun vertice viene assegnata una variabile decisionale binaria $x_i \in \{0, 1\}$, e per ogni arco viene introdotto un vincolo $x_u + x_v \leq 1$ che garantisce che venga selezionato al massimo un estremo di ciascun arco. Il problema può quindi essere formulato come il seguente problema di massimizzazione:

Il MIS trova ampio impiego in una vasta gamma di applicazioni pratiche. Nella progettazione delle reti wireless, un insieme indipendente corrisponde a un gruppo di trasmettitori che possono tutti trasmettere contemporaneamente senza interferenze reciproche. Nella pianificazione, modella l'insieme più ampio di attività che possono essere eseguite contemporaneamente, tenendo conto dei conflitti tra risorse a coppie. Nella biologia computazionale, questo concetto descrive insiemi di proteine che non interagiscono tra loro all’interno di una rete.

Nonostante la sua formulazione intuitiva, il problema MIS è NP-difficile e, anche nel caso di grafi con poche centinaia di nodi, alcune istanze specifiche risultano difficili da risolvere in modo esatto o euristico [2]. Il problema dà inoltre origine a strutture di vincoli sparse che si prestano bene alle implementazioni hardware dell’ottimizzazione quantistica, rendendolo un benchmark interessante per i dispositivi quantistici di prossima generazione.

Ottimizzatore quantistico vincolato Aqarios

L'approccio standard per incorporare un problema binario con vincoli nell'ottimizzazione quantistica consiste nel trasformare il modello in un formato senza vincoli aggiungendo termini di penalità: ogni vincolo violato $x_u + x_v \leq 1$ contribuisce $2 x_u x_v$ all'obiettivo di minimizzazione $-\sum_i x_i$. Questa operazione viene gestita automaticamente dalla funzione Qiskit "Constrained Quantum Optimizer".

Oltre a questa trasformazione standard, l'ottimizzatore identifica i clique nel grafo dei vincoli. Una cricca è un insieme di nodi $V_C$ in cui ogni coppia di nodi è collegata da un arco. Di conseguenza, i vincoli a coppie $\binom{|V_C|}{2}$ $x_u + x_v \leq 1 \;\forall (u,v) \in E_C$ possono essere sostituiti da un unico vincolo più rigoroso $\sum_{i \in V_C} x_i \leq 1$. Introducendo una variabile di margine $y$, si ottiene un'uguaglianza $\sum_i x_i + y = 1$, che assume la forma di un vincolo "one-hot" applicabile direttamente in QAOA tramite i mixer XY [3]. Ciò riduce lo spazio di ricerca ed evita la necessità di applicare termini di penalità per tali vincoli, migliorando la qualità della soluzione.

Inoltre, le variabili collegate a un solo vicino sono denominate “nodi pendenti” e vengono fissate in modo deterministico dall’algoritmo prima dell’esecuzione quantistica, riducendo ulteriormente la dimensione effettiva del problema.

Il Constrained Quantum Optimizer adotta un approccio iterativo di “warm-starting” compatibile con i mixer XY [1], che restringe progressivamente lo spazio di ricerca orientando la distribuzione degli stati quantistici verso regioni di soluzione promettenti nel corso delle iterazioni. Ciò consente di utilizzare parametri QAOA ad angolo fisso, eliminando la necessità di un addestramento variazionale dei parametri. Il fabbisogno totale di risorse quantistiche dipende esclusivamente dal numero di iterazioni di avvio a caldo, il che significa che il costo quantistico è facilmente controllabile.

Requisiti

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

• Qiskit Runtime (pip install qiskit-ibm-runtime)
• Qiskit Functions Catalog IBM Cliente (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 è necessario installare

• Modello Luna (pip install luna-model)

Configura

Importa tutte le dipendenze necessarie.

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

Per prima cosa, effettua l'autenticazione utilizzando la tua chiave API IBM Quantum. Quindi, selezionare la funzione Qiskit come indicato di seguito. (Questo codice presuppone che tu abbia già salvato il tuo account nell'ambiente locale.)

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

Fase 1: Mappatura degli input classici al problema quantistico

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

1. Recupera un'istanza di grafico dalla libreria QOBLIB [2]
2. Formulare il problema di ottimizzazione
3. Genera il file LP

Carica il grafico dell'istanza del problema

I grafici sono specificati nel formato .gph DIMACS, un formato basato su righe in cui le righe che iniziano con e definiscono gli spigoli, quelle che iniziano con p definiscono l'intestazione del problema e quelle 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 utilizzando la seguente funzione, che provvede anche a analizzarlo per ricavarne un grafico di tipo “ NetworkX ”. Si noti che il formato DIMACS utilizza una numerazione dei nodi a partire da 1, che in questo caso viene convertita in un'indicizzazione a partire da 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.

Questo esempio utilizza l'istanza es60fst02 di QOBLIB, un grafo con 186 nodi e 280 archi. Grazie alle fasi di pre-elaborazione utilizzate dal Constrained Quantum Optimizer, questa istanza è risolvibile su dispositivi Heron da 156 qubit. Il grafico può essere visualizzato utilizzando matplotlib:

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

Output:

Formulare il problema di ottimizzazione

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

# 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 già implementata per il problema dell'insieme indipendente massimo, che semplifica la formulazione sopra riportata in una singola chiamata:

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

Converti il problema in un file LP

Il programma in sé OptimizationProblem non supporta l'esportazione di file LP, ma è interoperabile con DOcplex, che invece la supporta. Per generare il contenuto del file LP bastano 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("...")

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

Questo formato è nativo del Constrained Quantum Optimizer.

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

Tutte le operazioni di sintesi, ottimizzazione e transpilazione dei circuiti sono gestite in modo nativo dalla funzione. Consultare la sezione “Input” nella documentazione di riferimento dell’API per conoscere gli argomenti con cui chiamare la funzione.

Per ottimizzare il comportamento dell'algoritmo, consultare l' elenco delle opzioni nella documentazione di riferimento dell'API. Se desideri che la mappatura del circuito sia riproducibile tra una serie e l'altra, imposta l'opzione seed_transpiler .

Per ulteriori informazioni, consultare la guida e il manuale di riferimento dell'API di Aqarios Constrained Quantum Optimizer.

Passaggio 3: Eseguire il comando utilizzando Qiskit primitives

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

Output:

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

A livello interno, l'algoritmo procede attraverso le seguenti fasi:

1. Pre-elaborazione :
   • Ridurre le variabili modificabili
   • Trova i gruppetti
   • Identificare i tipi di vincolo
   • Valutare i fattori di penalizzazione per i termini soggetti a penalizzazione
   • Applica le trasformazioni di vincolo
   • Sintetizzare circuiti con metodi di applicazione dei vincoli
   • Approssimazione del problema e transpilazione
2. Catene parallele di cicli iterativi :
   • Campione tratto da un circuito con parametri fissi
   • Applica la post-elaborazione
   • Valutare e impostare nuove probabilità di avvio a caldo
3. Post-elaborazione :
   • Trova i migliori esempi e verifica la fattibilità rispetto al problema di partenza

Monitorare lo stato di avanzamento

Per monitorare lo stato di avanzamento del tuo lavoro, consulta le seguenti sezioni nella pagina “Guida introduttiva a Qiskit Functions ”:

• Verifica lo stato del lavoro
• Recupera i risultati

# Monitor the job status
job.status()

Output:

'QUEUED'

Fase 4: Elaborazione successiva e restituzione dei risultati nel formato classico desiderato

Il risultato restituito è un dizionario, i cui campi sono descritti nella sezione "Output " della documentazione di riferimento dell'API.

Quando l'elenco solutions contiene più di una voce, significa che sono stati individuati più ottimi degeneri. In questa sede viene presa in considerazione solo la prima soluzione, indicata dal nome della variabile. Le stesse soluzioni sono disponibili anche come stringhe di bit in solution_bitstrings, dove metadata.solver_info.variable_mapping indica la posizione di ciascun carattere all'interno 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) + "}")

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}

Visualizzazione

L'insieme indipendente individuato può essere visualizzato evidenziando i nodi selezionati nel grafico:

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

Appendice: Descrizione del problema con il modello Luna

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

Configurazione:

from luna_model import Model, Sense
import numpy as np

Il modello viene quindi costruito a partire dal grafico, allo stesso modo di qiskit-addon-opt-mapper:

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

Fasi successive

Riferimenti

1. IBM Quantum : Guida all'ottimizzatore quantistico con vincoli di Aqarios
2. Koch et al. (2026), The Quantum Optimization Benchmarking Library 10.1038/s43588-026-00991-1
3. Bucher et al. (2026), *Ottimizzazione quantistica vincolata tramite XY-Mixer iterativi con warm-start *10.1088/1367-2630/ae8ea2
4. Documentazione sul modello Luna di Aqarios GmbH,