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.

Quantum-enhanced Markov chain Monte Carlo

タグ: algorithm sample-based

このチュートリアルでは、Qamomileを使ってQuantum-enhanced Markov chain Monte Carlo (QeMCMC) Layden et al. (2023) を実装する例を示します。


背景

ボルツマン分布のサンプリング

多くの物理・工学的な問題では、ある確率分布μ(x)\mu(\bm{x})からサンプルx\bm{x}を得ることが重要な計算タスクになります。代表的な例が、統計力学におけるボルツマン分布です:

μ(x)=1Zexp⁡(−βE(x)),Z=∑xexp⁡(−βE(x)).\mu(\bm{x}) = \frac{1}{Z} \exp\bigl(-\beta E(\bm{x})\bigr), \quad Z = \sum_{\bm{x}} \exp\bigl(-\beta E(\bm{x})\bigr).

ここで、E(x)E(\bm{x})は状態x\bm{x}のエネルギー、β=1/T\beta = 1/Tは逆温度、ZZは分配関数と呼ばれる規格化定数です。 ボルツマン分布は熱平衡状態における状態x\bm{x}の確率分布を与えるだけでなく、これを目標分布とするサンプリングは組合せ最適化問題の解法としても広く利用されています。

ボルツマン分布のエネルギー関数の具体例として、イジング模型を考えてみましょう。イジング模型は、各サイトiiにスピン変数xi∈{−1,+1}x_i \in \{-1, +1\}が置かれた系で、そのエネルギーは次式で与えられます:

E(x)=−∑⟨i,j⟩Jij xixj−∑ihi xi.E(\bm{x}) = -\sum_{\langle i, j \rangle} J_{ij} \, x_i x_j - \sum_i h_i \, x_i.

ここで、JijJ_{ij}はスピン間の相互作用、hih_iはサイトiiにかかる外部磁場です。状態の総数は2n2^nと指数的に増えるため、nnが大きい場合には分配関数ZZを厳密に計算することは困難です。そこで、μ(x)\mu(\bm{x})から直接サンプルを得る手法として、後述するMCMCが利用されます。

まずは、小さなイジング模型について実際にボルツマン分布を可視化してみましょう。ここでは、1次元強磁性イジング鎖(Ji,i+1=1J_{i,i+1} = 1、hi=0h_i = 0)を考え、逆温度β\betaを変えながら、エネルギーE(x)E(\bm{x})ごとの確率を集計したヒストグラムをプロットします。

<Figure size 1200x350 with 3 Axes>

マルコフ連鎖モンテカルロ法 (MCMC)

マルコフ連鎖モンテカルロ法 (MCMC) は、確率分布からのサンプリングに使用される一般的な手法です。MCMCはマルコフ連鎖と呼ばれる確率過程を利用することで、目的の分布μ(x)\mu(\bm{x})からのサンプリングを実現します。ここでは、MCMCの代表的な実装であるMetropolis-Hastings (MH) アルゴリズム Hastings (1970) を紹介します。

MHアルゴリズムは、ある提案確率Q(y∣x)Q(\bm{y}|\bm{x})に従ってマルコフ連鎖の新たな遷移x→y\bm{x} \rightarrow \bm{y}を生成し、次の採択確率

A(y∣x)=min⁡(1,μ(y)μ(x)⋅Q(x∣y)Q(y∣x)).A(\bm{y} | \bm{x}) = \min \left(1, \frac{\mu(\bm{y})}{\mu(\bm{x})} \cdot \frac{Q(\bm{x} | \bm{y})}{Q(\bm{y} | \bm{x})} \right).

に従って採用または棄却するという2つのステップからなります。この一連の手順により、時刻ttの状態から時刻t+1t+1の状態を生成します。十分な時間が経過したのちには、このマルコフ連鎖の状態はサンプリングしたい分布μ(x)\mu(\bm{x})に従います。よって、十分に遷移を重ねることで、得られるマルコフ連鎖の状態列{x(t)}\{\bm{x}^{(t)}\}を目的のサンプルとして利用できます。

実際に確認してみましょう。先ほど用意したボルツマン分布をMH法でサンプリングしてみます。提案分布にはさまざまなものが使えますが、ここでは最もシンプルな、ランダムなスピンを1つだけ選んで反転させるものを利用します。

次に、採択確率に従って、提案された遷移を確率的に処理するステップを実装します。この提案分布はQ(x∣y)=Q(y∣x)Q(\bm{x} \mid \bm{y}) = Q(\bm{y} \mid \bm{x})を満たすため、採択確率においてQQの比は打ち消されます。したがって、目的分布をボルツマン分布とすると、採択確率は以下の簡潔な形になります:

A(y∣x)=min⁡(1,μ(y)μ(x))=min⁡(1,exp⁡(−β(E(y)−E(x)))).A(\bm{y} | \bm{x}) = \min \left(1, \frac{\mu(\bm{y})}{\mu(\bm{x})}\right) = \min \left(1, \exp(-\beta (E(\bm{y}) - E(\bm{x})))\right).

これでMCMCが実装できました。それでは、MCMCを使ってサンプリングしてみましょう。

得られたサンプル列がボルツマン分布に従っているかを確認しましょう。得られたサンプルを用いて、ボルツマン分布μ(x)\mu(\bm{x})に関する物理量を推定してみます。ここでは、スピンの平均磁化:

⟨m⟩=∑xμ(x)m(x)\langle m \rangle = \sum_{\bm{x}} \mu(\bm{x}) m(\bm{x})

を推定します。磁化は、

m(x)=1n∑i=1nxim(\bm{x}) = \frac{1}{n} \sum_{i=1}^n x_i

です。平均磁化は磁化のボルツマン分布に関する期待値なので、サンプル数を増やすとともに、得られたサンプル列がボルツマン分布に近いほど推定精度はよくなるはずです。MCMCのtt番目までのサンプルによる推定量mˉt\bar{m}_tをプロットしてみましょう。

<Figure size 640x480 with 1 Axes>

アルゴリズム

Quantum-enhanced MCMCアルゴリズムは、量子回路からのサンプリングを提案分布として利用するMCMCです Layden et al. (2023)。現在の状態x\bm{x}から始め、量子回路UUを作用させて計算基底で測定することで、新たな状態y\bm{y}を得ます。このとき、提案分布Q(y∣x)Q(\bm{y}|\bm{x})は以下のようになります:

Q(y∣x)=∥⟨y∣U∣x⟩∥2Q(\bm{y}|\bm{x}) = \| \langle \bm{y} | U | \bm{x} \rangle \|^2

この確率を直接計算するのは困難ですが、量子回路がU=U⊤U = U^\topを満たすとき、提案分布はQ(x∣y)=Q(y∣x)Q(\bm{x} \mid \bm{y}) = Q(\bm{y} \mid \bm{x})を満たし、採択確率の中でQQの項は打ち消されるため、QQを明示的に計算する必要がなくなります。例えば、イジング模型のボルツマン分布をサンプリングするためには、時間に依存しないハミルトニアンによるTrotter化された時間発展を利用できます:

U(γ,t)=exp⁡(−iHt),H=(1−γ)αHM+γHC.U(\gamma, t) = \exp(-i H t), \quad \quad H = (1-\gamma) \alpha H_M + \gamma H_C.

ここで、HMH_Mはミキサーハミルトニアンと呼ばれ、状態間の量子遷移を生み出します。一方、HCH_Cはイジングハミルトニアンです。γ∈[0,1]\gamma \in [0,1]は2つの項の重みを制御するパラメータです。α\alphaは、ミキサーハミルトニアンとコストハミルトニアンの固有値のスケールを揃えるための規格化因子です。(γ,t)(\gamma, t)はMCMCの効率を決める調整可能なパラメータです。


アルゴリズムの実装

1. ハミルトニアンの準備

いよいよ、アルゴリズムを実装していきましょう。まず、サンプリングしたいモデルのイジングハミルトニアンHCH_Cと、提案回路UUのためのミキサーハミルトニアンHMH_Mを準備します。

2. 量子回路の構築

次に、量子回路を実装していきましょう。まず、現在の状態x\bm{x}を入力状態として符号化するため、computational_basis_stateを用いて量子状態∣x⟩\ket{\bm{x}}を準備します。提案遷移にはTrotter分解に基づく時間発展シミュレーションを利用します。先ほど準備したハミルトニアンに対する回路を、trotterized_time_evolutionを使って構築します。

3. トランスパイル

カーネルをトランスパイルします。量子回路を実行するには、ハミルトニアンの混合係数γ\gammaとシミュレーション時間ttを固定する必要があります。 に従い、γ=0.45\gamma=0.45、t=12t=12、Δt=0.8\Delta t = 0.8と設定します。トランスパイル時にn、order、time、stepをバインドし、input_bitsはランタイムパラメータとして残します。

4. 量子回路をMCMCに組み込む

これで量子回路シミュレーションの準備が整いました。最後に、量子計算のブロックをMCMCに組み込みましょう。回路の入力および出力はビット列x∈{0,1}n\bm{x} \in \{0,1\}^nであるため、スピン変数s∈{1,−1}n\bm{s} \in \{1, -1\}^nとの変換も準備しておきます。


実行例

実装したQeMCMCアルゴリズムを実行してみましょう。先ほどよりも低温の β=1.0\beta = 1.0 に設定し、古典MCMCの局所更新では混合が遅くなる条件で量子提案分布の挙動を観察します。公平な比較のため、同じ β=1.0\beta = 1.0 で古典MCMCも併走させます。

平均磁化の推定量を計算し、同じ β=1.0\beta = 1.0 で実行した古典MCMCの結果と比較します。

<Figure size 640x480 with 1 Axes>

まとめ

本チュートリアルでは、古典的なMetropolis-Hastings法によるMCMCの復習からはじめ、量子回路U(γ,t)=exp⁡(−itH)U(\gamma, t) = \exp(-i t H)(H=(1−γ)HM+γHCH = (1-\gamma) H_M + \gamma H_C)を提案分布として利用するQuantum-enhanced MCMC (QeMCMC) をQamomile上で実装しました。具体的には、qamomile.observableでミキサー/コストハミルトニアンを準備したうえで、@qkernelの中でtrotterized_time_evolutionを用いたSuzuki-Trotter時間発展による提案回路を構築しました。最後に、トランスパイルされたexecutorを介して量子提案分布を既存のMHループに組み込み、古典MCMCとQeMCMCを同一のイジング鎖上で走らせて平均磁化の収束を比較することで、一連の量子古典ハイブリッドループが意図どおり動作することを確認しました。

References
  1. Layden, D., Mazzola, G., Mishmash, R. V., Motta, M., Wocjan, P., Kim, J.-S., & Sheldon, S. (2023). Quantum-enhanced Markov chain Monte Carlo. Nature, 619(7969), 282–287. 10.1038/s41586-023-06095-4
  2. Hastings, W. K. (1970). Monte Carlo sampling methods using Markov chains and their applications. Biometrika, 57(1), 97–109. 10.1093/biomet/57.1.97