Aqarios制約付き量子最適化ツールを使用して、最大独立集合を見つける

注

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

推定実行時間：Heron r2 プロセッサで 30 秒。（注：これはあくまで目安です。（実行時間は異なる場合があります。）

背景

このチュートリアルでは、 Aqarios Constrained Quantum Optimizer [1] を使用して、グラフの最大独立集合を求める方法について解説します。これは、制約付き組み合わせ最適化問題です。 QOBLIB [2] ベンチマークライブラリのインスタンスは、二値線形計画問題として定式化され、最適化アプリケーション関数に渡されます。オプティマイザは、すべての再定式化、回路合成、トランスパイル、および反復的なウォームスタートを内部で処理する（詳細については [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\}$ が割り当てられ、各辺に対して制約 $x_u + x_v \leq 1$ が導入される。これにより、各辺の端点のうち、選択されるのはせいぜい1つだけとなることが保証される。したがって、この問題は次のような最大化問題として定式化できる：

\max_{x_i} \sum_{i \in V} x_i \qquad\text{(find the largest set)}\\ \text{s.t.} \quad x_u + x_v \leq 1 \quad \forall (u, v) \in E.

MISには、幅広い実用的な応用分野があります。無線ネットワークの計画において、独立集合とは、相互に干渉することなく、すべて同時に送信できる送信機のグループを指します。スケジューリングにおいて、このモデルは、リソース間の2つごとの競合を考慮した上で、並行して実行可能なタスクの最大集合をモデル化しています。計算生物学において、これはネットワーク内で互いに相互作用しないタンパク質の集合を表す。

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

Aqarios 制約付き量子オプティマイザー

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

この標準的な変換に加え、オプティマイザは制約グラフ内のクリークを特定します。「クリーク」とは、 $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で直接適用可能なワンホット制約の形式をとる。これにより、探索空間が縮小され、それらの制約に対するペナルティ項を設ける必要がなくなるため、解の質が向上する。

さらに、単一の隣接ノードのみに接続されている変数は「 ペンダントノード」と呼ばれ、量子実行の前にアルゴリズムによって決定論的に固定されるため、有効な問題規模がさらに縮小される。

制約付き量子オプティマイザーは、XYミキサー [1] と互換性のある反復的なウォームスタート手法を採用しており、反復を重ねるごとに量子状態の分布を有望な解の領域へと偏らせることで、探索空間を段階的に絞り込んでいく。これにより、 固定角度のQAOAパラメータを使用できるようになり、変分パラメータ学習が不要になる。必要な量子リソースの総量は、ウォームスタートの反復回数によってのみ決まるため、量子コストは簡単に制御できる。

要件

このチュートリアルを始める前に、以下の要件が満たされていることを確認してください：

Qiskit Runtime (pip install qiskit-ibm-runtime)
Qiskit Functions Catalog IBM クライアント (pip install qiskit-ibm-catalog)
Qiskit アドオン「Optimization Mapper」(pip install qiskit-addon-opt-mapper)
NumPy (pip install numpy)
Matplotlib (pip install matplotlib)
NetworkX (pip install networkx)

必要に応じて、付録のために以下をインストールする必要があります

ルナ・モデル (pip install luna-model)

セットアップ

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

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関数を選択します。（このコードは、アカウントがすでにローカル環境に保存されていることを前提としています。）

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

ステップ1：古典的な入力を量子問題に写像する

この問題は、最適化問題で一般的に用いられる形式である LPファイルとして定式化されており、Aqarios Constrained Quantum Optimizerへの入力として使用されます。この機能は、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)

Output:

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:

最適化問題を定式化する

最大独立集合問題は、…を用いて直接定式化することができる 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）問題用のあらかじめ実装済みのアプリケーションクラスが用意されており、これにより上記の定式化が1回の呼び出しに簡略化されます：

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

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

このツール OptimizationProblem 自体はLPファイルへのエクスポートに対応していませんが、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("...")

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

この形式は、Constrained Quantum Optimizer に固有のものです。

ステップ2：量子ハードウェアでの実行に向けて問題を最適化する

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

アルゴリズムの動作を微調整するには、APIリファレンスの「オプション」リストを参照してください。

詳細については、『 Aqarios Constrained Quantum Optimizer 』のガイドおよび APIリファレンスをご覧ください。

ステップ 3: `Qiskit primitives` を使用して実行する

これで、LPファイルをオプティマイザーに送信できるようになりました：

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

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

Output:

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

アルゴリズムは内部的に、以下の段階を経て処理を進めます：

前処理 ：
- 修正可能な変数を減らす
- グループを探す
- 制約の種類を特定する
- ペナルティ条項に対するペナルティ要因を評価する
- 制約変換を適用する
- 制約を遵守させる手法を用いた回路の合成
- 問題の近似とトランスパイレーション
並列に実行される反復ループの連鎖 ：
- パラメータが固定された回路からのサンプル
- 後処理を適用する
- ウォームスタートの確率を評価し、新たに設定する
後処理 ：
- 最適なサンプルを見つけ、与えられた問題について実現可能性を確認する

進捗状況を監視する

ジョブの進行状況を監視するには、「 Qiskit Functions のはじめに」ページの以下のセクションを参照してください：

# Monitor the job status
job.status()

Output:

'QUEUED'

ステップ4：後処理を行い、結果を所望の従来の形式で出力する

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

リスト solutions に複数のエントリが含まれている場合、複数の縮退最適解が見つかったことになります。ここでは、最初の解のみを検討する：

# 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['obj_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}

視覚化

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

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

付録：ルナ・モデルを用いた問題定義

上記の手法 qiskit-addon-opt-mapper に加え、Qiskit Function では、Aqarios のモデリング SDK である Luna Model [4] を使用して作成されたモデルも利用可能です。 PyPIluna-model パッケージをインストールしたら、次のようにインポートしてください：

セットアップ

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(model=input_str, backend_name="ibm_fez")

ネクスト・ステップ

推奨事項

すべての機能の詳細な手順については、『 Aqarios Constrained Quantum Optimizer』ガイドを参照してください。
入力パラメータおよび出力フィールドの完全な一覧については、 APIリファレンスをご覧ください。
独自の制約付き二値最適化問題を用いて、アルゴリズムのオプション（reps, num_parallel, shots, postprocessing）を試行し、それらが解の品質や実行時間に与える影響を評価してください。

参照

IBM Quantum、『 Aqarios Constrained Quantum Optimizer』ガイド
Koch ら (2026)、 *「量子最適化ベンチマークライブラリ」 *10.1038/s43588-026-00991-1
Bucher ら (2026)、「 *反復ウォームスタートXYミキサーを用いた制約付き量子最適化」 *10.1088/1367-2630/ae8ea2
Aqarios GmbH, Luna モデルドキュメント

このページは役に立ちましたか？

バグや誤字の報告、またはコンテンツの要求はGitHubで行ってください。

Aqarios制約付き量子最適化ツールを使用して、最大独立集合を見つける

背景

最大独立集合問題

Aqarios 制約付き量子オプティマイザー

要件

セットアップ

ステップ1：古典的な入力を量子問題に写像する

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

最適化問題を定式化する

近道

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

ステップ2：量子ハードウェアでの実行に向けて問題を最適化する

ステップ 3: Qiskit primitives を使用して実行する

進捗状況を監視する

ステップ4：後処理を行い、結果を所望の従来の形式で出力する

視覚化

付録：ルナ・モデルを用いた問題定義

ネクスト・ステップ

参照

ステップ 3: `Qiskit primitives` を使用して実行する