Finden Sie die maximale unabhängige Menge mit dem Aqarios Constrained Quantum Optimizer

Geschätzte Laufzeit: 30 Sekunden auf einem Heron- r2 -Prozessor. (HINWEIS: Dies ist lediglich eine Schätzung. (Die Laufzeit kann variieren.)

Hintergrund

Dieses Tutorial zeigt, wie man mithilfe des Aqarios Constrained Quantum Optimizer [1] die maximale unabhängige Menge eines Graphen ermittelt – ein kombinatorisches Optimierungsproblem mit Nebenbedingungen. Eine Instanz aus der QOBLIB-Benchmark-Bibliothek [2] wird als binäres lineares Programm formuliert und an die Optimierungs-Anwendungsfunktion übergeben. Der Optimierer übernimmt alle Schritte der Umformulierung, Schaltungssynthese, Transpilierung und des iterativen Warmstarts intern (Einzelheiten siehe [3] ).

Das Tutorial behandelt die folgenden Schritte:

1. Definieren Sie das Problem als lineares Programm unter Verwendung der Funktion OptimizationProblem aus qiskit-addon-opt-mapper
2. Führen Sie die Quantenoptimierung mit dem „Aqarios Constrained Quantum Optimizer“ durch
3. Ergebnisse abrufen und visualisieren

Das Problem der maximalen unabhängigen Menge

Das Problem der maximalen unabhängigen Menge (MIS) stellt eine grundlegende Herausforderung in der kombinatorischen Optimierung dar. Formal gesehen besteht das Ziel bei einem gegebenen Graphen $G(V, E)$ darin, 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$ dargestellt. 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:

MIS bietet ein breites Spektrum an praktischen Anwendungsmöglichkeiten. Bei der Planung von Funknetzen entspricht eine unabhängige Gruppe einer Gruppe von Sendern, die alle gleichzeitig senden können, ohne sich gegenseitig zu stören. Bei der Terminierung modelliert es die größte Menge an Aufgaben, die unter Berücksichtigung paarweiser Ressourcenkonflikte gleichzeitig ausgeführt werden können. In der Bioinformatik bezeichnet der Begriff Gruppen von Proteinen in einem Netzwerk, die untereinander keine Wechselwirkungen eingehen.

Trotz seiner intuitiven Formulierung ist MIS NP-schwer, und selbst bei Graphen mit nur wenigen hundert Knoten lassen sich bestimmte Instanzen nur schwer exakt oder heuristisch lösen [2]. Das Problem führt zudem zu spärlichen Nebenbedingungsstrukturen, die sich gut für Hardware-Implementierungen der Quantenoptimierung eignen, was es zu einem attraktiven Benchmark für Quantencomputer der nahen Zukunft macht.

Aqarios Constrained Quantum Optimizer

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

Über diese Standardtransformation hinaus identifiziert der Optimierer Cliquen im Beschränkungsgraphen. Eine Clique ist eine Menge von Knoten $V_C$, bei der jedes Knotenpaar durch eine Kante verbunden ist. Folglich können die paarweisen Nebenbedingungen $\binom{|V_C|}{2}$ $x_u + x_v \leq 1 \;\forall (u,v) \in E_C$ durch eine einzige, strengere Nebenbedingung $\sum_{i \in V_C} x_i \leq 1$ ersetzt werden. Durch die Einführung einer Slack-Variablen $y$ wird daraus eine Gleichung $\sum_i x_i + y = 1$, die die Form einer One-Hot-Nebenbedingung annimmt, die in QAOA mithilfe von XY-Mixern [3] direkt durchgesetzt werden kann. Dadurch wird der Suchraum verkleinert und die Notwendigkeit von Straftermen für diese Nebenbedingungen vermieden, was die Qualität der Lösung verbessert.

Zudem werden Variablen, die nur mit einem einzigen Nachbarn verbunden sind, als „pendant nodes“ bezeichnet und vom Algorithmus vor der Quantenausführung deterministisch festgelegt, wodurch sich die effektive Problemgröße weiter verringert.

Der „Constrained Quantum Optimizer“ nutzt einen iterativen Warm-Start-Ansatz, der mit XY-Mischern kompatibel ist [1] und den Suchraum schrittweise eingrenzt, indem er die Verteilung der Quantenzustände im Laufe der Iterationen in Richtung vielversprechender Lösungsbereiche verschiebt. Dies ermöglicht die Verwendung von QAOA-Parametern mit festem Winkel, wodurch ein variationales Parametertraining entfällt. Der Gesamtbedarf an Quantenressourcen hängt ausschließlich von der Anzahl der Warm-Start-Iterationen ab, was bedeutet, dass sich die Quantenkosten leicht steuern lassen.

Anforderungen

Bevor Sie mit dieser Anleitung beginnen, stellen Sie bitte sicher, dass die folgenden Voraussetzungen erfüllt sind:

• Qiskit Runtime (pip install qiskit-ibm-runtime)
• Qiskit Functions Catalog IBM Client (pip install qiskit-ibm-catalog)
• Qiskit-Add-on „Optimization Mapper“ (pip install qiskit-addon-opt-mapper)
• Numpy (pip install numpy)
• Matplotlib (pip install matplotlib)
• NetworkX (pip install networkx)

Optional müssen Sie für den Anhang Folgendes installieren:

• Luna-Modell (pip install luna-model)

Einrichtung

Importiere alle erforderlichen Abhängigkeiten.

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

Melden Sie sich zunächst mit Ihrem API-Schlüssel für „ IBM Quantum “ an. Wählen Sie anschließend die Qiskit-Funktion wie folgt aus. (Dieser Code setzt voraus, dass Sie Ihr Konto bereits in Ihrer lokalen Umgebung gespeichert haben.)

catalog = QiskitFunctionsCatalog(channel="ibm_quantum_platform")

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

Output:

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

Output:

[<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: Abbildung klassischer Eingaben auf das Quantenproblem

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 Funktion auch MPS-Dateien und native Luna-Modelldarstellungen. Die LP-Datei wird in den folgenden Schritten erstellt:

1. Eine Graph-Instanz aus der QOBLIB [2] abrufen
2. Das Optimierungsproblem modellieren
3. LP-Datei erstellen

Den Graphen der Probleminstanz laden

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

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

Die Datei .gph kann mithilfe der folgenden Funktion aus dem QOBLIB-Repository heruntergeladen werden; dabei wird sie zudem in einen „ NetworkX “-Graph geparst. Beachten Sie, dass das DIMACS-Format eine Knotenbeschriftung mit 1 als Startwert verwendet, die hier in eine Indizierung mit 0 als Startwert 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)

Output:

Loading graph with 186 nodes and 280 edges.

In diesem Beispiel wird die Instanz es60fst02 aus QOBLIB verwendet, ein Graph mit 186 Knoten und 280 Kanten. Dank der vom Constrained Quantum Optimizer durchgeführten Vorverarbeitungsschritte lässt sich diese Instanz auf Heron-Geräten mit 156 Qubits lösen. Die Grafik lässt sich mit matplotlib visualisieren:

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

Output:

Formulieren Sie das Optimierungsproblem

Das Problem der maximalen unabhängigen Menge lässt sich direkt mithilfe von formulieren OptimizationProblem. Jeder Knoten des Graphen wird zu einer binären Entscheidungsvariablen, 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 stellt eine vorgefertigte Anwendungsklasse für das Problem der maximalen unabhängigen Menge bereit, wodurch sich die obige Formulierung auf einen einzigen Aufruf vereinfachen lässt:

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

Übersetzen Sie die Aufgabe in eine LP-Datei

Das Programm selbst OptimizationProblem unterstützt zwar keinen Export von LP-Dateien, ist jedoch mit DOcplex kompatibel, das diese Funktion bietet. Um den Inhalt der LP-Datei zu erstellen, sind lediglich zwei Zeilen erforderlich:

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

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

Output:

\ 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 im „Constrained Quantum Optimizer“ nativ unterstützt.

Schritt 2: Optimierung des Problems für die Ausführung auf Quantenhardware

Die gesamte Schaltungssynthese, -optimierung und -transpilierung wird von der Funktion nativ übernommen. Die Argumente, mit denen die Funktion aufgerufen werden muss, finden Sie im Abschnitt „Eingaben“ der API-Referenz.

Informationen zur Feinabstimmung des Algorithmus finden Sie in der Liste „Optionen“ in der API-Referenz. Wenn Sie möchten, dass die Schaltkreisabbildung über mehrere Durchläufe hinweg reproduzierbar ist, legen Sie die Option seed_transpiler fest.

Weitere Informationen finden Sie im Handbuch und in der API-Referenz zum Aqarios Constrained Quantum Optimizer.

Schritt 3: Mit „ Qiskit primitives “ ausführen

Die LP-Datei kann nun an den Optimierer übermittelt werden:

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

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

Output:

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

Intern durchläuft der Algorithmus die folgenden Schritte:

1. Vorverarbeitung :
   • Behebbare Variablen reduzieren
   • Cliquen finden
   • Einschränkungstypen identifizieren
   • Strafkoeffizienten für Strafklauseln bewerten
   • Beschränkungstransformationen anwenden
   • Schaltung mit Methoden zur Durchsetzung von Beschränkungen synthetisieren
   • Annäherung an das Problem und Transpilierung
2. Parallele Ketten von iterativen Schleifen :
   • Beispiel aus einer Schaltung mit festen Parametern
   • Nachbearbeitung anwenden
   • Die Wahrscheinlichkeiten für einen Warmstart bewerten und neu festlegen
3. Nachbearbeitung :
   • Finden Sie die besten Beispiele und prüfen Sie die Machbarkeit in Bezug auf das Ausgangsproblem

Den Fortschritt überwachen

Lesen Sie die folgenden Abschnitte auf der Seite „Erste Schritte mit Qiskit Functions “, um den Fortschritt Ihres Auftrags zu überwachen:

• Auftragsstatus prüfen
• Ergebnisse abrufen

# Monitor the job status
job.status()

Output:

'QUEUED'

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

Die Ausgabe besteht aus einem Wörterbuch, dessen Felder im Abschnitt „Ausgaben“ 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 betrachtet, die über den Variablennamen angesprochen wird. Die gleichen Lösungen sind auch als Bitfolgen in verfügbar solution_bitstrings, wobei die Zeichenposition der jeweiligen Variablen angibt metadata.solver_info.variable_mapping .

# 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) + "}")

Output:

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 lässt sich visualisieren, 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)

Output:

Anhang: Problemstellung mit dem Luna-Modell

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

Einrichten:

from luna_model import Model, Sense
import numpy as np

Das Modell wird dann anhand des Graphen auf dieselbe Weise wie bei … erstellt qiskit-addon-opt-mapper:

Erstellen Sie das Modell:

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ächsSchr

Referenzen

1. IBM Quantum : Leitfaden zum Aqarios Constrained Quantum Optimizer
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-Modell-Dokumentation