Lutasin ang maximum independent set na problema na mas marami ang variable kaysa sa qubit gamit ang SQOA Solver ng JIJ

tala

Ang Qiskit Functions ay isang experimental na feature na available lang sa mga user ng IBM Quantum® Premium Plan, Flex Plan, at On-Prem (sa pamamagitan ng IBM Quantum Platform API) Plan. Nasa preview release status ang mga ito at maaaring magbago.

Tantiya sa paggamit: 10 segundo sa isang Heron r2 processor. (TANDAAN: Tantiya lang ito. Maaaring iba ang runtime mo.)

Background

Ipinapakita ng tutorial na ito kung paano gamitin ang SQOA Solver, isang Qiskit Function mula sa JIJ, para lutasin ang isang maximum independent set (MIS) na problema na mas marami ang binary variable kaysa sa bilang ng qubit ng napiling QPU. Ang mga pangunahing hakbang ay: mag-load ng MIS instance mula sa Quantum Optimization Benchmarking Library (QOBLIB) [1], buuin ito sa quadratic unconstrained binary optimization (QUBO) form gamit ang qiskit-addon-opt-mapper, isumite ito sa SQOA Solver para patakbuhin sa isang IBM® QPU, at i-validate ang ibinalik na solusyon.

Ang maximum independent set na problema

Ang independent set ay isang subset ng mga node sa isang graph kung saan walang dalawang napiling node na may pinagsasaluhang edge. Ang maximum independent set (MIS) ay isang independent set na may pinakamaraming posibleng node. Kabilang sa mga aplikasyon ng MIS ang scheduling, resource allocation, at network design.

Ang MIS ay NP-hard. Sa isang exhaustive search, dumodoble ang bilang ng mga subset na kailangang isaalang-alang sa bawat dagdag na node, kaya hindi praktikal ang pamamaraang ito kahit sa mga graph na katamtaman ang laki. Kasama ang MIS sa sampung klase ng problema ng QOBLIB, kaya isa itong kapaki-pakinabang na benchmark para suriin ang mga quantum optimization workflow sa totoong hardware.

Mathematical formulation

Sa isang undirected graph na $G = (V, E)$, magtalaga ng binary variable na $x_v$ sa bawat node na $v$:

• $x_v = 1$ kung napili ang node na $v$.

• $x_v = 0$ otherwise.

Ang binary linear formulation ay ina-maximize ang bilang ng mga napiling node habang pinipigilang mapili ang magkabilang dulo ng alinmang edge:

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

Binibilang ng objective ang mga napiling node. Sama-sama, tinitiyak ng mga edge constraint na bumubuo ng independent set ang mga napiling node.

Ginagamit ng tutorial na ito ang binary unconstrained formulation ng QOBLIB, na pinapalitan ng mga quadratic penalty ang mga edge constraint:

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

Tuwing napili ang magkabilang dulo ng isang edge, binabawasan ng ikalawang term ang objective ng dalawa. Dahil sa penalty na ito, mas hindi paborable ang magkasalungat na pagpili kaysa sa pagpili ng isa lang sa mga dulo. Ang resultang objective ay isang QUBO, na siyang input format na tinatanggap ng SQOA Solver.

Bakit gagamitin ang SQOA Solver?

Maraming quantum optimization approach ang nagtatalaga ng isang qubit sa bawat binary variable, kaya ang kapasidad ng quantum hardware ay direktang maaaring maglimita sa laki ng problema. Pinagsasama ng SQOA Solver ang ilang reduction at hybrid-computing technique para pagaanin ang limitasyong ito:

• Kaya nitong harapin ang mga problemang mas marami ang binary variable kaysa sa bilang ng qubit ng QPU. Ang presolve ay naglalapat ng mga reduction rule na kayang mag-fix ng mga variable at pasimplehin ang natitirang QUBO habang pinapanatili ang kahit isang optimal na solusyon. Ayon sa karanasan, maaari ring gawing mas sparse ng presolve ang natitirang QUBO, na nakakatulong sa QRAC-based na encoding na sumusunod dito.

  Pagkatapos, gumagamit ang solver ng QRAC-based na encoding na hinango mula sa Quantum Random Access Optimization (QRAO) [3] para katawanin ang maraming variable (hanggang tatlo) na walang direktang QUBO interaction sa iisang qubit.

  Nakadepende sa estruktura ng problema ang mga reduction mula sa presolve at encoding. Halimbawa, sa tutorial na ito, 67 qubit lang ang ginagamit ng isang problemang may 200 variable.

• Maaari itong mas hindi sensitibo sa hardware noise. Ginagamit ng sample-based quantum diagonalization [4], [5] ang QPU para mag-sample ng mga bitstring pero classical ang paggawa ng diagonalization. Iniiwasan nito ang paulit-ulit na QPU evaluation para sa mga update ng variational parameter at maaaring bawasan ang epekto ng noise sa optimization workflow.

• Ina-automate nito ang workflow mula presolve hanggang post-processing. Magbibigay ka ng wastong naka-format na QUBO instance at pipili ng backend. Pagkatapos, awtomatikong patatakbuhin ng SQOA Solver ang buong workflow. Naglalapat ito ng presolve, imamapa ang mga classical variable sa isang relaxed na quantum problem, bubuuin at ita-transpile ang mga sampling circuit, magsasagawa ng quantum sampling at classical diagonalization, magro-round at magre-refine ng assignment, at muling bubuuin at susuriin ang classical na solusyon.

Mga Kinakailangan

Bago simulan ang tutorial na ito, siguraduhing naka-install ang mga sumusunod na package:

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

• Qiskit addon optimization mapper, na ginagamit para buuin ang problema (pip install qiskit-addon-opt-mapper).

• NetworkX at Matplotlib, na ginagamit para hawakan at i-plot ang graph (pip install networkx matplotlib).

Kailangan mo rin ng access sa SQOA Solver mula sa Qiskit Functions Catalog. Punan ang form para humiling ng access sa function.

# 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

Setup

Una, i-import ang mga kinakailangang package at tool.

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

Tinatanggap ng SQOA Solver ang isang QUBO na problema bilang coefficient dictionary sa tuple-string format na ginagamit ng mga optimization function ng IBM®. Magdefine ng helper function na kino-convert ang QUBO na ibinalik ng OptimizationProblemToQubo sa format na ito.

Laging minimization na problema ang ibinabalik ng converter, na tugma sa kung paano tinatrato ng SQOA Solver ang isang dictionary na problema. Gumagamit ang mga key ng mga variable index ng QUBO, at bawat variable ay may linear entry, kahit zero ang coefficient, para masaklaw ng ibinalik na solusyon ang lahat ng variable.

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

Hakbang 1: I-map ang mga classical input sa isang quantum na problema

Tinatanggap ng SQOA Solver ang isang QUBO na problema at ginagawa ang quantum mapping sa loob ng function. Sa tutorial na ito, magda-download ka ng MIS instance mula sa QOBLIB at bubuuin ito bilang QUBO gamit ang qiskit-addon-opt-mapper. Saklaw ng hakbang na ito ang mga sumusunod:

• Kumonekta sa SQOA Solver.

• Unawain ang SQOA framework.

• I-load ang problem instance.

• Buuin ang QUBO at i-convert ito para sa pagsusumite.

Kumonekta sa SQOA Solver

Kumonekta sa Qiskit Functions Catalog gamit ang iyong IBM Quantum Platform credentials, tapos i-load ang SQOA Solver. Ipinapalagay ng sumusunod na code na na-save mo na ang iyong account sa iyong lokal na environment.

Kung pumalya ang koneksyon, tiyaking binigyan ng administrator ng iyong IBM Quantum Platform account ang napiling service instance ng access sa SQOA Solver.

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

Unawain ang SQOA framework

Pinagsasama ng Sampling-based Quantum Optimization Algorithm with Quantum Relaxation (SQOA-QR) [2] ang Quantum Random Access Optimization (QRAO) at sample-based quantum diagonalization:

1. Quantum relaxation at encoding: Kino-convert ng SQOA Solver ang QUBO sa isang minimization Ising objective na may anyong $c + \sum_i h_i z_i + \sum_{i<j} J_{ij} z_i z_j$, kung saan $z_i \in \{-1, +1\}$. Pagkatapos, imamapa ng QRAO [3] ang bawat spin variable sa isang Pauli observable. Para sa $(3,1)$-QRAC encoding na ginagamit dito, ang relaxed Hamiltonian ay

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

   kung saan ang $I$ ay ang identity operator, itinatalaga ng $f(i)$ ang variable na $i$ sa isang qubit at sa isa sa $X$, $Y$, o $Z$, at ang $k_i \in \{1,2,3\}$ ay ang bilang ng mga variable na naka-map sa parehong qubit ng $i$. Kapag may tatlong variable ang parehong kaugnay na qubit, ang mga linear at quadratic scaling factor ay nagiging $\sqrt{3}$ at $3$, ayon sa pagkakasunod.

   Ang mga variable na nagbabahagi ng qubit ay itinatalaga ng magkakaibang noncommuting na Pauli observable. Ang mga variable na may interaction sa QUBO ay inilalagay sa magkakaibang qubit, habang ang mga variable na walang direktang QUBO interaction ay maaaring magbahagi ng qubit. Kaya nakadepende sa estruktura ng problema ang pagbawas sa bilang ng qubit.

2. Quantum sampling: Nagsa-sample ang isang quantum processor ng mga bitstring mula sa mga circuit na dinisenyo para tuklasin ang mga low-energy state ng relaxed Hamiltonian.

3. Sample-based diagonalization: Ipinoproject ng solver ang relaxed Hamiltonian sa subspace na sakop ng mga basis state na nakuha mula sa mga na-sample na bitstring at dina-diagonalize ang na-project na Hamiltonian nang classical [4], [5]. Para sa isang nakapirming set ng mga na-sample na bitstring, hayaang ang $\mathcal{S}_r$ ay ang subspace na sakop ng $r$ magkakaibang basis state, kaya $\dim(\mathcal{S}_r) \leq r$. Ang tinatayang ground-state energy nito ay:

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

   kung saan ang $E_{\mathrm{exact}}$ ay ang ground-state energy ng buong relaxed Hamiltonian. Kaya, hindi maaaring pataasin ng mas malaking pinanatiling subspace ang tinatayang ground-state energy.

   Ipinapalagay ng pagkakasunod-sunod na ito ang parehong sampling result at tungkol ito sa energy ng relaxed Hamiltonian bago mag-rounding. Hindi nito teoretikal na ginagarantiyahan ang mas mahusay na ibinalik na classical na solusyon. Gayunpaman, sa QRAO, heuristikong inaasahan na ang mas mababang-energy na state ay magbibigay ng mas mahusay na classical na solusyon.

4. Rounding: Ang relaxed state na nakuha mula sa diagonalization ay kino-convert sa isang classical na binary assignment.

Binabalutan ng SQOA Solver ang framework na ito ng classical processing. Bago ang quantum mapping, naglalapat ang presolve ng mga reduction rule na kayang mag-fix ng mga variable at pasimplehin ang natitirang QUBO habang pinapanatili ang kahit isang optimal na solusyon. Pagkatapos ng diagonalization at rounding, nire-refine ng isang classical local search ang assignment, at binubuo muli at sinusuri ng OMMX ang kumpletong solusyon.

I-load ang instance

Ipinamamahagi ng QOBLIB ang bawat MIS instance bilang graph sa DIMACS .gph format, isang line-based na format kung saan ang linyang nagsisimula sa p ay nagbibigay ng bilang ng mga node at edge at ang bawat linyang nagsisimula sa e ay nagdedefine ng isang edge.

Naglalathala rin ang QOBLIB ng optimal o best-known na reference solution para sa bawat instance. Dina-download ng mga sumusunod na function ang dalawa mula sa QOBLIB repository. Nagsisimula sa 1 ang pag-label ng DIMACS sa mga node, kaya nire-relabel ang graph para magsimula sa 0.

Kung gusto mong magsimula sa sarili mong graph, laktawan ang download at buuin ang problema mula sa iyong NetworkX graph sa parehong paraan.

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)

Gagamitin mo ang objective value ng reference solution mamaya para suriin ang resulta mula sa SQOA Solver. Nilulutas ng tutorial na ito ang problemang ito sa isang device na may 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

I-visualize ang graph. Gagamitin mo rin ito mamaya para i-verify na bumubuo ng independent set ang mga node na ibinalik ng 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()

Buuin ang QUBO

Buuin ang binary linear formulation mula sa seksyong Background bilang isang OptimizationProblem na may isang binary variable kada node, isang objective na bumibilang sa mga napiling node, at isang constraint kada edge. Pagkatapos, i-convert ito gamit ang OptimizationProblemToQubo.

Sa penalty weight na 2, pinapalitan ng converter ang bawat edge constraint ng penalty term na $2 x_v x_w$ at ginagawang minimization ang maximization, kaya ang na-convert na problema ay ang binary unconstrained formulation ng QOBLIB na may baligtad na sign. Ang mga variable index ng QUBO ay ang mga label ng node ng graph. Ang IndependentSet application class sa qiskit_addon_opt_mapper.applications ay bumubuo ng parehong constrained model gamit ang IndependentSet(G).to_optimization_problem().

Panghuli, i-convert ang QUBO sa dictionary format gamit ang to_problem_dict(). Dahil binary QUBO ang problema, idineklara ng request sa Hakbang 2 ang variable domain nito bilang "binary". Ginagawa ng function ang presolve, quantum mapping, at circuit construction pagkatapos ng pagsusumite.

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

Hakbang 2: I-optimize ang problema para sa pagpapatakbo sa quantum hardware

Ginagawa ng SQOA Solver ang quantum mapping at paghahanda ng hardware sa loob ng function. Una nitong inilalapat ang presolve sa QUBO, tapos imamapa ang natitirang mga variable sa isang relaxed Hamiltonian gamit ang QRAC-based na encoding.

Para sa quantum sampling, bumubuo ito ng mga circuit batay sa relaxed Hamiltonian at tina-transpile ang mga ito para sa napiling backend. Nakadepende sa problema ang pagbawas sa laki ng problema at bilang ng qubit mula sa presolve at encoding, kaya i-configure ang solver nang hindi ipinapalagay ang nakapirming reduction factor.

I-configure ang mga input ng solver

Nangangailangan ang SQOA Solver ng dalawang input:

• problem, ang dictionary mula sa Hakbang 1.

• variable_type, na "binary" para sa QUBO na ito.

Tumatanggap din ito ng dalawang opsyonal na input:

• Pinipili ng backend_name ang QPU. Kapag hindi ito ibinigay o None, pinipili ng function ang pinakakaunting abalang operational na QPU na ma-a-access ng iyong instance.

• Ang options ay isang dictionary na kumokontrol sa sampling budget (shots), sa classical seed (seed), sa paggamit ng session (session), sa classical local search (postprocessing_level), at sa mga job tag (job_tags). Kung dadagdagan mo ang shots, maaaring gumanda ang sampling statistics.

Para sa lahat ng input, sa mga default na halaga nito, at sa mga validation rule, tingnan ang API reference.

Tahasang pinangalanan ng tutorial na ito ang backend, ginagamit ang mga default na halaga para sa shots, session, at postprocessing_level, at itinatakda ang classical seed. Ipunin ang mga input sa isang dictionary para maipasa mo ang mga ito sa solver.run() sa Hakbang 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,
}

Hakbang 3: Patakbuhin gamit ang mga primitive

Isumite ang job gamit ang koneksyon sa SQOA Solver na ginawa sa Hakbang 1. Pinapatakbo ng function ang IBM Quantum Sampler primitive sa napiling backend, kinokolekta ang mga sinukat na bitstring, at nagpapatuloy sa classical diagonalization at post-processing. Isang function job lang ang kinakausap mo.

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

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

Para tingnan ang status ng workload, tingnan ang Check job status. Sa loob, dumadaan ang function sa mga phase ng mapping, hardware optimization, paghihintay sa queue, QPU execution, at post-processing.

job.status()

'INITIALIZING'

Hinaharang ng job.result() ang takbo hanggang matapos ang job at nagbabalik ng dictionary na may solusyon, ang objective value at feasibility nito, at metadata na naglalaman ng impormasyon ng solver at resource usage. Para sa buong definisyon ng mga input at output, tingnan ang API reference.

result = job.result()

Hakbang 4: I-post-process ang resulta at i-convert ito sa classical na format

Suriin ang kumpletong output ng function, i-map pabalik sa graph ang ibinalik na assignment, i-verify ang mga napiling node, at i-visualize ang resulta.

Suriin ang resulta

Ang result dictionary ay may apat na top-level na field:

• Ang solution ay ang kumpletong variable assignment, na naka-key sa x_i, kung saan ang i ay ang variable index (halimbawa, x_17). Sa tutorial na ito, ang variable index ay ang label ng node.

• Ang objective_value ay ang objective ng assignment na iyon na sinuri sa isinumiteng dictionary, ibig sabihin, sa minimization QUBO.

• Ang feasible ay tumutukoy lang sa variable domain, dahil walang constraint ang dictionary.

• Naglalaman ang metadata ng solver_info at resource_usage. Itinatala ng solver_info ang epektibong seed ng run. Kung tumakbo ang classical local search, itinatala rin ng solver_info ang rounded assignment mula bago ang refinement na iyon sa 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']

I-map ang solusyon sa graph

Ipunin ang mga ibinalik na halaga ayon sa pagkakasunod-sunod ng mga variable index, at i-map ang mga ito pabalik sa mga variable ng orihinal na problema gamit ang interpret(). Ang mga napiling node ay ang mga variable na may halagang 1, at sinusuri ng is_feasible() ang assignment laban sa mga edge constraint ng orihinal na problema.

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

Ihambing sa solusyon bago ang post-processing

Dahil 1 ang postprocessing_level, itinatala rin ng solver_info ang rounded assignment mula bago ang classical local search sa solution_before_postprocessing. Pareho ang mga key nito sa solution.

Suriin ito sa QUBO para makita kung gaano kalaki ang naitulong ng refinement sa resulta. Parehong mga objective ng isinumiteng minimization QUBO ang dalawang halaga, kaya mas maganda ang mas mababang halaga. Hindi isinasama ang field kapag hindi tumakbo ang local search, halimbawa, kapag na-fix ng presolve ang bawat variable.

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

I-verify ang independence constraint

Dahil kinakatawan ng QUBO ang adjacency sa pamamagitan ng mga penalty term sa halip na tahasang constraint, maaari pa ring mapili ng isang heuristic na resulta ang magkatabing node. Direktang suriin ang mga ibinalik na node laban sa graph. Para sa paghahambing at visualization sa mga susunod na seksyon, kopyahin ang ibinalik na set at greedy na alisin ang isang dulo ng bawat natukoy na conflict.

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

Ihambing sa reference solution

Sa Hakbang 1, dina-download mo ang objective value ng QOBLIB reference solution. Maaaring optimal o best-known ang mga QOBLIB reference solution, kaya ihambing sa reference objective nang hindi ipinapalagay na laging certified optimum ito.

Para sa maximization na problemang ito, ang ratio na 1.0 ay nangangahulugang tugma ng naayos na resulta ang reference objective.

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

I-visualize ang resulta

I-plot muli ang graph na naka-highlight ang naayos na independent set. Walang dalawang naka-highlight na node ang may pinagsasaluhang edge.

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

Basahin ang resource usage

Iniuulat ng result metadata ang CPU_TIME para sa mga phase maliban sa RUNNING: EXECUTING_QPU, kapag available ito. Maaaring mag-ulat ang phase na RUNNING: EXECUTING_QPU ng QPU_TIME, ang QPU usage na ibinalik ng Quantum Compute, kung available ang huling usage para sa bawat Quantum Compute job.

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

Konklusyon

Sa tutorial na ito, nag-download ka ng MIS instance mula sa QOBLIB, ginawa itong QUBO gamit ang qiskit-addon-opt-mapper, kumonekta sa SQOA Solver, kinonfigure at isinumite ang workload, imina-map pabalik sa graph ang ibinalik na assignment, at tiningnan ang mga napiling node laban sa orihinal na graph.

Inihambing mo rin ang resulta sa reference solution ng QOBLIB, sinuri ang kontribusyon ng classical post-processing, at siniyasat ang resource usage ng bawat execution phase.

Pinagsasama ng SQOA Solver ang presolve, QRAO na may QRAC-based na encoding, pagbuo ng sampling circuit, hardware-aware na transpilation, sample-based na diagonalization, rounding, at classical refinement. Kaya ng workflow na ito na mag-map ng mas maraming binary variable kaysa sa papayagan ng one-variable-per-qubit na encoding. Ang laki ng pagbawas mula sa presolve at encoding ay nakadepende sa istruktura ng problema, at ang kalidad ng solusyon ay nakadepende sa nakuhang mga sample.

Kinokontrol ng mga setting na shots at postprocessing_level ang quantum sampling budget at ang classical refinement, ayon sa pagkakasunod, nang hindi binabago ang submission workflow.

Appendix: Isumite ang problema bilang OMMX instance

Tumatanggap din ang SQOA Solver ng ommx.v1.Instance mula sa OMMX SDK. Ang package na OMMX Quantum Benchmarks ay nagdi-distribute ng mga problema ng QOBLIB bilang OMMX instance kasama ang kanilang mga reference solution, kaya mailo-load mo ang parehong QUBO nang hindi mo ito kailangang i-formulate.

Sa OMMX input, ang objective_value ay sinusuri ayon sa kahulugan ng instance, at naglalaman din ang resulta ng canonical na ommx.v1.Solution. I-install ang package, na nag-i-install din ng OMMX SDK:

# %pip install ommx-quantum-benchmarks

I-load ang binary_unconstrained model ng parehong instance. Nagpi-print ng mga progress message ang dataset loader, kaya kinukuha ng code ang mga ito para manatiling compact ang output.

%%capture
from ommx_quantum_benchmarks.qoblib import IndependentSet

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

Tumatanggap ang SQOA Solver ng OMMX instance bilang standard padded Base64 string at ibinabalik ang canonical solution sa parehong format. Tumukoy ng dalawang helper function para sa conversion na ito:

• Sina-serialize ng to_problem_payload() ang isang ommx.v1.Instance tungo sa string na ipapasa mo bilang problem.

• Dine-decode ng to_ommx_solution() ang canonical na ommx.v1.Solution mula sa resulta.

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

Isumite ang instance gamit ang parehong mga input tulad ng dati, problem lang ang papalitan. Pagkatapos, i-decode ang canonical solution at basahin ang mga napiling node ayon sa pangalan ng variable.

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

Mga susunod na hakbang

Mga Rekomendasyon

• Ilapat ang workflow sa sarili mong mga QUBO problem. Bumuo ng OptimizationProblem tulad ng ipinapakita sa SQOA Solver guide. Pareho pa rin ang mga hakbang para sa conversion at pagsumite, ngunit iangkop ang validation sa istruktura ng iyong problema.
• Isumite ang problema bilang OMMX instance, tulad ng ipinapakita sa appendix. Tingnan ang API reference para sa mga tinatanggap na format ng problema at sa mga ibinabalik na field.
• Mag-explore ng iba pang independent-set instance sa QOBLIB repository o sa pamamagitan ng OMMX Quantum Benchmarks.
• Matuto pa tungkol sa pagmomodelo gamit ang qiskit-addon-opt-mapper o JijModeling at sa pagpapalitan ng mga problema gamit ang OMMX.

Mga Sanggunian

[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