Najdi Maximum Independent Set pomocí Aqarios Constrained Quantum Optimizer

Poznámka

Qiskit Functions jsou experimentální funkce dostupné pouze uživatelům plánů IBM Quantum® Premium Plan, Flex Plan a On-Prem (přes IBM Quantum Platform API). Jsou ve stavu preview release a mohou se změnit.

Odhadovaná doba běhu: 30 sekund na procesoru Heron r2. (POZNÁMKA: Toto je pouze odhad. Skutečná doba běhu se může lišit.)

Kontext

Tento tutoriál ukazuje, jak najít maximální nezávislou množinu (maximum independent set) grafu pomocí Aqarios Constrained Quantum Optimizer [1], tedy omezeného problému kombinatorické optimalizace. Instance z benchmarkové knihovny QOBLIB [2] je formulována jako binární lineární program a předána Optimizer Application Function. Optimalizátor interně řeší veškerou reformulaci, syntézu obvodu, transpilaci a iterativní warm-startování (podrobnosti viz [3]).

Tento tutoriál pokrývá následující kroky:

1. Definuj problém jako lineární program pomocí OptimizationProblem z qiskit-addon-opt-mapper

2. Spusť kvantovou optimalizaci pomocí Aqarios Constrained Quantum Optimizer

3. Získej a vizualizuj výsledky

Problém Maximum Independent Set

Problém Maximum Independent Set (MIS) je základní výzvou v kombinatorické optimalizaci. Formálně: pro daný graf $G(V, E)$ je cílem najít největší podmnožinu vrcholů $V_I \subset V$ takovou, že žádné dva vrcholy v $V_I$ nejsou spojeny hranou, jak vyjadřuje $\nexists (u, v) \in E : v \in V_I \wedge u \in V_I$. Každému vrcholu je přiřazena binární rozhodovací proměnná $x_i \in \{0, 1\}$ a pro každou hranu je zavedeno omezení $x_u + x_v \leq 1$, které zajišťuje, že je vybrán nejvýše jeden koncový bod každé hrany. Problém tak lze formulovat jako následující maximalizační úlohu:

$$\max_{x_i} \sum_{i \in V} x_i \qquad\text{(najdi největší množinu)}\\ \text{za podmínky} \quad x_u + x_v \leq 1 \quad \forall (u, v) \in E.$$

MIS má široké spektrum praktických aplikací. Při plánování bezdrátových sítí odpovídá nezávislá množina skupině vysílačů, které mohou všechny vysílat současně bez vzájemného rušení. Při plánování úloh (scheduling) modeluje největší kolekci úloh, které mohou běžet souběžně s ohledem na párové konflikty zdrojů. V oblasti výpočetní biologie zachycuje množiny vzájemně neinteragujících proteinů v síti.

Navzdory své intuitivní formulaci je MIS NP-těžký problém a konkrétní instance se u grafů s několika stovkami uzlů stávají obtížně řešitelnými přesně i heuristicky [2]. Problém navíc vede k řídkým strukturám omezení, které jsou dobře vhodné pro hardwarové implementace kvantové optimalizace, což z něj dělá atraktivní benchmark pro současná (NISQ) kvantová zařízení.

Aqarios Constrained Quantum Optimizer

Standardní přístup k vložení omezeného binárního problému do kvantové optimalizace transformuje model na neomezený formát přidáním penalizačních členů: každé porušené omezení $x_u + x_v \leq 1$ přispívá hodnotou $2 x_u x_v$ do minimalizačního cíle $-\sum_i x_i$. Toto zajišťuje automaticky Qiskit Function Constrained Quantum Optimizer.

Kromě této standardní transformace optimalizátor identifikuje kliky v grafu omezení. Klika je množina uzlů $V_C$, ve které každá dvojice uzlů sdílí hranu. V důsledku toho lze $\binom{|V_C|}{2}$ párových omezení $x_u + x_v \leq 1 \;\forall (u,v) \in E_C$ nahradit jediným, přísnějším omezením $\sum_{i \in V_C} x_i \leq 1$. Zavedením pomocné proměnné (slack variable) $y$ se z toho stane rovnost $\sum_i x_i + y = 1$, která má tvar one-hot omezení, jež lze v QAOA vynutit přímo pomocí XY-mixerů [3]. Tím se zmenší prohledávaný prostor a odpadá potřeba penalizačních členů pro tato omezení, což zlepšuje kvalitu řešení.

Proměnné napojené pouze na jednoho souseda se navíc nazývají pendant uzly a algoritmus je deterministicky zafixuje ještě před kvantovým spuštěním, čímž dále snižuje efektivní velikost problému.

Constrained Quantum Optimizer využívá přístup iterativního warm-startování kompatibilní s XY-mixery [1], který postupně zužuje prohledávaný prostor tím, že v jednotlivých iteracích posouvá rozdělení kvantového stavu směrem k slibným oblastem řešení. To umožňuje použití fixed-angle QAOA parametrů, čímž odpadá potřeba trénování variačních parametrů. Celkové nároky na kvantové zdroje jsou dány výhradně počtem warm-start iterací, což znamená, že kvantové náklady lze snadno řídit.

Požadavky

Než začneš s tímto tutoriálem, ujisti se, že máš nainstalované následující požadavky:

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

Volitelně, pro Dodatek potřebuješ nainstalovat

• Luna Model (pip install luna-model)

Nastavení

Importuj všechny potřebné závislosti.

# 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

Nejprve se autentizuj pomocí svého IBM Quantum API klíče. Poté vyber Qiskit Function následujícím způsobem. (Tento kód předpokládá, že jsi již uložil svůj účet do lokálního prostředí.)

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

Krok 1: Namapuj klasické vstupy na kvantový problém

Problém je formulován jako LP soubor, běžný formát pro optimalizační problémy, který slouží jako vstup pro Aqarios Constrained Quantum Optimizer. Kromě LP souborů funkce podporuje také MPS soubory a nativní reprezentace Luna Model. LP soubor se generuje pomocí následujících kroků:

1. Stáhni instanci grafu z QOBLIB [2]

2. Namodeluj optimalizační problém

3. Vygeneruj LP soubor

Načti graf instance problému

Grafy jsou specifikovány ve formátu DIMACS .gph, řádkovém formátu, kde řádky začínající e definují hrany, řádky začínající p definují hlavičku problému a řádky začínající c jsou komentáře:

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

Soubor .gph lze stáhnout z repozitáře QOBLIB pomocí následující funkce, která ho zároveň naparsuje do grafu NetworkX. Všimni si, že formát DIMACS používá číslování uzlů od 1, které je zde převedeno na indexování od 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.

Tento příklad používá instanci es60fst02 z QOBLIB, graf se 186 uzly a 280 hranami. Díky předzpracovávacím krokům, které používá Constrained Quantum Optimizer, je tato instance řešitelná na 156qubitových zařízeních Heron. Graf lze vizualizovat pomocí matplotlib:

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

Sestav optimalizační problém

Problém Maximum Independent Set lze formulovat přímo pomocí OptimizationProblem. Každý uzel grafu se stane binární rozhodovací proměnnou a každá hrana zavádí omezení zajišťující, že je vybrán nejvýše jeden z jejích koncových bodů:

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

Zkratka

Balíček qiskit-addon-opt-mapper poskytuje předimplementovanou aplikační třídu pro problém Maximum Independent Set, která výše uvedenou formulaci zjednodušuje do jediného volání:

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

Převeď problém na LP soubor

Samotná OptimizationProblem nepodporuje export do LP souboru, je ale interoperabilní s DOcplex, který tuto možnost má. Vygenerování obsahu LP souboru vyžaduje pouze dva řádky:

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

Tento formát je pro Constrained Quantum Optimizer nativní.

Krok 2: Optimalizuj problém pro spuštění na kvantovém hardwaru

Veškerá syntéza obvodu, optimalizace a transpilace je řešena funkcí nativně. Argumenty, se kterými funkci volat, najdeš v sekci inputs v API referenci.

Pro jemné doladění chování algoritmu se podívej na seznam Options v API referenci. Pokud chceš, aby bylo mapování obvodu reprodukovatelné napříč běhy, nastav pevnou hodnotu volby seed_transpiler.

Další informace najdeš v průvodci Aqarios Constrained Quantum Optimizer a v API referenci.

Krok 3: Spusť pomocí Qiskit primitiv

LP soubor teď lze odeslat optimalizátoru:

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ě algoritmus prochází následujícími fázemi:

1. Preprocessing:

   • Redukuj fixovatelné proměnné

   • Najdi kliky

   • Identifikuj typy omezení

   • Vyhodnoť penalizační faktory pro penalizační členy

   • Aplikuj transformace omezení

   • Syntetizuj obvod pomocí metod vynucujících omezení

   • Aproximace problému a transpilace

2. Paralelní řetězce iterativních smyček:

   • Vzorkuj z obvodu s fixními parametry

   • Aplikuj postprocessing

   • Vyhodnoť a nastav nové warm-startovací pravděpodobnosti

3. Postprocessing:

   • Najdi nejlepší vzorky a zkontroluj proveditelnost vzhledem ke vstupnímu problému

Sleduj průběh

Pro sledování průběhu své úlohy (job) se podívej na následující sekce na stránce Get started with Qiskit Functions:

• Zkontroluj stav úlohy

• Získej výsledky

# Monitor the job status
job.status()

'QUEUED'

Krok 4: Zpracuj výsledky a vrať je v požadovaném klasickém formátu

Výstupní výsledek je slovník (dictionary), jehož pole jsou popsána v sekci Outputs v API referenci.

Pokud seznam solutions obsahuje více než jednu položku, bylo nalezeno více degenerovaných optim. Zde je uvažováno pouze první řešení, adresované názvem proměnné. Stejná řešení jsou k dispozici také jako bitové řetězce v solution_bitstrings, kde metadata.solver_info.variable_mapping udává pozici znaku každé proměnné.

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

Vizualizace

Nalezenou nezávislou množinu lze vizualizovat zvýrazněním vybraných uzlů v grafu:

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

Dodatek: Zadání problému pomocí Luna Model

Kromě výše uvedeného přístupu pomocí qiskit-addon-opt-mapper Qiskit Function přijímá i modely vytvořené pomocí Luna Model [4], modelovacího SDK od Aqarios. Po instalaci balíčku PyPI luna-model ho naimportuj následujícím způsobem:

Setup:

from luna_model import Model, Sense
import numpy as np

Model se poté sestaví z grafu stejným způsobem jako u qiskit-addon-opt-mapper: Sestav model:

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

Další kroky

Doporučení

• Podrobný přehled všech funkcí najdeš v průvodci Aqarios Constrained Quantum Optimizer.
• Úplný seznam vstupních parametrů a výstupních polí najdeš v API referenci.
• Vyzkoušej možnosti algoritmu (reps, num_parallel, shots, postprocessing_level) na svém vlastním omezeném binárním optimalizačním problému a posuď jejich vliv na kvalitu řešení a dobu běhu.

Reference

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