Skip to article frontmatterSkip to article content
Site not loading correctly?

This may be due to an incorrect BASE_URL configuration. See the MyST Documentation for reference.

QAOA によるグラフ分割

タグ: algorithm optimization variational

本チュートリアルでは、Quantum Approximate Optimization Algorithm(QAOA)を用いてグラフ分割問題を解く方法を紹介します。

ワークフロー:

JijModeling 問題定義 → problem.eval() → QAOAConverter → transpile → sample → decode
  1. JijModeling で問題を定式化する。

  2. 具体的なデータでインスタンスを作成する。

  3. QAOAConverter を使って QAOA 回路とハミルトニアンを構築する。

  4. 古典オプティマイザで変分パラメータを最適化する。

  5. 最適化された回路をサンプリングし、結果をデコードする。

問題の定式化

無向グラフ G=(V,E)G = (V, E) が与えられたとき、頂点を同じサイズの 2 つのグループに分割し、グループ間のエッジ数を最小化することが目標です。

目的関数:

min⁡∑(u,v)∈E[xu(1−xv)+xv(1−xu)]\min \sum_{(u,v) \in E} \bigl[x_u(1 - x_v) + x_v(1 - x_u)\bigr]

制約条件:

∑u∈Vxu=∣V∣2\sum_{u \in V} x_u = \frac{|V|}{2}

ここで xu∈{0,1}x_u \in \{0, 1\} は頂点 uu がどちらのグループに属するかを表します。

JijModeling による問題定義

Loading...

グラフインスタンス

再現性を確保するため、8 ノード 16 エッジの固定グラフを使用します。

<Figure size 500x500 with 1 Axes>

インスタンスの作成

グラフからエッジリストを取得し、JijModeling の問題を具体的なデータで評価します。

QAOAConverter のセットアップ

QAOAConverter は OMMX インスタンスを受け取り、内部で以下を行います:

  1. 問題を QUBO(Quadratic Unconstrained Binary Optimization)形式に変換。

  2. BINARY 変数から SPIN 変数へ変換。

  3. Pauli-Z 演算子の和としてコストハミルトニアンを構築。

元の問題には制約があるため、QUBO 定式化では制約がペナルティ項として目的関数に組み込まれます。そのため、デコードされたサンプルのエネルギー値は元の目的関数(カットエッジ数)とは異なり、ペナルティを含んでいます。実行可能性の確認と真の目的関数値の計算を別途行う必要があります。

Hamiltonian((Z0, Z1): 1.0, (Z0, Z5): 1.0, (Z0, Z6): 1.0, (Z0, Z7): 1.0, (Z1, Z6): 1.0, (Z2, Z4): 1.0, (Z2, Z5): 1.0, (Z2, Z7): 1.0, (Z3, Z4): 1.0, (Z3, Z6): 1.0, (Z3, Z7): 1.0, (Z4, Z7): 1.0)

実行可能な回路へのトランスパイル

converter.transpile() は p 層の QAOA アンザッツ回路を構築し、ExecutableProgram にコンパイルします。変分パラメータ gammas(コスト層)と betas(ミキサー層)はランタイムパラメータとして残ります。

QAOA 回路の可視化

QAOAConverter._transpile_quadratic() は内部で次のサンプリング qkernel を組み立てて transpile します。チュートリアルでは可視化のため、その qkernel をそのままここに再掲します。Transpiler.to_block で IR ブロックに落とし、Transpiler.inline でサブ qkernel を展開してから MatplotlibDrawer.draw に渡すことで、コンバーターが内部で扱うのと同じ Block 構造を描画できます(レイヤー構造を読みやすくするため p=2 に縮小)。

<Figure size 10086x656 with 1 Axes>

内部の構成要素を見る

qaoa_sampling の中では qaoa_state を呼んでいますが、qaoa_state 自体は次の3つの組み合わせで構成されています:

  • superposition_vector(n) — 全ビットに H を作用させて初期状態 ∣+⟩⊗n|+\rangle^{\otimes n} を準備する。

  • ising_cost(quad, linear, q, gamma) — 二次項 quad の各エントリに対して RZZ、線形項 linear の各エントリに対して RZ を作用させるコスト層。今回の問題では線形項がない(linear={})ので RZZ だけが現れる。

  • x_mixer(q, beta) — 全ビットに RX(2\beta) を作用させるミキサー層。

qaoa_layers(p, ...) はこの ising_cost と x_mixer を p 回交互に作用させているだけです。各部品を個別に描画して中身を確認します。

<Figure size 600x656 with 1 Axes>
<Figure size 3832x656 with 1 Axes>
<Figure size 600x656 with 1 Axes>

QAOA パラメータの最適化

executable.sample() を使って各イテレーションでコストを評価します。オプティマイザはサンプリングされたビット列の平均エネルギーを最小化する gammas と betas を探索します。

Optimized cost: 15.799
Optimal params: [np.float64(0.8478), np.float64(-0.2839), np.float64(3.0681), np.float64(0.4712), np.float64(2.4944), np.float64(1.8724), np.float64(2.516), np.float64(0.743), np.float64(2.8569), np.float64(1.0257)]
Function evaluations: 103
<Figure size 800x400 with 1 Axes>

最適化されたパラメータでサンプリング

最適化されたパラメータを使い、回路をサンプリングしてビット列として候補解を取得します。

結果の分析

実行可能性のチェック

QAOAのサンプルは候補解であり、元の制約を満たすとは限りません。制約∑xu=∣V∣/2\sum x_u = |V|/2はQUBOのペナルティとして組み込まれているため、制約を満たさないビット列も出力に含まれる可能性があります。

SampleSet.summaryはショットごとに1行を持つDataFrameで、feasible列には元の制約に対する実行可能性がすでに格納されています。実行可能なショット数はそこから直接取得できます。

Feasible samples: 530 / 1000 (53.0%)

最良の実行可能解

SampleSet.best_feasibleは、実行可能解のうち目的関数値が最良(ここでは最小)のものを返します。コンバーターをOMMXのInstanceから構築しているため、報告される目的関数値は元のペナルティを含まないもの、すなわちカットエッジ数そのものです。決定変数の値はdecision_variables_dfに元の変数IDをキーとして格納されています。

Best feasible solution: {0: 0, 1: 0, 2: 0, 3: 0, 4: 1, 5: 1, 6: 1, 7: 1}
Cut edges:             6

目的関数値の分布

実行可能なサンプルのみについて、真の目的関数値(カットエッジ数)の分布を表示します。summaryにはショットごとに元の目的関数値が格納されているため、実行可能なスライスに対してvalue_counts()を呼ぶだけで分布が得られます。

<Figure size 800x400 with 1 Axes>

最良の分割の可視化

QAOA が見つけた最良の実行可能な分割に基づいて、グラフのノードを色分けします。

<Figure size 500x500 with 1 Axes>