量子断熱条件から量子アニーリングの収束条件を導出.どれくらいゆっくり制御すればよいか

量子コンピュータ

最近,量子アニーリングを勉強している大学院生です.学部では物理,大学院では機械や情報を専攻しています.

今回は,量子アニーリングの収束条件の話です.

量子アニーリングとは,最適化手法の一つです.

量子アニーリングでは,焼きなまし法(SA,シミュレテッドアニーリング)と同様,制御変数をゆっくりと小さくしていかなければ正しい解にたどり着けません.

では,どれくらい「ゆっくり」変数を小さくすればよいのか?を解説することがこの記事の目的です.

今回も,こちらの本を参考にさせて頂きます.

量子アニーリングとは

量子アニーリングは,主に組合せ最適化問題を解くための手法です.

シミュレテッドアニーリングでは熱揺らぎを用いて最適解を探索するのに対して,

量子アニーリングでは量子揺らぎを用いて最適解を探索します.

また,シミュレテッドアニーリングでは大域的に解を探すために最初は温度高くし,徐々に下げていって解を発見するのに対し,

量子アニーリングでは,横磁場(量子効果を及ぼす項)を徐々に小さくしていきます.

より詳細な説明は,こちらをご覧ください.

以降を読むには,量子力学の基本知識が必要です

量子断熱条件

量子アニーリングの収束条件を説明する前に,量子断熱条件を説明しておく必要があります.

結論から言うと,量子断熱条件は以下の通りです.

量子断熱条件

ハミルトニアンH(t)において,定常固有状態を|j(t)>とする.t=0に基底状態|0(t)>から出発したとき,時刻tにおいて系が励起状態|j(t)> ( j \geq 1)に存在する確率は,次の関係が満たされている限り,十分小さい.

   \[\frac{1}{\Delta_j(t)^2}\left|<j(t)|\dot{\hat{H}}(t)|0(t)>\right| \ll 1\]

\dot{\hat H}はハミルトニアン(演算子)の時間微分,\Delta_j(t)は状態|j(t)|0(t)のエネルギー差(エネルギーギャップ)を表す.

すなわち,この条件を常に満たすように量子アニーリングを実行すれば,常に基底状態を追えることができ,正解にたどり着けるわけですね.

常に基底状態にいるには,各時刻のエネルギーギャップが大きくなければいけませんが,その「どれくらいエネルギーギャップが大きければOKか?」をこの条件式が与えてくれているというわけです.

それでは,この条件式を導出していきます.

量子断熱条件の導出

方針としては,シュレディンガー方程式に従う励起状態の出現確率が十分小さいという式を導出していきます.

t=0からt=\tauまでの時間発展を考えます.

量子アニーリングに使うハミルトニアンを,以下のように書きます.

   \[\hat H(t) = \frac{t}{\tau} \hat H_0 - \left(1-\frac{t}{\tau} \right) \sum_{i}\hat \sigma^x_i\]

ここで,s = \frac{t}{\tau}と置きます.

   \[\hat H(s) = s \hat H_0 - \left(1-s \right) \sum_{i}\hat \sigma^x_i\]

このとき,シュレディンガー方程式は,s = \frac{t}{\tau}を変数として表記すると

   \[i\frac{d}{ds}|\psi(s)> = \tau \hat H(s)|\psi(s)>\]

となります.

また各状態に対する固有方程式を以下のように書きます.

   \[\hat H(s)|j(s)> = \epsilon_j(s)|j(s)>\]

実対称行列\hat H(s)の固有ベクトルの完全性により,|\psi(s)を各固有状態|j(s)>で展開して書くことができます.

   \[\psi(s)> = \sum_j c_j(s)e^{i\tau\phi_j}|j(s)>\]

ここで

   \[\phi_j(s)=\int_{0}^{s}ds'\epsilon_j(s')\]

です.このc_j(s)が,状態|j(s)>の存在確率となっています.

この展開した|\psi(s)>を,シュレディンガー方程式に代入して,存在確率c_j(s)についての方程式に直していきます.

|\psi(s)> = \sum_j c_j(s)e^{i\tau\phi_j}|j(s)>を先ほどのシュレディンガー方程式に代入すると,その左辺は

   \[i\sum_j \left( \dot c_j(s)e^{-i\tau\phi_j(s)}|j(s)>-i\tau c_j(s)\epsilon_j(s)e^{-i\tau \phi_j(s)}|j(s)> +c_j(s)e^{-i\tau \phi_j(s)}\frac{d}{ds}|j(s)> \right)\]

となり,右辺は

   \[\tau\sum_j c_{j}(s)\epsilon_j(s)e^{-i\tau \phi_j(s)}|j(s)>\]

となります.これら2つの式に左から<k(s)|をかけて内積をとって等しいと置くと,

   \[\frac{d}{ds}c_k(s)=\sum_{j(\neq k)}c_j(s) \frac{e^{i\tau (\phi_k(s)-\phi_j(s))}}{\epsilon_k(s)-\epsilon_j(s)}<k(s)|\dot{\hat{H}}(s)|j(s)>\]

となります.ただし,この式に変形するために以下の2つの式を用いました.

   \[<k(s)|\frac{d}{ds}|j(s)>= \frac{1}{\epsilon_j(s)-\epsilon_k(s)}<k(s)|\dot{\hat{H}}(s)|j(s)> (k\neq j)\]

   \[<k(s)|\frac{d}{ds}|k(s)>=0\]

この2つの式の証明は,ここでは省略します.最初に紹介した本には書いてあります.

このc_k(s)に関する微分方程式を積分すると,

   \[c_k(s)=c_k(0)+\sum_{j(\neq k)} \int_{0}^{s}du c_j(u) \frac{e^{i\tau (\phi_k(u)-\phi_j(u))}}{\epsilon_k(u)-\epsilon_j(u)}<k(u)|\dot{\hat{H}}(u)|j(u)>\]

が得られます.

これで,量子断熱条件の導出のほとんどの部分は終わりました.あとは,\tauが十分小さい時に,励起状態|k(s)>の出現確率c_k(s) (k \neq 0)が十分小さいということを考えればOKです.

初期状態では,基底状態のみが出現しているとします.

   \[c_0(0) =1\]

   \[c_k(0) = 0\]

また,十分ゆっくり時間発展させ,系が基底状態に留まる状況を考えると,次のように書けると予想されます.

   \[c_0=1-\mathcal{O}(\tau^{-1})\]

   \[c_k(s) = \mathcal{O}(\tau^{-1}) (k \neq 0)\]

実際,このような形になることは後の結果から分かります.

先ほどの積分した結果であるc_k(s)は,これらの近似を踏まえると,c_0(u)以外の項はc_0(u)に比べて\tauオーダー高いので,\tauが十分大きい今は無視できますから,

   \[c_k(s)=\int_{0}^{s}du c_j(u) \frac{e^{i\tau (\phi_k(u)-\phi_0(u))}}{\epsilon_k(u)-\epsilon_0(u)}<k(u)|\dot{\hat{H}}(u)|0(u)>+\mathcal{O}(\tau^{-2})\]

となります.これを部分積分すると,以下が得られます.

   \[c_k(s)=\frac{i}{\tau} \left( A_k(0) - e^{i\tau (\phi_k(s)-\phi_0(s))} A_k(s) \right)+\mathcal{O}(\tau^{-2})\]

   \[A_k(s) = \frac{1}{\Delta_k(s)^2}<k(s)|\dot{\hat{H}}(s)|0(s)>\]

   \[\Delta_k(s)=\epsilon_k(s)-\epsilon_0(s)\]

さて,これらの式から,励起状態|k(s)>の出現確率が\tau \ll 1で十分小さいためには

   \[\tau \ll \frac{1}{\Delta_k(s)^2}\left| <k(s)|\dot{\hat{H}}(s)|0(s)>\right|\]

となります.変数とt=s\tauに直して表記すると量子断熱条件

   \[\frac{1}{\Delta_k(t)^2}\left| <k(t)|\dot{\hat{H}}(t)|0(t)>\right| \ll 1\]

が得られます.

(量子断熱条件の導出終わり)

量子アニーリングの収束条件

さて,量子断熱条件を紹介したところで,量子断熱条件を満たすような制御変数\Gammaはどのようなものかを考えていきましょう.

結論から先に言うと,以下のようにすれば,量子断熱条件が満たされ,量子アニーリングにより基底状態を求めることができます.

収束条件

\Gamma(t)を単調減少正値関数であるとすると,

   \[\Gamma(t) = a(\delta t + c)^{-1/(2N+1)}\]

となる.

Nはスピンの数であり,問題の大きさです.acNによらない定数で,\deltaは1より十分小さい値です.

色々定数がくっ付いていますがacはあまり気にせず,時間tの関数として,Nに対してどのような形で減少する関数なのかに注目すればOKです.

この式をtについて解くと,\Gammaが十分小さい値\epsilonになるまでの時間は,

   \[t \propto \exp\left( a|\log\epsilon|N\right)\]

となり,指数時間かかります.

このように,アニーリング法は汎用性が高い分,計算時間は比較的ゆっくりでないと正解にたどり着けない可能性があります.

シミュレテッドアニーリングとの比較

ちなみに,シミュレテッドアニーリング(焼きなまし法)の収束条件は,制御変数T(t)を用いて

   \[T(t) \geq \frac{aN}{\log(\alpha t +1)}\]

と表され,T(t)が十分小さい値\epsilonになるときにtについて解くと

   \[t \propto \exp\left( \frac{b}{\epsilon}N\right)\]

なので,やはり指数時間かかります.しかし,指数の方の部分に注目すると,小さい\epsilonに対して|\log\epsilon|の方が1/\epsilonよりも小さいため,シミュレテッドアニーリングよりも量子アニーリングの方が速くなることが確認できます.

アニーリング法は指数時間かかるということを述べましたが,実際に実行する場合には,そこまでの時間を書けなくとも正しい解にたどり着ける場合が多いです.

それでは,以降で量子アニーリング制御変数の収束条件を導出していきます.

収束条件の導出

量子断熱条件を満たすように,制御変数の形を決定します.

量子アニーリングのハミルトニアンは

   \[\hat H(t) = \hat H_0 - \Gamma(t)\sum_{i=1}^{N}\hat \sigma_i^x\]

です(これがどういう意味かは,<↑|猫でもわかる量子アニーリングの理論|↓>を参考にしてください).

これを用いて量子断熱条件の左辺の分子について評価すると,

   \[\left|<j(t)|\dot{\hat{H}}(t)|0(t)>\right| \leq |\dot{\Gamma}| \left|\left<j(t)\left|\sum_{i=1}^{N}\hat \sigma_i^x\right|0(t)\right>\right| \leq -\dot{\Gamma}\sum_{i=1}^{N}|<j(t)|\hat \sigma_i^x|0(t)>|\leq -N\dot{\Gamma}\]

となります.初めの比較は絶対値を分けたほうが大きいというよくある比較で,2つ目の比較は\Gamma(t)が減少関数であるという仮定を用いています.3つ目の比較は,スピン部分の計算は最大でもNであるからです.

結論,

   \[\left|<j(t)|\dot{\hat{H}}(t)|0(t)>\right| \leq -N\dot{\Gamma}\]

となります.これで,断熱条件の分子についての評価は終わりです.次は分母のエネルギーギャップについての評価を行い,これらを合わせて収束条件を導いていきます.

分母のエネルギーギャップの評価をする準備のために,Hopfの定理を紹介しておきます.

Hopfの定理

正方行列\hat Mのすべての要素が正定値のとき,\hat Mの最大固有値\lambda_0と他の任意の固有値\lambdaは以下の関係を満たす.

   \[|\lambda| \leq \frac{\kappa-1}{\kappa+1}\lambda_0\]

ただし,

   \[\kappa = \max_{i,j,k} \frac{M_{ik}}{M_{jk}}\]

である.

さて,ではエネルギーギャップ\Delta_j(t)の下限を評価しましょう.

行列\hat M

   \[\hat M = (E_{+}-\hat H(t))^{N}\]

とします.ただし,E_{+}>E_{max}+\Gamma_0(\Gamma_0 = \Gamma(t_0))を満たす定数で,E_{max}\hat {H_0}の最大固有値です.\hat Mの各要素はある状態からある状態への遷移確率となります.

あるスピン状態はN回スピンを反転させることで他のどんなスピン状態にできるので,\hat Mのすべての行列要素は正定値であり,\hat MにはHopfの定理を適用することができます.

\hat Mの最小行列要素はN!\Gamma(t)^N,最大固有値は(E_+ - E_{min} + N\Gamma_0)^Nです.Hopfの定理における\kappaは,

   \[\kappa \leq \frac{(E_+ - E_{min} + N\Gamma_0)^N}{N!\Gamma(t)^N}\]

を満たします.そしてHopfの定理より,

   \[(E_+ - \epsilon_j(t))^N \leq \frac{\kappa -1}{\kappa +1}(E_+ - \epsilon_0(t))^N\]

となります.

これら2つの式を使ってエネルギーギャップを考えます.\kappa \leq 1, N \leq 1のとき,

   \[\frac{2}{N(\kappa+1)} \leq 1 -\left( \frac{\kappa-1}{\kappa+1} \right)^{\frac{1}{N}}\]

となることを 用いると,エネルギーギャップは

   \[\delta_j(t) = \epsilon_j(t) - \epsilon_0(t) \leq \frac{2(E_+ - \epsilon_0(t))N!}{N(E_+ - E_{min} + N\Gamma_0)^N}\Gamma(t)^N = A\Gamma(t)^N\]

となります.ここで,

   \[A = \frac{2(E_+ - \epsilon_0(t))N!}{N(E_+ - E_{min} + N\Gamma_0)^N}\]

と置きました.ANが十分大きいときにはスターリングの公式より,

   \[A \approx \frac{2\sqrt{2\pi N}(E_+ -\epsilon_0^{max})}{Ne^{N}}(\frac{N}{E_+ - E_{min} + N\Gamma_0})^N\]

となり,Nが十分に大きければ0に近づきます.

さて,まとめます.

断熱条件

   \[\frac{1}{\Delta_j(t)^2}\left|<j(t)|\dot{\hat{H}}(t)|0(t)>\right| \ll 1\]

   \[\left|<j(t)|\dot{\hat{H}}(t)|0(t)>\right| \leq -N\dot{\Gamma}\]

   \[\delta_j(t) \leq A\Gamma(t)^N\]

を代入すると,以下の方程式が得られます.

   \[-\frac{N}{A^2\Gamma(t)^{2N}}\frac{d\Gamma}{dt} = \delta \ll 1\]

これを\Gammaについて解くと,

   \[-\frac{1}{2N+1}\Gamma^{-(2N+1)} = \frac{A^2}{N}\delta t + D\]

   \[\Gamma = \left{ \frac{2N+1}{N}A^2 \right}^{-\frac{1}{2N+1}} \left(\delta t + \frac{N}{2N+1}\frac{D}{A^2} \right)^{-\frac{1}{2N+1}}\]

となります.ここで,Dは積分定数です.

Nが十分に大きい時には,

   \[\left{ \frac{2N+1}{N}A^2 \right}^{-\frac{1}{2N+1}} \approx a\]

   \[\frac{N}{2N+1}\frac{D}{A^2} \approx c\]

と置けるので,

   \[\Gamma = a\left(\delta t + c\right)^{-\frac{1}{2N+1}}\]

となり,断熱条件から収束条件を導くことができました.

(収束条件の導出終わり)

ちなみに

量子アニーリングマシンではなく,お手元のパソコンで量子アニーリングを実行する場合は,量子モンテカルロ法を使ったりします.

量子モンテカルロ法による量子アニーリングのアルゴリズムは以下の記事に書いたので,ぜひ参考にしてください.

コメント

タイトルとURLをコピーしました