Znajdź maksymalny zbiór niezależny za pomocą Aqarios Constrained Quantum Optimizer

Uwaga

Qiskit Functions to eksperymentalna funkcja dostępna wyłącznie dla użytkowników planów IBM Quantum® Premium Plan, Flex Plan oraz On-Prem (poprzez IBM Quantum Platform API). Znajdują się w statusie wersji zapoznawczej (preview) i mogą ulec zmianie.

Szacowany czas wykonania: 30 sekund na procesorze Heron r2. (UWAGA: to tylko szacunek. Rzeczywisty czas wykonania może się różnić.)

Kontekst

Ten samouczek pokazuje, jak znaleźć maksymalny zbiór niezależny grafu za pomocą Aqarios Constrained Quantum Optimizer [1], problemu ograniczonej optymalizacji kombinatorycznej. Instancja z biblioteki testowej QOBLIB [2] jest formułowana jako binarny program liniowy i przekazywana do Optimizer Application Function. Optymalizator obsługuje wewnętrznie całą reformulację, syntezę obwodu, transpilację oraz iteracyjny warm-starting (szczegóły znajdziesz w [3]).

Samouczek obejmuje następujące kroki:

1. Zdefiniuj problem jako program liniowy za pomocą OptimizationProblem z qiskit-addon-opt-mapper

2. Uruchom optymalizację kwantową za pomocą Aqarios Constrained Quantum Optimizer

3. Pobierz i zwizualizuj wyniki

Problem maksymalnego zbioru niezależnego

Problem maksymalnego zbioru niezależnego (MIS) jest fundamentalnym wyzwaniem w optymalizacji kombinatorycznej. Formalnie, dla danego grafu $G(V, E)$, celem jest znalezienie największego podzbioru wierzchołków $V_I \subset V$ takiego, że żadne dwa wierzchołki w $V_I$ nie są połączone krawędzią, czyli $\nexists (u, v) \in E : v \in V_I \wedge u \in V_I$. Każdemu wierzchołkowi przypisywana jest binarna zmienna decyzyjna $x_i \in \{0, 1\}$, a dla każdej krawędzi wprowadzane jest ograniczenie $x_u + x_v \leq 1$, zapewniające, że wybrany zostanie co najwyżej jeden koniec każdej krawędzi. Problem można więc zapisać jako następujący problem maksymalizacji:

$$\max_{x_i} \sum_{i \in V} x_i \qquad\text{(znajdź największy zbiór)}\\ \text{s.t.} \quad x_u + x_v \leq 1 \quad \forall (u, v) \in E.$$

MIS ma szerokie zastosowanie praktyczne. W planowaniu sieci bezprzewodowych zbiór niezależny odpowiada grupie nadajników, które mogą jednocześnie nadawać bez wzajemnych zakłóceń. W harmonogramowaniu modeluje on największy zbiór zadań, które mogą być wykonywane równocześnie, gdy pewne pary zadań konkurują o te same zasoby. W biologii obliczeniowej opisuje zbiory wzajemnie nieoddziałujących ze sobą białek w sieci.

Mimo intuicyjnego sformułowania, MIS jest problemem NP-trudnym, a nawet dla grafów liczących kilkaset węzłów konkretne instancje stają się trudne do rozwiązania dokładnie lub heurystycznie [2]. Problem ten prowadzi również do rzadkich struktur ograniczeń, które dobrze nadają się do sprzętowych implementacji optymalizacji kwantowej, co czyni go atrakcyjnym benchmarkiem dla urządzeń kwantowych najbliższej generacji.

Aqarios Constrained Quantum Optimizer

Standardowe podejście do osadzania ograniczonego problemu binarnego w optymalizacji kwantowej przekształca model w format nieograniczony poprzez dodanie członów kary: każde naruszone ograniczenie $x_u + x_v \leq 1$ wnosi $2 x_u x_v$ do funkcji celu minimalizacji $-\sum_i x_i$. Jest to obsługiwane automatycznie przez Constrained Quantum Optimizer Qiskit Function.

Poza tą standardową transformacją, optymalizator identyfikuje kliki w grafie ograniczeń. Klika to zbiór węzłów $V_C$, w którym każda para węzłów jest połączona krawędzią. W konsekwencji $\binom{|V_C|}{2}$ ograniczeń parowych $x_u + x_v \leq 1 \;\forall (u,v) \in E_C$ można zastąpić pojedynczym, ściślejszym ograniczeniem $\sum_{i \in V_C} x_i \leq 1$. Wprowadzenie zmiennej luzu $y$ zamienia to w równość $\sum_i x_i + y = 1$, która przyjmuje postać ograniczenia typu one-hot, możliwego do bezpośredniego wymuszenia w QAOA za pomocą mikserów XY [3]. Zmniejsza to przestrzeń przeszukiwań i eliminuje potrzebę stosowania członów kary dla tych ograniczeń, poprawiając jakość rozwiązania.

Dodatkowo zmienne połączone tylko z jednym sąsiadem nazywane są węzłami wiszącymi (ang. pendant) i są ustalane deterministycznie przez algorytm przed wykonaniem kwantowym, co dodatkowo zmniejsza efektywny rozmiar problemu.

Constrained Quantum Optimizer wykorzystuje podejście iteracyjnego warm-startingu zgodne z mikserami XY [1], które stopniowo zawęża przestrzeń przeszukiwań poprzez obciążanie rozkładu stanu kwantowego w kierunku obiecujących obszarów rozwiązań w kolejnych iteracjach. Umożliwia to zastosowanie parametrów QAOA o stałych kątach, eliminując potrzebę treningu parametrów wariacyjnych. Całkowite zapotrzebowanie na zasoby kwantowe zależy wyłącznie od liczby iteracji warm-startu, co sprawia, że koszt kwantowy jest łatwy do kontrolowania.

Wymagania

Przed rozpoczęciem tego samouczka upewnij się, że zainstalowałeś następujące wymagania:

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

Opcjonalnie, do Dodatku musisz zainstalować

• Luna Model (pip install luna-model)

Konfiguracja

Zaimportuj wszystkie wymagane zależności.

# 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

Najpierw uwierzytelnij się za pomocą swojego klucza API IBM Quantum. Następnie wybierz funkcję Qiskit w następujący sposób. (Ten kod zakłada, że masz już zapisane konto w swoim lokalnym środowisku.)

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: Odwzoruj dane klasyczne na problem kwantowy

Problem jest formułowany jako plik LP, powszechny format problemów optymalizacyjnych, który służy jako dane wejściowe dla Aqarios Constrained Quantum Optimizer. Oprócz plików LP, funkcja obsługuje również pliki MPS oraz natywne reprezentacje Luna Model. Plik LP jest generowany w następujących krokach:

1. Pobierz instancję grafu z QOBLIB [2]

2. Zamodeluj problem optymalizacyjny

3. Wygeneruj plik LP

Wczytaj graf instancji problemu

Grafy są określone w formacie DIMACS .gph, formacie opartym na liniach, w którym linie zaczynające się od e definiują krawędzie, linie zaczynające się od p definiują nagłówek problemu, a linie zaczynające się od c są komentarzami:

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

Plik .gph można pobrać z repozytorium QOBLIB za pomocą poniższej funkcji, która również parsuje go do grafu NetworkX. Zwróć uwagę, że format DIMACS wykorzystuje numerację węzłów od 1, która jest tutaj konwertowana na indeksowanie 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.

Ten przykład wykorzystuje instancję es60fst02 z QOBLIB, graf zawierający 186 węzłów i 280 krawędzi. Dzięki krokom wstępnego przetwarzania stosowanym przez Constrained Quantum Optimizer, ta instancja jest rozwiązywalna na 156-kubitowych urządzeniach Heron. Graf można zwizualizować za pomocą matplotlib:

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

Skonstruuj problem optymalizacyjny

Problem maksymalnego zbioru niezależnego można sformułować bezpośrednio za pomocą OptimizationProblem. Każdy węzeł grafu staje się binarną zmienną decyzyjną, a każda krawędź wprowadza ograniczenie zapewniające, że wybrany zostanie co najwyżej jeden z jej końców:

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

Skrót

Pakiet qiskit-addon-opt-mapper udostępnia gotową klasę aplikacyjną dla problemu maksymalnego zbioru niezależnego, która upraszcza powyższe sformułowanie do pojedynczego wywołania:

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

Przekształć problem do pliku LP

Sama klasa OptimizationProblem nie obsługuje eksportu do pliku LP, ale jest interoperacyjna z DOcplex, które to wsparcie posiada. Wygenerowanie zawartości pliku LP wymaga jedynie dwóch 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
...

Ten format jest natywny dla Constrained Quantum Optimizer.

Krok 2: Zoptymalizuj problem pod kątem wykonania na sprzęcie kwantowym

Cała synteza obwodu, optymalizacja i transpilacja są obsługiwane natywnie przez funkcję. Zobacz sekcję dotyczącą danych wejściowych w dokumentacji API, aby poznać argumenty, z jakimi należy wywołać funkcję.

Aby dostroić zachowanie algorytmu, zobacz listę opcji w dokumentacji API. Jeśli chcesz, aby mapowanie obwodu było powtarzalne między uruchomieniami, ustaw stałą wartość opcji seed_transpiler.

Aby uzyskać więcej informacji, zobacz przewodnik Aqarios Constrained Quantum Optimizer oraz dokumentację API.

Krok 3: Wykonaj za pomocą prymitywów Qiskit

Plik LP można teraz przesłać do optymalizatora:

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

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

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

Wewnętrznie algorytm przechodzi przez następujące etapy:

1. Preprocessing:

   • Zredukuj zmienne możliwe do ustalenia

   • Znajdź kliki

   • Zidentyfikuj typy ograniczeń

   • Oblicz współczynniki kary dla członów kary

   • Zastosuj transformacje ograniczeń

   • Zsyntetyzuj obwód z metodami wymuszającymi ograniczenia

   • Aproksymacja problemu i transpilacja

2. Równoległe łańcuchy pętli iteracyjnych:

   • Próbkuj z obwodu o stałych parametrach

   • Zastosuj przetwarzanie końcowe

   • Oblicz i ustaw nowe prawdopodobieństwa warm-startu

3. Postprocessing:

   • Znajdź najlepsze próbki i sprawdź ich wykonalność względem problemu wejściowego

Monitoruj postęp

Zobacz następujące sekcje na stronie „Pierwsze kroki z Qiskit Functions”, aby monitorować postęp swojego zadania:

• Sprawdź status zadania

• Pobierz wyniki

# Monitor the job status
job.status()

'QUEUED'

Krok 4: Przetwórz końcowo i zwróć wyniki w żądanym formacie klasycznym

Wynik jest słownikiem, którego pola są opisane w sekcji dotyczącej danych wyjściowych dokumentacji API.

Gdy lista solutions zawiera więcej niż jeden wpis, oznacza to, że znaleziono wiele zdegenerowanych optimów. Tutaj rozważamy tylko pierwsze rozwiązanie, w którym wartości są indeksowane nazwami zmiennych. Te same rozwiązania są również dostępne jako ciągi bitów w solution_bitstrings, gdzie metadata.solver_info.variable_mapping podaje pozycję znaku każdej zmiennej.

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

Wizualizacja

Zidentyfikowany zbiór niezależny można zwizualizować, podświetlając wybrane węzły na grafie:

# 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: Sformułowanie problemu za pomocą Luna Model

Oprócz podejścia opartego na qiskit-addon-opt-mapper przedstawionego powyżej, funkcja Qiskit akceptuje również modele stworzone za pomocą Luna Model [4], SDK do modelowania firmy Aqarios. Po zainstalowaniu pakietu PyPI luna-model, zaimportuj go w następujący sposób:

Setup:

from luna_model import Model, Sense
import numpy as np

Model jest następnie konstruowany z grafu w taki sam sposób, jak w przypadku qiskit-addon-opt-mapper: Zbuduj 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")

Kolejne kroki

Zalecenia

• Zapoznaj się z przewodnikiem Aqarios Constrained Quantum Optimizer, aby uzyskać szczegółowe omówienie wszystkich możliwości tej funkcji.
• Sprawdź dokumentację API, aby zobaczyć pełną listę parametrów wejściowych i pól wyjściowych.
• Poeksperymentuj z opcjami algorytmu (reps, num_parallel, shots, postprocessing_level) na własnym ograniczonym problemie optymalizacji binarnej, aby ocenić ich wpływ na jakość rozwiązania i czas wykonania.

Bibliografia

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