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

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

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

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

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

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

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

リンク

量子アニーリングとは
量子断熱条件
1. 量子断熱条件の導出
量子アニーリングの収束条件
1. シミュレテッドアニーリングとの比較
2. 収束条件の導出

量子アニーリングとは

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

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

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

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

量子アニーリングでは，横磁場（量子効果を及ぼす項）を徐々に小さくしていきます．

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

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

量子断熱条件

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

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

量子断熱条件

ハミルトニアン $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) = a(\delta t + c)^{-1/(2N+1)}$

$N$ はスピンの数であり，問題の大きさです． $a$ や $c$ は $N$ によらない定数で， $\delta$ は１より十分小さい値です．

色々定数がくっ付いていますが $a$ や $c$ はあまり気にせず，時間 $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$

です（これがどういう意味かは，＜↑｜猫でもわかる量子アニーリングの理論｜↓＞を参考にしてください）．

この先は執筆途中です．近日公開します

（ちなみに）

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

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