Menyelesaikan masalah set tak bersandar maksimum dengan lebih banyak pemboleh ubah daripada qubit menggunakan SQOA Solver daripada JIJ

nota

Qiskit Functions ialah ciri eksperimen yang hanya tersedia kepada pengguna IBM Quantum® Premium Plan, Flex Plan, dan On-Prem (melalui IBM Quantum Platform API) Plan. Ia berada dalam status keluaran pratonton dan tertakluk kepada perubahan.

Anggaran penggunaan: 10 saat pada pemproses Heron r2. (NOTA: Ini hanyalah anggaran. Masa jalan anda mungkin berbeza.)

Latar belakang

Tutorial ini menunjukkan cara menggunakan SQOA Solver, sebuah Qiskit Function oleh JIJ, untuk menyelesaikan masalah set tak bersandar maksimum (MIS) dengan lebih banyak pemboleh ubah binari daripada bilangan qubit pada QPU yang dipilih. Langkah asasnya ialah memuatkan satu instans MIS daripada Quantum Optimization Benchmarking Library (QOBLIB) [1], merumuskannya dalam bentuk pengoptimuman binari tanpa kekangan kuadratik (QUBO) dengan qiskit-addon-opt-mapper, menyerahkannya kepada SQOA Solver untuk pelaksanaan pada QPU IBM®, dan mengesahkan penyelesaian yang dikembalikan.

Masalah set tak bersandar maksimum

Set tak bersandar ialah subset nod dalam graf supaya tiada dua nod terpilih berkongsi satu tepi. Set tak bersandar maksimum (MIS) ialah set tak bersandar dengan bilangan nod terbesar yang mungkin. Aplikasi MIS termasuk penjadualan, peruntukan sumber, dan reka bentuk rangkaian.

MIS ialah NP-hard. Dalam carian lengkap, setiap nod tambahan menggandakan bilangan subset yang perlu dipertimbangkan, jadi pendekatan ini tidak praktikal walaupun untuk graf bersaiz sederhana. QOBLIB memasukkan MIS sebagai salah satu daripada sepuluh kelas masalahnya, jadi ia ialah penanda aras yang berguna untuk menilai aliran kerja pengoptimuman kuantum pada perkakasan sebenar.

Perumusan matematik

Diberi graf tak berarah $G = (V, E)$, tetapkan pemboleh ubah binari $x_v$ kepada setiap nod $v$:

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

• $x_v = 0$ otherwise.

Perumusan linear binari memaksimumkan bilangan nod terpilih sambil menghalang kedua-dua hujung mana-mana tepi daripada dipilih:

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

Objektif mengira nod terpilih. Bersama-sama, kekangan tepi memastikan nod terpilih membentuk set tak bersandar.

Tutorial ini menggunakan perumusan binari tanpa kekangan QOBLIB, yang menggantikan kekangan tepi 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.$$

Apabila kedua-dua hujung tepi dipilih, sebutan kedua menolak dua daripada objektif. Penalti ini menjadikan pilihan yang bercanggah kurang menguntungkan berbanding mengekalkan salah satu hujung sahaja. Objektif yang terhasil ialah QUBO, iaitu format input yang diterima oleh SQOA Solver.

Mengapa menggunakan SQOA Solver?

Banyak pendekatan pengoptimuman kuantum menetapkan satu qubit kepada setiap pemboleh ubah binari, jadi kapasiti perkakasan kuantum boleh terus mengehadkan saiz masalah. SQOA Solver menggabungkan beberapa teknik pengurangan dan pengkomputeran hibrid untuk melonggarkan sekatan ini:

• Ia boleh menangani masalah dengan lebih banyak pemboleh ubah binari daripada bilangan qubit pada QPU. Presolve menerapkan peraturan pengurangan yang boleh menetapkan pemboleh ubah dan memudahkan QUBO yang tinggal sambil mengekalkan sekurang-kurangnya satu penyelesaian optimum. Secara empirik, presolve juga boleh menjadikan QUBO yang tinggal lebih jarang, yang membantu pengekodan berasaskan QRAC yang mengikutinya.

  Penyelesai kemudian menggunakan pengekodan berasaskan QRAC yang diterbitkan daripada Quantum Random Access Optimization (QRAO) [3] untuk mewakili berbilang pemboleh ubah (sehingga tiga) tanpa interaksi QUBO langsung pada qubit yang sama.

  Pengurangan daripada presolve dan pengekodan bergantung pada struktur masalah. Contohnya, dalam tutorial ini, masalah 200 pemboleh ubah hanya menggunakan 67 qubit.

• Ia boleh kurang sensitif terhadap hingar perkakasan. Pepenyetriaan pepenjuru kuantum berasaskan sampel [4], [5] menggunakan QPU untuk mensampel rentetan bit tetapi melakukan pepenjuruan secara klasik. Ini mengelakkan penilaian QPU berulang untuk kemas kini parameter variasi dan boleh mengurangkan kesan hingar pada aliran kerja pengoptimuman.

• Ia mengautomasikan aliran kerja daripada presolve hingga pascapemprosesan. Anda menyediakan instans QUBO yang diformat dengan betul dan memilih Backend. SQOA Solver kemudian menjalankan keseluruhan aliran kerja secara automatik. Ia menerapkan presolve, memetakan pemboleh ubah klasik kepada masalah kuantum yang dilonggarkan, membina dan mentranspil litar pensampelan, melakukan pensampelan kuantum dan pepenjuruan klasik, membundarkan dan memperhalus penetapan, serta membina semula dan menilai penyelesaian klasik.

Keperluan

Sebelum anda memulakan tutorial ini, pastikan anda telah memasang pakej berikut:

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

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

• NetworkX dan Matplotlib, digunakan untuk mengendalikan dan memplot graf (pip install networkx matplotlib).

Anda juga memerlukan akses kepada SQOA Solver daripada Qiskit Functions Catalog. Isi borang untuk memohon akses kepada 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

Persediaan

Pertama, import pakej 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 kamus pekali dalam format tuple-rentetan yang digunakan oleh function pengoptimuman IBM®. Tentukan fungsi pembantu yang menukar QUBO yang dikembalikan oleh OptimizationProblemToQubo kepada format ini.

Penukar sentiasa mengembalikan masalah peminimuman, yang sepadan dengan cara SQOA Solver memperlakukan masalah kamus. Kunci menggunakan indeks pemboleh ubah QUBO, dan setiap pemboleh ubah menerima entri linear, walaupun dengan pekali sifar, supaya penyelesaian yang dikembalikan meliputi semua pemboleh ubah.

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 kepada masalah kuantum

SQOA Solver menerima masalah QUBO dan melakukan pemetaan kuantum di dalam function. Dalam tutorial ini, anda memuat turun satu instans MIS daripada QOBLIB dan merumuskannya sebagai QUBO dengan qiskit-addon-opt-mapper. Langkah ini merangkumi perkara berikut:

• Sambung kepada SQOA Solver.

• Fahami rangka kerja SQOA.

• Muatkan instans masalah.

• Rumuskan QUBO dan tukarkannya untuk penyerahan.

Sambung kepada SQOA Solver

Sambung kepada Qiskit Functions Catalog dengan bukti kelayakan IBM Quantum Platform anda, kemudian muatkan SQOA Solver. Kod berikut mengandaikan bahawa anda telah menyimpan akaun anda ke persekitaran tempatan anda.

Jika sambungan gagal, sahkan bahawa pentadbir akaun IBM Quantum Platform anda telah memberikan akses kepada SQOA Solver untuk instans perkhidmatan yang dipilih.

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

Fahami rangka kerja SQOA

Algoritma Pengoptimuman Kuantum Berasaskan Pensampelan dengan Pelonggaran Kuantum (SQOA-QR) [2] menggabungkan Quantum Random Access Optimization (QRAO) dengan pepenjuruan kuantum berasaskan sampel:

1. Pelonggaran dan pengekodan kuantum: SQOA Solver menukar QUBO kepada objektif Ising peminimuman dalam bentuk $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 pemboleh ubah spin kepada observabel Pauli. Untuk pengekodan $(3,1)$-QRAC yang digunakan di sini, Hamiltonian yang dilonggarkan ialah

   $$\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$ ialah operator identiti, $f(i)$ menetapkan pemboleh ubah $i$ kepada satu qubit dan salah satu daripada $X$, $Y$, atau $Z$, dan $k_i \in \{1,2,3\}$ ialah bilangan pemboleh ubah yang dipetakan pada qubit yang sama dengan $i$. Apabila kedua-dua qubit yang berkaitan mengandungi tiga pemboleh ubah, faktor penskalaan linear dan kuadratik masing-masing menjadi $\sqrt{3}$ dan $3$.

   Pemboleh ubah yang berkongsi satu qubit ditetapkan observabel Pauli tidak kalis tukar tertib yang berbeza. Pemboleh ubah yang berinteraksi dalam QUBO disimpan pada qubit yang berbeza, manakala pemboleh ubah tanpa interaksi QUBO langsung boleh berkongsi satu qubit. Oleh itu, pengurangan bilangan qubit bergantung pada struktur masalah.

2. Pensampelan kuantum: Pemproses kuantum mensampel rentetan bit daripada litar yang direka untuk meneroka keadaan bertenaga rendah bagi Hamiltonian yang dilonggarkan.

3. Pepenjuruan berasaskan sampel: Penyelesai memproyeksikan Hamiltonian yang dilonggarkan ke atas subruang yang direntangi oleh keadaan asas yang diperoleh daripada rentetan bit yang disampel dan memepenjuruankan Hamiltonian terunjur secara klasik [4], [5]. Bagi set tetap rentetan bit yang disampel, biarkan $\mathcal{S}_r$ ialah subruang yang direntangi oleh $r$ keadaan asas yang berbeza, jadi $\dim(\mathcal{S}_r) \leq r$. Anggaran tenaga keadaan asasnya ialah:

   $$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}}$ ialah tenaga keadaan asas bagi Hamiltonian terlonggar yang penuh. Oleh itu, subruang terkekal yang lebih besar tidak boleh meningkatkan anggaran tenaga keadaan asas.

   Susunan ini mengandaikan hasil pensampelan yang sama dan berkenaan tenaga Hamiltonian terlonggar sebelum pembundaran. Ia tidak menjamin secara teori penyelesaian klasik yang dikembalikan lebih baik. Walau bagaimanapun, dalam QRAO, keadaan bertenaga lebih rendah dijangka secara heuristik memberikan penyelesaian klasik yang lebih baik.

4. Pembundaran: Keadaan terlonggar yang diperoleh daripada pepenjuruan ditukar kepada penetapan binari klasik.

SQOA Solver mengelilingi rangka kerja ini dengan pemprosesan klasik. Sebelum pemetaan kuantum, presolve menerapkan peraturan pengurangan yang boleh menetapkan pemboleh ubah dan memudahkan QUBO yang tinggal sambil mengekalkan sekurang-kurangnya satu penyelesaian optimum. Selepas pepenjuruan dan pembundaran, carian setempat klasik memperhalus penetapan, dan OMMX membina semula serta menilai penyelesaian lengkap.

Muatkan instans

QOBLIB mengedarkan setiap instans MIS sebagai graf dalam format DIMACS .gph, iaitu format berasaskan baris yang baris bermula dengan p memberikan bilangan nod dan tepi, dan setiap baris bermula dengan e mentakrifkan satu tepi.

QOBLIB juga menerbitkan penyelesaian rujukan optimum atau terbaik yang diketahui bagi setiap instans. Fungsi berikut memuat turun kedua-duanya daripada repositori QOBLIB. DIMACS melabelkan nod bermula dari 1, jadi graf dilabel semula supaya bermula dari 0.

Jika anda mahu bermula daripada graf anda sendiri, langkau muat turun dan rumuskan masalah daripada 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 menggunakan nilai objektif penyelesaian rujukan kemudian untuk menilai hasil daripada SQOA Solver. Tutorial ini menyelesaikan masalah ini pada peranti 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

Visualkan graf tersebut. Kemudian, anda juga menggunakannya untuk mengesahkan bahawa nod yang dikembalikan oleh SQOA Solver membentuk set tak bersandar.

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

Rumuskan QUBO

Bina perumusan linear binari daripada bahagian Latar belakang sebagai OptimizationProblem dengan satu pemboleh ubah binari bagi setiap nod, objektif yang mengira nod terpilih, dan satu kekangan bagi setiap tepi. Kemudian tukarkannya dengan OptimizationProblemToQubo.

Dengan berat penalti 2, penukar menggantikan setiap kekangan tepi dengan sebutan penalti $2 x_v x_w$ dan menukar pemaksimuman kepada peminimuman, jadi masalah yang ditukar ialah perumusan binari tanpa kekangan QOBLIB dengan tandanya diterbalikkan. Indeks pemboleh ubah QUBO ialah label nod graf. Kelas aplikasi IndependentSet dalam qiskit_addon_opt_mapper.applications membina model berkekangan yang sama dengan IndependentSet(G).to_optimization_problem().

Akhir sekali, tukarkan QUBO kepada format kamus dengan to_problem_dict(). Oleh kerana masalah ini ialah QUBO binari, permintaan dalam Langkah 2 mengisytiharkan domain pemboleh ubahnya sebagai "binary". Function melakukan presolve, pemetaan kuantum, dan pembinaan litar selepas penyerahan.

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: Optimumkan masalah untuk pelaksanaan pada perkakasan kuantum

SQOA Solver melakukan pemetaan kuantum dan penyediaan perkakasan di dalam function. Ia mula-mula menerapkan presolve pada QUBO, kemudian memetakan pemboleh ubah yang tinggal kepada Hamiltonian terlonggar menggunakan pengekodan berasaskan QRAC.

Untuk pensampelan kuantum, ia membina litar berdasarkan Hamiltonian terlonggar dan mentranspilnya untuk Backend yang dipilih. Pengurangan saiz masalah dan qubit daripada presolve dan pengekodan bergantung pada masalah, jadi konfigurasikan penyelesai tanpa mengandaikan faktor pengurangan yang tetap.

Konfigurasikan input penyelesai

SQOA Solver memerlukan dua input:

• problem, kamus daripada Langkah 1.

• variable_type, iaitu "binary" untuk QUBO ini.

Ia juga menerima dua input pilihan:

• backend_name memilih QPU. Apabila ia ditinggalkan atau None, function memilih QPU beroperasi yang paling kurang sibuk dan boleh diakses oleh instans anda.

• options ialah kamus yang mengawal bajet pensampelan (shots), benih klasik (seed), penggunaan Session (session), carian setempat klasik (postprocessing_level), dan teg kerja (job_tags). Jika anda menambah shots, statistik pensampelan boleh bertambah baik.

Untuk semua input, nilai lalai dan peraturan pengesahannya, lihat rujukan API.

Tutorial ini menamakan Backend secara eksplisit, menggunakan nilai lalai untuk shots, session, dan postprocessing_level, serta menetapkan benih klasik. Kumpulkan input dalam kamus supaya anda boleh menghantarnya kepada solver.run() dalam 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: Laksanakan menggunakan primitif

Serahkan kerja dengan sambungan SQOA Solver yang dicipta dalam Langkah 1. Function menjalankan primitif IBM Quantum Sampler pada Backend yang dipilih, mengumpul rentetan bit yang diukur, dan menyambung dengan pepenjuruan klasik dan pascapemprosesan. Anda berinteraksi dengan satu kerja function sahaja.

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

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

Untuk menyemak status beban kerja, lihat Semak status kerja. Secara dalaman, function melalui fasa pemetaan, pengoptimuman perkakasan, menunggu giliran, pelaksanaan QPU, dan pascapemprosesan.

job.status()

'INITIALIZING'

job.result() menyekat sehingga kerja selesai dan mengembalikan kamus dengan penyelesaian, nilai objektif dan kebolehlaksanaannya, serta metadata yang memegang maklumat penyelesai dan penggunaan sumber. Untuk takrifan penuh input dan output, lihat rujukan API.

result = job.result()

Langkah 4: Pascaproses hasil dan tukarkannya kepada format klasik

Periksa output function yang lengkap, petakan penetapan yang dikembalikan semula ke graf, sahkan nod terpilih, dan visualkan hasilnya.

Periksa hasil

Kamus hasil mengandungi empat medan peringkat teratas:

• solution ialah penetapan pemboleh ubah yang lengkap, dikunci dengan x_i, dengan i ialah indeks pemboleh ubah (contohnya, x_17). Dalam tutorial ini, indeks pemboleh ubah ialah label nod.

• objective_value ialah objektif penetapan tersebut yang dinilai pada kamus yang diserahkan, iaitu pada QUBO peminimuman.

• feasible merujuk hanya kepada domain pemboleh ubah, kerana kamus tidak mempunyai kekangan.

• metadata mengandungi solver_info dan resource_usage. solver_info merekodkan seed berkesan bagi larian tersebut. Jika carian setempat klasik dijalankan, solver_info juga merekodkan penetapan terbundar daripada sebelum penghalusan itu dalam 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']

Petakan penyelesaian ke graf

Kumpulkan nilai yang dikembalikan mengikut susunan indeks pemboleh ubah, dan petakan semula kepada pemboleh ubah masalah asal dengan interpret(). Nod terpilih ialah pemboleh ubah bernilai 1, dan is_feasible() menyemak penetapan terhadap kekangan tepi masalah asal.

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

Bandingkan dengan penyelesaian sebelum pascapemprosesan

Oleh kerana postprocessing_level ialah 1, solver_info juga merekodkan penetapan terbundar daripada sebelum carian setempat klasik dalam solution_before_postprocessing. Ia menggunakan kunci yang sama seperti solution.

Nilaikannya pada QUBO untuk melihat sejauh mana penghalusan memperbaiki hasil. Kedua-dua nilai ialah objektif QUBO peminimuman yang diserahkan, jadi nilai yang lebih rendah adalah lebih baik. Medan ini ditinggalkan apabila carian setempat tidak dijalankan, contohnya, apabila presolve menetapkan setiap pemboleh ubah.

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

Sahkan kekangan ketakbersandaran

Oleh kerana QUBO mewakili kejiranan melalui sebutan penalti dan bukannya kekangan eksplisit, hasil heuristik masih boleh memilih nod bersebelahan. Semak nod yang dikembalikan terus terhadap graf. Untuk perbandingan dan visualisasi dalam bahagian berikut, salin set yang dikembalikan dan buang secara tamak satu hujung bagi setiap konflik yang dikesan.

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

Bandingkan dengan penyelesaian rujukan

Dalam Langkah 1, anda memuat turun nilai objektif penyelesaian rujukan QOBLIB. Penyelesaian rujukan QOBLIB boleh jadi optimum atau terbaik yang diketahui, jadi bandingkan dengan objektif rujukan tanpa mengandaikan bahawa ia sentiasa optimum yang disahkan.

Untuk masalah pemaksimuman ini, nisbah 1.0 bermakna hasil yang dibaiki sepadan dengan objektif rujukan.

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

Visualkan hasil

Plotkan graf sekali lagi dengan set tak bersandar yang dibaiki diserlahkan. Tiada dua nod yang diserlahkan berkongsi satu tepi.

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

Baca penggunaan sumber

Metadata hasil melaporkan CPU_TIME bagi fasa selain RUNNING: EXECUTING_QPU, apabila ia tersedia. Fasa RUNNING: EXECUTING_QPU boleh melaporkan QPU_TIME, penggunaan QPU yang dikembalikan oleh Quantum Compute, jika penggunaan akhir tersedia bagi setiap kerja 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 memuat turun satu instans MIS daripada QOBLIB, merumuskannya sebagai QUBO dengan qiskit-addon-opt-mapper, menyambung kepada SQOA Solver, mengkonfigurasi dan menyerahkan beban kerja, memetakan penetapan yang dikembalikan semula ke graf, dan menyemak nod terpilih terhadap graf asal.

Anda juga membandingkan hasil dengan penyelesaian rujukan QOBLIB, meneliti sumbangan pascapemprosesan klasik, dan memeriksa penggunaan sumber bagi setiap fasa pelaksanaan.

SQOA Solver menggabungkan presolve, QRAO dengan pengekodan berasaskan QRAC, pembinaan litar pensampelan, transpilasi sedar perkakasan, pepenjuruan berasaskan sampel, pembundaran, dan penghalusan klasik. Aliran kerja ini boleh memetakan lebih banyak pemboleh ubah binari daripada yang dibenarkan oleh pengekodan satu-pemboleh-ubah-setiap-qubit. Jumlah pengurangan daripada presolve dan pengekodan bergantung pada struktur masalah, dan kualiti penyelesaian bergantung pada sampel yang diperoleh.

Tetapan shots dan postprocessing_level masing-masing mengawal bajet pensampelan kuantum dan penghalusan klasik, tanpa mengubah aliran kerja penyerahan.

Lampiran: Serahkan masalah sebagai instans OMMX

SQOA Solver juga menerima ommx.v1.Instance daripada SDK OMMX. Pakej OMMX Quantum Benchmarks mengedarkan masalah QOBLIB sebagai instans OMMX bersama penyelesaian rujukannya, jadi anda boleh memuatkan QUBO yang sama tanpa merumuskannya sendiri.

Dengan input OMMX, objective_value dinilai dalam erti instans, dan hasilnya juga mengandungi ommx.v1.Solution kanonik. Pasang pakej tersebut, yang turut memasang SDK OMMX:

# %pip install ommx-quantum-benchmarks

Muatkan model binary_unconstrained bagi instans yang sama. Pemuat set data mencetak mesej kemajuan, jadi kod menangkapnya untuk memastikan output padat.

%%capture
from ommx_quantum_benchmarks.qoblib import IndependentSet

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

SQOA Solver menerima instans OMMX sebagai rentetan Base64 berlapik piawai dan mengembalikan penyelesaian kanonik dalam format yang sama. Tentukan dua fungsi pembantu untuk penukaran ini:

• to_problem_payload() menyirikan ommx.v1.Instance menjadi rentetan yang anda hantar sebagai problem.

• to_ommx_solution() menyahkod ommx.v1.Solution kanonik daripada hasil.

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

Hantar instance dengan input yang sama seperti sebelum ini, dengan hanya menggantikan problem. Kemudian nyahkod penyelesaian kanonik dan baca nod yang dipilih mengikut nama pemboleh ubah.

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 seterusnya

Cadangan

• Gunakan aliran kerja ini pada masalah QUBO anda sendiri. Bina OptimizationProblem seperti yang ditunjukkan dalam panduan SQOA Solver. Langkah penukaran dan penghantaran kekal sama, tetapi sesuaikan pengesahan dengan struktur masalah anda.
• Hantar masalah sebagai instance OMMX, seperti yang ditunjukkan dalam lampiran. Lihat rujukan API untuk format masalah yang diterima dan medan yang dikembalikan.
• Terokai instance independent-set lain dalam repositori QOBLIB atau melalui OMMX Quantum Benchmarks.
• Ketahui lebih lanjut tentang pemodelan dengan qiskit-addon-opt-mapper atau JijModeling dan pertukaran masalah dengan OMMX.

Rujukan

[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