ここでは量子アニーリングマシンのみに焦点を当てて、量子アニーリングではどのような原理で最適解を探索しているのかを解説し、量子アニーリングシミュレータを作ろうに繋げます。このページはかなり上級者向けの内容となっているので注意してください。
マシンを使うだけならばこのページの内容は不要ですので飛ばしても大丈夫です。しかし量子アニーリングマシンは発展途上の段階にあるため、様々なチューニングや新機能を試すような深い使いこなしには、実装や原理に関する知識がある程度は必要になります。
量子アニーリングの原理 #
量子アニーリングマシンでは、前ページで解説したイジング模型が物理的に実装されています。この物理的なイジング模型の実際のパラメータに、解きたい問題をマッピングすることで、マシンが実現されます。
これまではイジング模型をただのエネルギー関数という形で扱ってきました。変数は \(\sigma \in \left\{ -1, +1 \right\}\) を取る値でしかありませんでした。以降は物理的にモデル化されたイジング変数であることを意識するために、イジング変数を物理学の用語を用いて「スピン」と呼びます。量子アニーリングマシンにおけるスピンはいわゆる量子ビットに対応します。このページでは、(イジング) 変数、スピン、量子ビットという様々な呼び方を使っていきますが、全て同じものです。ただ、イジング変数と言った場合には最適化関数を、スピンと言った場合には物理的状態を意識して使い分けようと思います。
アルゴリズムの概要 #
量子アニーリングは外部からイジング模型を時間変化させることで実現されます。しかし、単純にこれまで扱ってきたイジング模型の相互作用や磁場のパラメータのみを時間変化させるのではなく、新たに「量子ゆらぎ」と呼ばれる項を追加し、これを制御します。そして、アニーリング開始時刻 ( \(t=0\) ) では量子ゆらぎの項のみ、終時刻 ( \(t=\tau\) ) では最適化したいイジング模型のみになるよう、状態の入れ替えを行います。
式で表すと、量子アニーリングは下記のように表現されます。
\[ H_{\mathbf{QA}} \left(t\right) = A\left(t\right) H_A + B\left(t\right) H_B \]ここで、 \(H_A\) は量子効果を表す項を、 \(H_B\) は最適化したい関数の項をそれぞれ表します。スケジュール \(A\left(t\right)\) , \(B\left(t\right)\) は任意ですが、
\[ \begin{aligned} H_{\mathbf{QA}} \left(0\right) = A\left(0\right) H_A \\ H_{\mathbf{QA}} \left(\tau\right) = B\left(\tau\right) H_B \end{aligned} \]となることを要請します。つまり、有効的に
\[ B\left(0\right) / A\left(0\right) = 0, \quad A\left(\tau\right) / B\left(\tau\right) = 0 \]とします。
量子効果を表す \(H_A\) は、イメージとしては量子力学的な重ね合わせの強さを表します。初期時刻では全ての取りうる状態が重ね合わせの状態にあるのですが、これを徐々に弱くしていくと同時にエネルギー関数の項を強くすることで、終時刻ではエネルギーの低い最適解近傍のみ重ね合わせとして残ることを期待します。アニーリング (焼きなまし法) の量子版なので、これのアナロジーから量子アニーリングと呼ばれます。
量子アニーリングがどのような原理で最適解を探索しているのかを理解するためには、ある程度量子力学の知識が必要になりますが、ポイントとしては下記です。
- 量子ビット (スピン) の状態を複素ベクトルで表現する
- エネルギー関数をハミルトニアンと呼ばれる演算子(行列)で表現する
- ハミルトニアンを用いてシュレディンガー方程式を解く
- 得られた状態ベクトルの時間変化から最適解が得られる確率やエネルギー期待値を求める
イジング模型の量子化 #
量子アニーリングの概念自体は、エネルギー関数がイジング模型であることや、量子ゆらぎの具体的な形について仮定をしません。しかし現在の実装では、エネルギー関数をイジング模型として、量子ゆらぎを「横磁場」と呼ばれる項で導入しているため、これに即して具体的な説明を行います。
量子統計物理学のイジング模型を出発点とすると、物理の知識が背景に必要になってしまいます。そのため、どのようにしたらイジング模型が量子ビットの持つ「重ね合わせの性質」を実現できるか、逆説的に考えてみたいと思います。
量子ビットにおける重ね合わせの性質を式で表すと、次のようなベクトルの線形結合で表されるということでした。
\[ \left| \psi \right\rangle = a \left| \uparrow \right\rangle + b \left| \downarrow \right\rangle \]ここで左辺は量子ビット(つまりスピン)の状態を、右辺の \(\left| \uparrow \right\rangle\) , \(\left| \downarrow \right\rangle\) はそれぞれスピンの値 \(+1\) , \(-1\) を表しています。 また、 \(a, b\) は一般に複素数の値です。つまり量子ビットが \(\pm 1\) を同時に持つという表現を、係数 \(a, b\) を通じて互いがどういう強さで重ね合いにあるか定式化しています。
量子ビットの状態を \(\uparrow, \downarrow\) といった記号ではなく、ベクトルとして表現するためには、 \(\left| \uparrow \right\rangle\) , \(\left| \downarrow \right\rangle\) をそれぞれわかりやすい基底ベクトルに対応させれば良いです。つまり、 \[ \left| \uparrow \right\rangle = \binom{1}{0}, \quad \left| \downarrow \right\rangle = \binom{0}{1} \]
と選べば、量子ビットの状態は2次元の複素ベクトルで表すことが出来て、
\[ \left| \psi \right\rangle = \binom{a}{b} \]と書けます。これを状態ベクトルと呼びます。
次のステップとして、この量子ビットの状態ベクトルを量子力学のルールに従わせます。状態ベクトルが時間変化しない場合、時間に依存しないシュレディンガー方程式
\[ H \left| \psi \right\rangle = E \left| \psi \right\rangle \]の解になる必要があります。左辺の \(H\) は行列、右辺の \(E\) はスカラーです。 この方程式は \(H\) に対する固有方程式になっていて、 \(E\) はエネルギーを意味する固有値、 \(\left| \psi \right\rangle\) は状態の固有ベクトルです。
では行列 \(H\) はどのように作ったら良いか考えてみます。先ほど、1量子ビット (= 1スピン) の状態を \(\left| \uparrow \right\rangle\) , \(\left| \downarrow \right\rangle\) の線形結合で書き、それぞれを基底ベクトルに対応させました。 これらは正規直交基底なので、シュレディンガー方程式の解である固有ベクトルになっています。
一方、1スピンに対するエネルギー関数を最も単純化して下記とします。
\[ E = - \sigma_1 \]イジング変数は \(\sigma_1 = \pm1\) なので、 それぞれ \(E = \mp 1\) になります。 \(\sigma = 1\) の状態を \(\left| \uparrow \right\rangle\) 、 \(\sigma = -1\) の状態を \(\left| \downarrow \right\rangle\) と表すことを思い出すと、 それぞれに対応する \(E\) の値はシュレディンガー方程式の固有値になっています。
ということは、行列 \(H\) を下記のような対角行列で表現すると良さそうです。
\[ H = \begin{pmatrix} -1 & 0\\ 0 & 1 \end{pmatrix} \]この \(H\) に対してシュレディンガー方程式を解くと、解はそれぞれ、
\[ \left| \psi \right\rangle = - \binom{1}{0}, \qquad \left| \psi \right\rangle = \binom{0}{1} \]が得られます。
このように表したエネルギー固有値を持つ行列 \(H\) をハミルトニアンと呼びます。 \(H\) は行列なのでベクトルに対する演算子になっています。 量子力学で記述することにより、
\[ \text{エネルギー} E \quad \left(\text{スカラー}\right) \quad \rightarrow \quad \text{ハミルトニアン} H \quad \left(\text{行列} \right) \]という拡張が行われたとみなすことも出来ます。
複数スピンのハミルトニアン #
こんどは複数スピンにおけるハミルトニアンを考えてみます。まずは2スピンのエネルギー関数が下記で表されているとします。
\[ E = -J_{12} \sigma_1 \sigma_2 - h_1 \sigma_1 - h_2 \sigma_2 \]2スピンの取り得る状態は4通りです。二つのスピンをまとめて
\[\left| \uparrow \uparrow \right\rangle, \left| \uparrow \downarrow \right\rangle, \left| \downarrow \uparrow \right\rangle, \left| \downarrow \downarrow \right\rangle \]と書くことにします。右の矢印をスピン1、左の矢印をスピン2と考えることにしました。これらをベクトルで表して、
\[ \left| \uparrow\uparrow\right\rangle = \begin{pmatrix} 1\\ 0\\ 0\\ 0 \end{pmatrix}, \quad \left| \uparrow\downarrow \right\rangle = \begin{pmatrix} 0\\ 1\\ 0\\ 0 \end{pmatrix}, \quad \left| \downarrow \uparrow\right\rangle = \begin{pmatrix} 0\\ 0\\ 1\\ 0 \end{pmatrix}, \quad \left| \downarrow \downarrow \right\rangle = \begin{pmatrix} 0\\ 0\\ 0\\ 1 \end{pmatrix} \]とします。これらは正規直交基底になっています。
それではそれぞれに対応するエネルギーを調べてみます。1スピンの場合と同じようにハミルトニアンの対角項を埋めていきますが、1行目は \(\uparrow \uparrow\) つまり \(\sigma_1 = 1,\quad\sigma_2 = 1\) の時の \(E\) の値が入り、同様に2行目は \(\sigma_1 = -1,\quad\sigma_2 = 1\) の時の \(E\) 、3行目は \(\sigma_1 = 1,\quad\sigma_2 = -1\) の時の \(E\) 、4行目は \(\sigma_1 = -1,\quad\sigma_2 = -1\) の時の \(E\) と並びます。
\[ H = \begin{pmatrix} -J_{12} - h_1 - h_2 & 0 & 0 & 0\\ 0 & J_{12} - h_1 + h_2 & 0 & 0\\ 0 & 0 & J_{12} + h_1 - h_2 & 0\\ 0 & 0 & 0 & - J_{12} + h_1 + h_2 \end{pmatrix} \]このように複数のスピンについて拡張していくことができます。 \(N\) スピンの状態数は \(2^N\) なので、ハミルトニアンのサイズ、固有ベクトルのサイズ、固有値の数も \(2^N\) あることになります。そしてハミルトニアンの対角項にはそれぞれのスピンの状態から計算されるエネルギーの値が入ることになります。
横磁場 (量子効果) の導入 #
上記のハミルトニアンは最適化したい関数のみを考慮した場合、つまり \(H = H_B\) という状況でした。次に量子効果 \(H_A\) について説明します。
\(H_A\) はおおざっぱに言ってしまうとハミルトニアンの非対角成分のことです。どのように非対角成分を埋めるのかに任意性はあるのですが、典型的には横磁場1という形で導入されます。ハミルトニアンが対角成分だけの場合には、エネルギー(スカラー)をハミルトニアン(行列)で表した意義はそれほどなかったのですが、非対角成分の導入により、いよいよ量子力学らしくなってきます。
ここからはエネルギー関数ではなく、ハミルトニアンを出発点とします。そして、これまでの最適化ターゲットに対するスピンを \(\sigma^z\) 、横磁場に対応するスピンを \(\sigma^x\) と表すことにします。例えば、
\[ H_A = - \Gamma \sigma^x, \quad H_B = - J \sigma^z \] \[ H = H_A + H_B \]とした場合のハミルトニアンを考えてみます。これから説明しますが、 \(\sigma^z\) と \(\sigma^x\) は同じスピンに対する別の見方を表しています。 \(H_B\) の行列表現は前節で述べたように対角部分にエネルギー値を全通りを並べたものでした。
\[ H_B = \begin{pmatrix} -J & 0\\ 0 & J \end{pmatrix} \]\[H_B = - J \sigma^z\] と上式を見比べると、
\[ \sigma^z = \begin{pmatrix} 1 & 0\\ 0 & -1 \end{pmatrix} \]となっていることに気づきます。エネルギー関数のみを考えていたときには、 \(\sigma\) はただの変数値でしたが、エネルギー関数がハミルトニアンとして行列で表されることで、スピンも行列化されたことになります。
一方で、 \(\sigma^z\) が対角行列であるのに対し、 \(\sigma^x\) は下記の非対角行列で定義されます。
\[ \sigma^x = \begin{pmatrix} 0 & 1\\ 1 & 0 \end{pmatrix} \]この行列 \(\sigma^x\) 演算子には興味深い性質があり、スピンの方向をフリップします。
\[ \sigma^x \left| \uparrow \right\rangle = \begin{pmatrix} 0 & 1\\ 1 & 0 \end{pmatrix} \binom{1}{0} = \binom{0}{1} = \left| \downarrow \right\rangle \] \[ \sigma^x \left| \downarrow \right\rangle = \begin{pmatrix} 0 & 1\\ 1 & 0 \end{pmatrix} \binom{0}{1} = \binom{1}{0} = \left| \uparrow \right\rangle \]上の1スピンのハミルトニアンを行列形式で書くと下記のようになります。
\[ H = H_A + H_B = \begin{pmatrix} -J & -\Gamma\\ -\Gamma & J \end{pmatrix} \]つぎに2スピンの場合を考えてみます。 \(H_A = -\Gamma \left(\sigma_1^x + \sigma_2^x \right)\) とすると、1スピンの場合で見たように、 \(\sigma_1^x\) と \(\sigma_2^x\) はそれぞれ自身のスピンを反転するため、
\[ \sigma_1^x \left| \uparrow \uparrow \right\rangle = \left| \uparrow \downarrow \right\rangle, \quad \sigma_2^x \left| \uparrow \uparrow \right\rangle = \left| \downarrow \uparrow \right\rangle, \cdots \]という性質があります。つまり、
\[ H_A = \begin{pmatrix} 0 & -\Gamma & -\Gamma & 0\\ -\Gamma & 0 & 0 & -\Gamma\\ -\Gamma & 0 & 0 & -\Gamma\\ 0 & -\Gamma & -\Gamma & 0 \end{pmatrix} \]となります。これを言い換えると、非対角座標 \(i\) , \(j\) のうち、行番号 \(i\) に対して1スピン(ビット)反転した列 \(j\) の要素に横磁場の値が入ります。 例えば、 \(H_A\) の1行目は \(\left| \uparrow \uparrow \right\rangle\) が対応しますが、スピン1が反転すると \(\left| \uparrow \downarrow \right\rangle\) 、スピン2が反転すると \(\left| \downarrow \uparrow \right\rangle\) なのでそれぞれ1行2列目、1行3列目が埋まります。 これを全行で繰り返すと上のように非対角成分の一部が埋まることになります。
これは \(N\) スピンの場合にも同様です。横磁場による量子揺らぎを用いると、各行に対して1スピンだけ異なる列が横磁場の値で埋まります。そしてそれ以外の非対角要素は0です。 \(H_B\) のように対角項だけなら固有値・固有状態(固有ベクトル)は自明で互いに独立ですが、次で見るように非対角項 \(H_A\) が導入されることで、ある状態と別の状態の間で遷移が発生します。これをトンネル効果と呼ぶこともあります。
ハミルトニアンの時間変化 #
量子アニーリングは対角行列であるターゲット関数と非対角項の量子効果を時間変化させ、初期時刻では \(H_A\) のみ、終時刻では \(H_B\) のみが有効になるようにします。
\[ H_{\mathbf{QA}} \left(t\right) = A\left(t\right) H_A + B\left(t\right) H_B \] \[ H_{\mathbf{QA}} \left(0\right) = A\left(0\right) H_A \quad \rightarrow \quad H_{\mathbf{QA}} \left(\tau\right) = B\left(\tau \right) H_B \]まず、時刻 \(t = 0\) において初期状態をセットします。初期状態は \(H_A\) の基底状態 (固有値(エネルギー)最小に対応する固有状態) を選びます。 \(H_A\) として横磁場を用いる場合、
\[ H_A = - \sum_i^{N}{\sigma_i^x} \]の基底状態はすべてのスピンの組合わせ状態を等確率でもつ自明な状態です。つまり、
\[ \left| \psi_{t=0} \right\rangle = \begin{pmatrix} \frac{1}{2^{N/2}}\\ \frac{1}{2^{N/2}}\\ \vdots\\ \frac{1}{2^{N/2}}\\ \frac{1}{2^{N/2}} \end{pmatrix} \]を初期状態として設定します。この状態は量子アニーリングマシンで比較的容易に実現できると思われます。 初期状態のハミルトニアンは \(H \left(0\right) = A\left(0\right) H_A\) になっていますが、ここから \(A\left(t\right)\) , \(B\left(t\right)\) を変化させ、終時刻 \(\tau\) では \(H = B\left(\tau\right) H_B\) になるようにハミルトニアンを時間変化します。
行列形式で全体のハミルトニアンは書くと、下記のような時間変化する \(2^N \times 2^N\) 行列になっています。
\[ H \left (t \right )= \begin{pmatrix} B\left (t \right )E_{2^N-1} & -A\left (t \right ) & \cdots & 0 & 0\\ -A\left (t \right ) & B\left (t \right )E_{2^N-2} & & -A\left (t \right )& 0\\ \vdots & & \ddots & & \vdots\\ 0 & -A\left (t \right ) & & B\left (t \right )E_{1} & -A\left (t \right ) \\ 0 & 0 & \cdots& -A\left (t \right ) & B\left (t \right )E_{0} \end{pmatrix} \]このハミルトニアンを用いて、シュレディンガー方程式を解くことで状態ベクトルが記述されます。
断熱量子計算 #
時間に対して極めてゆっくりと変化させた場合(断熱変化)、初期状態のエネルギーレベル(固有値順で何番目の固有状態か)が維持されます。たとえば初期状態が基底状態ならば、各時刻の状態 \(H \left(t \right)\) も常に基底状態であることが知られています。
そのまま終時刻まで極めてゆっくりと \(H\left(t\right)\) を変化させると、基底状態が維持されたまま、 \(H_B\) の基底状態に到達します。 \(H_B\) の基底状態とは解きたい最適化問題の最低エネルギー状態なので、最適解が得られることになります。
これが量子アニーリングにおける最適解探索の基本的なアイデアです。 \(H_B\) の詳細は知らなくても、自明な基底状態からスタートして、自動的に非自明な基底状態(最適解)に到達することになります。
極めてゆっくりと断熱的に変化させる場合、断熱量子計算 (Adiabatic Quantum Computation) とも呼ばれます。どういうスケジュール \(A\left(t\right)\) , \(B\left(t\right)\) を選ぶと最適解に到達することが保証されているか、どの程度ゆっくりにする必要があるのかについて、アニーリングの収束条件や断熱条件が詳細に調べられています。
各時刻の状態ベクトルは、時間に依存しないシュレディンガー方程式に従います。
\[ H \left| \psi \right\rangle = E \left| \psi \right\rangle \]状態ベクトルは時刻に依存しないため、初期状態が基底状態であれば最後まで基底状態のままですし、初期状態が励起状態 (エネルギーの高い状態) にあれば終時刻でも励起状態のままになります。
量子アニーリング #
極めてゆっくりと変化させるようなスケジュールを選べば必ず最適解が得られることはわかっていても、現実的には適当な時間で終了させる必要があります。また1回の試行で必ずしも最適解に到達できなくても、現実的な試行回数で到達することが期待できれば十分であり、また近似的に精度の良い解が得られれば十分という場合もあるかと思います。量子アニーリングは、ハミルトニアンの時間変化による最適解探索に関する広い概念であり、基底状態を必ずたどる量子断熱発展も含みます。
量子アニーリングのように時間変化するハミルトニアンの場合には、状態ベクトルは下記の依存するシュレディンガー方程式に従います。
\[ \imath \hbar \frac{\mathrm{d} }{\mathrm{d} t}\left| \psi \left (t \right ) \right\rangle = H \left (t \right ) \left| \psi \left (t \right ) \right\rangle \]理想的な量子アニーリングマシンを用いた場合、量子ビットの状態はこの微分方程式に忠実に従うことが期待されます。
まとめ #
- 量子アニーリングマシンの量子ビットはイジング模型で記述される
- ユーザは解きたい問題をイジング模型に変換しパラメータをマシンにセットする
- 問題に対応したイジング模型と量子効果を表す項を時間変化させることで最適解を探索する
- 横磁場を用いる場合1スピン(1ビット)変化する非対角要素が与えられる
- 適切なスケジュールの元で、極めてゆっくりと時間変化させると、最適解に到達することが保証されている
- 理想的な量子アニーリングマシンはシュレディンガー方程式に従った時間発展を行う
- 極めてゆっくりの場合: 固有方程式 (時間に依存しないシュレディンガー方程式)
- 一般の時間変化の場合: 微分方程式 (時間に依存するシュレディンガー方程式)
-
これまで出てきた(縦)磁場hとは異なります。 ↩︎