Розв'язання задачі про максимальну незалежну множину з більшою кількістю змінних, ніж кубітів, за допомогою SQOA Solver від JIJ

примітка

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

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

Передумови

У цьому навчальному посібнику показано, як використати SQOA Solver, Qiskit Function від JIJ, щоб розв'язати задачу про максимальну незалежну множину (MIS) з більшою кількістю двійкових змінних, ніж кубітів у вибраному QPU. Основні кроки: завантажити екземпляр MIS із Quantum Optimization Benchmarking Library (QOBLIB) [1], сформулювати його у формі квадратичної неспрямованої двійкової оптимізації (QUBO) за допомогою qiskit-addon-opt-mapper, надіслати до SQOA Solver для виконання на QPU від IBM® та перевірити повернений розв'язок.

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

Незалежна множина — це підмножина вузлів графа, в якій жодні два вибрані вузли не мають спільного ребра. Максимальна незалежна множина (MIS) — це незалежна множина з найбільшою можливою кількістю вузлів. Застосування MIS охоплюють планування, розподіл ресурсів і проєктування мереж.

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

Математичне формулювання

Для заданого неорієнтованого графа $G = (V, E)$ призначимо двійкову змінну $x_v$ кожному вузлу $v$:

• $x_v = 1$, якщо вузол $v$ вибрано.

• $x_v = 0$ otherwise.

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

$$\begin{aligned} \max_{x} \quad & \sum_{v \in V} x_v \\ \text{subject to} \quad & x_v + x_w \leq 1 && \forall (v,w) \in E, \\ & x_v \in \{0,1\} && \forall v \in V. \end{aligned}$$

Цільова функція підраховує вибрані вузли. Разом обмеження на ребра гарантують, що вибрані вузли утворюють незалежну множину.

У цьому навчальному посібнику використовується двійкове формулювання без обмежень від QOBLIB, яке замінює обмеження на ребра квадратичними штрафами:

$$\max_{x \in \{0,1\}^{|V|}} \quad \sum_{v \in V} x_v - 2 \sum_{(v,w) \in E} x_v x_w.$$

Щоразу, коли вибрано обидва кінці ребра, другий доданок віднімає від цільової функції двійку. Цей штраф робить конфліктний вибір менш вигідним, ніж збереження лише одного з кінців. Отримана цільова функція є QUBO, що є вхідним форматом, який приймає SQOA Solver.

Навіщо використовувати SQOA Solver?

Багато підходів квантової оптимізації призначають один кубіт кожній двійковій змінній, тому місткість квантового обладнання може прямо обмежувати розмір задачі. SQOA Solver поєднує кілька технік редукції та гібридних обчислень, щоб пом'якшити це обмеження:

• Він може впоратися із задачами з більшою кількістю двійкових змінних, ніж кубітів у QPU. Presolve застосовує правила редукції, які можуть зафіксувати змінні та спростити решту QUBO, зберігаючи принаймні один оптимальний розв'язок. Емпірично presolve також може зробити решту QUBO розрідженішою, що допомагає кодуванню на основі QRAC, яке йде далі.

  Потім розв'язувач використовує кодування на основі QRAC, виведене з Quantum Random Access Optimization (QRAO) [3], щоб подати кілька змінних (до трьох) без прямої взаємодії в QUBO на одному кубіті.

  Редукції від presolve та кодування залежать від структури задачі. Наприклад, у цьому посібнику задача з 200 змінними використовує лише 67 кубітів.

• Він може бути менш чутливим до апаратного шуму. Вибіркова квантова діагоналізація [4], [5] використовує QPU для вибірки бітових рядків, але виконує діагоналізацію класично. Це уникає повторних обчислень на QPU для оновлення варіаційних параметрів і може зменшити вплив шуму на робочий процес оптимізації.

• Він автоматизує робочий процес від presolve до постобробки. Ти надаєш правильно відформатований екземпляр QUBO і вибираєш бекенд. Потім SQOA Solver виконує весь робочий процес автоматично. Він застосовує presolve, відображає класичні змінні на релаксовану квантову задачу, будує та транспілює схеми для семплювання, виконує квантове семплювання та класичну діагоналізацію, округлює й уточнює призначення, а також відновлює та оцінює класичний розв'язок.

Вимоги

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

• Клієнт Qiskit Functions Catalog (pip install qiskit-ibm-catalog).

• Відображувач оптимізації Qiskit addon, що використовується для формулювання задачі (pip install qiskit-addon-opt-mapper).

• NetworkX і Matplotlib, що використовуються для обробки та побудови графа (pip install networkx matplotlib).

Тобі також потрібен доступ до SQOA Solver із Qiskit Functions Catalog. Заповни форму, щоб запросити доступ до функції.

# Added by doQumentation — installs the packages this notebook needs if they are missing
import importlib.util

_needed = {"matplotlib": "matplotlib", "networkx": "networkx", "ommx": "ommx", "ommx_quantum_benchmarks": "ommx-quantum-benchmarks", "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")

# %pip install qiskit-ibm-catalog qiskit-addon-opt-mapper networkx matplotlib

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

Спершу імпортуй потрібні пакети та інструменти.

import urllib.request

import matplotlib.pyplot as plt
import networkx as nx
from qiskit_addon_opt_mapper import OptimizationProblem
from qiskit_addon_opt_mapper.converters import OptimizationProblemToQubo
from qiskit_ibm_catalog import QiskitFunctionsCatalog

SQOA Solver приймає задачу QUBO як словник коефіцієнтів у форматі кортеж-рядок, який використовують функції оптимізації IBM®. Визнач допоміжну функцію, що перетворює QUBO, повернений OptimizationProblemToQubo, на цей формат.

Конвертер завжди повертає задачу мінімізації, що відповідає тому, як SQOA Solver трактує задачу-словник. Ключі використовують індекси змінних QUBO, і кожна змінна отримує лінійний запис, навіть із нульовим коефіцієнтом, щоб повернений розв'язок охоплював усі змінні.

def to_problem_dict(qubo: OptimizationProblem) -> dict[str, float]:
    """Convert a QUBO from OptimizationProblemToQubo to the SQOA Solver dictionary format."""
    objective = qubo.objective
    payload = {"()": objective.constant}
    # Keep every variable in the problem, even with a zero linear coefficient.
    payload.update({f"({i},)": 0.0 for i in range(qubo.get_num_vars())})
    for i, coefficient in objective.linear.to_dict().items():
        payload[f"({i},)"] += coefficient
    for (i, j), coefficient in objective.quadratic.to_dict().items():
        # Fold a binary diagonal term x_i * x_i = x_i into the linear term.
        key = f"({i},)" if i == j else f"({i}, {j})"
        payload[key] = payload.get(key, 0.0) + coefficient
    return {key: float(value) for key, value in payload.items()}

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

SQOA Solver приймає задачу QUBO і виконує квантове відображення всередині функції. У цьому посібнику ти завантажуєш екземпляр MIS із QOBLIB і формулюєш його як QUBO за допомогою qiskit-addon-opt-mapper. Цей крок охоплює таке:

• Підключення до SQOA Solver.

• Розуміння фреймворку SQOA.

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

• Формулювання QUBO та його перетворення для надсилання.

Підключення до SQOA Solver

Підключися до Qiskit Functions Catalog за допомогою облікових даних IBM Quantum Platform, потім завантаж SQOA Solver. Наведений нижче код припускає, що ти вже зберіг свій обліковий запис у локальному середовищі.

Якщо підключення не вдається, переконайся, що адміністратор твого облікового запису IBM Quantum Platform надав вибраному екземпляру сервісу доступ до SQOA Solver.

catalog = QiskitFunctionsCatalog(channel="ibm_quantum_platform")
solver = catalog.load("jij/sqoa-solver")

Розуміння фреймворку SQOA

Квантовий алгоритм оптимізації на основі семплювання з квантовою релаксацією (SQOA-QR) [2] поєднує Quantum Random Access Optimization (QRAO) із вибірковою квантовою діагоналізацією:

1. Квантова релаксація та кодування: SQOA Solver перетворює QUBO на мінімізаційну цільову функцію Ізінга вигляду $c + \sum_i h_i z_i + \sum_{i<j} J_{ij} z_i z_j$, де $z_i \in \{-1, +1\}$. Потім QRAO [3] відображає кожну спінову змінну на спостережувану Паулі. Для кодування $(3,1)$-QRAC, що використовується тут, релаксований гамільтоніан має вигляд

   $$\widetilde{H} = cI + \sum_i \sqrt{k_i} h_i P_{f(i)} + \sum_{i<j} \sqrt{k_i k_j} J_{ij} P_{f(i)} P_{f(j)},$$

   де $I$ — одиничний оператор, $f(i)$ призначає змінну $i$ кубіту та одному з $X$, $Y$ або $Z$, а $k_i \in \{1,2,3\}$ — кількість змінних, відображених на той самий кубіт, що й $i$. Коли обидва відповідні кубіти містять по три змінні, лінійний і квадратичний масштабні множники стають відповідно $\sqrt{3}$ та $3$.

   Змінним, що ділять кубіт, призначаються різні некомутівні спостережувані Паулі. Змінні, які взаємодіють у QUBO, лишаються на різних кубітах, тоді як змінні без прямої взаємодії в QUBO можуть ділити кубіт. Тому зменшення кількості кубітів залежить від структури задачі.

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

3. Вибіркова діагоналізація: Розв'язувач проєктує релаксований гамільтоніан на підпростір, натягнутий на базисні стани, отримані з вибраних бітових рядків, і класично діагоналізує спроєктований гамільтоніан [4], [5]. Для фіксованого набору вибраних бітових рядків нехай $\mathcal{S}_r$ — підпростір, натягнутий на $r$ різних базисних станів, тож $\dim(\mathcal{S}_r) \leq r$. Його оцінена енергія основного стану дорівнює:

   $$E_r = \min_{\substack{|\psi\rangle \in \mathcal{S}_r \\ \langle\psi|\psi\rangle=1}} \langle\psi|\widetilde{H}|\psi\rangle, \qquad \mathcal{S}_r \subseteq \mathcal{S}_{r'} \Longrightarrow E_{\mathrm{exact}} \leq E_{r'} \leq E_r \quad (r' \geq r),$$

   де $E_{\mathrm{exact}}$ — енергія основного стану повного релаксованого гамільтоніана. Отже, більший збережений підпростір не може збільшити оцінену енергію основного стану.

   Цей порядок припускає той самий результат семплювання і стосується енергії релаксованого гамільтоніана до округлення. Він теоретично не гарантує кращого поверненого класичного розв'язку. Однак у QRAO евристично очікується, що стан з нижчою енергією дасть кращий класичний розв'язок.

4. Округлення: Релаксований стан, отриманий із діагоналізації, перетворюється на класичне двійкове призначення.

SQOA Solver оточує цей фреймворк класичною обробкою. Перед квантовим відображенням presolve застосовує правила редукції, які можуть зафіксувати змінні та спростити решту QUBO, зберігаючи принаймні один оптимальний розв'язок. Після діагоналізації та округлення класичний локальний пошук уточнює призначення, а OMMX відновлює та оцінює повний розв'язок.

Завантаження екземпляра

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

QOBLIB також публікує оптимальний або найкращий відомий еталонний розв'язок для кожного екземпляра. Наведені нижче функції завантажують обидва з репозиторію QOBLIB. DIMACS нумерує вузли з 1, тому граф перенумеровується, щоб починатися з 0.

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

QOBLIB_URL = "https://raw.githubusercontent.com/ZIB-AOPT/QOBLIB/refs/heads/main/07-independentset"

def fetch_qoblib_graph(name: str) -> nx.Graph:
    """Download a QOBLIB independent-set instance as a NetworkX graph."""
    with urllib.request.urlopen(
        f"{QOBLIB_URL}/instances/{name}.gph"
    ) as response:
        lines = response.read().decode().splitlines()
    graph = nx.Graph()
    for fields in map(str.split, lines):
        if fields and fields[0] == "p":
            # Header: p edge <number of nodes> <number of edges>
            graph.add_nodes_from(range(int(fields[2])))
        elif fields and fields[0] == "e":
            # DIMACS labels nodes from 1; relabel them to start from 0.
            graph.add_edge(int(fields[1]) - 1, int(fields[2]) - 1)
    return graph

def fetch_reference_objective(name: str) -> float:
    """Read the objective value of the QOBLIB reference solution."""
    with urllib.request.urlopen(
        f"{QOBLIB_URL}/solutions/{name}.opt.sol"
    ) as response:
        for line in response.read().decode().splitlines():
            if line.startswith("# Objective value"):
                return float(line.split("=")[1])
    raise ValueError(f"No objective value found for {name}.")

INSTANCE_NAME = "gen200_p0-9_44"
G = fetch_qoblib_graph(INSTANCE_NAME)
reference_objective = fetch_reference_objective(INSTANCE_NAME)

Значення цільової функції еталонного розв'язку ти використаєш пізніше, щоб оцінити результат від SQOA Solver. Цей посібник розв'язує цю задачу на пристрої зі 156 кубітами.

print(
    f"{INSTANCE_NAME}: {G.number_of_nodes()} nodes, {G.number_of_edges()} edges"
)
print(f"Reference objective: {reference_objective:g}")

gen200_p0-9_44: 200 nodes, 1990 edges
Reference objective: 44

Візуалізуй граф. Пізніше ти також використаєш його, щоб перевірити, що вузли, повернені SQOA Solver, утворюють незалежну множину.

layout = nx.forceatlas2_layout(
    G, max_iter=500, scaling_ratio=3.0, gravity=1.0, seed=7
)
node_size = max(8, min(60, 4000 / max(G.number_of_nodes(), 1)))

fig, ax = plt.subplots(figsize=(9, 7))
nx.draw_networkx_edges(G, layout, ax=ax, alpha=0.2, width=0.6)
nx.draw_networkx_nodes(
    G, layout, node_size=node_size, node_color="lightgray", ax=ax
)
ax.set_title(
    f"{INSTANCE_NAME}: {G.number_of_nodes()} nodes, {G.number_of_edges()} edges"
)
ax.set_axis_off()
plt.show()

Формулювання QUBO

Побудуй двійкове лінійне формулювання з розділу «Передумови» як OptimizationProblem з однією двійковою змінною на вузол, цільовою функцією, що підраховує вибрані вузли, та одним обмеженням на ребро. Потім перетвори його за допомогою OptimizationProblemToQubo.

З вагою штрафу 2 конвертер замінює кожне обмеження на ребро штрафним доданком $2 x_v x_w$ і перетворює максимізацію на мінімізацію, тож перетворена задача є двійковим формулюванням без обмежень від QOBLIB зі зміненим знаком. Індекси змінних QUBO — це мітки вузлів графа. Клас застосування IndependentSet у qiskit_addon_opt_mapper.applications будує ту саму модель з обмеженнями за допомогою IndependentSet(G).to_optimization_problem().

Нарешті, перетвори QUBO на формат словника за допомогою to_problem_dict(). Оскільки задача є двійковим QUBO, запит на кроці 2 оголошує область її змінних як "binary". Функція виконує presolve, квантове відображення та побудову схем після надсилання.

mis = OptimizationProblem(INSTANCE_NAME)
mis.binary_var_list(G.number_of_nodes(), name="x")
mis.maximize(linear={v: 1 for v in G.nodes})
for u, v in G.edges:
    mis.linear_constraint({u: 1, v: 1}, "<=", 1)

converter = OptimizationProblemToQubo(penalty=2)
qubo = converter.convert(mis)
problem_dict = to_problem_dict(qubo)

print(f"QUBO variables: {qubo.get_num_vars()}")
print(f"Dictionary entries: {len(problem_dict)}")

QUBO variables: 200
Dictionary entries: 2191

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

SQOA Solver виконує квантове відображення та підготовку до виконання на обладнанні всередині функції. Спершу він застосовує presolve до QUBO, потім відображає решту змінних на релаксований гамільтоніан за допомогою кодування на основі QRAC.

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

Налаштування вхідних даних розв'язувача

SQOA Solver вимагає двох вхідних даних:

• problem, словник із кроку 1.

• variable_type, що дорівнює "binary" для цього QUBO.

Він також приймає два необов'язкові вхідні дані:

• backend_name вибирає QPU. Якщо його пропущено або він дорівнює None, функція вибирає найменш завантажений робочий QPU, доступний твоєму екземпляру.

• options — це словник, що керує бюджетом семплювання (shots), класичним початковим значенням (seed), використанням сесії (session), класичним локальним пошуком (postprocessing_level) та тегами завдань (job_tags). Якщо збільшити shots, статистика семплювання може покращитися.

Усі вхідні дані, їхні типові значення та правила валідації дивись у довіднику API.

У цьому посібнику бекенд задається явно, використовуються типові значення для shots, session та postprocessing_level і задається класичне початкове значення. Збери вхідні дані в словник, щоб передати їх у solver.run() на кроці 3.

# ibm_fez has 156 qubits
backend_name = (
    "ibm_fez"  # Omit this key or pass None for automatic selection.
)

sqoa_input = {
    "problem": problem_dict,
    "variable_type": "binary",
    "backend_name": backend_name,
}

sqoa_input["options"] = {
    "shots": 4096,
    "seed": 42,
    "session": False,
    "postprocessing_level": 1,
}

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

Надішли завдання, використовуючи підключення до SQOA Solver, створене на кроці 1. Функція запускає примітив IBM Quantum Sampler на вибраному бекенді, збирає виміряні бітові рядки та продовжує класичною діагоналізацією і постобробкою. Ти взаємодієш з одним завданням функції.

job = solver.run(**sqoa_input)
print(f"Job ID: {job.job_id}")

Job ID: dcee8e26-b8ac-4dd7-a76e-5adb5bc388e5

Щоб перевірити стан робочого навантаження, дивись Перевірка стану завдання. Внутрішньо функція проходить фази відображення, оптимізації для обладнання, очікування в черзі, виконання на QPU та постобробки.

job.status()

'INITIALIZING'

job.result() блокує виконання до завершення завдання та повертає словник із розв'язком, його значенням цільової функції та допустимістю, а також метаданими, що містять інформацію про розв'язувач і використання ресурсів. Повне визначення вхідних і вихідних даних дивись у довіднику API.

result = job.result()

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

Перевір повний вивід функції, відобрази повернене призначення назад на граф, перевір вибрані вузли та візуалізуй результат.

Перевірка результату

Словник результату містить чотири поля верхнього рівня:

• solution — це повне присвоєння змінних, індексоване за x_i, де i — індекс змінної (наприклад, x_17). У цьому навчальному посібнику індекс змінної є міткою вузла.

• objective_value — це цільове значення цього присвоєння, обчислене на поданому словнику, тобто на мінімізаційній QUBO.

• feasible стосується лише області значень змінних, оскільки словник не містить обмежень.

• metadata містить solver_info та resource_usage. solver_info записує фактичне значення seed запуску. Якщо виконувався класичний локальний пошук, solver_info також записує округлене присвоєння до цього уточнення в solution_before_postprocessing.

solver_info = result["metadata"]["solver_info"]

print(f"Result fields: {list(result)}")
print(f"Solution entries: {len(result['solution'])}")
print(f"First entries: {dict(list(result['solution'].items())[:3])}")
print(f"Objective value: {result['objective_value']}")
print(f"Feasible: {result['feasible']}")
print(f"Solver-info fields: {list(solver_info)}")
print(f"Effective seed: {solver_info['seed']}")
print(f"Resource-usage phases: {list(result['metadata']['resource_usage'])}")

Result fields: ['solution', 'objective_value', 'feasible', 'metadata']
Solution entries: 200
First entries: {'x_0': 0.0, 'x_1': 0.0, 'x_2': 1.0}
Objective value: -35.0
Feasible: True
Solver-info fields: ['seed', 'solution_before_postprocessing']
Effective seed: 42
Resource-usage phases: ['RUNNING: MAPPING', 'RUNNING: OPTIMIZING_FOR_HARDWARE', 'RUNNING: WAITING_FOR_QPU', 'RUNNING: EXECUTING_QPU', 'RUNNING: POST_PROCESSING']

Відобрази розв'язок на граф

Збери повернуті значення в порядку індексів змінних і за допомогою interpret() відобрази їх назад на змінні вихідної задачі. Вибрані вузли — це змінні зі значенням 1, а is_feasible() перевіряє присвоєння на відповідність обмеженням ребер вихідної задачі.

x_qubo = [result["solution"][f"x_{i}"] for i in range(qubo.get_num_vars())]
x = converter.interpret(x_qubo)
selected_nodes = [node for node, value in enumerate(x) if value > 0.5]

print(f"Selected nodes: {len(selected_nodes)}")
print(f"Satisfies every edge constraint: {mis.is_feasible(x)}")

Selected nodes: 35
Satisfies every edge constraint: True

Порівняй з розв'язком до постобробки

Оскільки postprocessing_level дорівнює 1, solver_info також записує округлене присвоєння до класичного локального пошуку в solution_before_postprocessing. Воно використовує ті самі ключі, що й solution.

Обчисли його на QUBO, щоб побачити, наскільки уточнення покращило результат. Обидва значення — це цільові значення поданої мінімізаційної QUBO, тому менше значення краще. Поле відсутнє, якщо локальний пошук не запускається, наприклад, коли presolve фіксує кожну змінну.

before = solver_info.get("solution_before_postprocessing")
if before is None:
    print("The classical local search did not run for this problem.")
else:
    x_before = [before[f"x_{i}"] for i in range(qubo.get_num_vars())]
    changed = sum(
        before[key] != value for key, value in result["solution"].items()
    )
    print(
        f"Objective before local search: {qubo.objective.evaluate(x_before)}"
    )
    print(f"Objective after local search: {result['objective_value']}")
    print(f"Variables changed by local search: {changed}")

Objective before local search: -12.0
Objective after local search: -35.0
Variables changed by local search: 19

Перевір обмеження незалежності

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

returned_set = set(selected_nodes)
conflicts = [
    (u, v) for u, v in G.edges if u in returned_set and v in returned_set
]
print(f"Conflicting edges in the returned set: {len(conflicts)}")

independent_set = returned_set.copy()
for u, v in conflicts:
    if u in independent_set and v in independent_set:
        # Drop the endpoint that has more selected neighbors.
        drop = max(
            (u, v),
            key=lambda node: sum(nb in independent_set for nb in G[node]),
        )
        independent_set.remove(drop)

assert all(
    not (u in independent_set and v in independent_set) for u, v in G.edges
)
print(f"Independent set size after repair: {len(independent_set)}")

Conflicting edges in the returned set: 0
Independent set size after repair: 35

Порівняй з еталонним розв'язком

На кроці 1 ти завантажив(-ла) цільове значення еталонного розв'язку QOBLIB. Еталонні розв'язки QOBLIB можуть бути оптимальними або найкращими з відомих, тому порівнюй з еталонним цільовим значенням, не припускаючи, що воно завжди є сертифікованим оптимумом.

Для цієї задачі максимізації відношення 1,0 означає, що виправлений результат збігається з еталонним цільовим значенням.

ratio_to_reference = len(independent_set) / reference_objective

print(f"Reference objective: {reference_objective:g}")
print(f"Ratio to reference: {ratio_to_reference:.3f}")

Reference objective: 44
Ratio to reference: 0.795

Візуалізуй результат

Побудуй граф ще раз із виділеною виправленою незалежною множиною. Жодні два виділені вузли не мають спільного ребра.

fig, ax = plt.subplots(figsize=(9, 7))
nx.draw_networkx_edges(G, layout, ax=ax, alpha=0.2, width=0.6)
nx.draw_networkx_nodes(
    G,
    layout,
    nodelist=[v for v in G if v not in independent_set],
    node_size=node_size,
    node_color="lightgray",
    ax=ax,
)
nx.draw_networkx_nodes(
    G,
    layout,
    nodelist=sorted(independent_set),
    node_size=node_size * 1.4,
    node_color="tab:blue",
    ax=ax,
)
ax.set_title(
    f"Independent set size: {len(independent_set)} "
    f"(reference: {reference_objective:g})"
)
ax.set_axis_off()
plt.show()

Прочитай використання ресурсів

Метадані результату повідомляють CPU_TIME для фаз, відмінних від RUNNING: EXECUTING_QPU, коли він доступний. Фаза RUNNING: EXECUTING_QPU може повідомляти QPU_TIME — використання QPU, повернуте Quantum Compute, якщо остаточне використання доступне для кожного завдання Quantum Compute.

usage = result["metadata"]["resource_usage"]

for phase, metrics in usage.items():
    line = f"{phase:36s}"
    if "CPU_TIME" in metrics:
        line += f" CPU {metrics['CPU_TIME']:8.1f} s"
    if "QPU_TIME" in metrics:
        line += f" QPU {metrics['QPU_TIME']:8.1f} s"
    print(line)

RUNNING: MAPPING                     CPU     11.8 s
RUNNING: OPTIMIZING_FOR_HARDWARE     CPU     15.4 s
RUNNING: WAITING_FOR_QPU             CPU     16.5 s
RUNNING: EXECUTING_QPU               QPU      3.0 s
RUNNING: POST_PROCESSING             CPU     55.8 s

Висновок

У цьому навчальному посібнику ти завантажив(-ла) екземпляр MIS із QOBLIB, сформулював(-ла) його як QUBO за допомогою qiskit-addon-opt-mapper, підключився(-лась) до SQOA Solver, налаштував(-ла) та подав(-ла) навантаження, відобразив(-ла) повернуте присвоєння назад на граф і перевірив(-ла) вибрані вузли за вихідним графом.

Ти також порівняв(-ла) результат з еталонним розв'язком QOBLIB, дослідив(-ла) внесок класичної постобробки та перевірив(-ла) використання ресурсів кожною фазою виконання.

SQOA Solver поєднує presolve, QRAO з кодуванням на основі QRAC, побудову семплувальних кіл, транспіляцію з урахуванням апаратури, діагоналізацію на основі семплів, округлення та класичне уточнення. Цей робочий процес може відобразити більше бінарних змінних, ніж дозволило б кодування «одна змінна на кубіт». Обсяг скорочення завдяки presolve та кодуванню залежить від структури задачі, а якість розв'язку — від отриманих семплів.

Параметри shots та postprocessing_level керують відповідно бюджетом квантового семплування та класичним уточненням, не змінюючи робочого процесу подання.

Додаток: подай задачу як екземпляр OMMX

SQOA Solver також приймає ommx.v1.Instance із SDK OMMX. Пакет OMMX Quantum Benchmarks розповсюджує задачі QOBLIB як екземпляри OMMX разом з їхніми еталонними розв'язками, тож ти можеш завантажити ту саму QUBO, не формулюючи її самостійно.

З вхідними даними OMMX objective_value обчислюється в розумінні екземпляра, а результат також містить канонічний ommx.v1.Solution. Встанови пакет, який також встановлює SDK OMMX:

# %pip install ommx-quantum-benchmarks

Завантаж модель binary_unconstrained того самого екземпляра. Завантажувач наборів даних друкує повідомлення про перебіг, тому код перехоплює їх, щоб вивід був компактним.

%%capture
from ommx_quantum_benchmarks.qoblib import IndependentSet

ommx_instance, _ = IndependentSet()("binary_unconstrained", INSTANCE_NAME)

SQOA Solver отримує екземпляр OMMX як стандартний рядок Base64 із доповненням і повертає канонічний розв'язок у тому самому форматі. Визнач дві допоміжні функції для цього перетворення:

• to_problem_payload() серіалізує ommx.v1.Instance у рядок, який ти передаєш як problem.

• to_ommx_solution() декодує канонічний ommx.v1.Solution з результату.

import base64

from ommx.v1 import Instance, Solution

def to_problem_payload(instance: Instance) -> str:
    """Serialize an OMMX instance into the `problem` string for SQOA Solver."""
    return base64.b64encode(instance.to_bytes()).decode()

def to_ommx_solution(result: dict) -> Solution:
    """Decode the canonical OMMX solution from a SQOA Solver result."""
    payload = result["metadata"]["solver_info"]["ommx_solution"]
    return Solution.from_bytes(base64.b64decode(payload, validate=True))

Подай екземпляр з тими самими вхідними даними, що й раніше, замінивши лише problem. Потім декодуй канонічний розв'язок і прочитай вибрані вузли за іменами змінних.

ommx_job = solver.run(
    **{**sqoa_input, "problem": to_problem_payload(ommx_instance)}
)
ommx_result = ommx_job.result()

ommx_solution = to_ommx_solution(ommx_result)
x_values = ommx_solution.extract_decision_variables("x")
ommx_nodes = sorted(
    node for (node,), value in x_values.items() if value > 0.5
)

print(f"Objective value: {ommx_result['objective_value']}")
print(f"Selected nodes: {len(ommx_nodes)}")

Objective value: 35.0
Selected nodes: 35

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

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

• Застосуй цей робочий процес до власних задач QUBO. Побудуй OptimizationProblem, як показано в посібнику SQOA Solver. Кроки перетворення та подання залишаються тими самими, але адаптуй перевірку до структури твоєї задачі.
• Подай задачу як екземпляр OMMX, як показано в додатку. Прийнятні формати задач і повернені поля дивись у довіднику API.
• Дослідж інші екземпляри незалежних множин у репозиторії QOBLIB або через OMMX Quantum Benchmarks.
• Дізнайся більше про моделювання за допомогою qiskit-addon-opt-mapper або JijModeling та обмін задачами за допомогою OMMX.

Посилання

[1] Koch, T., Bernal Neira, D. E., Chen, Y., Cortiana, G., Egger, D. J., Heese, R., Hegade, N. N., Gomez Cadavid, A., Huang, R., Itoko, T., et al. (2026). Quantum optimization benchmarking library: The intractable decathlon. Nature Computational Science, 6, 653–671. DOI, arXiv:2504.03832

[2] Matsuyama, H., & Yamashiro, Y. (2025). Sampling-based quantum optimization algorithm with quantum relaxation. 2025 IEEE International Conference on Quantum Computing and Engineering (QCE), 1, 2323–2333. DOI, arXiv:2504.12629

[3] Fuller, B., Hadfield, C., Glick, J. R., Imamichi, T., Itoko, T., Thompson, R. J., Jiao, Y., Kagele, M. M., Blom-Schieber, A. W., Raymond, R., et al. (2024). Approximate solutions of combinatorial problems via quantum relaxations. IEEE Transactions on Quantum Engineering, 5, 1–15. DOI, arXiv:2111.03167

[4] Kanno, K., Kohda, M., Imai, R., Koh, S., Mitarai, K., Mizukami, W., & Nakagawa, Y. O. (2026). Quantum-selected configuration interaction: Classical diagonalization of Hamiltonians in subspaces selected by quantum computers. Physical Review Research, 8(2), 023268. DOI, arXiv:2302.11320

[5] Robledo-Moreno, J., Motta, M., Haas, H., Javadi-Abhari, A., Jurcevic, P., Kirby, W., et al. (2025). Chemistry beyond the scale of exact diagonalization on a quantum-centric supercomputer. Science Advances, 11(25), eadu9991. DOI, arXiv:2405.05068