Ein Maximum-Independent-Set-Problem mit mehr Variablen als Qubits mit dem SQOA Solver von JIJ lösen

hinweis

Qiskit Functions sind eine experimentelle Funktion, die nur Nutzern des IBM Quantum® Premium Plan, Flex Plan und On-Prem (über die IBM Quantum Platform API) Plan zur Verfügung steht. Sie befinden sich im Preview-Status und können sich ändern.

Geschätzte Nutzung: 10 Sekunden auf einem Heron-r2-Prozessor. (HINWEIS: Dies ist nur eine Schätzung. Deine Laufzeit kann abweichen.)

Hintergrund

Dieses Tutorial zeigt, wie du den SQOA Solver, eine Qiskit Function von JIJ, verwendest, um ein Maximum-Independent-Set-Problem (MIS) mit mehr binären Variablen zu lösen, als die gewählte QPU Qubits hat. Die grundlegenden Schritte sind: eine MIS-Instanz aus der Quantum Optimization Benchmarking Library (QOBLIB) [1] laden, sie mit qiskit-addon-opt-mapper in die Form der quadratischen unbeschränkten binären Optimierung (QUBO) bringen, sie zur Ausführung auf einer IBM® QPU an den SQOA Solver senden und die zurückgegebene Lösung validieren.

Das Maximum-Independent-Set-Problem

Eine unabhängige Menge ist eine Teilmenge von Knoten eines Graphen, sodass keine zwei ausgewählten Knoten eine Kante teilen. Eine maximale unabhängige Menge (Maximum Independent Set, MIS) ist eine unabhängige Menge mit der größtmöglichen Knotenzahl. Anwendungen von MIS sind unter anderem Scheduling, Ressourcenzuteilung und Netzwerkdesign.

MIS ist NP-schwer. Bei einer erschöpfenden Suche verdoppelt jeder zusätzliche Knoten die Zahl der zu betrachtenden Teilmengen, sodass dieser Ansatz schon für mittelgroße Graphen unpraktikabel ist. QOBLIB enthält MIS als eine seiner zehn Problemklassen und ist daher ein nützlicher Benchmark, um Workflows der Quantenoptimierung auf echter Hardware zu bewerten.

Mathematische Formulierung

Weise für einen ungerichteten Graphen $G = (V, E)$ jedem Knoten $v$ eine binäre Variable $x_v$ zu:

• $x_v = 1$, wenn Knoten $v$ ausgewählt ist.

• $x_v = 0$ otherwise.

Die binäre lineare Formulierung maximiert die Zahl der ausgewählten Knoten und verhindert zugleich, dass beide Endpunkte einer Kante ausgewählt werden:

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

Die Zielfunktion zählt die ausgewählten Knoten. Zusammen stellen die Kantenbedingungen sicher, dass die ausgewählten Knoten eine unabhängige Menge bilden.

Dieses Tutorial verwendet die binäre unbeschränkte Formulierung von QOBLIB, die die Kantenbedingungen durch quadratische Strafterme ersetzt:

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

Immer wenn beide Endpunkte einer Kante ausgewählt sind, zieht der zweite Term zwei von der Zielfunktion ab. Dieser Strafterm macht eine widersprüchliche Auswahl ungünstiger, als nur einen der beiden Endpunkte zu behalten. Die resultierende Zielfunktion ist ein QUBO, das Eingabeformat, das der SQOA Solver akzeptiert.

Warum den SQOA Solver verwenden?

Viele Ansätze der Quantenoptimierung weisen jeder binären Variable ein Qubit zu, sodass die Kapazität der Quantenhardware die Problemgröße direkt begrenzen kann. Der SQOA Solver kombiniert mehrere Reduktions- und Hybrid-Computing-Techniken, um diese Einschränkung abzumildern:

• Er kann Probleme mit mehr binären Variablen angehen, als die QPU Qubits hat. Presolve wendet Reduktionsregeln an, die Variablen fixieren und das verbleibende QUBO vereinfachen können, während mindestens eine optimale Lösung erhalten bleibt. Empirisch kann Presolve das verbleibende QUBO auch dünner besetzt machen, was der darauf folgenden QRAC-basierten Kodierung hilft.

  Der Solver verwendet dann eine QRAC-basierte Kodierung, die aus Quantum Random Access Optimization (QRAO) [3] abgeleitet ist, um mehrere Variablen (bis zu drei) ohne direkte QUBO-Wechselwirkung auf demselben Qubit darzustellen.

  Die Reduktionen durch Presolve und Kodierung hängen von der Problemstruktur ab. In diesem Tutorial verwendet beispielsweise ein Problem mit 200 Variablen nur 67 Qubits.

• Er kann weniger empfindlich gegenüber Hardwarerauschen sein. Die samplebasierte Quantendiagonalisierung [4], [5] verwendet die QPU, um Bitstrings zu samplen, führt die Diagonalisierung aber klassisch durch. Das vermeidet wiederholte QPU-Auswertungen für Aktualisierungen variationeller Parameter und kann den Einfluss von Rauschen auf den Optimierungs-Workflow verringern.

• Er automatisiert den Workflow von Presolve bis zur Nachbearbeitung. Du stellst eine korrekt formatierte QUBO-Instanz bereit und wählst ein Backend. Der SQOA Solver führt dann den gesamten Workflow automatisch aus. Er wendet Presolve an, bildet die klassischen Variablen auf ein relaxiertes Quantenproblem ab, konstruiert und transpiliert die Sampling-Circuits, führt das Quantensampling und die klassische Diagonalisierung durch, rundet und verfeinert die Zuweisung und rekonstruiert und bewertet die klassische Lösung.

Voraussetzungen

Stelle vor dem Start dieses Tutorials sicher, dass die folgenden Pakete installiert sind:

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

• Qiskit-Addon Optimization Mapper, zur Formulierung des Problems (pip install qiskit-addon-opt-mapper).

• NetworkX und Matplotlib, zur Verarbeitung und Darstellung des Graphen (pip install networkx matplotlib).

Außerdem benötigst du Zugriff auf den SQOA Solver aus dem Qiskit Functions Catalog. Fülle das Formular aus, um Zugriff auf die Function anzufordern.

# 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

Einrichtung

Importiere zunächst die erforderlichen Pakete und Werkzeuge.

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

Der SQOA Solver akzeptiert ein QUBO-Problem als Koeffizienten-Dictionary im Tupel-String-Format, das von IBM® Optimierungsfunktionen verwendet wird. Definiere eine Hilfsfunktion, die das von OptimizationProblemToQubo zurückgegebene QUBO in dieses Format umwandelt.

Der Konverter liefert immer ein Minimierungsproblem, was der Art entspricht, wie der SQOA Solver ein Dictionary-Problem behandelt. Die Schlüssel verwenden die Variablenindizes des QUBO, und jede Variable erhält einen linearen Eintrag, auch mit Koeffizient null, damit die zurückgegebene Lösung alle Variablen abdeckt.

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

Schritt 1: Klassische Eingaben auf ein Quantenproblem abbilden

Der SQOA Solver akzeptiert ein QUBO-Problem und führt die Quantenabbildung innerhalb der Function durch. In diesem Tutorial lädst du eine MIS-Instanz aus QOBLIB herunter und formulierst sie mit qiskit-addon-opt-mapper als QUBO. Dieser Schritt umfasst Folgendes:

• Mit dem SQOA Solver verbinden.

• Das SQOA-Framework verstehen.

• Die Probleminstanz laden.

• Das QUBO formulieren und für die Übermittlung konvertieren.

Mit dem SQOA Solver verbinden

Verbinde dich mit deinen IBM Quantum Platform-Zugangsdaten mit dem Qiskit Functions Catalog und lade dann den SQOA Solver. Der folgende Code setzt voraus, dass du dein Konto bereits in deiner lokalen Umgebung gespeichert hast.

Wenn die Verbindung fehlschlägt, vergewissere dich, dass der Administrator deines IBM Quantum Platform-Kontos der gewählten Service-Instanz Zugriff auf den SQOA Solver gewährt hat.

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

Das SQOA-Framework verstehen

Der Sampling-based Quantum Optimization Algorithm with Quantum Relaxation (SQOA-QR) [2] kombiniert Quantum Random Access Optimization (QRAO) mit samplebasierter Quantendiagonalisierung:

1. Quantenrelaxation und Kodierung: Der SQOA Solver wandelt das QUBO in eine Ising-Minimierungszielfunktion der Form $c + \sum_i h_i z_i + \sum_{i<j} J_{ij} z_i z_j$ um, wobei $z_i \in \{-1, +1\}$. QRAO [3] bildet dann jede Spinvariable auf eine Pauli-Observable ab. Für die hier verwendete $(3,1)$-QRAC-Kodierung lautet der relaxierte Hamiltonoperator

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

   wobei $I$ der Identitätsoperator ist, $f(i)$ die Variable $i$ einem Qubit und einem von $X$, $Y$ oder $Z$ zuweist und $k_i \in \{1,2,3\}$ die Zahl der Variablen ist, die demselben Qubit wie $i$ zugeordnet sind. Wenn beide betroffenen Qubits drei Variablen enthalten, werden die linearen und quadratischen Skalierungsfaktoren zu $\sqrt{3}$ beziehungsweise $3$.

   Variablen, die sich ein Qubit teilen, werden unterschiedlichen nichtkommutierenden Pauli-Observablen zugewiesen. Variablen, die im QUBO wechselwirken, werden auf verschiedenen Qubits gehalten, während Variablen ohne direkte QUBO-Wechselwirkung sich ein Qubit teilen können. Die Verringerung der Qubit-Zahl hängt daher von der Struktur des Problems ab.

2. Quantensampling: Ein Quantenprozessor sampelt Bitstrings aus Circuits, die darauf ausgelegt sind, energiearme Zustände des relaxierten Hamiltonoperators zu erkunden.

3. Samplebasierte Diagonalisierung: Der Solver projiziert den relaxierten Hamiltonoperator auf den Unterraum, der von den aus den gesampelten Bitstrings gewonnenen Basiszuständen aufgespannt wird, und diagonalisiert den projizierten Hamiltonoperator klassisch [4], [5]. Sei für eine feste Menge gesampelter Bitstrings $\mathcal{S}_r$ der von $r$ verschiedenen Basiszuständen aufgespannte Unterraum, sodass $\dim(\mathcal{S}_r) \leq r$. Seine geschätzte Grundzustandsenergie ist:

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

   wobei $E_{\mathrm{exact}}$ die Grundzustandsenergie des vollständigen relaxierten Hamiltonoperators ist. Ein größerer beibehaltener Unterraum kann die geschätzte Grundzustandsenergie daher nicht erhöhen.

   Diese Ordnung setzt dasselbe Sampling-Ergebnis voraus und betrifft die Energie des relaxierten Hamiltonoperators vor dem Runden. Sie garantiert theoretisch keine bessere zurückgegebene klassische Lösung. In QRAO wird jedoch heuristisch erwartet, dass ein Zustand mit niedrigerer Energie eine bessere klassische Lösung liefert.

4. Runden: Der aus der Diagonalisierung gewonnene relaxierte Zustand wird in eine klassische binäre Zuweisung umgewandelt.

Der SQOA Solver umgibt dieses Framework mit klassischer Verarbeitung. Vor der Quantenabbildung wendet Presolve Reduktionsregeln an, die Variablen fixieren und das verbleibende QUBO vereinfachen können, während mindestens eine optimale Lösung erhalten bleibt. Nach der Diagonalisierung und dem Runden verfeinert eine klassische lokale Suche die Zuweisung, und OMMX rekonstruiert und bewertet die vollständige Lösung.

Die Instanz laden

QOBLIB stellt jede MIS-Instanz als Graph im DIMACS-Format .gph bereit, einem zeilenbasierten Format, in dem die mit p beginnende Zeile die Anzahl der Knoten und Kanten angibt und jede mit e beginnende Zeile eine Kante definiert.

QOBLIB veröffentlicht außerdem für jede Instanz eine optimale oder bestbekannte Referenzlösung. Die folgenden Funktionen laden beides aus dem QOBLIB-Repository herunter. DIMACS nummeriert Knoten ab 1, daher wird der Graph so umbenannt, dass er bei 0 beginnt.

Wenn du stattdessen mit einem eigenen Graphen beginnen möchtest, überspringe den Download und formuliere das Problem auf dieselbe Weise aus deinem NetworkX-Graphen.

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)

Den Zielfunktionswert der Referenzlösung verwendest du später, um das Ergebnis des SQOA Solver zu bewerten. Dieses Tutorial löst dieses Problem auf einem Gerät mit 156 Qubits.

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

Visualisiere den Graphen. Später verwendest du ihn auch, um zu überprüfen, dass die vom SQOA Solver zurückgegebenen Knoten eine unabhängige Menge bilden.

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

Das QUBO formulieren

Baue die binäre lineare Formulierung aus dem Abschnitt Hintergrund als OptimizationProblem auf, mit einer binären Variable pro Knoten, einer Zielfunktion, die die ausgewählten Knoten zählt, und einer Bedingung pro Kante. Konvertiere sie dann mit OptimizationProblemToQubo.

Mit einem Strafgewicht von 2 ersetzt der Konverter jede Kantenbedingung durch den Strafterm $2 x_v x_w$ und macht aus der Maximierung eine Minimierung, sodass das konvertierte Problem die binäre unbeschränkte Formulierung von QOBLIB mit umgekehrtem Vorzeichen ist. Die Variablenindizes des QUBO sind die Knotenbezeichnungen des Graphen. Die Anwendungsklasse IndependentSet in qiskit_addon_opt_mapper.applications baut mit IndependentSet(G).to_optimization_problem() dasselbe beschränkte Modell auf.

Konvertiere das QUBO schließlich mit to_problem_dict() in das Dictionary-Format. Da das Problem ein binäres QUBO ist, deklariert die Anfrage in Schritt 2 seinen Variablenbereich als "binary". Die Function führt nach der Übermittlung Presolve, die Quantenabbildung und die Circuit-Konstruktion durch.

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

Schritt 2: Das Problem für die Ausführung auf Quantenhardware optimieren

Der SQOA Solver führt die Quantenabbildung und die Hardwarevorbereitung innerhalb der Function durch. Er wendet zunächst Presolve auf das QUBO an und bildet dann die verbleibenden Variablen mithilfe einer QRAC-basierten Kodierung auf einen relaxierten Hamiltonoperator ab.

Für das Quantensampling konstruiert er Circuits auf Basis des relaxierten Hamiltonoperators und transpiliert sie für das gewählte Backend. Die Verringerung von Problemgröße und Qubit-Zahl durch Presolve und Kodierung hängt vom Problem ab, konfiguriere den Solver also, ohne einen festen Reduktionsfaktor anzunehmen.

Die Solver-Eingaben konfigurieren

Der SQOA Solver benötigt zwei Eingaben:

• problem, das Dictionary aus Schritt 1.

• variable_type, das für dieses QUBO "binary" ist.

Er akzeptiert außerdem zwei optionale Eingaben:

• backend_name wählt die QPU aus. Wenn der Parameter weggelassen wird oder None ist, wählt die Function die am wenigsten ausgelastete betriebsbereite QPU, auf die deine Instanz zugreifen kann.

• options ist ein Dictionary, das das Sampling-Budget (shots), den klassischen Seed (seed), die Session-Nutzung (session), die klassische lokale Suche (postprocessing_level) und Job-Tags (job_tags) steuert. Wenn du shots erhöhst, kann sich die Sampling-Statistik verbessern.

Alle Eingaben, ihre Standardwerte und Validierungsregeln findest du in der API-Referenz.

Dieses Tutorial benennt das Backend explizit, verwendet die Standardwerte für shots, session und postprocessing_level und setzt den klassischen Seed. Fasse die Eingaben in einem Dictionary zusammen, damit du sie in Schritt 3 an solver.run() übergeben kannst.

# 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,
}

Schritt 3: Mit Primitives ausführen

Sende den Job mit der in Schritt 1 erstellten SQOA-Solver-Verbindung ab. Die Function führt das IBM Quantum Sampler-Primitive auf dem gewählten Backend aus, sammelt die gemessenen Bitstrings und fährt mit der klassischen Diagonalisierung und Nachbearbeitung fort. Du interagierst mit einem einzigen Function-Job.

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

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

Informationen zum Prüfen des Status der Workload findest du unter Jobstatus prüfen. Intern durchläuft die Function die Phasen Abbildung, Hardwareoptimierung, Warten in der Warteschlange, QPU-Ausführung und Nachbearbeitung.

job.status()

'INITIALIZING'

job.result() blockiert, bis der Job abgeschlossen ist, und gibt ein Dictionary mit der Lösung, ihrem Zielfunktionswert und ihrer Zulässigkeit sowie Metadaten mit Solver-Informationen und Ressourcennutzung zurück. Die vollständige Definition der Eingaben und Ausgaben findest du in der API-Referenz.

result = job.result()

Schritt 4: Das Ergebnis nachbearbeiten und in ein klassisches Format konvertieren

Untersuche die vollständige Ausgabe der Function, bilde die zurückgegebene Zuweisung wieder auf den Graphen ab, überprüfe die ausgewählten Knoten und visualisiere das Ergebnis.

Das Ergebnis untersuchen

Das Ergebnis-Dictionary enthält vier Felder der obersten Ebene:

• solution ist die vollständige Variablenzuweisung, indiziert mit x_i, wobei i der Variablenindex ist (zum Beispiel x_17). In diesem Tutorial ist der Variablenindex die Knotenbezeichnung.

• objective_value ist der Zielfunktionswert dieser Zuweisung, ausgewertet auf dem übermittelten Dictionary, also auf dem Minimierungs-QUBO.

• feasible bezieht sich nur auf den Variablenbereich, da das Dictionary keine Bedingungen enthält.

• metadata enthält solver_info und resource_usage. solver_info hält den effektiven seed des Laufs fest. Wenn die klassische lokale Suche lief, hält solver_info in solution_before_postprocessing außerdem die gerundete Zuweisung vor dieser Verfeinerung fest.

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']

Die Lösung auf den Graphen abbilden

Sammle die zurückgegebenen Werte in der Reihenfolge der Variablenindizes und bilde sie mit interpret() wieder auf die Variablen des ursprünglichen Problems ab. Die ausgewählten Knoten sind die Variablen mit dem Wert 1, und is_feasible() prüft die Zuweisung gegen die Kantenbedingungen des ursprünglichen Problems.

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

Mit der Lösung vor der Nachbearbeitung vergleichen

Da postprocessing_level den Wert 1 hat, hält solver_info in solution_before_postprocessing außerdem die gerundete Zuweisung vor der klassischen lokalen Suche fest. Sie verwendet dieselben Schlüssel wie solution.

Werte sie auf dem QUBO aus, um zu sehen, wie stark die Verfeinerung das Ergebnis verbessert hat. Beide Werte sind Zielfunktionswerte des übermittelten Minimierungs-QUBO, daher ist ein niedrigerer Wert besser. Das Feld fehlt, wenn die lokale Suche nicht läuft, zum Beispiel wenn Presolve jede Variable fixiert.

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

Die Unabhängigkeitsbedingung überprüfen

Da das QUBO Nachbarschaft über Strafterme statt über explizite Bedingungen darstellt, kann ein heuristisches Ergebnis dennoch benachbarte Knoten auswählen. Prüfe die zurückgegebenen Knoten direkt gegen den Graphen. Kopiere für den Vergleich und die Visualisierung in den folgenden Abschnitten die zurückgegebene Menge und entferne gierig einen Endpunkt jedes erkannten Konflikts.

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

Mit der Referenzlösung vergleichen

In Schritt 1 hast du den Zielfunktionswert der QOBLIB-Referenzlösung heruntergeladen. QOBLIB-Referenzlösungen können optimal oder bestbekannt sein, vergleiche also mit dem Referenz-Zielwert, ohne anzunehmen, dass er immer ein zertifiziertes Optimum ist.

Bei diesem Maximierungsproblem bedeutet ein Verhältnis von 1.0, dass das reparierte Ergebnis dem Referenz-Zielwert entspricht.

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

Das Ergebnis visualisieren

Zeichne den Graphen erneut, wobei die reparierte unabhängige Menge hervorgehoben ist. Keine zwei hervorgehobenen Knoten teilen eine Kante.

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

Die Ressourcennutzung auslesen

Die Ergebnis-Metadaten melden CPU_TIME für andere Phasen als RUNNING: EXECUTING_QPU, sofern verfügbar. Die Phase RUNNING: EXECUTING_QPU kann QPU_TIME melden, die von Quantum Compute zurückgegebene QPU-Nutzung, falls die endgültige Nutzung für jeden Quantum-Compute-Job verfügbar ist.

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

Fazit

In diesem Tutorial hast du eine MIS-Instanz aus QOBLIB heruntergeladen, sie mit qiskit-addon-opt-mapper als QUBO formuliert, dich mit dem SQOA Solver verbunden, die Workload konfiguriert und abgesendet, die zurückgegebene Zuweisung wieder auf den Graphen abgebildet und die ausgewählten Knoten gegen den ursprünglichen Graphen geprüft.

Außerdem hast du das Ergebnis mit der QOBLIB-Referenzlösung verglichen, den Beitrag der klassischen Nachbearbeitung untersucht und die Ressourcennutzung jeder Ausführungsphase inspiziert.

Der SQOA Solver kombiniert Presolve, QRAO mit einer QRAC-basierten Kodierung, die Konstruktion von Sampling-Circuits, hardwarebewusste Transpilation, samplebasierte Diagonalisierung, Runden und klassische Verfeinerung. Dieser Workflow kann mehr binäre Variablen abbilden, als es eine Kodierung mit einer Variable pro Qubit erlauben würde. Das Ausmaß der Reduktion durch Presolve und Kodierung hängt von der Problemstruktur ab, und die Lösungsqualität hängt von den gewonnenen Samples ab.

Die Einstellungen shots und postprocessing_level steuern das Budget für das Quantensampling bzw. die klassische Verfeinerung, ohne den Ablauf der Übermittlung zu ändern.

Anhang: Das Problem als OMMX-Instanz übermitteln

SQOA Solver akzeptiert auch eine ommx.v1.Instance aus dem OMMX-SDK. Das Paket OMMX Quantum Benchmarks stellt die QOBLIB-Probleme als OMMX-Instanzen zusammen mit ihren Referenzlösungen bereit, sodass du dasselbe QUBO laden kannst, ohne es selbst zu formulieren.

Bei einer OMMX-Eingabe wird objective_value im Sinne der Instanz ausgewertet, und das Ergebnis enthält außerdem die kanonische ommx.v1.Solution. Installiere das Paket, das auch das OMMX-SDK installiert:

# %pip install ommx-quantum-benchmarks

Lade das binary_unconstrained-Modell derselben Instanz. Der Dataset-Loader gibt Fortschrittsmeldungen aus, daher fängt der Code sie ab, um die Ausgabe kompakt zu halten.

%%capture
from ommx_quantum_benchmarks.qoblib import IndependentSet

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

SQOA Solver erhält eine OMMX-Instanz als standardmäßigen, aufgefüllten Base64-String und gibt die kanonische Lösung im selben Format zurück. Definiere zwei Hilfsfunktionen für diese Umwandlung:

• to_problem_payload() serialisiert eine ommx.v1.Instance in den String, den du als problem übergibst.

• to_ommx_solution() dekodiert die kanonische ommx.v1.Solution aus dem Ergebnis.

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

Übermittle die Instanz mit denselben Eingaben wie zuvor und ersetze nur problem. Dekodiere anschließend die kanonische Lösung und lies die ausgewählten Knoten anhand des Variablennamens aus.

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

Nächste Schritte

Empfehlungen

• Wende den Workflow auf deine eigenen QUBO-Probleme an. Erstelle ein OptimizationProblem, wie im Leitfaden zu SQOA Solver gezeigt. Die Schritte für Umwandlung und Übermittlung bleiben gleich, aber passe die Validierung an die Struktur deines Problems an.
• Übermittle das Problem als OMMX-Instanz, wie im Anhang gezeigt. Die akzeptierten Problemformate und die zurückgegebenen Felder findest du in der API-Referenz.
• Entdecke weitere Independent-Set-Instanzen im QOBLIB-Repository oder über OMMX Quantum Benchmarks.
• Erfahre mehr über das Modellieren mit qiskit-addon-opt-mapper oder JijModeling und über den Austausch von Problemen mit OMMX.

Referenzen

[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