Menyelesaikan masalah maximum independent set dengan variabel lebih banyak daripada qubit menggunakan SQOA Solver dari JIJ

catatan

Qiskit Functions adalah fitur eksperimental yang hanya tersedia untuk pengguna IBM Quantum® Premium Plan, Flex Plan, dan On-Prem (melalui IBM Quantum Platform API) Plan. Fitur ini berstatus rilis pratinjau dan dapat berubah.

Perkiraan penggunaan: 10 detik pada prosesor Heron r2. (CATATAN: Ini hanya perkiraan. Waktu jalan Anda bisa berbeda.)

Latar Belakang

Tutorial ini menunjukkan cara menggunakan SQOA Solver, sebuah Qiskit Function dari JIJ, untuk menyelesaikan masalah maximum independent set (MIS) dengan variabel biner lebih banyak daripada jumlah qubit pada QPU yang dipilih. Langkah dasarnya: memuat instans MIS dari Quantum Optimization Benchmarking Library (QOBLIB) [1], merumuskannya dalam bentuk quadratic unconstrained binary optimization (QUBO) dengan qiskit-addon-opt-mapper, mengirimkannya ke SQOA Solver untuk dieksekusi pada QPU IBM®, lalu memvalidasi solusi yang dikembalikan.

Masalah maximum independent set

Independent set adalah himpunan bagian node dalam sebuah graf sehingga tidak ada dua node terpilih yang berbagi sisi. Maximum independent set (MIS) adalah independent set dengan jumlah node terbanyak. Penerapan MIS mencakup penjadwalan, alokasi sumber daya, dan perancangan jaringan.

MIS bersifat NP-hard. Dalam pencarian menyeluruh, setiap node tambahan menggandakan jumlah himpunan bagian yang harus dipertimbangkan, sehingga pendekatan ini tidak praktis bahkan untuk graf berukuran sedang. QOBLIB memasukkan MIS sebagai salah satu dari sepuluh kelas masalahnya, jadi ini adalah benchmark yang berguna untuk mengevaluasi alur kerja optimisasi kuantum pada perangkat keras sungguhan.

Perumusan matematis

Diberikan graf tak berarah $G = (V, E)$, tetapkan variabel biner $x_v$ untuk setiap node $v$:

• $x_v = 1$ jika node $v$ dipilih.

• $x_v = 0$ otherwise.

Perumusan linear biner memaksimalkan jumlah node terpilih sambil mencegah kedua ujung sebuah sisi terpilih sekaligus:

$$\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}$$

Fungsi objektif menghitung node yang dipilih. Bersama-sama, batasan sisi memastikan node yang dipilih membentuk independent set.

Tutorial ini menggunakan perumusan biner tanpa batasan dari QOBLIB, yang mengganti batasan sisi dengan penalti kuadratik:

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

Setiap kali kedua ujung sebuah sisi terpilih, suku kedua mengurangi dua dari fungsi objektif. Penalti ini membuat pilihan yang bertentangan kurang menguntungkan daripada hanya memilih salah satu ujung. Fungsi objektif yang dihasilkan adalah QUBO, yaitu format input yang diterima SQOA Solver.

Kenapa pakai SQOA Solver?

Banyak pendekatan optimisasi kuantum menetapkan satu qubit untuk setiap variabel biner, sehingga kapasitas perangkat keras kuantum bisa langsung membatasi ukuran masalah. SQOA Solver menggabungkan beberapa teknik reduksi dan komputasi hibrida untuk melonggarkan batasan ini:

• Bisa menangani masalah dengan variabel biner lebih banyak daripada jumlah qubit pada QPU. Presolve menerapkan aturan reduksi yang dapat menetapkan variabel dan menyederhanakan QUBO yang tersisa sambil mempertahankan setidaknya satu solusi optimal. Secara empiris, presolve juga bisa membuat QUBO yang tersisa lebih jarang (sparse), yang membantu encoding berbasis QRAC sesudahnya.

  Solver kemudian memakai encoding berbasis QRAC yang diturunkan dari Quantum Random Access Optimization (QRAO) [3] untuk merepresentasikan beberapa variabel (hingga tiga) tanpa interaksi QUBO langsung pada qubit yang sama.

  Reduksi dari presolve dan encoding bergantung pada struktur masalah. Misalnya, dalam tutorial ini, masalah dengan 200 variabel hanya memakai 67 qubit.

• Bisa lebih tidak sensitif terhadap noise perangkat keras. Sample-based quantum diagonalization [4], [5] memakai QPU untuk mengambil sampel bitstring tetapi melakukan diagonalisasi secara klasik. Ini menghindari evaluasi QPU berulang untuk pembaruan parameter variasional dan dapat mengurangi dampak noise pada alur kerja optimisasi.

• Mengotomatiskan alur kerja dari presolve hingga pascapemrosesan. Anda menyediakan instans QUBO berformat benar dan memilih backend. SQOA Solver lalu menjalankan seluruh alur kerja secara otomatis. Ia menerapkan presolve, memetakan variabel klasik ke masalah kuantum terelaksasi, membangun dan men-transpile circuit sampling, melakukan sampling kuantum dan diagonalisasi klasik, membulatkan dan menyempurnakan penetapan, lalu merekonstruksi dan mengevaluasi solusi klasik.

Persyaratan

Sebelum memulai tutorial ini, pastikan paket berikut sudah terpasang:

• Klien Qiskit Functions Catalog (pip install qiskit-ibm-catalog).

• Qiskit addon optimization mapper, dipakai untuk merumuskan masalah (pip install qiskit-addon-opt-mapper).

• NetworkX dan Matplotlib, dipakai untuk menangani dan memplot graf (pip install networkx matplotlib).

Anda juga perlu akses ke SQOA Solver dari Qiskit Functions Catalog. Isi formulir untuk meminta akses ke function tersebut.

# 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

Penyiapan

Pertama, impor paket dan alat yang diperlukan.

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 menerima masalah QUBO sebagai dictionary koefisien dalam format tuple-string yang dipakai oleh fungsi optimisasi IBM®. Definisikan fungsi bantu yang mengubah QUBO yang dikembalikan oleh OptimizationProblemToQubo ke format ini.

Konverter selalu mengembalikan masalah minimisasi, sesuai dengan cara SQOA Solver memperlakukan masalah berbentuk dictionary. Kunci-kuncinya memakai indeks variabel QUBO, dan setiap variabel mendapat entri linear, bahkan dengan koefisien nol, supaya solusi yang dikembalikan mencakup semua variabel.

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()}

Langkah 1: Petakan input klasik ke masalah kuantum

SQOA Solver menerima masalah QUBO dan melakukan pemetaan kuantum di dalam function. Dalam tutorial ini, Anda mengunduh instans MIS dari QOBLIB dan merumuskannya sebagai QUBO dengan qiskit-addon-opt-mapper. Langkah ini mencakup hal berikut:

• Terhubung ke SQOA Solver.

• Memahami kerangka kerja SQOA.

• Memuat instans masalah.

• Merumuskan QUBO dan mengonversinya untuk pengiriman.

Terhubung ke SQOA Solver

Hubungkan ke Qiskit Functions Catalog dengan kredensial IBM Quantum Platform Anda, lalu muat SQOA Solver. Kode berikut mengasumsikan Anda sudah menyimpan akun Anda di lingkungan lokal.

Jika koneksi gagal, pastikan administrator akun IBM Quantum Platform Anda sudah memberikan akses ke SQOA Solver untuk service instance yang dipilih.

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

Memahami kerangka kerja SQOA

Sampling-based Quantum Optimization Algorithm with Quantum Relaxation (SQOA-QR) [2] menggabungkan Quantum Random Access Optimization (QRAO) dengan sample-based quantum diagonalization:

1. Relaksasi dan encoding kuantum: SQOA Solver mengubah QUBO menjadi fungsi objektif Ising minimisasi berbentuk $c + \sum_i h_i z_i + \sum_{i<j} J_{ij} z_i z_j$, dengan $z_i \in \{-1, +1\}$. QRAO [3] kemudian memetakan setiap variabel spin ke sebuah observabel Pauli. Untuk encoding $(3,1)$-QRAC yang dipakai di sini, Hamiltonian terelaksasinya adalah

   $$\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)},$$

   dengan $I$ adalah operator identitas, $f(i)$ menetapkan variabel $i$ ke sebuah qubit dan salah satu dari $X$, $Y$, atau $Z$, dan $k_i \in \{1,2,3\}$ adalah jumlah variabel yang dipetakan ke qubit yang sama dengan $i$. Ketika kedua qubit yang relevan berisi tiga variabel, faktor skala linear dan kuadratik masing-masing menjadi $\sqrt{3}$ dan $3$.

   Variabel yang berbagi qubit ditetapkan ke observabel Pauli noncommuting yang berbeda. Variabel yang berinteraksi dalam QUBO ditempatkan pada qubit berbeda, sedangkan variabel tanpa interaksi QUBO langsung bisa berbagi qubit. Jadi pengurangan jumlah qubit bergantung pada struktur masalah.

2. Sampling kuantum: Prosesor kuantum mengambil sampel bitstring dari circuit yang dirancang untuk menjelajahi keadaan berenergi rendah dari Hamiltonian terelaksasi.

3. Diagonalisasi berbasis sampel: Solver memproyeksikan Hamiltonian terelaksasi ke subruang yang direntang oleh keadaan basis dari bitstring hasil sampling, lalu mendiagonalisasi Hamiltonian terproyeksi secara klasik [4], [5]. Untuk himpunan bitstring sampel yang tetap, misalkan $\mathcal{S}_r$ adalah subruang yang direntang oleh $r$ keadaan basis berbeda, sehingga $\dim(\mathcal{S}_r) \leq r$. Estimasi energi keadaan dasarnya adalah:

   $$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),$$

   dengan $E_{\mathrm{exact}}$ adalah energi keadaan dasar dari Hamiltonian terelaksasi penuh. Karena itu, subruang yang dipertahankan lebih besar tidak bisa menaikkan estimasi energi keadaan dasar.

   Urutan ini mengasumsikan hasil sampling yang sama dan menyangkut energi Hamiltonian terelaksasi sebelum pembulatan. Ini tidak menjamin secara teoretis solusi klasik yang dikembalikan lebih baik. Meski begitu, dalam QRAO, keadaan berenergi lebih rendah secara heuristik diharapkan memberi solusi klasik yang lebih baik.

4. Pembulatan: Keadaan terelaksasi hasil diagonalisasi diubah menjadi penetapan biner klasik.

SQOA Solver membungkus kerangka kerja ini dengan pemrosesan klasik. Sebelum pemetaan kuantum, presolve menerapkan aturan reduksi yang dapat menetapkan variabel dan menyederhanakan QUBO yang tersisa sambil mempertahankan setidaknya satu solusi optimal. Setelah diagonalisasi dan pembulatan, local search klasik menyempurnakan penetapan, dan OMMX merekonstruksi serta mengevaluasi solusi lengkapnya.

Memuat instans

QOBLIB mendistribusikan setiap instans MIS sebagai graf dalam format DIMACS .gph, format berbasis baris di mana baris yang diawali p memberikan jumlah node dan sisi, dan setiap baris yang diawali e mendefinisikan sebuah sisi.

QOBLIB juga menerbitkan solusi referensi optimal atau terbaik yang diketahui untuk setiap instans. Fungsi-fungsi berikut mengunduh keduanya dari repositori QOBLIB. DIMACS memberi label node mulai dari 1, jadi graf diberi label ulang agar mulai dari 0.

Kalau Anda ingin mulai dari graf Anda sendiri, lewati pengunduhan dan rumuskan masalah dari graf NetworkX Anda dengan cara yang sama.

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)

Anda memakai nilai objektif dari solusi referensi nanti untuk menilai hasil dari SQOA Solver. Tutorial ini menyelesaikan masalah ini pada perangkat dengan 156 qubit.

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

Visualisasikan grafnya. Nanti, graf ini juga dipakai untuk memverifikasi bahwa node yang dikembalikan SQOA Solver membentuk independent set.

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

Merumuskan QUBO

Bangun perumusan linear biner dari bagian Latar Belakang sebagai OptimizationProblem dengan satu variabel biner per node, fungsi objektif yang menghitung node terpilih, dan satu batasan per sisi. Lalu konversi dengan OptimizationProblemToQubo.

Dengan bobot penalti 2, konverter mengganti setiap batasan sisi dengan suku penalti $2 x_v x_w$ dan mengubah maksimisasi menjadi minimisasi, sehingga masalah hasil konversi adalah perumusan biner tanpa batasan dari QOBLIB dengan tanda terbalik. Indeks variabel QUBO adalah label node graf. Kelas aplikasi IndependentSet di qiskit_addon_opt_mapper.applications membangun model berbatasan yang sama dengan IndependentSet(G).to_optimization_problem().

Terakhir, konversi QUBO ke format dictionary dengan to_problem_dict(). Karena masalahnya adalah QUBO biner, permintaan di Langkah 2 mendeklarasikan domain variabelnya sebagai "binary". Function melakukan presolve, pemetaan kuantum, dan konstruksi circuit setelah pengiriman.

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

Langkah 2: Optimalkan masalah untuk eksekusi di perangkat keras kuantum

SQOA Solver melakukan pemetaan kuantum dan persiapan perangkat keras di dalam function. Pertama ia menerapkan presolve pada QUBO, lalu memetakan variabel yang tersisa ke Hamiltonian terelaksasi dengan encoding berbasis QRAC.

Untuk sampling kuantum, ia membangun circuit berdasarkan Hamiltonian terelaksasi dan men-transpile-nya untuk backend yang dipilih. Pengurangan ukuran masalah dan jumlah qubit dari presolve dan encoding bergantung pada masalahnya, jadi konfigurasikan solver tanpa mengasumsikan faktor reduksi yang tetap.

Mengonfigurasi input solver

SQOA Solver memerlukan dua input:

• problem, dictionary dari Langkah 1.

• variable_type, yaitu "binary" untuk QUBO ini.

Ia juga menerima dua input opsional:

• backend_name memilih QPU. Jika dihilangkan atau None, function memilih QPU operasional yang paling tidak sibuk dan dapat diakses oleh instance Anda.

• options adalah dictionary yang mengatur anggaran sampling (shots), seed klasik (seed), penggunaan session (session), local search klasik (postprocessing_level), dan tag job (job_tags). Jika Anda menaikkan shots, statistik sampling bisa membaik.

Untuk semua input, nilai defaultnya, dan aturan validasi, lihat referensi API.

Tutorial ini menyebutkan backend secara eksplisit, memakai nilai default untuk shots, session, dan postprocessing_level, dan menetapkan seed klasik. Kumpulkan input dalam sebuah dictionary supaya bisa diteruskan ke solver.run() di Langkah 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,
}

Langkah 3: Eksekusi menggunakan primitive

Kirim job dengan koneksi SQOA Solver yang dibuat di Langkah 1. Function menjalankan primitive IBM Quantum Sampler pada backend yang dipilih, mengumpulkan bitstring hasil pengukuran, lalu melanjutkan dengan diagonalisasi klasik dan pascapemrosesan. Anda hanya berinteraksi dengan satu function job.

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

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

Untuk memeriksa status beban kerja, lihat Periksa status job. Secara internal, function melewati fase pemetaan, optimisasi perangkat keras, menunggu antrean, eksekusi QPU, dan pascapemrosesan.

job.status()

'INITIALIZING'

job.result() memblokir sampai job selesai dan mengembalikan dictionary berisi solusi, nilai objektif dan kelayakannya, serta metadata yang menyimpan informasi solver dan penggunaan sumber daya. Untuk definisi lengkap input dan output, lihat referensi API.

result = job.result()

Langkah 4: Pascapemrosesan hasil dan konversi ke format klasik

Periksa output function secara lengkap, petakan penetapan yang dikembalikan kembali ke graf, verifikasi node yang dipilih, dan visualisasikan hasilnya.

Memeriksa hasil

Dictionary hasil berisi empat field tingkat atas:

• solution adalah penetapan variabel lengkap, dengan kunci x_i, di mana i adalah indeks variabel (misalnya, x_17). Dalam tutorial ini, indeks variabel adalah label node.

• objective_value adalah nilai objektif dari penetapan tersebut yang dievaluasi pada dictionary yang dikirim, yaitu pada QUBO minimisasi.

• feasible hanya merujuk pada domain variabel, karena dictionary tidak memiliki batasan.

• metadata berisi solver_info dan resource_usage. solver_info mencatat seed efektif dari proses tersebut. Jika local search klasik dijalankan, solver_info juga mencatat penetapan terbulatkan dari sebelum penyempurnaan itu di 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']

Memetakan solusi ke graf

Kumpulkan nilai yang dikembalikan menurut urutan indeks variabel, lalu petakan kembali ke variabel masalah asli dengan interpret(). Node yang dipilih adalah variabel bernilai 1, dan is_feasible() memeriksa penetapan terhadap batasan sisi dari masalah asli.

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

Membandingkan dengan solusi sebelum pascapemrosesan

Karena postprocessing_level bernilai 1, solver_info juga mencatat penetapan terbulatkan dari sebelum local search klasik di solution_before_postprocessing. Ia memakai kunci yang sama dengan solution.

Evaluasi pada QUBO untuk melihat seberapa besar penyempurnaan memperbaiki hasil. Kedua nilai adalah nilai objektif dari QUBO minimisasi yang dikirim, jadi nilai yang lebih rendah lebih baik. Field ini dihilangkan ketika local search tidak dijalankan, misalnya, ketika presolve sudah menetapkan semua variabel.

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

Memverifikasi batasan independensi

Karena QUBO merepresentasikan keterhubungan lewat suku penalti, bukan batasan eksplisit, hasil heuristik masih bisa memilih node yang bertetangga. Periksa node yang dikembalikan langsung terhadap graf. Untuk perbandingan dan visualisasi di bagian berikutnya, salin himpunan yang dikembalikan dan hapus secara greedy satu ujung dari setiap konflik yang terdeteksi.

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

Membandingkan dengan solusi referensi

Di Langkah 1, Anda mengunduh nilai objektif dari solusi referensi QOBLIB. Solusi referensi QOBLIB bisa optimal atau terbaik yang diketahui, jadi bandingkan dengan objektif referensi tanpa mengasumsikan bahwa itu selalu optimum yang tersertifikasi.

Untuk masalah maksimisasi ini, rasio 1.0 berarti hasil yang sudah diperbaiki sama dengan objektif referensi.

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

Memvisualisasikan hasil

Plot graf sekali lagi dengan independent set yang sudah diperbaiki disorot. Tidak ada dua node yang disorot yang berbagi sisi.

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

Membaca penggunaan sumber daya

Metadata hasil melaporkan CPU_TIME untuk fase selain RUNNING: EXECUTING_QPU, jika tersedia. Fase RUNNING: EXECUTING_QPU dapat melaporkan QPU_TIME, penggunaan QPU yang dikembalikan oleh Quantum Compute, jika penggunaan akhir tersedia untuk setiap job 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

Kesimpulan

Dalam tutorial ini, Anda mengunduh instans MIS dari QOBLIB, merumuskannya sebagai QUBO dengan qiskit-addon-opt-mapper, terhubung ke SQOA Solver, mengonfigurasi dan mengirim beban kerja, memetakan penetapan yang dikembalikan kembali ke graf, dan memeriksa node yang dipilih terhadap graf asli.

Anda juga membandingkan hasil dengan solusi referensi QOBLIB, memeriksa kontribusi pascapemrosesan klasik, dan memeriksa penggunaan sumber daya dari setiap fase eksekusi.

SQOA Solver menggabungkan presolve, QRAO dengan encoding berbasis QRAC, konstruksi circuit sampling, transpilasi yang sadar perangkat keras, diagonalisasi berbasis sampel, pembulatan, dan penyempurnaan klasik. Alur kerja ini dapat memetakan lebih banyak variabel biner daripada yang diizinkan encoding satu-variabel-per-qubit. Besarnya reduksi dari presolve dan encoding bergantung pada struktur masalah, dan kualitas solusi bergantung pada sampel yang diperoleh.

Pengaturan shots dan postprocessing_level masing-masing mengendalikan anggaran sampling kuantum dan penyempurnaan klasik, tanpa mengubah alur kerja pengiriman.

Lampiran: Kirim masalah sebagai instans OMMX

SQOA Solver juga menerima ommx.v1.Instance dari SDK OMMX. Paket OMMX Quantum Benchmarks mendistribusikan masalah QOBLIB sebagai instans OMMX beserta solusi referensinya, sehingga Anda bisa memuat QUBO yang sama tanpa merumuskannya sendiri.

Dengan input OMMX, objective_value dievaluasi menurut makna instans tersebut, dan hasilnya juga memuat ommx.v1.Solution kanonik. Pasang paketnya, yang juga memasang SDK OMMX:

# %pip install ommx-quantum-benchmarks

Muat model binary_unconstrained dari instans yang sama. Pemuat dataset mencetak pesan progres, jadi kode menangkapnya agar output tetap ringkas.

%%capture
from ommx_quantum_benchmarks.qoblib import IndependentSet

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

SQOA Solver menerima instans OMMX sebagai string Base64 berpadding standar dan mengembalikan solusi kanonik dalam format yang sama. Definisikan dua fungsi bantu untuk konversi ini:

• to_problem_payload() men-serialize ommx.v1.Instance menjadi string yang Anda berikan sebagai problem.

• to_ommx_solution() men-decode ommx.v1.Solution kanonis dari hasilnya.

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

Kirim instance dengan input yang sama seperti sebelumnya, hanya ganti problem. Lalu decode solusi kanonis dan baca node yang terpilih berdasarkan nama variabelnya.

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

Langkah selanjutnya

Rekomendasi

• Terapkan alur kerja ini pada masalah QUBO milikmu sendiri. Buat OptimizationProblem seperti yang ditunjukkan di panduan SQOA Solver. Langkah konversi dan pengiriman tetap sama, tetapi sesuaikan validasinya dengan struktur masalahmu.
• Kirim masalah sebagai instance OMMX, seperti yang ditunjukkan di lampiran. Lihat referensi API untuk format masalah yang diterima dan field yang dikembalikan.
• Jelajahi instance independent-set lainnya di repositori QOBLIB atau lewat OMMX Quantum Benchmarks.
• Pelajari lebih lanjut tentang pemodelan dengan qiskit-addon-opt-mapper atau JijModeling dan pertukaran masalah dengan OMMX.

Referensi

[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