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でMaxCutを解く: 回路をゼロから構築する

タグ: algorithm optimization variational

このチュートリアルでは、Qamomileの低レベル回路プリミティブを使って、QAOA (Quantum Approximate Optimization Algorithm) のパイプラインをステップごとに構築します。高レベルなQAOAConverterは使わずに、以下の手順で進めます:

  1. 小さなグラフでMaxCut問題を定義する。

  2. スピン変数上のIsingモデルとして直接定式化する。

  3. @qkernelを使ってQAOA回路をステップごとに記述する。

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

  5. 結果をデコードして可視化する。

最後に、qamomile.circuit.algorithm.qaoa_stateが同じ回路を1つの関数呼び出しで提供することを示します。

MaxCut問題とは?

無向グラフG=(V,E)G = (V, E)が与えられたとき、MaxCut問題は頂点を2つの集合に分割し、2つの集合間を横切る辺の数を最大化する問題です。

MaxCutは本来、スピン変数で記述するのが自然な問題です。各頂点iiにスピンsi∈{+1,−1}s_i \in \{+1, -1\}を割り当て、頂点がどちら側に属するかを表現します。辺(i,j)(i, j)が「カットされる」のはsi≠sjs_i \ne s_jのときなので、カットされる辺数は

MaxCut(s)=∑(i,j)∈E1−sisj2\text{MaxCut}(\boldsymbol{s}) = \sum_{(i,j) \in E} \frac{1 - s_i s_j}{2}

と書けます。

MaxCutやスピングラス基底状態探索、Isingモデルベンチマークといったスピン変数で自然に定義される問題は、スピン領域で記述するのが最もクリーンです。そこで本チュートリアルではQUBO/バイナリ変数への寄り道は挟まず、最初から最後までスピン変数で扱います。

グラフの作成

5頂点、6辺の小さなグラフを使います。全探索が可能な規模でありながら、自明でない構造を持っています。

<Figure size 500x400 with 1 Axes>

Ising定式化

∑(i,j)∈E(1−sisj)/2\sum_{(i,j) \in E} (1 - s_i s_j) / 2を最大化することは、定数を除いて以下の反強磁性Isingハミルトニアンを最小化することと等価です:

HC(s)=∑(i,j)∈Esisj.H_C(\boldsymbol{s}) = \sum_{(i,j) \in E} s_i s_j.

一般のIsing形式H=∑ihisi+∑i<jJijsisjH = \sum_i h_i s_i + \sum_{i < j} J_{ij} s_i s_jと比較すると、重みなしMaxCutは以下の特徴を持ちます:

  • 線形項なし: 全頂点についてhi=0h_i = 0

  • 一様な相互作用: 全辺(i,j)∈E(i, j) \in EについてJij=1J_{ij} = 1

BinaryModel.from_isingはIsing係数を直接受け取ります。QUBOを経由して変数型を変換する必要はありません。

Variable type:          SPIN
Linear terms (h_i):     {}
Quadratic terms (J_ij): {(0, 1): 1.0, (0, 2): 1.0, (1, 2): 1.0, (1, 3): 1.0, (2, 3): 1.0, (3, 4): 1.0}
Constant:               0.0

Note: BinaryModelはQUBO向けのfrom_qubo()や高次版のfrom_hubo()も提供しており、割当問題や制約(ペナルティ項)を伴う問題のようにバイナリ領域で自然に定式化される問題に利用できます。QUBO/JijModelingベースのワークフローについてはQAOAによるグラフ分割を参照してください。

厳密解(全探索)

QAOAを実行する前に、すべての2n=322^n = 32通りのスピン配置を試して最適な分割を求めておきます。QAOAの結果と比較するための基準になります。

Optimal MaxCut value: 5
Number of optimal partitions: 2
  (1, -1, -1, 1, -1)
  (-1, 1, 1, -1, 1)

QAOA回路: 基本的な考え方

QAOAのアンザッツはパラメータ付き量子状態を準備します:

∣γ,β⟩=∏l=1pe−iβlHM e−iγlHC  ∣+⟩⊗n|\boldsymbol{\gamma}, \boldsymbol{\beta}\rangle = \prod_{l=1}^{p} e^{-i \beta_l H_M} \, e^{-i \gamma_l H_C} \; |{+}\rangle^{\otimes n}

ここで:

  • ∣+⟩⊗n|{+}\rangle^{\otimes n}: 一様重ね合わせ(全量子ビットにHadamardゲート)

  • e−iγHCe^{-i \gamma H_C}: コストユニタリ — IsingコストHCH_Cの場合、二次項はRZZ\text{RZZ}ゲート、一次項はRZ\text{RZ}ゲートに分解されます(ゲートの規約についてはステップ2–3を参照)

  • e−iβHMe^{-i \beta H_M}: ミキサーユニタリ — HM=∑iXiH_M = \sum_i X_iの場合、各量子ビットへのRX(2β)\text{RX}(2\beta)になります

  • pp: レイヤー数(アンザッツの深さ)

スピンと計算基底の対応は量子力学の標準的な規約Z∣0⟩=∣0⟩Z|0\rangle = |0\rangle, Z∣1⟩=−∣1⟩Z|1\rangle = -|1\rangleに従います。すなわち、測定結果0はスピン+1、測定結果1はスピン-1に対応します。

各コンポーネントを@qkernelとして実装していきます。

ステップ1: 一様重ね合わせ

全量子ビットにHadamardゲートを適用し、均等な重ね合わせ状態∣+⟩⊗n|{+}\rangle^{\otimes n}を作ります。

ステップ2: コスト層

コストユニタリe−iγHCe^{-i \gamma H_C}を適用します。

Qamomileの回転ゲートは1/21/2の因子を含む規約を使います: RZ(θ)=e−iθZ/2\text{RZ}(\theta) = e^{-i \theta Z / 2}、RZZ(θ)=e−iθZ⊗Z/2\text{RZZ}(\theta) = e^{-i \theta Z \otimes Z / 2}。e−iγHCe^{-i \gamma H_C}と厳密に一致させるため、rzzには2Jijγ2 J_{ij} \gamma、rzには2hiγ2 h_i \gammaを渡します。

重みなしMaxCutではlinear引数は空ですが、そのまま引数として残しておきます。こうすることで、線形項hih_iを持つ重みつきMaxCutや一般のスピングラスハミルトニアンにそのまま流用できます。

ステップ3: ミキサー層

ミキサーユニタリe−iβHMe^{-i \beta H_M}を適用します(HM=∑iXiH_M = \sum_i X_i)。RX(θ)=e−iθX/2\text{RX}(\theta) = e^{-i \theta X / 2}なので、e−iβXie^{-i \beta X_i}を実装するにはθ=2β\theta = 2\betaとします。

ステップ4: 完全なQAOAアンザッツ

3つの要素を組み合わせます: 重ね合わせ → ppラウンドのコスト層 + ミキサー層 → 測定。

トランスパイルと最適化

カーネルをトランスパイルします。問題の構造(Ising係数、量子ビット数、レイヤー数)はバインドし、gammasとbetasはオプティマイザがチューニングするランタイムパラメータとして残します。

scipy.optimize.minimizeのCOBYLA法を使います。各反復で回路をサンプリングし、平均エネルギーを評価します。

本チュートリアルでは再現性を確保するため、(i)AerSimulatorにseed_simulator=SEEDを渡してショットごとの擬似乱数サンプリングを決定的にし、(ii)NumPy乱数生成器も同じ値でシードして初期変分パラメータを固定し、(iii)スレッド間で乱数ドローが交錯しないようmax_parallel_threads=1に設定します。シングルスレッド化は若干の性能低下と引き換えに完全な再現性を得るための設定で、実運用コードでは省略するか、テスト/ドキュメントビルド時のみ有効化する形で構いません。

Optimized cost: -0.8203
Optimal params: [np.float64(0.8871), np.float64(-0.1645), np.float64(2.0864), np.float64(0.7465), np.float64(-1.292), np.float64(1.4783)]
<Figure size 800x400 with 1 Axes>

結果のデコードと分析

最適化されたパラメータで回路をサンプリングし、測定結果を解釈します。decode_from_sampleresultはスピン領域(+1 / -1)のサンプルを返すので、バイナリ変換を挟まずに直接カット辺数を数えられます。

Best QAOA cut: 5  (optimal: 5)
Best partition (spins): [1, -1, -1, 1, -1]
<Figure size 800x400 with 1 Axes>
<Figure size 500x400 with 1 Axes>

組み込みのqaoa_stateを使う

上で実装したすべて — 重ね合わせ、コスト層、ミキサー層、レイヤーのループ — はqamomile.circuit.algorithm.qaoa_stateとして既に提供されています。同じIsing係数(quad, linear)と変分パラメータ(gammas, betas)を受け取ります。

組み込み関数を使って同じ構造の回路が実装されていることを確認します。下記の各executorは同じseed_simulator=SEEDで初期化されているため、シードを揃えた条件下では回路が完全一致しているならばサンプル列も平均エネルギーも完全一致します。なお、有限ショットによる推定誤差(shot noise)はシードを揃えても消えるわけではなく、各回路に対して常に存在します。したがって両者の平均エネルギーに差分が残る場合は、shot noiseが原因ではなく手動版と組み込み版の回路が(ゲート順序やコンパイル過程の違いなどで)ビット単位では一致していないことを示します。

同じ最適化済みパラメータでトランスパイル・サンプリングします。

Manual   mean energy: -0.8203
Built-in mean energy: -0.8203

まとめ

このチュートリアルでは:

  1. MaxCut問題を定義し、QUBO/バイナリ変数を経由せずに直接スピン変数上のIsingハミルトニアンとして記述しました。

  2. BinaryModel.from_isingでスピン領域のBinaryModelを構築しました。

  3. QAOA回路の全コンポーネント — 重ね合わせ、コスト層、ミキサー層、完全なアンザッツ — を@qkernelとして実装しました。

  4. 古典最適化ループを実行し、スピン領域のまま結果をデコードしました。

  5. qamomile.circuit.algorithm.qaoa_stateが同じ回路を1つの関数呼び出しで提供することを確認しました。

この「スピンから始める」レシピは、スピングラス基底状態探索、重みつきMaxCut、Sherrington–Kirkpatrickモデルといった任意のIsing型問題にそのまま適用できます。hih_iとJijJ_{ij}をBinaryModel.from_isingに渡し、上で作成した回路コンポーネントを再利用するだけです。

次のステップ:

  • バイナリ変数で自然に定式化される問題や、制約(ペナルティ項)が必要な問題については、JijModelingと高レベルのQAOAConverterを使うQAOAによるグラフ分割を参照してください。