量子アニーリングの原理について

量子アニーリングという言葉を初めて耳にした時から，ずっと気になっていた．なぜなら学生時代に材料工学を専攻していた私にとって，「量子」と「アニーリング」という言葉はどちらも聞き馴染みのある言葉だったからである．最近になって，やっと勉強を始めることができ，これから理論的な背景から応用までしっかり学んでいきたいと思っている．せっかくなので勉強した時のメモを少しずつブログにしていく予定である．

量子アニーリングとは
イジング模型
量子ゆらぎの導入
断熱変化
応用
参考

量子アニーリングとは

量子アニーリングとは，量子力学の法則を利用して，ある種の難しい問題を解くための枠組みである．その大きな特徴は，組み合わせ最適化問題に対するメタヒューリスティックな解法として利用可能な点である．組み合わせ最適化問題とは，離散値をとる多くの変数があるときに，それらの目的関数を最小化ないし最大化する問題である．この組み合わせ最適化問題をイジング模型の基底状態探索として表現し，量子力学的なゆらぎを利用して探索する方法が量子アニーリングである．

量子アニーリングは，シミュレーテッドアニーリングの量子力学版ともとらえることができる．温度の代わりに量子ゆらぎを導入し，古典的な確率過程の代わりに量子力学的な状態の重ね合わせを利用している．
量子アニーリングは1998年に以下の論文で提案されたものである．

arxiv.org

量子アニーリングをハードウェアの動作原理として実装したものには，カナダのベンチャー企業D-Wave Systemsによって開発されたD-Waveマシンなどがある．

イジング模型

量子アニーリングの原理を理解する出発点となるのがイジング模型である．量子アニーリングでは，最適化問題の目的関数を統計力学のイジング模型で表現し，イジング模型の基底状態（最低エネルギー状態）を探索することで最適解を得る．
イジング模型のハミルトニアンは以下のように表される．

$\displaystyle \hat{H_0}=-\sum_{i\verb|<|j}J_{ij}\hat{\sigma_i^z}\hat{\sigma_j^z}-\sum_{i=1}^Nh_i\hat{\sigma_i^z}$

$\hat{\sigma_i^z}$ はパウリ行列のz成分である．また， $i$ はイジング模型における格子点の番号， $J_{ij}$ は相互作用の強さ， $h_i$ は局所磁場の強さを表している．

イジング模型における格子点は，量子アニーリングマシンにおけるスピンいわゆる量子ビットに対応する．
ここで，量子ビットがもつ上向きスピン $+1$ および下向きスピン $-1$ という状態を以下のようにベクトルで表現する．

$\displaystyle \mid\uparrow\rangle= \begin{pmatrix} 1 \\ 0 \\ \end{pmatrix} , \mid\downarrow\rangle= \begin{pmatrix} 0 \\ 1 \\ \end{pmatrix}$

パウリ行列のz成分を上記の2つのベクトルに作用させると，

$\displaystyle \begin{pmatrix} 1 & 0 \\ 0 & -1 \\ \end{pmatrix} \begin{pmatrix} 1 \\ 0 \\ \end{pmatrix} = \begin{pmatrix} 1 \\ 0 \\ \end{pmatrix} , \begin{pmatrix} 1 & 0 \\ 0 & -1 \\ \end{pmatrix} \begin{pmatrix} 0 \\ 1 \\ \end{pmatrix} =- \begin{pmatrix} 0 \\ 1 \\ \end{pmatrix}$

となるから， $\binom{1}{0}$ は $\hat{\sigma_i^z}$ の固有値1の固有ベクトル， $\binom{0}{1}$ は固有値-1の固有ベクトルである．したがって， $\hat{\sigma_i^z}$ を上向きスピンと下向きスピンが同時に存在する量子力学的な重ね合わせの行列表現であると解釈できる．

一般の組み合わせ最適化問題は，多くの場合，前述のようなスピン間の相互作用をもつイジング模型の基底状態探索問題として表現できる．逆に言うと，基底状態が最適解になるように，解きたい最適化問題に合わせて $J_{ij}$ や $h_i$ を設定することができれば，量子アニーリングで最適化問題を解くことができる．

量子ゆらぎの導入

量子アニーリングでは，イジング模型の相互作用のパラメータや局所磁場のパラメータのみでなく，量子ゆらぎと呼ばれるものを導入する． $\hat{H_0}$ の基底状態を求めるために，量子力学的なゆらぎを利用して状態探索を行うのが量子アニーリングの基本戦略である．
量子ゆらぎを導入したハミルトニアンを以下の式で表す．

$\displaystyle \hat{H}(t)=\hat{H_0}+\Gamma(t)\hat{H_1}$

$\Gamma$ は量子ゆらぎの制御変数である．
初期状態 $t=0$ においては， $\Gamma$ を十分大きく選ぶことで右辺第1項を無視でき，第2項の量子ゆらぎの項のみとなる． $\Gamma$ を時間とともにだんだん小さくしていって，終状態 $t=T$ においては， $\Gamma(T)=0$ となり，最適化したい関数の項のみが残る．
ここで，初期ハミルトニアン $\hat{H_1}$ の基底状態が自明に見つかるように $\hat{H_1}$ を選ぶことが重要である．よく用いられる量子ゆらぎとして，横磁場があり，横磁場の効果を示すハミルトニアンを以下のように表す．

$\displaystyle \hat{H_1}=-\sum_{i=1}^N\hat{\sigma_i^x}$

$\hat{\sigma_i^z}$ はパウリ行列のx成分である． $\hat{\sigma_i^z}$ の固有ベクトルは，

$\displaystyle \begin{pmatrix} 0 & 1 \\ 1 & 0 \\ \end{pmatrix} \begin{pmatrix} 1 \\ 1 \\ \end{pmatrix} = \begin{pmatrix} 1 \\ 1 \\ \end{pmatrix} , \begin{pmatrix} 0 & 1 \\ 1 & 0 \\ \end{pmatrix} \begin{pmatrix} 1 \\ -1 \\ \end{pmatrix} =- \begin{pmatrix} 1 \\ -1 \\ \end{pmatrix}$

$\binom{1}{1}$ と $\binom{1}{-1}$ の二つである．
これらはいずれも $\binom{1}{0}$ と $\binom{0}{1}$ を同じ絶対値を持つ係数（1と1あるいは1と-1）で加えたものであるから， $\hat{\sigma_i^z}$ は上向きと下向きのスピンが等確率で重ね合わされた状態を表している．

$\hat{H_1}$ の基底状態は， $2^N$ 個の状態が重ね合わされて，量子力学の意味で同時に存在する．当然ながら，元のイジング模型のハミルトニアン $\hat{H_0}$ の基底状態はあらかじめわかっていないため， $2^N$ 個の全ての状態の同じ確率の重ね合わせを出発点として探索を始めることは理にかなっている．

$\hat{H_1}$ の自明な基底状態を初期状態として選び， $\hat{H}(t)$ で記述される系を時間に依存したシュレディンガー方程式に従って時間発展させる．

$\displaystyle i\frac{\partial}{\partial t}\mid\Psi(t)\rangle=\hat{H}(t)\mid\Psi(t)\rangle$

$\mid\Psi(t)\rangle$ は，各時刻における系の状態である．
このとき， $\Gamma(t)$ の時間変化が十分ゆっくりであれば，後述する量子力学の断熱定理が適用できる．

断熱変化

ハミルトニアン $\hat{H}(t)$ は時間変数 $t$ に依存するが，系が断熱的に（ゆっくりと）変化していると見なせる場合には，各時刻における系の状態 $\mid\Psi(t)\rangle$ は， $t$ を固定パラメータとみなしたときの定常状態のシュレディンガー方程式

$\displaystyle \hat{H}(t)\mid\Phi_t\rangle=E_0(t)\mid\Phi_t\rangle$

の基底状態 $\mid\Phi_t\rangle$ に十分に近い．実際の状態 $\mid\Psi(t)\rangle$ と定常基底状態が $\mid\Phi_t\rangle$ いずれも規格化されているとして，これらの内積が1に十分近いことを意味している．

$\displaystyle |\langle\Phi_t\mid\Psi(t)\rangle|^2=1-\delta^2\quad(\delta\ll1)$

これは各瞬間の基底状態をほぼ正確にたどっていくということを示している．
こうして，横磁場項 $\Gamma(t)\hat{H_1}$ により引き起こされる量子ゆらぎを $\Gamma(t)$ を通じて適切に制御することにより，自明な初期状態から出発して，非自明な状態である最適問題の解に到達する．以上が量子アニーリングの基本的な原理である．

応用

最後に少しだけ量子アニーリングの応用について触れる．最初に述べた通り，量子アニーリングの応用先として期待されているのは組み合わせ最適化問題である．（実際には機械学習のサンプリングにも有効であるそうだ）
一般的に組み合わせ最適化問題の例としてよく登場するものは，巡回セールスマン問題やナップサック問題などが挙げられる．一方，「量子アニーリングの基礎」の中で，クラスタリングが例に挙げられていたのが個人的には興味深かった．クラスタリングを組み合わせ最適化問題として考えたことはなかったが，ある点がどのクラスに属するかというのは直感的にも組み合わせであるし，異なるクラスに属する点の間の距離を最大化するという問題に読みかえれば組み合わせ最適化問題の目的関数として定式化できる．この辺りはもっと調べたいので，以下の論文などを読んで学んでいきたい．