Găsește Maximum Independent Set cu Aqarios Constrained Quantum Optimizer

Notă

Qiskit Functions este o funcționalitate experimentală disponibilă doar utilizatorilor IBM Quantum® Premium Plan, Flex Plan și On-Prem (prin IBM Quantum Platform API) Plan. Acestea au statutul de preview release și pot suferi modificări.

Estimare de utilizare: 30 de secunde pe un procesor Heron r2. (NOTĂ: Aceasta este doar o estimare. Timpul tău de execuție poate varia.)

Context

Acest tutorial demonstrează cum să găsești mulțimea independentă maximă a unui graf folosind Aqarios Constrained Quantum Optimizer [1], o problemă de optimizare combinatorică cu restricții. O instanță din biblioteca de benchmark QOBLIB [2] este formulată ca un program liniar binar și transmisă Optimizer Application Function. Optimizatorul se ocupă intern de toate reformulările, sinteza circuitului, transpilarea și warm-starting-ul iterativ (vezi [3] pentru detalii).

Tutorialul acoperă următorii pași:

1. Definește problema ca un program liniar folosind OptimizationProblem din qiskit-addon-opt-mapper

2. Rulează optimizarea cuantică folosind Aqarios Constrained Quantum Optimizer

3. Preia și vizualizează rezultatele

Problema Maximum Independent Set

Problema mulțimii independente maxime (MIS) este o provocare fundamentală în optimizarea combinatorică. Formal, dat fiind un graf $G(V, E)$, scopul este să găsim cea mai mare submulțime de vârfuri $V_I \subset V$ astfel încât să nu existe două vârfuri din $V_I$ conectate printr-o muchie, ca în $\nexists (u, v) \in E : v \in V_I \wedge u \in V_I$. Fiecărui vârf i se atribuie o variabilă de decizie binară $x_i \in \{0, 1\}$, și pentru fiecare muchie se introduce o restricție $x_u + x_v \leq 1$, asigurând că cel mult un capăt al fiecărei muchii este selectat. Problema poate fi astfel formulată ca următoarea problemă de maximizare:

$$\max_{x_i} \sum_{i \in V} x_i \qquad\text{(găsește cea mai mare mulțime)}\\ \text{a.î.} \quad x_u + x_v \leq 1 \quad \forall (u, v) \in E.$$

MIS are o gamă largă de aplicații practice. În planificarea rețelelor wireless, o mulțime independentă corespunde unui grup de emițători care pot transmite simultan fără interferențe reciproce. În planificarea sarcinilor, modelează cea mai mare colecție de sarcini care pot fi executate concurent, având în vedere conflictele de resurse pe perechi. În biologia computațională, capturează mulțimi de proteine care nu interacționează reciproc într-o rețea.

În ciuda formulării sale intuitive, MIS este NP-hard, iar chiar și pentru grafuri cu câteva sute de noduri, anumite instanțe devin dificil de rezolvat exact sau euristic [2]. Problema generează, de asemenea, structuri de restricții rare (cu puține conexiuni), care sunt bine potrivite pentru implementările hardware ale optimizării cuantice, făcând din ea un benchmark atractiv pentru dispozitivele cuantice pe termen scurt.

Aqarios Constrained Quantum Optimizer

Abordarea standard pentru încorporarea unei probleme binare cu restricții în optimizarea cuantică transformă modelul într-un format fără restricții prin adăugarea de termeni de penalizare: fiecare restricție încălcată $x_u + x_v \leq 1$ contribuie cu $2 x_u x_v$ la obiectivul de minimizare $-\sum_i x_i$. Acest lucru este gestionat automat de Constrained Quantum Optimizer Qiskit Function.

Dincolo de această transformare standard, optimizatorul identifică clici în graful de restricții. O clică este o mulțime de noduri $V_C$ în care oricare două noduri sunt conectate printr-o muchie. Ca urmare, cele $\binom{|V_C|}{2}$ restricții pe perechi $x_u + x_v \leq 1 \;\forall (u,v) \in E_C$ pot fi înlocuite cu o singură restricție mai strictă $\sum_{i \in V_C} x_i \leq 1$. Introducerea unei variabile de compensare (slack) $y$ transformă aceasta într-o egalitate $\sum_i x_i + y = 1$, care ia forma unei restricții one-hot ce poate fi impusă direct în QAOA folosind XY-mixers [3]. Aceasta reduce spațiul de căutare și evită nevoia de termeni de penalizare pentru acele restricții, îmbunătățind calitatea soluției.

În plus, variabilele conectate la un singur vecin sunt numite noduri pendant și sunt fixate în mod determinist de algoritm înainte de execuția cuantică, reducând și mai mult dimensiunea efectivă a problemei.

Constrained Quantum Optimizer folosește o abordare de warm-starting iterativ compatibilă cu XY-mixers [1], care restrânge progresiv spațiul de căutare prin direcționarea distribuției stării cuantice către regiuni de soluții promițătoare de-a lungul iterațiilor. Acest lucru permite utilizarea parametrilor QAOA cu unghi fix, eliminând nevoia de antrenare a parametrilor variaționali. Cerințele totale de resurse cuantice sunt determinate exclusiv de numărul de iterații de warm-start, ceea ce face ca costul cuantic să fie ușor de controlat.

Cerințe

Înainte de a începe acest tutorial, asigură-te că ai instalate următoarele cerințe:

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

Opțional, pentru Anexă trebuie să instalezi

• Luna Model (pip install luna-model)

Configurare

Importă toate dependențele necesare.

# 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

Mai întâi, autentifică-te folosind cheia ta API IBM Quantum. Apoi, selectează Qiskit Function după cum urmează. (Acest cod presupune că ai salvat deja contul în mediul tău 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")

Pasul 1: Mapează intrările clasice la problema cuantică

Problema este formulată ca un fișier LP, un format comun pentru problemele de optimizare care servește drept intrare pentru Aqarios Constrained Quantum Optimizer. Pe lângă fișierele LP, funcția acceptă și fișiere MPS și reprezentări native Luna Model. Fișierul LP este generat prin următorii pași:

1. Preia o instanță de graf din QOBLIB [2]

2. Modelează problema de optimizare

3. Generează fișierul LP

Încarcă graful instanței problemei

Grafurile sunt specificate în formatul DIMACS .gph, un format bazat pe linii, unde liniile care încep cu e definesc muchii, liniile care încep cu p definesc antetul problemei, iar liniile care încep cu c sunt comentarii:

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

Fișierul .gph poate fi descărcat din repozitoriul QOBLIB folosind următoarea funcție, care îl parsează și într-un graf NetworkX. Reține că formatul DIMACS folosește etichetarea nodurilor începând de la 1, care aici este convertită la indexare începând de la 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.

Acest exemplu folosește instanța es60fst02 din QOBLIB, un graf cu 186 de noduri și 280 de muchii. Datorită pașilor de preprocesare folosiți de Constrained Quantum Optimizer, această instanță poate fi rezolvată pe dispozitive Heron cu 156 de qubiți. Graful poate fi vizualizat folosind matplotlib:

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

Construiește problema de optimizare

Problema Maximum Independent Set poate fi formulată direct folosind OptimizationProblem. Fiecare nod al grafului devine o variabilă de decizie binară, iar fiecare muchie introduce o restricție care asigură că este selectat cel mult unul dintre capetele sale:

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

O scurtătură

Pachetul qiskit-addon-opt-mapper oferă o clasă de aplicație preimplementată pentru problema Maximum Independent Set, care simplifică formularea de mai sus într-un singur apel:

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

Transformă problema într-un fișier LP

OptimizationProblem în sine nu acceptă exporturi în fișiere LP, dar este interoperabil cu DOcplex, care le acceptă. Generarea conținutului fișierului LP necesită doar două linii:

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

Acest format este nativ pentru Constrained Quantum Optimizer.

Pasul 2: Optimizează problema pentru execuția pe hardware cuantic

Toată sinteza circuitului, optimizarea și transpilarea sunt gestionate nativ de funcție. Consultă secțiunea de intrări din referința API pentru argumentele cu care se apelează funcția.

Pentru a ajusta fin comportamentul algoritmului, consultă lista de opțiuni din referința API. Dacă vrei ca maparea circuitului să fie reproductibilă între rulări, fixează opțiunea seed_transpiler.

Pentru mai multe informații, consultă ghidul Aqarios Constrained Quantum Optimizer și referința API.

Pasul 3: Execută folosind primitivele Qiskit

Fișierul LP poate fi acum trimis optimizatorului:

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

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

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

Intern, algoritmul parcurge următoarele etape:

1. Preprocessing:

   • Reduce variabilele fixabile

   • Găsește clici

   • Identifică tipurile de restricții

   • Evaluează factorii de penalizare pentru termenii de penalizare

   • Aplică transformările restricțiilor

   • Sintetizează circuitul folosind metode de impunere a restricțiilor

   • Aproximarea problemei și transpilare

2. Lanțuri paralele de bucle iterative:

   • Eșantionează din circuit cu parametri fixați

   • Aplică postprocesarea

   • Evaluează și setează noi probabilități de warm-starting

3. Postprocessing:

   • Găsește cele mai bune eșantioane și verifică fezabilitatea în raport cu problema de intrare

Monitorizează progresul

Consultă următoarele secțiuni din pagina Get started with Qiskit Functions pentru a monitoriza progresul job-ului tău:

• Verifică starea job-ului

• Preia rezultatele

# Monitor the job status
job.status()

'QUEUED'

Pasul 4: Postprocesează și returnează rezultatele în formatul clasic dorit

Rezultatul de ieșire este un dicționar, ale cărui câmpuri sunt descrise în secțiunea de ieșiri din referința API.

Când lista solutions conține mai mult de o intrare, au fost găsite mai multe optime degenerate. Aici este luată în considerare doar prima soluție, adresată după numele variabilei. Aceleași soluții sunt disponibile și ca șiruri de biți în solution_bitstrings, unde metadata.solver_info.variable_mapping indică poziția de caracter a fiecărei 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}

Vizualizare

Mulțimea independentă identificată poate fi vizualizată evidențiind nodurile selectate din graf:

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

Anexă: Enunțul problemei cu Luna Model

Pe lângă abordarea qiskit-addon-opt-mapper prezentată mai sus, Qiskit Function acceptă și modele create cu Luna Model [4], SDK-ul de modelare al Aqarios. După instalarea pachetului PyPI luna-model, importă-l după cum urmează:

Setup:

from luna_model import Model, Sense
import numpy as np

Modelul este apoi construit din graf în același mod ca la qiskit-addon-opt-mapper: Construiește modelul:

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

Pași următori

Recomandări

• Consultă ghidul Aqarios Constrained Quantum Optimizer pentru o prezentare detaliată a tuturor caracteristicilor funcției.
• Explorează referința API pentru lista completă a parametrilor de intrare și a câmpurilor de ieșire.
• Experimentează cu opțiunile algoritmului (reps, num_parallel, shots, postprocessing_level) pe propria ta problemă de optimizare binară cu restricții pentru a evalua impactul lor asupra calității soluției și a timpului de execuție.

Referințe

1. IBM Quantum, Aqarios Constrained Quantum Optimizer Guide

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