Temukan Maximum Independent Set dengan Aqarios Constrained Quantum Optimizer

Note

Qiskit Functions adalah fitur eksperimental yang hanya tersedia untuk pengguna IBM Quantum® Premium Plan, Flex Plan, dan On-Prem (via IBM Quantum Platform API) Plan. Fitur ini berstatus preview release dan dapat berubah sewaktu-waktu.

Perkiraan penggunaan: 30 detik pada prosesor Heron r2. (CATATAN: Ini hanya perkiraan. Runtime Anda mungkin berbeda.)

Latar Belakang

Tutorial ini mendemonstrasikan cara menemukan maximum independent set dari sebuah graf menggunakan Aqarios Constrained Quantum Optimizer [1], sebuah masalah optimisasi kombinatorial berkendala. Sebuah instance dari pustaka benchmark QOBLIB [2] diformulasikan sebagai program linear biner dan diteruskan ke Optimizer Application Function. Optimizer menangani semua reformulasi, sintesis sirkuit, transpilasi, dan iterative warm starting secara internal (lihat [3] untuk detailnya).

Tutorial ini mencakup langkah-langkah berikut:

1. Definisikan masalah sebagai program linear menggunakan OptimizationProblem dari qiskit-addon-opt-mapper

2. Jalankan optimisasi kuantum menggunakan Aqarios Constrained Quantum Optimizer

3. Ambil dan visualisasikan hasilnya

Masalah Maximum Independent Set

Masalah Maximum Independent Set (MIS) adalah tantangan mendasar dalam optimisasi kombinatorial. Secara formal, diberikan sebuah graf $G(V, E)$, tujuannya adalah menemukan subset vertex terbesar $V_I \subset V$ sedemikian rupa sehingga tidak ada dua vertex dalam $V_I$ yang terhubung oleh sebuah edge, seperti pada $\nexists (u, v) \in E : v \in V_I \wedge u \in V_I$. Setiap vertex diberi variabel keputusan biner $x_i \in \{0, 1\}$, dan sebuah kendala $x_u + x_v \leq 1$ diperkenalkan untuk setiap edge, memastikan bahwa paling banyak satu endpoint dari setiap edge yang dipilih. Masalah ini dengan demikian dapat dinyatakan sebagai masalah maksimisasi berikut:

$$\max_{x_i} \sum_{i \in V} x_i \qquad\text{(temukan himpunan terbesar)}\\ \text{s.t.} \quad x_u + x_v \leq 1 \quad \forall (u, v) \in E.$$

MIS memiliki berbagai aplikasi praktis. Dalam perencanaan jaringan nirkabel, independent set sesuai dengan sekelompok pemancar yang dapat menyiarkan secara bersamaan tanpa interferensi timbal balik. Dalam penjadwalan, ini memodelkan kumpulan terbesar dari tugas yang dapat dijalankan secara bersamaan mengingat konflik sumber daya berpasangan. Dalam biologi komputasi, ini menangkap kumpulan protein yang tidak saling berinteraksi dalam suatu jaringan.

Meskipun formulasinya intuitif, MIS bersifat NP-hard, dan bahkan untuk graf dengan beberapa ratus node, instance tertentu menjadi sulit diselesaikan secara eksak maupun heuristik [2]. Masalah ini juga menghasilkan struktur kendala yang jarang (sparse) yang sangat cocok untuk implementasi perangkat keras optimisasi kuantum, menjadikannya benchmark yang menarik untuk perangkat kuantum near-term.

Aqarios Constrained Quantum Optimizer

Pendekatan standar untuk menyematkan masalah biner berkendala ke dalam optimisasi kuantum mengubah model menjadi format tanpa kendala dengan menambahkan suku penalti: setiap kendala yang dilanggar $x_u + x_v \leq 1$ berkontribusi $2 x_u x_v$ terhadap tujuan minimisasi $-\sum_i x_i$. Ini ditangani secara otomatis oleh Constrained Quantum Optimizer Qiskit Function.

Selain transformasi standar ini, optimizer mengidentifikasi klik (cliques) dalam graf kendala. Sebuah klik adalah himpunan node $V_C$ di mana setiap pasangan node terhubung oleh sebuah edge. Sebagai konsekuensinya, $\binom{|V_C|}{2}$ kendala berpasangan $x_u + x_v \leq 1 \;\forall (u,v) \in E_C$ dapat digantikan oleh satu kendala tunggal yang lebih ketat $\sum_{i \in V_C} x_i \leq 1$. Memperkenalkan variabel slack $y$ mengubah ini menjadi persamaan $\sum_i x_i + y = 1$, yang berbentuk kendala one-hot yang dapat diberlakukan langsung dalam QAOA menggunakan XY-mixers [3]. Ini mengurangi ruang pencarian dan menghindari kebutuhan akan suku penalti untuk kendala-kendala tersebut, meningkatkan kualitas solusi.

Selain itu, variabel yang terhubung hanya ke satu tetangga disebut node pendant dan ditetapkan secara deterministik oleh algoritme sebelum eksekusi kuantum, sehingga ukuran efektif masalah makin berkurang.

Constrained Quantum Optimizer menggunakan pendekatan iterative warm-starting yang kompatibel dengan XY-mixers [1], yang secara progresif mempersempit ruang pencarian dengan membiaskan distribusi keadaan kuantum menuju wilayah solusi yang menjanjikan di setiap iterasi. Ini memungkinkan penggunaan parameter QAOA sudut tetap (fixed-angle), menghilangkan kebutuhan akan pelatihan parameter variasional. Total kebutuhan sumber daya kuantum diatur hanya oleh jumlah iterasi warm-start, yang berarti biaya kuantum mudah dikendalikan.

Persyaratan

Sebelum memulai tutorial ini, pastikan Anda telah menginstal persyaratan berikut:

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

Opsional, untuk Lampiran Anda perlu menginstal

• Luna Model (pip install luna-model)

Pengaturan

Impor semua dependensi yang diperlukan.

# 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

Pertama, lakukan autentikasi menggunakan IBM Quantum API key Anda. Kemudian, pilih Qiskit Function sebagai berikut. (Kode ini mengasumsikan Anda sudah menyimpan akun Anda ke lingkungan lokal Anda.)

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

Langkah 1: Memetakan input klasik ke masalah kuantum

Masalah ini diformulasikan sebagai sebuah LP-file, format umum untuk masalah optimisasi yang menjadi input bagi Aqarios Constrained Quantum Optimizer. Selain LP-file, function ini juga mendukung MPS-file dan representasi Luna Model native. LP-file dihasilkan melalui langkah-langkah berikut:

1. Ambil sebuah instance graf dari QOBLIB [2]

2. Modelkan masalah optimisasi

3. Hasilkan LP-file

Muat graf instance masalah

Graf ditentukan dalam format DIMACS .gph, sebuah format berbasis baris di mana baris yang dimulai dengan e mendefinisikan edge, baris yang dimulai dengan p mendefinisikan header masalah, dan baris yang dimulai dengan c adalah komentar:

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

File .gph dapat diunduh dari repositori QOBLIB menggunakan fungsi berikut, yang juga mengurainya menjadi graf NetworkX. Perhatikan bahwa format DIMACS menggunakan penomoran node berbasis 1, yang di sini dikonversi menjadi pengindeksan berbasis 0.

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.

Contoh ini menggunakan instance es60fst02 dari QOBLIB, sebuah graf dengan 186 node dan 280 edge. Berkat langkah-langkah preprocessing yang digunakan oleh Constrained Quantum Optimizer, instance ini dapat diselesaikan pada perangkat Heron 156-qubit. Graf ini dapat divisualisasikan menggunakan matplotlib:

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

Membangun masalah optimisasi

Masalah Maximum Independent Set dapat diformulasikan langsung menggunakan OptimizationProblem. Setiap node graf menjadi variabel keputusan biner, dan setiap edge memperkenalkan kendala yang memastikan bahwa paling banyak satu endpoint-nya yang dipilih:

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

Cara pintas

Paket qiskit-addon-opt-mapper menyediakan kelas aplikasi yang sudah diimplementasikan untuk masalah Maximum Independent Set, yang menyederhanakan formulasi di atas menjadi satu panggilan tunggal:

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

Menerjemahkan masalah menjadi LP-file

OptimizationProblem itu sendiri tidak mendukung ekspor LP-file, tetapi dapat dioperasikan bersama DOcplex, yang mendukungnya. Menghasilkan konten LP-file hanya memerlukan dua baris:

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

Format ini native untuk Constrained Quantum Optimizer.

Langkah 2: Mengoptimalkan masalah untuk eksekusi perangkat keras kuantum

Semua sintesis sirkuit, optimisasi, dan transpilasi ditangani secara native oleh function. Lihat bagian inputs dalam referensi API untuk argumen yang digunakan memanggil function.

Untuk menyetel perilaku algoritme secara lebih rinci, lihat Daftar Opsi dalam referensi API. Jika Anda ingin pemetaan sirkuit dapat direproduksi di setiap run, tetapkan opsi seed_transpiler.

Untuk informasi lebih lanjut, lihat panduan Aqarios Constrained Quantum Optimizer dan referensi API.

Langkah 3: Menjalankan menggunakan Qiskit primitives

LP-file sekarang dapat diserahkan ke optimizer:

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

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

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

Secara internal, algoritme berlangsung melalui tahapan-tahapan berikut:

1. Preprocessing:

   • Mengurangi variabel yang dapat ditetapkan (fixable)

   • Menemukan klik (cliques)

   • Mengidentifikasi jenis kendala

   • Mengevaluasi faktor penalti untuk suku penalti

   • Menerapkan transformasi kendala

   • Mensintesis sirkuit dengan metode penegakan kendala

   • Aproksimasi masalah dan transpilasi

2. Rantai paralel dari loop iteratif:

   • Mengambil sampel dari sirkuit dengan parameter tetap

   • Menerapkan postprocessing

   • Mengevaluasi dan menetapkan probabilitas warm-starting baru

3. Postprocessing:

   • Menemukan sampel terbaik dan memeriksa kelayakan (feasibility) terhadap masalah input

Pantau kemajuan

Lihat bagian-bagian berikut di halaman Get started with Qiskit Functions untuk memantau kemajuan job Anda:

• Periksa status job

• Ambil hasil

# Monitor the job status
job.status()

'QUEUED'

Langkah 4: Pascaproses dan kembalikan hasil dalam format klasik yang diinginkan

Output hasil adalah sebuah dictionary, yang field-nya dijelaskan dalam bagian Outputs dari referensi API.

Ketika daftar solutions berisi lebih dari satu entri, berarti beberapa optima degenerate telah ditemukan. Di sini hanya solusi pertama yang dipertimbangkan, diakses berdasarkan nama variabel. Solusi yang sama juga tersedia sebagai bitstring di solution_bitstrings, di mana metadata.solver_info.variable_mapping memberikan posisi karakter setiap variabel.

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

Visualisasi

Independent set yang teridentifikasi dapat divisualisasikan dengan menyorot node-node yang terpilih dalam graf:

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

Lampiran: Pernyataan masalah dengan Luna Model

Selain pendekatan qiskit-addon-opt-mapper yang ditunjukkan di atas, Qiskit Function juga menerima model yang dibuat dengan Luna Model [4], SDK pemodelan milik Aqarios. Setelah menginstal paket PyPI luna-model, impor sebagai berikut:

Setup:

from luna_model import Model, Sense
import numpy as np

Model kemudian dibangun dari graf dengan cara yang sama seperti dengan qiskit-addon-opt-mapper: Bangun model:

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

Langkah Selanjutnya

Recommendations

• Lihat panduan Aqarios Constrained Quantum Optimizer untuk penjelasan rinci tentang semua fitur function.
• Jelajahi referensi API untuk daftar lengkap parameter input dan field output.
• Bereksperimenlah dengan opsi algoritme (reps, num_parallel, shots, postprocessing_level) pada masalah optimisasi biner berkendala Anda sendiri untuk menilai dampaknya terhadap kualitas solusi dan runtime.

Referensi

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