Rezolvă o problemă de mulțime independentă maximă cu mai multe variabile decât qubiți folosind SQOA Solver de la JIJ

notă

Qiskit Functions sunt o funcționalitate experimentală disponibilă doar utilizatorilor planurilor IBM Quantum® Premium Plan, Flex Plan și On-Prem (prin IBM Quantum Platform API). Se află în stadiul de versiune preliminară și pot suferi modificări.

Estimare de utilizare: 10 secunde pe un procesor Heron r2. (NOTĂ: Aceasta este doar o estimare. Timpul tău de rulare poate varia.)

Context

Acest tutorial arată cum să folosești SQOA Solver, o Qiskit Function de la JIJ, pentru a rezolva o problemă de mulțime independentă maximă (MIS) cu mai multe variabile binare decât are QPU-ul selectat qubiți. Pașii de bază sunt: încărcarea unei instanțe MIS din Quantum Optimization Benchmarking Library (QOBLIB) [1], formularea ei în formă de optimizare binară pătratică fără constrângeri (QUBO) cu qiskit-addon-opt-mapper, trimiterea ei la SQOA Solver pentru execuție pe un QPU IBM® și validarea soluției returnate.

Problema mulțimii independente maxime

O mulțime independentă este o submulțime de noduri dintr-un graf astfel încât oricare două noduri selectate să nu aibă o muchie comună. O mulțime independentă maximă (MIS) este o mulțime independentă cu cel mai mare număr posibil de noduri. Aplicațiile MIS includ planificarea, alocarea resurselor și proiectarea rețelelor.

MIS este NP-hard. Într-o căutare exhaustivă, fiecare nod suplimentar dublează numărul de submulțimi de luat în considerare, deci această abordare este impracticabilă chiar și pentru grafuri de dimensiuni moderate. QOBLIB include MIS ca una dintre cele zece clase de probleme ale sale, deci este un benchmark util pentru evaluarea fluxurilor de lucru de optimizare cuantică pe hardware real.

Formularea matematică

Dat fiind un graf neorientat $G = (V, E)$, atribuie o variabilă binară $x_v$ fiecărui nod $v$:

• $x_v = 1$ dacă nodul $v$ este selectat.

• $x_v = 0$ otherwise.

Formularea liniară binară maximizează numărul de noduri selectate, împiedicând în același timp selectarea ambelor capete ale oricărei muchii:

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

Obiectivul numără nodurile selectate. Împreună, constrângerile pe muchii asigură că nodurile selectate formează o mulțime independentă.

Acest tutorial folosește formularea binară fără constrângeri din QOBLIB, care înlocuiește constrângerile pe muchii cu penalizări pătratice:

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

Ori de câte ori ambele capete ale unei muchii sunt selectate, al doilea termen scade două unități din obiectiv. Această penalizare face o selecție conflictuală mai puțin favorabilă decât păstrarea unui singur capăt. Obiectivul rezultat este un QUBO, care este formatul de intrare acceptat de SQOA Solver.

De ce să folosești SQOA Solver?

Multe abordări de optimizare cuantică atribuie câte un qubit fiecărei variabile binare, astfel încât capacitatea hardware-ului cuantic poate limita direct dimensiunea problemei. SQOA Solver combină mai multe tehnici de reducere și de calcul hibrid pentru a atenua această restricție:

• Poate aborda probleme cu mai multe variabile binare decât are QPU-ul qubiți. Presolve aplică reguli de reducere care pot fixa variabile și simplifica QUBO-ul rămas, păstrând cel puțin o soluție optimă. Empiric, presolve poate face QUBO-ul rămas și mai rar, ceea ce ajută codificarea bazată pe QRAC care urmează.

  Solver-ul folosește apoi o codificare bazată pe QRAC, derivată din Quantum Random Access Optimization (QRAO) [3], pentru a reprezenta pe același qubit mai multe variabile (până la trei) fără interacțiune directă în QUBO.

  Reducerile obținute din presolve și din codificare depind de structura problemei. De exemplu, în acest tutorial, o problemă cu 200 de variabile folosește doar 67 de qubiți.

• Poate fi mai puțin sensibil la zgomotul hardware. Diagonalizarea cuantică bazată pe eșantioane [4], [5] folosește QPU-ul pentru a eșantiona șiruri de biți, dar efectuează diagonalizarea clasic. Aceasta evită evaluările repetate pe QPU pentru actualizarea parametrilor variaționali și poate reduce impactul zgomotului asupra fluxului de optimizare.

• Automatizează fluxul de lucru de la presolve până la post-procesare. Furnizezi o instanță QUBO formatată corect și selectezi un backend. SQOA Solver rulează apoi automat întregul flux de lucru. Aplică presolve, mapează variabilele clasice pe o problemă cuantică relaxată, construiește și transpilează circuitele de eșantionare, efectuează eșantionarea cuantică și diagonalizarea clasică, rotunjește și rafinează atribuirea și reconstruiește și evaluează soluția clasică.

Cerințe

Înainte de a începe acest tutorial, asigură-te că ai instalate următoarele pachete:

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

• Qiskit addon optimization mapper, folosit pentru formularea problemei (pip install qiskit-addon-opt-mapper).

• NetworkX și Matplotlib, folosite pentru a gestiona și a desena graful (pip install networkx matplotlib).

Ai nevoie, de asemenea, de acces la SQOA Solver din Qiskit Functions Catalog. Completează formularul pentru a solicita acces la funcție.

# 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

Configurare

Mai întâi, importă pachetele și instrumentele necesare.

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 acceptă o problemă QUBO sub forma unui dicționar de coeficienți în formatul tuplu-șir folosit de funcțiile de optimizare IBM®. Definește o funcție ajutătoare care convertește QUBO-ul returnat de OptimizationProblemToQubo în acest format.

Convertorul returnează întotdeauna o problemă de minimizare, ceea ce corespunde modului în care SQOA Solver tratează o problemă dată ca dicționar. Cheile folosesc indicii variabilelor din QUBO, iar fiecare variabilă primește o intrare liniară, chiar și cu coeficient zero, astfel încât soluția returnată să acopere toate variabilele.

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

Pasul 1: Mapează intrările clasice pe o problemă cuantică

SQOA Solver acceptă o problemă QUBO și efectuează maparea cuantică în interiorul funcției. În acest tutorial, descarci o instanță MIS din QOBLIB și o formulezi ca QUBO cu qiskit-addon-opt-mapper. Acest pas cuprinde următoarele:

• Conectarea la SQOA Solver.

• Înțelegerea cadrului SQOA.

• Încărcarea instanței problemei.

• Formularea QUBO-ului și convertirea lui pentru trimitere.

Conectează-te la SQOA Solver

Conectează-te la Qiskit Functions Catalog cu credențialele tale IBM Quantum Platform, apoi încarcă SQOA Solver. Codul următor presupune că ți-ai salvat deja contul în mediul local.

Dacă conectarea eșuează, verifică dacă administratorul contului tău IBM Quantum Platform a acordat instanței de serviciu selectate acces la SQOA Solver.

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

Înțelege cadrul SQOA

Algoritmul de optimizare cuantică bazat pe eșantionare cu relaxare cuantică (Sampling-based Quantum Optimization Algorithm with Quantum Relaxation, SQOA-QR) [2] combină Quantum Random Access Optimization (QRAO) cu diagonalizarea cuantică bazată pe eșantioane:

1. Relaxare și codificare cuantică: SQOA Solver convertește QUBO-ul într-un obiectiv Ising de minimizare de forma $c + \sum_i h_i z_i + \sum_{i<j} J_{ij} z_i z_j$, unde $z_i \in \{-1, +1\}$. QRAO [3] mapează apoi fiecare variabilă de spin pe o observabilă Pauli. Pentru codificarea $(3,1)$-QRAC folosită aici, hamiltonianul relaxat este

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

   unde $I$ este operatorul identitate, $f(i)$ atribuie variabila $i$ unui qubit și uneia dintre $X$, $Y$ sau $Z$, iar $k_i \in \{1,2,3\}$ este numărul de variabile mapate pe același qubit ca $i$. Când ambii qubiți relevanți conțin trei variabile, factorii de scalare liniar și pătratic devin $\sqrt{3}$ și, respectiv, $3$.

   Variabilele care împart un qubit primesc observabile Pauli necomutative diferite. Variabilele care interacționează în QUBO sunt păstrate pe qubiți diferiți, în timp ce variabilele fără interacțiune directă în QUBO pot împărți un qubit. Reducerea numărului de qubiți depinde, așadar, de structura problemei.

2. Eșantionare cuantică: Un procesor cuantic eșantionează șiruri de biți din circuite concepute pentru a explora stările de energie joasă ale hamiltonianului relaxat.

3. Diagonalizare bazată pe eșantioane: Solver-ul proiectează hamiltonianul relaxat pe subspațiul generat de stările de bază obținute din șirurile de biți eșantionate și diagonalizează clasic hamiltonianul proiectat [4], [5]. Pentru un set fix de șiruri de biți eșantionate, fie $\mathcal{S}_r$ subspațiul generat de $r$ stări de bază distincte, deci $\dim(\mathcal{S}_r) \leq r$. Energia sa estimată a stării fundamentale este:

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

   unde $E_{\mathrm{exact}}$ este energia stării fundamentale a hamiltonianului relaxat complet. Prin urmare, un subspațiu păstrat mai mare nu poate crește energia estimată a stării fundamentale.

   Această ordonare presupune același rezultat de eșantionare și privește energia hamiltonianului relaxat înainte de rotunjire. Ea nu garantează teoretic o soluție clasică returnată mai bună. Totuși, în QRAO, se așteaptă euristic ca o stare de energie mai joasă să ofere o soluție clasică mai bună.

4. Rotunjire: Starea relaxată obținută din diagonalizare este convertită într-o atribuire binară clasică.

SQOA Solver înconjoară acest cadru cu procesare clasică. Înainte de mapare cuantică, presolve aplică reguli de reducere care pot fixa variabile și simplifica QUBO-ul rămas, păstrând cel puțin o soluție optimă. După diagonalizare și rotunjire, o căutare locală clasică rafinează atribuirea, iar OMMX reconstruiește și evaluează soluția completă.

Încarcă instanța

QOBLIB distribuie fiecare instanță MIS ca graf în formatul DIMACS .gph, un format pe linii în care linia care începe cu p indică numărul de noduri și de muchii, iar fiecare linie care începe cu e definește o muchie.

QOBLIB publică, de asemenea, o soluție de referință optimă sau cea mai bună cunoscută pentru fiecare instanță. Funcțiile următoare descarcă ambele din depozitul QOBLIB. DIMACS numerotează nodurile începând de la 1, deci graful este renumerotat să înceapă de la 0.

Dacă vrei să pornești de la propriul graf, omite descărcarea și formulează problema din graful tău NetworkX în același mod.

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)

Folosești mai târziu valoarea obiectivului soluției de referință pentru a evalua rezultatul de la SQOA Solver. Acest tutorial rezolvă problema pe un dispozitiv cu 156 de qubiți.

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

Vizualizează graful. Mai târziu, îl folosești și pentru a verifica dacă nodurile returnate de SQOA Solver formează o mulțime independentă.

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

Formulează QUBO-ul

Construiește formularea liniară binară din secțiunea Context ca un OptimizationProblem cu o variabilă binară pentru fiecare nod, un obiectiv care numără nodurile selectate și o constrângere pentru fiecare muchie. Apoi convertește-l cu OptimizationProblemToQubo.

Cu o pondere de penalizare de 2, convertorul înlocuiește fiecare constrângere de muchie cu termenul de penalizare $2 x_v x_w$ și transformă maximizarea într-o minimizare, deci problema convertită este formularea binară fără constrângeri din QOBLIB cu semnul inversat. Indicii variabilelor QUBO-ului sunt etichetele nodurilor grafului. Clasa de aplicație IndependentSet din qiskit_addon_opt_mapper.applications construiește același model cu constrângeri cu IndependentSet(G).to_optimization_problem().

În final, convertește QUBO-ul în formatul dicționar cu to_problem_dict(). Deoarece problema este un QUBO binar, cererea din Pasul 2 declară domeniul variabilelor ca "binary". Funcția efectuează presolve, maparea cuantică și construcția circuitelor după trimitere.

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

Pasul 2: Optimizează problema pentru execuția pe hardware cuantic

SQOA Solver efectuează maparea cuantică și pregătirea hardware în interiorul funcției. Mai întâi aplică presolve asupra QUBO-ului, apoi mapează variabilele rămase pe un hamiltonian relaxat folosind o codificare bazată pe QRAC.

Pentru eșantionarea cuantică, construiește circuite pe baza hamiltonianului relaxat și le transpilează pentru backend-ul selectat. Reducerile dimensiunii problemei și ale numărului de qubiți obținute din presolve și din codificare depind de problemă, așa că configurează solver-ul fără a presupune un factor de reducere fix.

Configurează intrările solver-ului

SQOA Solver necesită două intrări:

• problem, dicționarul din Pasul 1.

• variable_type, care este "binary" pentru acest QUBO.

Acceptă și două intrări opționale:

• backend_name selectează QPU-ul. Când este omis sau este None, funcția selectează QPU-ul operațional cel mai puțin aglomerat accesibil instanței tale.

• options este un dicționar care controlează bugetul de eșantionare (shots), seed-ul clasic (seed), utilizarea sesiunii (session), căutarea locală clasică (postprocessing_level) și etichetele jobului (job_tags). Dacă mărești shots, statisticile de eșantionare se pot îmbunătăți.

Pentru toate intrările, valorile lor implicite și regulile de validare, consultă referința API.

Acest tutorial numește explicit backend-ul, folosește valorile implicite pentru shots, session și postprocessing_level și setează seed-ul clasic. Adună intrările într-un dicționar pentru a le putea transmite lui solver.run() în Pasul 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,
}

Pasul 3: Execută folosind primitive

Trimite jobul cu conexiunea SQOA Solver creată în Pasul 1. Funcția rulează primitiva IBM Quantum Sampler pe backend-ul selectat, colectează șirurile de biți măsurate și continuă cu diagonalizarea clasică și post-procesarea. Interacționezi cu un singur job de funcție.

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

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

Pentru a verifica starea sarcinii de lucru, consultă Verifică starea jobului. Intern, funcția parcurge fazele de mapare, optimizare hardware, așteptare în coadă, execuție pe QPU și post-procesare.

job.status()

'INITIALIZING'

job.result() blochează până la finalizarea jobului și returnează un dicționar cu soluția, valoarea obiectivului și fezabilitatea ei, plus metadate care conțin informații despre solver și utilizarea resurselor. Pentru definiția completă a intrărilor și ieșirilor, consultă referința API.

result = job.result()

Pasul 4: Post-procesează rezultatul și convertește-l într-un format clasic

Inspectează ieșirea completă a funcției, mapează atribuirea returnată înapoi pe graf, verifică nodurile selectate și vizualizează rezultatul.

Inspectează rezultatul

Dicționarul rezultat conține patru câmpuri de nivel superior:

• solution este atribuirea completă a variabilelor, cu cheia x_i, unde i este indicele variabilei (de exemplu, x_17). În acest tutorial, indicele variabilei este eticheta nodului.

• objective_value este obiectivul acelei atribuiri evaluat pe dicționarul trimis, adică pe QUBO-ul de minimizare.

• feasible se referă doar la domeniul variabilelor, deoarece dicționarul nu are constrângeri.

• metadata conține solver_info și resource_usage. solver_info înregistrează seed-ul efectiv al rulării. Dacă a rulat căutarea locală clasică, solver_info înregistrează și atribuirea rotunjită dinaintea acelei rafinări în 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']

Mapează soluția pe graf

Adună valorile returnate în ordinea indicilor variabilelor și mapează-le înapoi pe variabilele problemei originale cu interpret(). Nodurile selectate sunt variabilele cu valoarea 1, iar is_feasible() verifică atribuirea față de constrângerile pe muchii ale problemei originale.

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

Compară cu soluția dinaintea post-procesării

Deoarece postprocessing_level este 1, solver_info înregistrează și atribuirea rotunjită dinaintea căutării locale clasice în solution_before_postprocessing. Aceasta folosește aceleași chei ca solution.

Evaluează-o pe QUBO pentru a vedea cât de mult a îmbunătățit rafinarea rezultatul. Ambele valori sunt obiective ale QUBO-ului de minimizare trimis, deci o valoare mai mică este mai bună. Câmpul este omis când căutarea locală nu rulează, de exemplu, când presolve fixează toate variabilele.

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

Verifică constrângerea de independență

Deoarece QUBO-ul reprezintă adiacența prin termeni de penalizare, nu prin constrângeri explicite, un rezultat euristic poate totuși selecta noduri adiacente. Verifică direct nodurile returnate față de graf. Pentru comparația și vizualizarea din secțiunile următoare, copiază mulțimea returnată și elimină în mod greedy un capăt al fiecărui conflict detectat.

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

Compară cu soluția de referință

În Pasul 1, ai descărcat valoarea obiectivului soluției de referință QOBLIB. Soluțiile de referință QOBLIB pot fi optime sau cele mai bune cunoscute, așa că compară cu obiectivul de referință fără a presupune că este întotdeauna un optim certificat.

Pentru această problemă de maximizare, un raport de 1.0 înseamnă că rezultatul reparat egalează obiectivul de referință.

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

Vizualizează rezultatul

Desenează din nou graful, cu mulțimea independentă reparată evidențiată. Două noduri evidențiate nu au nicio muchie comună.

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

Citește utilizarea resurselor

Metadatele rezultatului raportează CPU_TIME pentru fazele diferite de RUNNING: EXECUTING_QPU, când este disponibil. Faza RUNNING: EXECUTING_QPU poate raporta QPU_TIME, utilizarea QPU returnată de Quantum Compute, dacă utilizarea finală este disponibilă pentru fiecare 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

Concluzie

În acest tutorial ai descărcat o instanță MIS din QOBLIB, ai formulat-o ca QUBO cu qiskit-addon-opt-mapper, te-ai conectat la SQOA Solver, ai configurat și ai trimis sarcina de lucru, ai mapat înapoi pe graf atribuirea returnată și ai verificat nodurile selectate față de graful original.

Ai comparat și rezultatul cu soluția de referință QOBLIB, ai examinat contribuția post-procesării clasice și ai inspectat utilizarea resurselor în fiecare fază de execuție.

SQOA Solver combină presolve, QRAO cu o codificare bazată pe QRAC, construirea circuitelor de eșantionare, transpilarea adaptată hardware-ului, diagonalizarea bazată pe eșantioane, rotunjirea și rafinarea clasică. Acest flux de lucru poate mapa mai multe variabile binare decât ar permite o codificare cu o variabilă per qubit. Cât de mult reduc presolve și codificarea depinde de structura problemei, iar calitatea soluției depinde de eșantioanele obținute.

Setările shots și postprocessing_level controlează bugetul de eșantionare cuantică și, respectiv, rafinarea clasică, fără a modifica fluxul de trimitere.

Anexă: Trimite problema ca instanță OMMX

SQOA Solver acceptă și o ommx.v1.Instance din SDK-ul OMMX. Pachetul OMMX Quantum Benchmarks distribuie problemele QOBLIB ca instanțe OMMX, împreună cu soluțiile lor de referință, astfel încât poți încărca același QUBO fără să-l formulezi tu.

Cu o intrare OMMX, objective_value este evaluat în sensul instanței, iar rezultatul conține și ommx.v1.Solution canonic. Instalează pachetul, care instalează și SDK-ul OMMX:

# %pip install ommx-quantum-benchmarks

Încarcă modelul binary_unconstrained al aceleiași instanțe. Încărcătorul de seturi de date afișează mesaje de progres, așa că codul le captează pentru a păstra ieșirea compactă.

%%capture
from ommx_quantum_benchmarks.qoblib import IndependentSet

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

SQOA Solver primește o instanță OMMX ca șir Base64 standard cu padding și returnează soluția canonică în același format. Definește două funcții ajutătoare pentru această conversie:

• to_problem_payload() serializează o ommx.v1.Instance în șirul pe care îl transmiți ca problem.

• to_ommx_solution() decodifică ommx.v1.Solution canonic din rezultat.

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

Trimite instanța cu aceleași intrări ca înainte, înlocuind doar problem. Apoi decodifică soluția canonică și citește nodurile selectate după numele variabilei.

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

Pașii următori

Recomandări

• Aplică fluxul de lucru propriilor tale probleme QUBO. Construiește un OptimizationProblem așa cum este arătat în ghidul SQOA Solver. Pașii de conversie și trimitere rămân aceiași, dar adaptează validarea la structura problemei tale.
• Trimite problema ca instanță OMMX, așa cum este arătat în anexă. Consultă referința API pentru formatele de problemă acceptate și câmpurile returnate.
• Explorează alte instanțe de mulțime independentă în depozitul QOBLIB sau prin OMMX Quantum Benchmarks.
• Află mai multe despre modelare cu qiskit-addon-opt-mapper sau JijModeling și despre schimbul de probleme cu OMMX.

Referințe

[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