Finde das Maximum Independent Set mit dem Aqarios Constrained Quantum Optimizer

Hinweis

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

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

Hintergrund

Dieses Tutorial zeigt, wie man mit dem Aqarios Constrained Quantum Optimizer [1] das Maximum Independent Set eines Graphen findet – ein kombinatorisches Optimierungsproblem mit Nebenbedingungen. Eine Instanz aus der QOBLIB [2]-Benchmark-Bibliothek wird als binäres lineares Programm formuliert und an die Optimizer Application Function übergeben. Der Optimizer übernimmt intern die gesamte Umformulierung, Circuit-Synthese, Transpilation und den iterativen Warmstart (siehe [3] für Details).

Das Tutorial umfasst die folgenden Schritte:

1. Definiere das Problem als lineares Programm mithilfe von OptimizationProblem aus qiskit-addon-opt-mapper

2. Führe die Quantenoptimierung mit dem Aqarios Constrained Quantum Optimizer aus

3. Rufe die Ergebnisse ab und visualisiere sie

Das Maximum-Independent-Set-Problem

Das Maximum-Independent-Set-Problem (MIS) ist eine grundlegende Herausforderung in der kombinatorischen Optimierung. Formal ist bei einem gegebenen Graphen $G(V, E)$ das Ziel, die größte Teilmenge von Knoten $V_I \subset V$ zu finden, sodass keine zwei Knoten in $V_I$ durch eine Kante verbunden sind, wie in $\nexists (u, v) \in E : v \in V_I \wedge u \in V_I$. Jedem Knoten wird eine binäre Entscheidungsvariable $x_i \in \{0, 1\}$ zugewiesen, und für jede Kante wird eine Nebenbedingung $x_u + x_v \leq 1$ eingeführt, die sicherstellt, dass höchstens ein Endpunkt jeder Kante ausgewählt wird. Das Problem lässt sich somit als folgendes Maximierungsproblem formulieren:

$$\max_{x_i} \sum_{i \in V} x_i \qquad\text{(finde die größte Menge)}\\ \text{s.t.} \quad x_u + x_v \leq 1 \quad \forall (u, v) \in E.$$

MIS hat ein breites Spektrum praktischer Anwendungen. In der Planung drahtloser Netzwerke entspricht eine unabhängige Menge einer Gruppe von Sendern, die alle gleichzeitig ohne gegenseitige Störung senden können. Bei der Ablaufplanung modelliert es die größte Sammlung von Aufgaben, die bei paarweisen Ressourcenkonflikten gleichzeitig ausgeführt werden können. In der Computerbiologie erfasst es Mengen von Proteinen in einem Netzwerk, die nicht miteinander interagieren.

Trotz seiner intuitiven Formulierung ist MIS NP-schwer, und schon bei Graphen mit einigen Hundert Knoten werden bestimmte Instanzen schwierig, exakt oder heuristisch zu lösen [2]. Das Problem führt zudem zu dünnbesetzten Nebenbedingungsstrukturen, die sich gut für Hardware-Implementierungen der Quantenoptimierung eignen, was es zu einem attraktiven Benchmark für Quantengeräte der nahen Zukunft macht.

Aqarios Constrained Quantum Optimizer

Der Standardansatz zur Einbettung eines binären Problems mit Nebenbedingungen in die Quantenoptimierung wandelt das Modell durch Hinzufügen von Straftermen in ein Format ohne Nebenbedingungen um: Jede verletzte Nebenbedingung $x_u + x_v \leq 1$ trägt $2 x_u x_v$ zur Minimierungszielfunktion $-\sum_i x_i$ bei. Dies wird automatisch von der Constrained Quantum Optimizer Qiskit Function übernommen.

Über diese Standardtransformation hinaus identifiziert der Optimizer Cliquen im Constraint-Graphen. Eine Clique ist eine Menge von Knoten $V_C$, bei der jedes Knotenpaar durch eine Kante verbunden ist. Infolgedessen können die $\binom{|V_C|}{2}$ paarweisen Nebenbedingungen $x_u + x_v \leq 1 \;\forall (u,v) \in E_C$ durch eine einzige, engere Nebenbedingung $\sum_{i \in V_C} x_i \leq 1$ ersetzt werden. Durch Einführung einer Schlupfvariable $y$ wird dies zu einer Gleichung $\sum_i x_i + y = 1$, die die Form einer One-Hot-Nebenbedingung annimmt, die in QAOA direkt mithilfe von XY-Mixern [3] durchgesetzt werden kann. Dies verkleinert den Suchraum und macht Strafterme für diese Nebenbedingungen überflüssig, wodurch sich die Lösungsqualität verbessert.

Zusätzlich werden Variablen, die nur mit einem einzigen Nachbarn verbunden sind, als Pendant-Knoten bezeichnet und vom Algorithmus vor der Quantenausführung deterministisch festgelegt, wodurch die effektive Problemgröße weiter reduziert wird.

Der Constrained Quantum Optimizer verwendet einen mit XY-Mixern kompatiblen Ansatz des iterativen Warmstarts [1], der den Suchraum schrittweise eingrenzt, indem er die Verteilung des Quantenzustands über die Iterationen hinweg gezielt in Richtung vielversprechender Lösungsbereiche gewichtet. Dies ermöglicht die Verwendung von QAOA-Parametern mit festem Winkel, wodurch ein variationelles Parametertraining überflüssig wird. Der gesamte Quantenressourcenbedarf hängt ausschließlich von der Anzahl der Warmstart-Iterationen ab, wodurch sich die Quantenkosten unkompliziert steuern lassen.

Voraussetzungen

Stelle vor Beginn dieses Tutorials sicher, dass du die folgenden Voraussetzungen installiert hast:

• Qiskit Runtime (pip install qiskit-ibm-runtime)

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

• Qiskit Addon Optimization Mapper (pip install qiskit-addon-opt-mapper)

• Numpy (pip install numpy)

• Matplotlib (pip install matplotlib)

• NetworkX (pip install networkx)

Optional benötigst du für den Anhang die Installation von

• Luna Model (pip install luna-model)

Setup

Importiere alle erforderlichen Abhängigkeiten.

# Added by doQumentation — installs the packages this notebook needs if they are missing
import importlib.util

_needed = {"luna_model": "luna-model", "networkx": "networkx", "numpy": "numpy", "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")

import networkx as nx
import urllib.request

from qiskit_ibm_catalog import QiskitFunctionsCatalog

from qiskit_addon_opt_mapper import OptimizationProblem
from qiskit_addon_opt_mapper.applications import IndependentSet
from qiskit_addon_opt_mapper.translators import to_docplex_mp

Authentifiziere dich zunächst mit deinem IBM Quantum API-Schlüssel. Wähle dann die Qiskit Function wie folgt aus. (Dieser Code setzt voraus, dass du dein Konto bereits lokal gespeichert hast.)

catalog = QiskitFunctionsCatalog(channel="ibm_quantum_platform")

# Verify that you have access to the function
catalog.list()

[QiskitFunction(aqarios/constrained-quantum-optimizer)]

# Load the function
optimizer = catalog.load("aqarios/constrained-quantum-optimizer")

# Check the list of backends you have access to
catalog.backends()

[<IBMBackend('ibm_pittsburgh')>,
 <IBMBackend('ibm_boston')>,
 <IBMBackend('ibm_phoenix')>,
 <IBMBackend('ibm_fez')>,
 <IBMBackend('ibm_miami')>,
 <IBMBackend('ibm_marrakesh')>,
 <IBMBackend('ibm_kingston')>]

# Select the backend you want to use
backend = catalog.backend("ibm_pittsburgh")

Schritt 1: Klassische Eingaben auf das Quantenproblem abbilden

Das Problem wird als LP-Datei formuliert, einem gängigen Format für Optimierungsprobleme, das als Eingabe für den Aqarios Constrained Quantum Optimizer dient. Neben LP-Dateien unterstützt die Function auch MPS-Dateien und native Luna-Model-Darstellungen. Die LP-Datei wird durch die folgenden Schritte erzeugt:

1. Rufe eine Graph-Instanz aus der QOBLIB ab [2]

2. Modelliere das Optimierungsproblem

3. Erzeuge die LP-Datei

Lade den Graphen der Probleminstanz

Die Graphen werden im DIMACS-Format .gph angegeben, einem zeilenbasierten Format, bei dem Zeilen, die mit e beginnen, Kanten definieren, Zeilen, die mit p beginnen, den Problem-Header definieren, und Zeilen, die mit c beginnen, Kommentare sind:

c some-comment
p edge 3 2
e 1 2
e 2 3
...

Die Datei .gph kann mit der folgenden Funktion aus dem QOBLIB-Repository heruntergeladen werden, die sie außerdem in einen NetworkX-Graphen parst. Beachte, dass das DIMACS-Format eine 1-basierte Knotennummerierung verwendet, die hier in eine 0-basierte Indizierung umgewandelt wird.

URL_BASE = "https://raw.githubusercontent.com/ZIB-AOPT/QOBLIB/refs/heads/main/07-independentset/instances/"

def fetch_qoblib_graph(name: str) -> nx.Graph:
    """Fetch and parse the QOBLIB graph file."""
    # Download the .gph file
    file, _ = urllib.request.urlretrieve(URL_BASE + f"{name}.gph")
    with open(file) as f:
        # Read the file contents
        lines = f.readlines()

    # Skip comments
    lines = [line for line in lines if not line.startswith("c")]

    # Read graph definition
    _, _, num_nodes, num_edges = lines[0].split()
    print(f"Loading graph with {num_nodes} nodes and {num_edges} edges.")

    # Parse edge information
    # The .gph format starts node labeling with 1; we need 0 here, so we subtract one.
    split_edges = (line.split() for line in lines[1:])
    edges = [(int(u) - 1, int(v) - 1) for _, u, v in split_edges]

    return nx.Graph(edges)

graph_name = "es60fst02"
graph = fetch_qoblib_graph(graph_name)

Loading graph with 186 nodes and 280 edges.

Dieses Beispiel verwendet die Instanz es60fst02 aus QOBLIB, einen Graphen mit 186 Knoten und 280 Kanten. Dank der Vorverarbeitungsschritte des Constrained Quantum Optimizer ist diese Instanz auf 156-Qubit-Heron-Geräten lösbar. Der Graph kann mit matplotlib visualisiert werden:

# Keep layout for later reuse
layout = nx.spring_layout(graph, seed=1)
nx.draw(graph, layout, node_size=40)

Erstelle das Optimierungsproblem

Das Maximum-Independent-Set-Problem kann direkt mit OptimizationProblem formuliert werden. Jeder Graphknoten wird zu einer binären Entscheidungsvariable, und jede Kante führt eine Nebenbedingung ein, die sicherstellt, dass höchstens einer ihrer Endpunkte ausgewählt wird:

# Create an OptimizationProblem instance
mis_problem = OptimizationProblem("MIS")

# Add a binary variable for each node
x = mis_problem.binary_var_list(graph.number_of_nodes())

# Maximize the sum of all node variables
mis_problem.maximize(linear={xi.name: 1 for xi in x})

# Add '<= 1' constraints for each edge
for u, v in graph.edges:
    mis_problem.linear_constraint({x[u].name: 1, x[v].name: 1}, "<=", 1)

Eine Abkürzung

Das Paket qiskit-addon-opt-mapper bietet eine vorimplementierte Application-Klasse für das Maximum-Independent-Set-Problem, die die obige Formulierung auf einen einzigen Aufruf vereinfacht:

mis = IndependentSet(graph)
mis_problem = mis.to_optimization_problem()

Übersetze das Problem in eine LP-Datei

OptimizationProblem selbst unterstützt keine LP-Datei-Exporte, ist jedoch mit DOcplex interoperabel, das dies kann. Die Erzeugung des LP-Datei-Inhalts erfordert nur zwei Zeilen:

mp_model = to_docplex_mp(mis_problem)
lp_str = mp_model.export_as_lp_string()

print("\n".join(lp_str.split("\n")[:60]))
print("...")

\ This file has been generated by DOcplex
\ ENCODING=ISO-8859-1
\Problem name: Independent set

Maximize
 obj: x_0 + x_1 + x_2 + x_3 + x_4 + x_5 + x_6 + x_7 + x_8 + x_9 + x_10 + x_11
      + x_12 + x_13 + x_14 + x_15 + x_16 + x_17 + x_18 + x_19 + x_20 + x_21
      + x_22 + x_23 + x_24 + x_25 + x_26 + x_27 + x_28 + x_29 + x_30 + x_31
      + x_32 + x_33 + x_34 + x_35 + x_36 + x_37 + x_38 + x_39 + x_40 + x_41
      + x_42 + x_43 + x_44 + x_45 + x_46 + x_47 + x_48 + x_49 + x_50 + x_51
      + x_52 + x_53 + x_54 + x_55 + x_56 + x_57 + x_58 + x_59 + x_60 + x_61
      + x_62 + x_63 + x_64 + x_65 + x_66 + x_67 + x_68 + x_69 + x_70 + x_71
      + x_72 + x_73 + x_74 + x_75 + x_76 + x_77 + x_78 + x_79 + x_80 + x_81
      + x_82 + x_83 + x_84 + x_85 + x_86 + x_87 + x_88 + x_89 + x_90 + x_91
      + x_92 + x_93 + x_94 + x_95 + x_96 + x_97 + x_98 + x_99 + x_100 + x_101
      + x_102 + x_103 + x_104 + x_105 + x_106 + x_107 + x_108 + x_109 + x_110
      + x_111 + x_112 + x_113 + x_114 + x_115 + x_116 + x_117 + x_118 + x_119
      + x_120 + x_121 + x_122 + x_123 + x_124 + x_125 + x_126 + x_127 + x_128
      + x_129 + x_130 + x_131 + x_132 + x_133 + x_134 + x_135 + x_136 + x_137
      + x_138 + x_139 + x_140 + x_141 + x_142 + x_143 + x_144 + x_145 + x_146
      + x_147 + x_148 + x_149 + x_150 + x_151 + x_152 + x_153 + x_154 + x_155
      + x_156 + x_157 + x_158 + x_159 + x_160 + x_161 + x_162 + x_163 + x_164
      + x_165 + x_166 + x_167 + x_168 + x_169 + x_170 + x_171 + x_172 + x_173
      + x_174 + x_175 + x_176 + x_177 + x_178 + x_179 + x_180 + x_181 + x_182
      + x_183 + x_184 + x_185
Subject To
 c0: x_60 + x_61 <= 1
 c1: x_14 + x_60 <= 1
 c2: x_7 + x_60 <= 1
 c3: x_7 + x_61 <= 1
 c4: x_61 + x_62 <= 1
 c5: x_61 + x_64 <= 1
 c6: x_14 + x_62 <= 1
 c7: x_62 + x_65 <= 1
 c8: x_23 + x_63 <= 1
 c9: x_53 + x_63 <= 1
 c10: x_39 + x_63 <= 1
 c11: x_7 + x_68 <= 1
 c12: x_18 + x_68 <= 1
 c13: x_68 + x_69 <= 1
 c14: x_68 + x_72 <= 1
 c15: x_64 + x_65 <= 1
 c16: x_64 + x_69 <= 1
 c17: x_65 + x_66 <= 1
 c18: x_51 + x_53 <= 1
 c19: x_69 + x_73 <= 1
 c20: x_66 + x_67 <= 1
 c21: x_42 + x_66 <= 1
 c22: x_67 + x_75 <= 1
 c23: x_43 + x_67 <= 1
 c24: x_42 + x_75 <= 1
 c25: x_75 + x_83 <= 1
 c26: x_12 + x_51 <= 1
 c27: x_18 + x_70 <= 1
 c28: x_18 + x_26 <= 1
 c29: x_70 + x_71 <= 1
 c30: x_70 + x_76 <= 1
 c31: x_71 + x_72 <= 1
 c32: x_72 + x_73 <= 1
 c33: x_72 + x_78 <= 1
...

Dieses Format ist nativ für den Constrained Quantum Optimizer.

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

Die gesamte Circuit-Synthese, Optimierung und Transpilation wird nativ von der Function übernommen. Die Argumente, mit denen die Function aufgerufen wird, findest du im Abschnitt Inputs der API-Referenz.

Um das Verhalten des Algorithmus feinabzustimmen, sieh dir die Optionsliste in der API-Referenz an. Wenn das Circuit-Mapping über mehrere Läufe hinweg reproduzierbar sein soll, lege die Option seed_transpiler fest.

Weitere Informationen findest du im Aqarios Constrained Quantum Optimizer Guide und in der API-Referenz.

Schritt 3: Ausführung mit Qiskit-Primitiven

Die LP-Datei kann jetzt an den Optimizer übermittelt werden:

job = optimizer.run(problem=lp_str, backend_name=backend.name)

print(f"Job ID: {job.job_id}")

Job ID: 87ec08b9-6275-40fa-be94-340a0a916bf1

Intern durchläuft der Algorithmus die folgenden Phasen:

1. Preprocessing:

   • Fixierbare Variablen reduzieren

   • Cliquen finden

   • Nebenbedingungstypen identifizieren

   • Straffaktoren für Strafterme bewerten

   • Nebenbedingungstransformationen anwenden

   • Circuit mit nebenbedingungserzwingenden Methoden synthetisieren

   • Approximation des Problems und Transpilation

2. Parallele Ketten iterativer Schleifen:

   • Sampling aus dem Circuit mit festen Parametern

   • Nachbearbeitung anwenden

   • Neue Warmstart-Wahrscheinlichkeiten bewerten und festlegen

3. Postprocessing:

   • Beste Samples finden und auf Zulässigkeit bezüglich des Eingabeproblems prüfen

Überwache den Fortschritt

Die folgenden Abschnitte auf der Seite „Erste Schritte mit Qiskit Functions“ helfen dir, den Fortschritt deines Jobs zu überwachen:

• Jobstatus prüfen

• Ergebnisse abrufen

# Monitor the job status
job.status()

'QUEUED'

Schritt 4: Nachbearbeitung und Rückgabe der Ergebnisse im gewünschten klassischen Format

Die Ergebnisausgabe ist ein Dictionary, dessen Felder im Abschnitt Outputs der API-Referenz beschrieben sind.

Wenn die Liste solutions mehr als einen Eintrag enthält, wurden mehrere entartete Optima gefunden. Hier wird nur die erste Lösung berücksichtigt, angesprochen über den Variablennamen. Dieselben Lösungen sind auch als Bitstrings in solution_bitstrings verfügbar, wobei metadata.solver_info.variable_mapping die Zeichenposition jeder Variable angibt.

# Retrieve the job result
result = job.result()

# Retrieve the first solution from the result
solution = result["solutions"][0]

print(f"The found maximum independent set of {graph_name} contains:", end=" ")
print(
    f"{int(result['objective_value'])} nodes and is {'feasible' if result['feasible'] else 'infeasible'}."
)
print("{" + " ".join(k[2:] for k, v in solution.items() if v == 1) + "}")

The found maximum independent set of es60fst02 contains: 88 nodes and is feasible.
{100 103 107 109 111 113 115 118 121 123 124 127 129 130 132 133 138 142 144 148 149 155 156 16 161 162 165 167 169 170 175 28 31 33 35 36 47 50 58 59 60 62 64 66 68 71 73 75 78 79 84 85 87 90 91 93 94 95 39 5 27 23 43 15 22 9 4 56 32 30 53 26 17 54 1 37 41 49 34 11 139 153 12 3 6 57 20 44}

Visualisierung

Die ermittelte unabhängige Menge kann visualisiert werden, indem die ausgewählten Knoten im Graphen hervorgehoben werden:

# Color all selected nodes in orange
node_map = {
    int(k.split("_")[1]): "tab:orange" if v else "tab:blue"
    for k, v in solution.items()
}
node_colors = [node_map[k] for k in graph.nodes]

# Draw with the same layout used before
nx.draw(graph, layout, node_size=40, node_color=node_colors)

Anhang: Problemstellung mit Luna Model

Zusätzlich zu dem oben gezeigten Ansatz mit qiskit-addon-opt-mapper akzeptiert die Qiskit Function auch Modelle, die mit Luna Model [4], dem Modellierungs-SDK von Aqarios, erstellt wurden. Nach der Installation des PyPI-Pakets luna-model importierst du es wie folgt:

Setup:

from luna_model import Model, Sense
import numpy as np

Das Modell wird dann auf dieselbe Weise wie mit qiskit-addon-opt-mapper aus dem Graphen erstellt: Modell erstellen:

edges = np.array(graph.edges)

# Create the optimization model with a name
model = Model(name=f"MIS-{graph_name}", sense=Sense.MAX)
# Add binary variables
x = model.add_variables("x", graph.number_of_nodes())
# Set the objective
model.objective = x.sum()

# Use numpy like batch generation of constraints
model.add_constraints(x[edges].sum(axis=1) <= 1)

input_str = model.encode_b64()

# optimizer.run(problem=input_str, backend_name="ibm_fez")

Nächste Schritte

Empfehlungen

• Im Aqarios Constrained Quantum Optimizer Guide findest du eine ausführliche Schritt-für-Schritt-Erklärung aller Features der Function.
• In der API-Referenz findest du die vollständige Liste der Eingabeparameter und Ausgabefelder.
• Experimentiere mit den Algorithmusoptionen (reps, num_parallel, shots, postprocessing_level) an deinem eigenen binären Optimierungsproblem mit Nebenbedingungen, um deren Auswirkungen auf Lösungsqualität und Laufzeit zu bewerten.

Referenzen

1. IBM Quantum, Aqarios Constrained Quantum Optimizer Guide

2. Koch et al. (2026), The Quantum Optimization Benchmarking Library 10.1038/s43588-026-00991-1

3. Bucher et al. (2026), Constrained Quantum Optimization via Iterative Warm-Start XY-Mixers 10.1088/1367-2630/ae8ea2

4. Aqarios GmbH, Luna Model Docs