Cari Maximum Independent Set dengan Aqarios Constrained Quantum Optimizer

Nota

Qiskit Functions ialah ciri eksperimen yang hanya tersedia untuk pengguna Pelan Premium, Pelan Flex, dan Pelan On-Prem (melalui IBM Quantum Platform API) IBM Quantum®. Ciri ini berstatus keluaran pratonton dan tertakluk kepada perubahan.

Anggaran penggunaan: 30 saat pada pemproses Heron r2. (NOTA: Ini hanyalah anggaran. Masa larian anda mungkin berbeza.)

Latar Belakang

Tutorial ini menunjukkan cara mencari set bebas maksimum (maximum independent set) bagi suatu graf menggunakan Aqarios Constrained Quantum Optimizer [1], iaitu masalah pengoptimuman kombinatorik terkekang. Satu contoh daripada perpustakaan penanda aras QOBLIB [2] dirumuskan sebagai program linear binari dan dihantar kepada Optimizer Application Function. Optimizer ini mengendalikan semua perumusan semula, sintesis litar, transpilation, dan warm-starting berulang secara dalaman (lihat [3] untuk butiran).

Tutorial ini merangkumi langkah-langkah berikut:

1. Takrifkan masalah sebagai program linear menggunakan OptimizationProblem daripada qiskit-addon-opt-mapper

2. Jalankan pengoptimuman kuantum menggunakan Aqarios Constrained Quantum Optimizer

3. Dapatkan dan visualisasikan hasilnya

Masalah Maximum Independent Set

Masalah Maximum Independent Set (MIS) merupakan cabaran asas dalam pengoptimuman kombinatorik. Secara formal, diberikan graf $G(V, E)$, matlamatnya adalah untuk mencari subset bucu terbesar $V_I \subset V$ sedemikian rupa sehingga tiada dua bucu dalam $V_I$ disambungkan oleh tepi, seperti dalam $\nexists (u, v) \in E : v \in V_I \wedge u \in V_I$. Setiap bucu diberikan pemboleh ubah keputusan binari $x_i \in \{0, 1\}$, dan kekangan $x_u + x_v \leq 1$ diperkenalkan untuk setiap tepi, memastikan bahawa paling banyak satu hujung bagi setiap tepi dipilih. Masalah ini dengan itu boleh dinyatakan sebagai masalah pemaksimuman berikut:

$$\max_{x_i} \sum_{i \in V} x_i \qquad\text{(cari set terbesar)}\\ \text{dengan syarat} \quad x_u + x_v \leq 1 \quad \forall (u, v) \in E.$$

MIS mempunyai pelbagai aplikasi praktikal. Dalam perancangan rangkaian wayarles, set bebas sepadan dengan sekumpulan pemancar yang semuanya boleh menyiar secara serentak tanpa gangguan sesama sendiri. Dalam penjadualan, ia memodelkan kumpulan tugas terbesar yang boleh dilaksanakan serentak memandangkan konflik sumber berpasangan. Dalam biologi pengkomputeran, ia menangkap set protein yang tidak saling berinteraksi dalam suatu rangkaian.

Walaupun perumusannya intuitif, MIS adalah NP-hard, dan bahkan bagi graf dengan hanya beberapa ratus nod, tika tertentu menjadi sukar untuk diselesaikan secara tepat atau secara heuristik [2]. Masalah ini juga menghasilkan struktur kekangan jarang yang sangat sesuai untuk pelaksanaan perkakasan pengoptimuman kuantum, menjadikannya penanda aras yang menarik untuk peranti kuantum jangka pendek.

Aqarios Constrained Quantum Optimizer

Pendekatan standard untuk membenamkan masalah binari terkekang ke dalam pengoptimuman kuantum mengubah model tersebut menjadi format tanpa kekangan dengan menambah terma penalti: setiap kekangan yang dilanggar $x_u + x_v \leq 1$ menyumbang $2 x_u x_v$ kepada objektif peminimuman $-\sum_i x_i$. Ini dikendalikan secara automatik oleh Constrained Quantum Optimizer Qiskit Function.

Selain transformasi standard ini, pengoptimum mengenal pasti klik (cliques) dalam graf kekangan. Klik ialah set nod $V_C$ di mana setiap pasangan nod berkongsi tepi. Akibatnya, $\binom{|V_C|}{2}$ kekangan berpasangan $x_u + x_v \leq 1 \;\forall (u,v) \in E_C$ boleh digantikan dengan satu kekangan tunggal yang lebih ketat $\sum_{i \in V_C} x_i \leq 1$. Memperkenalkan pemboleh ubah kendur $y$ mengubah ini menjadi persamaan $\sum_i x_i + y = 1$, yang mengambil bentuk kekangan one-hot yang boleh dikuatkuasakan secara langsung dalam QAOA menggunakan XY-mixers [3]. Ini mengurangkan ruang carian dan mengelakkan keperluan terma penalti untuk kekangan tersebut, meningkatkan kualiti penyelesaian.

Selain itu, pemboleh ubah yang disambungkan kepada hanya satu jiran dipanggil nod pendant dan ditetapkan secara deterministik oleh algoritma sebelum pelaksanaan kuantum, seterusnya mengurangkan saiz masalah yang efektif.

Constrained Quantum Optimizer menggunakan pendekatan warm-starting berulang yang serasi dengan XY-mixers [1], yang secara beransur-ansur mengecilkan ruang carian dengan memberi bias kepada taburan keadaan kuantum ke arah kawasan penyelesaian yang menjanjikan merentasi iterasi. Ini membolehkan penggunaan parameter QAOA sudut tetap (fixed-angle), menghapuskan keperluan latihan parameter variasi. Keperluan sumber kuantum keseluruhan dikawal semata-mata oleh bilangan iterasi warm-start, yang bermakna kos kuantum mudah dikawal.

Keperluan

Sebelum memulakan tutorial ini, pastikan anda telah memasang keperluan 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)

Secara pilihan, untuk Lampiran anda perlu memasang

• Luna Model (pip install luna-model)

Persediaan

Import 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, sahkan diri menggunakan kunci API IBM Quantum anda. Kemudian, pilih Qiskit Function seperti berikut. (Kod ini mengandaikan anda telah menyimpan akaun anda ke persekitaran tempatan 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 kepada Masalah Kuantum

Masalah ini dirumuskan sebagai fail LP, iaitu format lazim untuk masalah pengoptimuman yang berfungsi sebagai input kepada Aqarios Constrained Quantum Optimizer. Selain fail LP, fungsi ini juga menyokong fail MPS dan representasi Luna Model asli. Fail LP dijana melalui langkah-langkah berikut:

1. Dapatkan contoh graf daripada QOBLIB [2]

2. Modelkan masalah pengoptimuman

3. Jana fail LP

Muatkan Graf Contoh Masalah

Graf-graf ditentukan dalam format DIMACS .gph, iaitu format berasaskan baris di mana baris yang bermula dengan e mentakrifkan tepi, baris yang bermula dengan p mentakrifkan pengepala masalah, dan baris yang bermula dengan c adalah komen:

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

Fail .gph boleh dimuat turun daripada repositori QOBLIB menggunakan fungsi berikut, yang juga menghurai (parse) fail tersebut menjadi graf NetworkX. Perhatikan bahawa format DIMACS menggunakan pelabelan nod berasaskan 1, yang ditukar kepada pengindeksan berasaskan 0 di sini.

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 tika es60fst02 daripada QOBLIB, iaitu graf dengan 186 nod dan 280 tepi. Berkat langkah-langkah pra-pemprosesan yang digunakan oleh Constrained Quantum Optimizer, tika ini boleh diselesaikan pada peranti Heron 156-qubit. Graf tersebut boleh divisualisasikan menggunakan matplotlib:

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

Bina Masalah Pengoptimuman

Masalah Maximum Independent Set boleh dirumuskan secara langsung menggunakan OptimizationProblem. Setiap nod graf menjadi pemboleh ubah keputusan binari, dan setiap tepi memperkenalkan kekangan yang memastikan paling banyak satu hujungnya 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)

Jalan pintas

Pakej qiskit-addon-opt-mapper menyediakan kelas aplikasi sedia ada untuk masalah Maximum Independent Set, yang memudahkan perumusan di atas menjadi satu panggilan sahaja:

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

Terjemah Masalah kepada Fail LP

OptimizationProblem itu sendiri tidak menyokong eksport fail LP, tetapi ia boleh beroperasi bersama DOcplex, yang menyokongnya. Menjana kandungan fail LP 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 adalah asli kepada Constrained Quantum Optimizer.

Langkah 2: Optimumkan Masalah untuk Pelaksanaan Perkakasan Kuantum

Semua sintesis litar, pengoptimuman, dan transpilation dikendalikan secara asli oleh fungsi ini. Lihat bahagian input dalam rujukan API untuk argumen yang digunakan untuk memanggil fungsi tersebut.

Untuk menala halus kelakuan algoritma, lihat senarai Options dalam rujukan API. Jika anda mahu pemetaan litar boleh dihasilkan semula merentas larian, tetapkan pilihan seed_transpiler.

Untuk maklumat lanjut, lihat panduan Aqarios Constrained Quantum Optimizer dan rujukan API.

Langkah 3: Laksanakan menggunakan Qiskit Primitives

Fail LP kini boleh dihantar kepada pengoptimum:

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 dalaman, algoritma ini melalui peringkat-peringkat berikut:

1. Preprocessing:

   • Kurangkan pemboleh ubah yang boleh ditetapkan

   • Cari klik (cliques)

   • Kenal pasti jenis kekangan

   • Nilaikan faktor penalti untuk terma penalti

   • Guna pakai transformasi kekangan

   • Sintesiskan litar dengan kaedah penguatkuasaan kekangan

   • Penghampiran masalah dan transpilation

2. Rantaian selari gelung berulang:

   • Sampel daripada litar dengan parameter tetap

   • Guna pakai pascapemprosesan

   • Nilai dan tetapkan kebarangkalian warm-starting yang baharu

3. Postprocessing:

   • Cari sampel terbaik dan semak kebolehlaksanaan berkenaan masalah input

Pantau Kemajuan

Lihat bahagian-bahagian berikut dalam halaman Get started with Qiskit Functions untuk memantau kemajuan job anda:

• Semak status job

• Dapatkan hasil

# Monitor the job status
job.status()

'QUEUED'

Langkah 4: Pascaproses dan Kembalikan Hasil dalam Format Klasik yang Dikehendaki

Output hasil adalah sebuah dictionary, yang medan-medannya diterangkan dalam bahagian Outputs rujukan API.

Apabila senarai solutions mengandungi lebih daripada satu entri, ini bermakna beberapa optima degenerat telah ditemui. Hanya penyelesaian pertama dipertimbangkan di sini, dirujuk melalui nama pemboleh ubah. Penyelesaian yang sama juga tersedia sebagai bitstring dalam solution_bitstrings, di mana metadata.solver_info.variable_mapping memberikan kedudukan aksara bagi setiap pemboleh ubah.

# 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

Set bebas yang dikenal pasti boleh divisualisasikan dengan menonjolkan nod 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 ini juga menerima model yang dicipta dengan Luna Model [4], SDK pemodelan Aqarios. Selepas memasang pakej PyPI luna-model, import pakej tersebut seperti berikut:

Setup:

from luna_model import Model, Sense
import numpy as np

Model tersebut kemudian dibina daripada graf dengan cara yang sama seperti dengan qiskit-addon-opt-mapper: Bina 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 Seterusnya

Cadangan

• Rujuk panduan Aqarios Constrained Quantum Optimizer untuk penerangan terperinci tentang semua ciri fungsi ini.
• Terokai rujukan API untuk senarai penuh parameter input dan medan output.
• Cuba pelbagai pilihan algoritma (reps, num_parallel, shots, postprocessing_level) pada masalah pengoptimuman binari terkekang anda sendiri untuk menilai kesannya terhadap kualiti penyelesaian dan masa larian.

Rujukan

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