Risolvi un problema di insieme indipendente massimo con più variabili che qubit usando SQOA Solver di JIJ

nota

Le Qiskit Functions sono una funzionalità sperimentale disponibile solo per gli utenti dei piani IBM Quantum® Premium Plan, Flex Plan e On-Prem (tramite IBM Quantum Platform API). Sono in stato di rilascio in anteprima e soggette a modifiche.

Stima di utilizzo: 10 secondi su un processore Heron r2. (NOTA: si tratta solo di una stima. Il tuo tempo di esecuzione potrebbe variare.)

Contesto

Questo tutorial mostra come usare SQOA Solver, una Qiskit Function di JIJ, per risolvere un problema di insieme indipendente massimo (MIS) con più variabili binarie dei qubit della QPU selezionata. I passaggi fondamentali sono: caricare un'istanza MIS dalla Quantum Optimization Benchmarking Library (QOBLIB) [1], formularla in forma QUBO (quadratic unconstrained binary optimization) con qiskit-addon-opt-mapper, inviarla a SQOA Solver per l'esecuzione su una QPU IBM® e validare la soluzione restituita.

Il problema dell'insieme indipendente massimo

Un insieme indipendente è un sottoinsieme di nodi di un grafo tale che due nodi selezionati qualsiasi non condividono un arco. Un insieme indipendente massimo (MIS) è un insieme indipendente con il maggior numero possibile di nodi. Le applicazioni del MIS includono la pianificazione, l'allocazione delle risorse e la progettazione di reti.

Il MIS è NP-hard. In una ricerca esaustiva ogni nodo aggiuntivo raddoppia il numero di sottoinsiemi da considerare, quindi questo approccio è impraticabile anche per grafi di dimensioni moderate. QOBLIB include il MIS come una delle sue dieci classi di problemi, quindi è un benchmark utile per valutare i flussi di lavoro di ottimizzazione quantistica su hardware reale.

Formulazione matematica

Dato un grafo non orientato $G = (V, E)$, assegna una variabile binaria $x_v$ a ciascun nodo $v$:

• $x_v = 1$ se il nodo $v$ è selezionato.

• $x_v = 0$ otherwise.

La formulazione lineare binaria massimizza il numero di nodi selezionati impedendo che entrambi gli estremi di un arco siano selezionati:

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

La funzione obiettivo conta i nodi selezionati. Insieme, i vincoli sugli archi garantiscono che i nodi selezionati formino un insieme indipendente.

Questo tutorial usa la formulazione binaria non vincolata di QOBLIB, che sostituisce i vincoli sugli archi con penalità quadratiche:

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

Ogni volta che entrambi gli estremi di un arco sono selezionati, il secondo termine sottrae due dalla funzione obiettivo. Questa penalità rende una selezione in conflitto meno favorevole rispetto a mantenere solo uno dei due estremi. La funzione obiettivo risultante è un QUBO, che è il formato di input accettato da SQOA Solver.

Perché usare SQOA Solver?

Molti approcci di ottimizzazione quantistica assegnano un qubit a ogni variabile binaria, quindi la capacità dell'hardware quantistico può limitare direttamente la dimensione del problema. SQOA Solver combina diverse tecniche di riduzione e di calcolo ibrido per attenuare questa restrizione:

• Può affrontare problemi con più variabili binarie dei qubit della QPU. Il presolve applica regole di riduzione che possono fissare variabili e semplificare il QUBO rimanente preservando almeno una soluzione ottimale. Empiricamente, il presolve può anche rendere il QUBO rimanente più sparso, il che aiuta la codifica basata su QRAC che lo segue.

  Il solver usa poi una codifica basata su QRAC derivata dalla Quantum Random Access Optimization (QRAO) [3] per rappresentare sullo stesso qubit più variabili (fino a tre) prive di interazione QUBO diretta.

  Le riduzioni dovute a presolve e codifica dipendono dalla struttura del problema. Per esempio, in questo tutorial un problema con 200 variabili usa solo 67 qubit.

• Può essere meno sensibile al rumore dell'hardware. La diagonalizzazione quantistica basata su campioni [4], [5] usa la QPU per campionare stringhe di bit ma esegue la diagonalizzazione in modo classico. Questo evita ripetute valutazioni sulla QPU per l'aggiornamento dei parametri variazionali e può ridurre l'impatto del rumore sul flusso di lavoro di ottimizzazione.

• Automatizza il flusso di lavoro dal presolve al post-processing. Fornisci un'istanza QUBO formattata correttamente e selezioni un backend. SQOA Solver esegue poi automaticamente l'intero flusso di lavoro. Applica il presolve, mappa le variabili classiche su un problema quantistico rilassato, costruisce e traspila i circuiti di campionamento, esegue il campionamento quantistico e la diagonalizzazione classica, arrotonda e perfeziona l'assegnazione, e ricostruisce e valuta la soluzione classica.

Requisiti

Prima di iniziare questo tutorial, assicurati di avere installato i seguenti pacchetti:

• Client del catalogo delle Qiskit Functions (pip install qiskit-ibm-catalog).

• Qiskit addon optimization mapper, usato per formulare il problema (pip install qiskit-addon-opt-mapper).

• NetworkX e Matplotlib, usati per gestire e rappresentare il grafo (pip install networkx matplotlib).

Ti serve inoltre l'accesso a SQOA Solver dal catalogo delle Qiskit Functions. Compila il modulo per richiedere l'accesso alla funzione.

# 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

Configurazione

Per prima cosa, importa i pacchetti e gli strumenti necessari.

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 accetta un problema QUBO come dizionario di coefficienti nel formato tupla-stringa usato dalle funzioni di ottimizzazione di IBM®. Definisci una funzione di supporto che converte il QUBO restituito da OptimizationProblemToQubo in questo formato.

Il convertitore restituisce sempre un problema di minimizzazione, che corrisponde a come SQOA Solver tratta un problema in forma di dizionario. Le chiavi usano gli indici delle variabili del QUBO e ogni variabile riceve una voce lineare, anche con coefficiente zero, in modo che la soluzione restituita copra tutte le variabili.

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

Passaggio 1: Mappare gli input classici su un problema quantistico

SQOA Solver accetta un problema QUBO ed esegue la mappatura quantistica all'interno della funzione. In questo tutorial scarichi un'istanza MIS da QOBLIB e la formuli come QUBO con qiskit-addon-opt-mapper. Questo passaggio comprende quanto segue:

• Connettersi a SQOA Solver.

• Comprendere il framework SQOA.

• Caricare l'istanza del problema.

• Formulare il QUBO e convertirlo per l'invio.

Connettersi a SQOA Solver

Connettiti al catalogo delle Qiskit Functions con le tue credenziali di IBM Quantum Platform, poi carica SQOA Solver. Il codice seguente presuppone che tu abbia già salvato il tuo account nel tuo ambiente locale.

Se la connessione non riesce, verifica che l'amministratore del tuo account IBM Quantum Platform abbia concesso all'istanza di servizio selezionata l'accesso a SQOA Solver.

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

Comprendere il framework SQOA

Il Sampling-based Quantum Optimization Algorithm with Quantum Relaxation (SQOA-QR) [2] combina la Quantum Random Access Optimization (QRAO) con la diagonalizzazione quantistica basata su campioni:

1. Rilassamento quantistico e codifica: SQOA Solver converte il QUBO in una funzione obiettivo di Ising da minimizzare della forma $c + \sum_i h_i z_i + \sum_{i<j} J_{ij} z_i z_j$, dove $z_i \in \{-1, +1\}$. La QRAO [3] mappa poi ogni variabile di spin su un'osservabile di Pauli. Per la codifica $(3,1)$-QRAC usata qui, l'Hamiltoniana rilassata è

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

   dove $I$ è l'operatore identità, $f(i)$ assegna la variabile $i$ a un qubit e a uno tra $X$, $Y$ o $Z$, e $k_i \in \{1,2,3\}$ è il numero di variabili mappate sullo stesso qubit di $i$. Quando entrambi i qubit interessati contengono tre variabili, i fattori di scala lineare e quadratico diventano rispettivamente $\sqrt{3}$ e $3$.

   Alle variabili che condividono un qubit vengono assegnate osservabili di Pauli diverse e non commutanti. Le variabili che interagiscono nel QUBO sono mantenute su qubit diversi, mentre le variabili senza interazione QUBO diretta possono condividere un qubit. La riduzione del numero di qubit dipende quindi dalla struttura del problema.

2. Campionamento quantistico: Un processore quantistico campiona stringhe di bit da circuiti progettati per esplorare stati a bassa energia dell'Hamiltoniana rilassata.

3. Diagonalizzazione basata su campioni: Il solver proietta l'Hamiltoniana rilassata sul sottospazio generato dagli stati di base ottenuti dalle stringhe di bit campionate e diagonalizza in modo classico l'Hamiltoniana proiettata [4], [5]. Per un insieme fisso di stringhe di bit campionate, sia $\mathcal{S}_r$ il sottospazio generato da $r$ stati di base distinti, quindi $\dim(\mathcal{S}_r) \leq r$. La sua energia dello stato fondamentale stimata è:

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

   dove $E_{\mathrm{exact}}$ è l'energia dello stato fondamentale dell'intera Hamiltoniana rilassata. Pertanto, un sottospazio mantenuto più grande non può aumentare l'energia dello stato fondamentale stimata.

   Questo ordinamento presuppone lo stesso risultato di campionamento e riguarda l'energia dell'Hamiltoniana rilassata prima dell'arrotondamento. Non garantisce teoricamente una soluzione classica restituita migliore. Tuttavia, nella QRAO, ci si aspetta euristicamente che uno stato a energia più bassa fornisca una soluzione classica migliore.

4. Arrotondamento: Lo stato rilassato ottenuto dalla diagonalizzazione viene convertito in un'assegnazione binaria classica.

SQOA Solver circonda questo framework con elaborazione classica. Prima della mappatura quantistica, il presolve applica regole di riduzione che possono fissare variabili e semplificare il QUBO rimanente preservando almeno una soluzione ottimale. Dopo la diagonalizzazione e l'arrotondamento, una ricerca locale classica perfeziona l'assegnazione e OMMX ricostruisce e valuta la soluzione completa.

Carica l'istanza

QOBLIB distribuisce ogni istanza MIS come grafo nel formato DIMACS .gph, un formato basato su righe in cui la riga che inizia con p indica il numero di nodi e di archi e ogni riga che inizia con e definisce un arco.

QOBLIB pubblica anche una soluzione di riferimento ottimale o la migliore nota per ogni istanza. Le funzioni seguenti scaricano entrambe dal repository QOBLIB. DIMACS numera i nodi a partire da 1, quindi il grafo viene rietichettato per iniziare da 0.

Se preferisci partire da un tuo grafo, salta il download e formula il problema dal tuo grafo NetworkX allo stesso modo.

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)

Userai più avanti il valore della funzione obiettivo della soluzione di riferimento per valutare il risultato di SQOA Solver. Questo tutorial risolve il problema su un dispositivo con 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

Visualizza il grafo. Più avanti lo userai anche per verificare che i nodi restituiti da SQOA Solver formino un insieme indipendente.

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

Formula il QUBO

Costruisci la formulazione lineare binaria della sezione Contesto come OptimizationProblem con una variabile binaria per nodo, una funzione obiettivo che conta i nodi selezionati e un vincolo per arco. Poi convertila con OptimizationProblemToQubo.

Con un peso di penalità pari a 2, il convertitore sostituisce ogni vincolo sugli archi con il termine di penalità $2 x_v x_w$ e trasforma la massimizzazione in una minimizzazione, quindi il problema convertito è la formulazione binaria non vincolata di QOBLIB con il segno invertito. Gli indici delle variabili del QUBO sono le etichette dei nodi del grafo. La classe applicativa IndependentSet in qiskit_addon_opt_mapper.applications costruisce lo stesso modello vincolato con IndependentSet(G).to_optimization_problem().

Infine, converti il QUBO nel formato dizionario con to_problem_dict(). Poiché il problema è un QUBO binario, la richiesta nel Passaggio 2 dichiara il suo dominio delle variabili come "binary". La funzione esegue il presolve, la mappatura quantistica e la costruzione dei circuiti dopo l'invio.

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

Passaggio 2: Ottimizzare il problema per l'esecuzione su hardware quantistico

SQOA Solver esegue la mappatura quantistica e la preparazione dell'hardware all'interno della funzione. Applica prima il presolve al QUBO, poi mappa le variabili rimanenti su un'Hamiltoniana rilassata usando una codifica basata su QRAC.

Per il campionamento quantistico, costruisce circuiti basati sull'Hamiltoniana rilassata e li traspila per il backend selezionato. Le riduzioni della dimensione del problema e dei qubit dovute a presolve e codifica dipendono dal problema, quindi configura il solver senza presupporre un fattore di riduzione fisso.

Configura gli input del solver

SQOA Solver richiede due input:

• problem, il dizionario del Passaggio 1.

• variable_type, che è "binary" per questo QUBO.

Accetta inoltre due input opzionali:

• backend_name seleziona la QPU. Quando viene omesso o è None, la funzione seleziona la QPU operativa meno occupata accessibile alla tua istanza.

• options è un dizionario che controlla il budget di campionamento (shots), il seed classico (seed), l'uso della sessione (session), la ricerca locale classica (postprocessing_level) e i tag del job (job_tags). Se aumenti shots, le statistiche di campionamento possono migliorare.

Per tutti gli input, i loro valori predefiniti e le regole di validazione, consulta il riferimento API.

Questo tutorial indica esplicitamente il backend, usa i valori predefiniti per shots, session e postprocessing_level e imposta il seed classico. Raccogli gli input in un dizionario in modo da poterli passare a solver.run() nel Passaggio 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,
}

Passaggio 3: Eseguire usando le primitive

Invia il job con la connessione a SQOA Solver creata nel Passaggio 1. La funzione esegue la primitiva IBM Quantum Sampler sul backend selezionato, raccoglie le stringhe di bit misurate e prosegue con la diagonalizzazione classica e il post-processing. Interagisci con un unico job della funzione.

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

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

Per controllare lo stato del carico di lavoro, consulta Controllare lo stato del job. Internamente, la funzione attraversa le fasi di mappatura, ottimizzazione per l'hardware, attesa in coda, esecuzione sulla QPU e post-processing.

job.status()

'INITIALIZING'

job.result() si blocca fino al completamento del job e restituisce un dizionario con la soluzione, il suo valore della funzione obiettivo e l'ammissibilità, e i metadati che contengono le informazioni sul solver e l'utilizzo delle risorse. Per la definizione completa di input e output, consulta il riferimento API.

result = job.result()

Passaggio 4: Eseguire il post-processing del risultato e convertirlo in un formato classico

Ispeziona l'output completo della funzione, mappa l'assegnazione restituita sul grafo, verifica i nodi selezionati e visualizza il risultato.

Ispeziona il risultato

Il dizionario del risultato contiene quattro campi di primo livello:

• solution è l'assegnazione completa delle variabili, con chiavi x_i, dove i è l'indice della variabile (per esempio, x_17). In questo tutorial l'indice della variabile è l'etichetta del nodo.

• objective_value è il valore della funzione obiettivo di quell'assegnazione valutato sul dizionario inviato, cioè sul QUBO di minimizzazione.

• feasible si riferisce solo al dominio delle variabili, perché il dizionario non ha vincoli.

• metadata contiene solver_info e resource_usage. solver_info registra il seed effettivo dell'esecuzione. Se la ricerca locale classica è stata eseguita, solver_info registra anche l'assegnazione arrotondata precedente a quel perfezionamento in 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']

Mappa la soluzione sul grafo

Raccogli i valori restituiti nell'ordine degli indici delle variabili e mappali di nuovo sulle variabili del problema originale con interpret(). I nodi selezionati sono le variabili con valore 1 e is_feasible() verifica l'assegnazione rispetto ai vincoli sugli archi del problema 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

Confronta con la soluzione prima del post-processing

Poiché postprocessing_level è 1, solver_info registra anche l'assegnazione arrotondata precedente alla ricerca locale classica in solution_before_postprocessing. Usa le stesse chiavi di solution.

Valutala sul QUBO per vedere quanto il perfezionamento abbia migliorato il risultato. Entrambi i valori sono valori della funzione obiettivo del QUBO di minimizzazione inviato, quindi un valore più basso è migliore. Il campo viene omesso quando la ricerca locale non viene eseguita, per esempio quando il presolve fissa ogni variabile.

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

Verifica il vincolo di indipendenza

Poiché il QUBO rappresenta l'adiacenza tramite termini di penalità anziché vincoli espliciti, un risultato euristico può comunque selezionare nodi adiacenti. Controlla direttamente i nodi restituiti rispetto al grafo. Per il confronto e la visualizzazione nelle sezioni seguenti, copia l'insieme restituito e rimuovi in modo greedy un estremo di ciascun conflitto rilevato.

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

Confronta con la soluzione di riferimento

Nel Passaggio 1 hai scaricato il valore della funzione obiettivo della soluzione di riferimento di QOBLIB. Le soluzioni di riferimento di QOBLIB possono essere ottimali o le migliori note, quindi confronta con la funzione obiettivo di riferimento senza presupporre che sia sempre un ottimo certificato.

Per questo problema di massimizzazione, un rapporto di 1.0 significa che il risultato riparato corrisponde alla funzione obiettivo di riferimento.

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

Visualizza il risultato

Rappresenta di nuovo il grafo con l'insieme indipendente riparato evidenziato. Due nodi evidenziati qualsiasi non condividono un arco.

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

Leggi l'utilizzo delle risorse

I metadati del risultato riportano CPU_TIME per le fasi diverse da RUNNING: EXECUTING_QPU, quando è disponibile. La fase RUNNING: EXECUTING_QPU può riportare QPU_TIME, l'utilizzo della QPU restituito da Quantum Compute, se l'utilizzo finale è disponibile per ogni job di 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

Conclusione

In questo tutorial hai scaricato un'istanza MIS da QOBLIB, l'hai formulata come QUBO con qiskit-addon-opt-mapper, ti sei connesso a SQOA Solver, hai configurato e inviato il carico di lavoro, hai mappato l'assegnazione restituita sul grafo e hai controllato i nodi selezionati rispetto al grafo originale.

Hai inoltre confrontato il risultato con la soluzione di riferimento di QOBLIB, esaminato il contributo del post-processing classico e ispezionato l'utilizzo delle risorse di ogni fase di esecuzione.

SQOA Solver combina presolve, QRAO con una codifica basata su QRAC, costruzione dei circuiti di campionamento, transpilazione consapevole dell'hardware, diagonalizzazione basata su campioni, arrotondamento e perfezionamento classico. Questo flusso di lavoro può mappare più variabili binarie di quante ne consentirebbe una codifica con una variabile per qubit. L'entità della riduzione dovuta a presolve e codifica dipende dalla struttura del problema, e la qualità della soluzione dipende dai campioni ottenuti.

Le impostazioni shots e postprocessing_level controllano rispettivamente il budget di campionamento quantistico e il perfezionamento classico, senza modificare il flusso di lavoro di invio.

Appendice: Inviare il problema come istanza OMMX

SQOA Solver accetta anche un ommx.v1.Instance dall'SDK OMMX. Il pacchetto OMMX Quantum Benchmarks distribuisce i problemi QOBLIB come istanze OMMX insieme alle relative soluzioni di riferimento, così puoi caricare lo stesso QUBO senza doverlo formulare tu stesso.

Con un input OMMX, objective_value viene valutato nel senso dell'istanza e il risultato contiene anche la ommx.v1.Solution canonica. Installa il pacchetto, che installa anche l'SDK OMMX:

# %pip install ommx-quantum-benchmarks

Carica il modello binary_unconstrained della stessa istanza. Il loader del dataset stampa messaggi di avanzamento, quindi il codice li cattura per mantenere compatto l'output.

%%capture
from ommx_quantum_benchmarks.qoblib import IndependentSet

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

SQOA Solver riceve un'istanza OMMX come stringa Base64 standard con padding e restituisce la soluzione canonica nello stesso formato. Definisci due funzioni di supporto per questa conversione:

• to_problem_payload() serializza un ommx.v1.Instance nella stringa che passi come problem.

• to_ommx_solution() decodifica la ommx.v1.Solution canonica dal risultato.

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

Invia l'istanza con gli stessi input di prima, sostituendo solo problem. Poi decodifica la soluzione canonica e leggi i nodi selezionati per nome di variabile.

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

Prossimi passi

Raccomandazioni

• Applica il workflow ai tuoi problemi QUBO. Costruisci un OptimizationProblem come mostrato nella guida a SQOA Solver. I passaggi di conversione e invio restano gli stessi, ma adatta la validazione alla struttura del tuo problema.
• Invia il problema come istanza OMMX, come mostrato nell'appendice. Consulta il riferimento API per i formati di problema accettati e i campi restituiti.
• Esplora altre istanze di independent set nel repository QOBLIB o tramite OMMX Quantum Benchmarks.
• Approfondisci la modellazione con qiskit-addon-opt-mapper o JijModeling e lo scambio di problemi con OMMX.

Riferimenti

[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