Aqarios Constrained Quantum Optimizerで最大独立集合を求める

注記

Qiskit Functionsは実験的機能であり、IBM Quantum® Premium Plan、Flex Plan、およびOn-Prem(IBM Quantum Platform API経由)Planのユーザーのみが利用できます。これらはプレビューリリースの状態であり、変更される可能性があります。

使用量の目安: Heron r2プロセッサーで30秒。(注: これはあくまで目安です。実際の実行時間は変動する場合があります。)

背景

このチュートリアルでは、Aqarios Constrained Quantum Optimizer [1]を使用して、制約付き組み合わせ最適化問題であるグラフの最大独立集合を求める方法を示します。 QOBLIB [2]ベンチマークライブラリのインスタンスは二値線形計画問題として定式化され、Optimizer Application Functionに渡されます。オプティマイザーは、再定式化、回路合成、トランスパイル、および反復的なウォームスタートのすべてを内部で処理します(詳細は[3]を参照してください)。

このチュートリアルでは、次のステップを扱います。

qiskit-addon-opt-mapperのOptimizationProblemを使用して、問題を線形計画問題として定義する
Aqarios Constrained Quantum Optimizerを使用して量子最適化を実行する
結果を取得し可視化する

最大独立集合問題

最大独立集合(MIS)問題は、組み合わせ最適化における基本的な課題です。形式的には、グラフ $G(V, E)$ が与えられたとき、目標は $V_I$ 内のいずれの2頂点も辺で結ばれていないような頂点の最大部分集合 $V_I \subset V$ を見つけることです。これは $\nexists (u, v) \in E : v \in V_I \wedge u \in V_I$ と表されます。各頂点には二値決定変数 $x_i \in \{0, 1\}$ が割り当てられ、各辺に対して、その端点のうち高々1つしか選択されないことを保証する制約 $x_u + x_v \leq 1$ が導入されます。したがって、この問題は次の最大化問題として述べることができます。

\max_{x_i} \sum_{i \in V} x_i \qquad\text{(最大集合を求める)}\\ \text{s.t.} \quad x_u + x_v \leq 1 \quad \forall (u, v) \in E.

MISには幅広い実用的な応用があります。無線ネットワークの計画では、独立集合は互いに干渉することなく同時に送信できる送信機のグループに対応します。スケジューリングでは、ペアごとのリソース競合がある中で同時に実行できる最大のタスク集合をモデル化します。計算生物学では、ネットワーク内で互いに相互作用しないタンパク質の集合を捉えます。

直感的な定式化にもかかわらず、MISはNP困難であり、数百ノード程度のグラフであっても、特定のインスタンスは厳密解法でもヒューリスティック解法でも解くことが困難になります[2]。この問題はまた、量子最適化のハードウェア実装に適したスパースな制約構造を生み出すため、近い将来の量子デバイスにとって魅力的なベンチマークとなっています。

Aqarios Constrained Quantum Optimizer

制約付き二値問題を量子最適化に埋め込む標準的なアプローチは、ペナルティ項を追加することでモデルを制約なしの形式に変換します。違反した各制約 $x_u + x_v \leq 1$ は、最小化目的関数 $-\sum_i x_i$ に $2 x_u x_v$ を加えます。これはConstrained Quantum Optimizer Qiskit Functionによって自動的に処理されます。

この標準的な変換に加えて、オプティマイザーは制約グラフ内のクリークを識別します。クリークとは、すべてのノードのペアが辺を共有するノード集合 $V_C$ のことです。その結果、 $\binom{|V_C|}{2}$ 個のペアワイズ制約 $x_u + x_v \leq 1 \;\forall (u,v) \in E_C$ を、単一のより厳しい制約 $\sum_{i \in V_C} x_i \leq 1$ に置き換えることができます。スラック変数 $y$ を導入すると、これは等式 $\sum_i x_i + y = 1$ になり、これはXYミキサー[3]を用いてQAOAで直接強制できるワンホット制約の形をとります。これにより探索空間が縮小され、これらの制約に対するペナルティ項が不要になり、解の質が向上します。

さらに、隣接ノードが1つしかない変数はペンダントノードと呼ばれ、量子実行前にアルゴリズムによって決定的に固定され、実効的な問題サイズをさらに縮小します。

Constrained Quantum Optimizerは、XY-mixers[1]と互換性のある反復的なウォームスタートアプローチを採用しており、反復を重ねるごとに量子状態分布を有望な解の領域へと偏らせることで、探索空間を段階的に狭めていきます。これにより固定角度QAOAパラメータの使用が可能になり、変分パラメータの学習が不要になります。量子リソースの総所要量はウォームスタートの反復回数のみによって決まるため、量子コストの制御が容易になります。

要件

このチュートリアルを開始する前に、以下の要件がインストールされていることを確認してください。

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)

オプションとして、付録のために以下をインストールする必要があります。

Luna Model(pip install luna-model)

セットアップ

必要な依存関係をすべてインポートします。

# 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

まず、IBM Quantum APIキーを使用して認証を行います。次に、以下のようにQiskit Functionを選択します。(このコードは、すでにアカウントを保存してローカル環境に設定済みであることを前提としています。)

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

ステップ1: 古典的な入力を量子問題にマッピングする

この問題は、Aqarios Constrained Quantum Optimizerへの入力となる、最適化問題の一般的な形式であるLPファイルとして定式化されます。LPファイルに加えて、この関数はMPSファイルとネイティブのLuna Model表現もサポートしています。 LPファイルは、次の手順で生成されます。

QOBLIB[2]からグラフインスタンスを取得する
最適化問題をモデル化する
LPファイルを生成する

問題インスタンスのグラフを読み込む

グラフはDIMACSの.gph形式で指定されます。これは行ベースの形式であり、eで始まる行は辺を定義し、pで始まる行は問題ヘッダーを定義し、cで始まる行はコメントです。

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

.gphファイルは、以下の関数を使用してQOBLIBリポジトリからダウンロードでき、この関数はそれをNetworkXグラフにパースも行います。なお、DIMACS形式は1始まりのノードラベリングを使用しますが、ここでは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.

この例では、QOBLIBのes60fst02インスタンス(186ノード、280辺のグラフ)を使用します。Constrained Quantum Optimizerが採用する前処理ステップのおかげで、このインスタンスは156量子ビットのHeronデバイスで解くことができます。グラフはmatplotlibを使用して可視化できます。

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

Output of the previous code cell

最適化問題を構築する

最大独立集合問題は、OptimizationProblemを使用して直接定式化できます。各グラフノードは二値決定変数になり、各エッジはその端点のうち高々1つしか選択されないことを保証する制約を導入します。

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

ショートカット

qiskit-addon-opt-mapperパッケージは、最大独立集合問題向けにあらかじめ実装されたアプリケーションクラスを提供しており、上記の定式化を単一の呼び出しに簡略化できます。

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

問題をLPファイルに変換する

OptimizationProblem自体はLPファイルへのエクスポートをサポートしていませんが、それをサポートするDOcplexと相互運用可能です。LPファイルの内容を生成するには、わずか2行で済みます。

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

この形式は、Constrained Quantum Optimizerのネイティブ形式です。

ステップ2: 量子ハードウェア実行のために問題を最適化する

回路合成、最適化、トランスパイルはすべて関数によってネイティブに処理されます。関数を呼び出す際の引数については、APIリファレンスの入力セクションを参照してください。

アルゴリズムの動作を微調整するには、APIリファレンスのオプション一覧を参照してください。実行間で回路のマッピングを再現可能にしたい場合は、seed_transpilerオプションを固定してください。

詳細については、Aqarios Constrained Quantum OptimizerガイドおよびAPIリファレンスを参照してください。

ステップ3: Qiskitプリミティブを使用して実行する

これで、LPファイルをオプティマイザーに送信できます。

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

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

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

内部的には、アルゴリズムは次の段階を経て進行します。

Preprocessing:
- 固定可能な変数を削減する
- クリークを見つける
- 制約のタイプを識別する
- ペナルティ項のペナルティ係数を評価する
- 制約変換を適用する
- 制約強制手法を用いて回路を合成する
- 問題の近似とトランスパイル
反復ループの並列チェーン:
- 固定パラメータを用いて回路からサンプリングする
- 後処理を適用する
- 新しいウォームスタート確率を評価して設定する
Postprocessing:
- 最良のサンプルを見つけ、入力問題に対する実行可能性を確認する

進捗を監視する

ジョブの進捗を監視するには、「Get started with Qiskit Functions」ページの以下のセクションを参照してください。

# Monitor the job status
job.status()

'QUEUED'

ステップ4: 目的の古典的な形式に結果を後処理して返す

結果の出力は辞書であり、そのフィールドはAPIリファレンスの出力セクションで説明されています。

solutionsリストに複数のエントリが含まれる場合、複数の縮退した最適解が見つかったことを意味します。ここでは最初の解のみを扱い、各値には変数名でアクセスします。同じ解はsolution_bitstringsにビット列としても用意されており、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) + "}")

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}

可視化

特定された独立集合は、グラフ内の選択されたノードを強調表示することで可視化できます。

# 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 of the previous code cell

付録: Luna Modelによる問題記述

上記で示したqiskit-addon-opt-mapperによるアプローチに加えて、このQiskit Functionは、AqariosのモデリングSDKであるLuna Model[4]で作成されたモデルも受け付けます。 luna-modelのPyPIパッケージをインストールした後、次のようにインポートします。

Setup:

from luna_model import Model, Sense
import numpy as np

その後、モデルはqiskit-addon-opt-mapperの場合と同様の方法でグラフから構築されます。 モデルを構築する:

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

次のステップ

推奨事項

すべての関数機能の詳細な説明については、Aqarios Constrained Quantum Optimizerガイドを参照してください。
入力パラメータと出力フィールドの完全な一覧については、APIリファレンスを参照してください。
制約付き二値最適化問題に対してアルゴリズムのオプション(reps、num_parallel、shots、postprocessing_level)を試し、解の質と実行時間への影響を評価してください。

参考文献

IBM Quantum、Aqarios Constrained Quantum Optimizer Guide
Koch et al. (2026), The Quantum Optimization Benchmarking Library 10.1038/s43588-026-00991-1
Bucher et al. (2026), Constrained Quantum Optimization via Iterative Warm-Start XY-Mixers 10.1088/1367-2630/ae8ea2
Aqarios GmbH, Luna Model Docs

背景​

最大独立集合問題​

Aqarios Constrained Quantum Optimizer​

要件​

セットアップ​

ステップ1: 古典的な入力を量子問題にマッピングする​

問題インスタンスのグラフを読み込む​

最適化問題を構築する​

ショートカット​

問題をLPファイルに変換する​

ステップ2: 量子ハードウェア実行のために問題を最適化する​

ステップ3: Qiskitプリミティブを使用して実行する​

進捗を監視する​

ステップ4: 目的の古典的な形式に結果を後処理して返す​

可視化​

付録: Luna Modelによる問題記述​

次のステップ​

参考文献​

背景