Знайдіть максимальну незалежну множину за допомогою Aqarios Constrained Quantum Optimizer

Примітка

Qiskit Functions — це експериментальна функція, доступна лише користувачам IBM Quantum® Premium Plan, Flex Plan та On-Prem (через IBM Quantum Platform API) Plan. Вона перебуває у статусі попереднього випуску (preview) і може змінюватися.

Орієнтовний час виконання: 30 секунд на процесорі Heron r2. (ПРИМІТКА: це лише оцінка. Ваш час виконання може відрізнятися.)

Загальні відомості

Цей навчальний посібник демонструє, як знайти максимальну незалежну множину графа за допомогою Aqarios Constrained Quantum Optimizer [1] — задачі обмеженої комбінаторної оптимізації. Екземпляр із бібліотеки бенчмарків QOBLIB [2] формулюється як бінарна лінійна програма і передається до Optimizer Application Function. Оптимізатор внутрішньо обробляє все переформулювання, синтез схеми, транспіляцію та ітеративний «теплий» старт (докладніше див. [3]).

Навчальний посібник охоплює такі кроки:

1. Визначте задачу як лінійну програму за допомогою OptimizationProblem з qiskit-addon-opt-mapper

2. Виконайте квантову оптимізацію за допомогою Aqarios Constrained Quantum Optimizer

3. Отримайте та візуалізуйте результати

Задача про максимальну незалежну множину

Задача про максимальну незалежну множину (MIS) є фундаментальною проблемою комбінаторної оптимізації. Формально, для заданого графа $G(V, E)$ мета полягає в тому, щоб знайти найбільшу підмножину вершин $V_I \subset V$ таку, що жодні дві вершини у $V_I$ не з'єднані ребром, тобто $\nexists (u, v) \in E : v \in V_I \wedge u \in V_I$. Кожній вершині присвоюється бінарна змінна рішення $x_i \in \{0, 1\}$, і для кожного ребра вводиться обмеження $x_u + x_v \leq 1$, яке гарантує, що обрана буде щонайбільше одна кінцева точка кожного ребра. Таким чином, задачу можна сформулювати як таку задачу максимізації:

$$\max_{x_i} \sum_{i \in V} x_i \qquad\text{(знайти найбільшу множину)}\\ \text{за умови} \quad x_u + x_v \leq 1 \quad \forall (u, v) \in E.$$

MIS має широкий спектр практичних застосувань. У плануванні бездротових мереж незалежна множина відповідає групі передавачів, які можуть одночасно транслювати без взаємних завад. У плануванні розкладу вона моделює найбільшу сукупність завдань, які можуть виконуватися паралельно за наявності попарних конфліктів ресурсів. У обчислювальній біології вона описує множини білків у мережі, які не взаємодіють між собою.

Незважаючи на інтуїтивно зрозуміле формулювання, MIS є NP-складною задачею, і навіть для графів із кількома сотнями вузлів окремі екземпляри стає важко розв'язати точно або евристично [2]. Ця задача також породжує розріджені структури обмежень, які добре підходять для апаратних реалізацій квантової оптимізації, що робить її привабливим бенчмарком для квантових пристроїв найближчого покоління.

Aqarios Constrained Quantum Optimizer

Стандартний підхід до вбудовування обмеженої бінарної задачі в квантову оптимізацію перетворює модель у необмежений формат шляхом додавання штрафних доданків: кожне порушене обмеження $x_u + x_v \leq 1$ додає $2 x_u x_v$ до цільової функції мінімізації $-\sum_i x_i$. Це автоматично обробляється Qiskit Function Constrained Quantum Optimizer.

Окрім цього стандартного перетворення, оптимізатор виявляє кліки в графі обмежень. Кліка — це множина вузлів $V_C$, у якій кожна пара вузлів з'єднана ребром. Як наслідок, $\binom{|V_C|}{2}$ попарних обмежень $x_u + x_v \leq 1 \;\forall (u,v) \in E_C$ можна замінити одним, жорсткішим обмеженням $\sum_{i \in V_C} x_i \leq 1$. Введення допоміжної змінної $y$ перетворює це на рівність $\sum_i x_i + y = 1$, яка набуває форми обмеження «one-hot», яке можна безпосередньо застосувати в QAOA за допомогою XY-мікшерів [3]. Це зменшує простір пошуку та усуває потребу у штрафних доданках для цих обмежень, покращуючи якість розв'язку.

Крім того, змінні, з'єднані лише з одним сусідом, називаються висячими (pendant) вузлами і детерміновано фіксуються алгоритмом перед квантовим виконанням, що додатково зменшує ефективний розмір задачі.

Constrained Quantum Optimizer використовує підхід ітеративного «теплого» старту, сумісний з XY-мікшерами [1], який поступово звужує простір пошуку, зміщуючи розподіл квантового стану в бік перспективних областей розв'язку протягом ітерацій. Це дозволяє використовувати параметри QAOA з фіксованими кутами, усуваючи потребу у варіаційному навчанні параметрів. Загальні вимоги до квантових ресурсів визначаються лише кількістю ітерацій «теплого» старту, а це означає, що квантову вартість легко контролювати.

Вимоги

Перш ніж розпочати цей навчальний посібник, переконайся, що ти встановив такі залежності:

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

За бажанням, для Додатка вам потрібно встановити

• Luna Model (pip install luna-model)

Налаштування

Імпортуйте всі необхідні залежності.

# 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

Спочатку автентифікуйтеся за допомогою вашого ключа API IBM Quantum. Потім виберіть Qiskit Function, як показано нижче. (Цей код передбачає, що ви вже зберегли свій обліковий запис у своєму локальному середовищі.)

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

Крок 1: Відображення класичних вхідних даних у квантову задачу

Задача формулюється у вигляді LP-файлу — поширеного формату для задач оптимізації, який слугує вхідними даними для Aqarios Constrained Quantum Optimizer. Окрім LP-файлів, функція також підтримує MPS-файли та рідні представлення Luna Model. LP-файл генерується за допомогою таких кроків:

1. Отримайте екземпляр графа з QOBLIB [2]

2. Змоделюйте задачу оптимізації

3. Згенеруйте LP-файл

Завантаження графа екземпляра задачі

Графи задаються у форматі DIMACS .gph — рядковому форматі, у якому рядки, що починаються з e, визначають ребра, рядки, що починаються з p, визначають заголовок задачі, а рядки, що починаються з c, є коментарями:

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

Файл .gph можна завантажити з репозиторію QOBLIB за допомогою наступної функції, яка також перетворює його на граф NetworkX. Зверніть увагу, що формат DIMACS використовує нумерацію вузлів з 1, яка тут перетворюється на індексацію з 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.

У цьому прикладі використовується екземпляр es60fst02 з QOBLIB — граф із 186 вузлами та 280 ребрами. Завдяки крокам попередньої обробки, що застосовуються Constrained Quantum Optimizer, цей екземпляр можна розв'язати на 156-кубітних пристроях Heron. Граф можна візуалізувати за допомогою matplotlib:

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

Побудова задачі оптимізації

Задачу про максимальну незалежну множину можна сформулювати безпосередньо за допомогою OptimizationProblem. Кожен вузол графа стає бінарною змінною рішення, а кожне ребро вводить обмеження, яке гарантує, що обрана буде щонайбільше одна з його кінцевих точок:

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

Скорочений шлях

Пакет qiskit-addon-opt-mapper надає готовий клас застосування для задачі про максимальну незалежну множину, який спрощує наведене вище формулювання до одного виклику:

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

Перетворення задачі на LP-файл

Сам OptimizationProblem не підтримує експорт у LP-файл, але він сумісний із DOcplex, який це підтримує. Для генерування вмісту LP-файлу потрібно лише два рядки:

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

Цей формат є рідним для Constrained Quantum Optimizer.

Крок 2: Оптимізація задачі для виконання на квантовому апаратному забезпеченні

Увесь синтез схеми, оптимізація та транспіляція обробляються функцією нативно. Див. розділ inputs у довіднику API для аргументів, з якими слід викликати функцію.

Щоб точно налаштувати поведінку алгоритму, див. список опцій у довіднику API. Якщо ти хочеш, щоб відображення схеми було відтворюваним між запусками, зафіксуй опцію seed_transpiler.

Для отримання додаткової інформації див. посібник Aqarios Constrained Quantum Optimizer та довідник API.

Крок 3: Виконання за допомогою примітивів Qiskit

Тепер LP-файл можна надіслати до оптимізатора:

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

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

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

Внутрішньо алгоритм проходить через такі етапи:

1. Preprocessing:

   • Вилучення змінних, які можна зафіксувати

   • Пошук клік

   • Визначення типів обмежень

   • Обчислення штрафних коефіцієнтів для штрафних доданків

   • Застосування перетворень обмежень

   • Синтез схеми з методами примусового дотримання обмежень

   • Апроксимація задачі та транспіляція

2. Паралельні ланцюги ітеративних циклів:

   • Семплування зі схеми з фіксованими параметрами

   • Застосування постобробки

   • Обчислення та встановлення нових ймовірностей «теплого» старту

3. Postprocessing:

   • Пошук найкращих семплів і перевірка на допустимість щодо вхідної задачі

Моніторинг прогресу

Див. такі розділи на сторінці «Початок роботи з Qiskit Functions», щоб відстежувати прогрес вашого завдання:

• Перевірка стану завдання

• Отримання результатів

# Monitor the job status
job.status()

'QUEUED'

Крок 4: Постобробка та повернення результатів у бажаному класичному форматі

Результат виводиться у вигляді словника, поля якого описані в розділі Outputs довідника API.

Якщо список solutions містить більше одного запису, це означає, що знайдено кілька вироджених оптимумів. Тут розглядається лише перший розв'язок, до якого звертаються за іменем змінної. Ті самі розв'язки також доступні як бітові рядки в solution_bitstrings, де metadata.solver_info.variable_mapping вказує позицію символу кожної змінної.

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

Візуалізація

Знайдену незалежну множину можна візуалізувати, виділивши обрані вузли на графі:

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

Додаток: Постановка задачі за допомогою Luna Model

На додачу до показаного вище підходу з qiskit-addon-opt-mapper, Qiskit Function також приймає моделі, створені за допомогою Luna Model [4] — SDK моделювання від Aqarios. Після встановлення пакета PyPI luna-model імпортуйте його наступним чином:

Setup:

from luna_model import Model, Sense
import numpy as np

Потім модель будується з графа так само, як і з qiskit-addon-opt-mapper: Побудова моделі:

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

Наступні кроки

Рекомендації

• Зверніться до посібника Aqarios Constrained Quantum Optimizer для детального огляду всіх можливостей функції.
• Ознайомтеся з довідником API для повного списку вхідних параметрів і вихідних полів.
• Поекспериментуйте з опціями алгоритму (reps, num_parallel, shots, postprocessing_level) на своїй власній задачі обмеженої бінарної оптимізації, щоб оцінити їхній вплив на якість розв'язку та час виконання.

Список літератури

1. IBM Quantum, Посібник Aqarios Constrained Quantum Optimizer

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