補遺: シミュレーテッドアニーリング

シミュレーテッドアニーリングは、最適化問題に温度を入れる方法です。目的関数をエネルギーと見なし、高温では広く探索し、低温では低エネルギー状態へ集中させます。言葉だけなら素朴ですが、そこには統計力学、Markov連鎖、量子断熱定理までつながる一本の道があります。

ここではまず、固定した温度でBoltzmann分布をサンプルするMCMCを確認します。次に、温度をゆっくり下げるSAの考え方を述べ、Geman--Gemanの定理を紹介します。最後に、古典分布を量子状態へ写すと、SAの収束条件が量子断熱定理から出てくることを見ます。

GA・SA・QAとHopfの収束評価では、独立突然変異を持つ集団更新を正の行列として扱い、スペクトル評価の共通点と、最適解への収束証明の違いを比較します。

1. 最適化問題をBoltzmann分布に埋め込む

有限個の状態からなる集合を $\mathrm{\Omega }$ とします。組合せ最適化では、$\mathrm{\Omega }$ はビット列、スピン配位、経路、割当などの候補全体です。各状態 $x\in \mathrm{\Omega }$ に対して、最小化したいエネルギーを

$$E(x)$$

と書きます。最適解は

$$x_{\ast }\in \underset{x\in \mathrm{\Omega }}{\arg \min }E(x)$$

です。全探索すれば必ず見つかりますが、$\mathrm{\Omega }$ が指数的に大きいとすぐに破綻します。そこで、いきなり最小値を探す代わりに、温度 $T$ を導入してBoltzmann分布

$${\pi }_T(x)=\frac{1}{Z_T}\exp (-\frac{E(x)}{k_{\mathrm{B}}T}),Z_T=\sum _{x\in \mathrm{\Omega }}\exp (-\frac{E(x)}{k_{\mathrm{B}}T})$$

を考えます。$k_{\mathrm{B}}$ はBoltzmann定数です。計算機上のアルゴリズムでは、単位を選んで $k_{\mathrm{B}}=1$ と置くことも多いです。

逆温度

$$\beta =\frac{1}{k_{\mathrm{B}}T}$$

を使うと、${\pi }_T(x)\propto e^{-\beta E(x)}$ です。高温、つまり $\beta$ が小さいと、エネルギー差はあまり効かず、分布はほぼ一様になります。低温、つまり $\beta$ が大きいと、高エネルギー状態の重みは指数的に小さくなります。

最低エネルギー状態の集合を

$$\mathcal{G}=\{x\in \mathrm{\Omega }\mid E(x)=E_{min}\}$$

とすると、$T\to 0$ で分布は $\mathcal{G}$ に集中します。縮退があれば、最低エネルギー状態の間で重みが分かれます。

$$\underset{T\to 0}{lim}{\pi }_T(x)=\{\begin{array}{ll}1/|\mathcal{G}|,& x\in \mathcal{G},\\ 0,& x\notin \mathcal{G}.\end{array}$$

この式がSAの入口です。最適解を直接探す代わりに、低温のBoltzmann分布からサンプルできればよいです。問題は、その分布からどうやってサンプルするかです。

2. MCMCと釣り合い条件

MCMC、Markov chain Monte Carloでは、現在の状態 $x$ から次の状態 $y$ へ確率的に移ります。温度 $T$ での遷移確率を

$$P_T(x,y)=Pr(x_{t+1}=y\mid x_t=x)$$

と書きます。これは各 $x$ について

$$\sum _{y\in \mathrm{\Omega }}{P}_T(x,y)=1,P_T(x,y)\ge 0$$

を満たします。いま時刻 $t$ の分布が ${\mu }_t(x)$ なら、1ステップ後の分布は

$${\mu }_{t+1}(y)=\sum _{x\in \mathrm{\Omega }}{\mu }_t(x)P_T(x,y)$$

です。目標は、十分長く動かすと ${\mu }_t$ が ${\pi }_T$ へ近づくような $P_T$ を作ることです。

そのために必要なのが、釣り合い条件です。${\pi }_T$ が定常分布であるとは、

$${\pi }_T(y)=\sum _{x\in \mathrm{\Omega }}{\pi }_T(x)P_T(x,y)$$

がすべての $y$ で成り立つことを言います。右辺は、他の状態から $y$ へ流れ込む確率の総和です。左辺と一致していれば、分布 ${\pi }_T$ で始めたとき、1ステップ後も ${\pi }_T$ のままです。

同じことを確率流で書くと、

$$\sum _{y\in \mathrm{\Omega }}[{\pi }_T(x)P_T(x,y)-{\pi }_T(y)P_T(y,x)]=0$$

です。各状態 $x$ について、出ていく流れと入ってくる流れの総量が等しいです。これが釣り合い条件、あるいは大域的釣り合い条件です。

ただし、釣り合い条件だけでは十分ではありません。状態空間が分断されていると、初期状態のある領域から出られません。周期的に同じ状態群を行き来するだけでも収束しません。実用上は、少なくとも既約性と非周期性を求めます。

$$\text{既約性: 任意の }x,y\in \mathrm{\Omega }\text{ の間を正の確率で到達できる}$$

$$\text{非周期性: 固定された周期だけで戻る鎖になっていない}$$

有限状態のMarkov連鎖では、これらがそろうと、${\pi }_T$ が一意の極限分布になります。

3. 詳細釣り合い条件

釣り合い条件を直接満たす遷移確率を設計するのは、意外に面倒です。そこでよく使うのが詳細釣り合い条件です。

$${\pi }_T(x)P_T(x,y)={\pi }_T(y)P_T(y,x)(\mathrm{\forall }x,y)$$

これは、$x$ から $y$ へ流れる量と、$y$ から $x$ へ流れる量が、ペアごとに等しいという条件です。これを $y$ について足し上げると、

$$\sum _y{\pi }_T(x)P_T(x,y)=\sum _y{\pi }_T(y)P_T(y,x)={\pi }_T(x)$$

となり、釣り合い条件が従います。つまり詳細釣り合いは、釣り合い条件の十分条件です。

ここで大切なのは、詳細釣り合いは必要条件ではないということです。定常分布を変えないまま、一方向に回る確率流を残すことができます。その場合、

$$J_T(x,y)={\pi }_T(x)P_T(x,y)-{\pi }_T(y)P_T(y,x)$$

という流れは $0$ でなくてもよいです。ただし各点で発散が消えていれば、

$$\sum _y{J}_T(x,y)=0$$

なので、分布全体は変わりません。これが詳細釣り合いを破る非可逆MCMCの基本的な見方です。

では、なぜ詳細釣り合い条件を使うのでしょうか。第一に、設計が簡単です。第二に、Boltzmann分布を本当に定常分布にしているかを局所的な比で確認できます。第三に、Metropolis法や熱浴法のような基本アルゴリズムが、この条件からほとんど自動的に出てきます。

一方で、詳細釣り合いをあえて破る方法論も重要です。非可逆な流れを入れると、ランダムウォーク的な行きつ戻りつが減り、混合が速くなることがあります。確率過程の立場では、平衡分布は保ったまま、定常確率流を持つ非平衡定常状態を作る、という言い方もできます。ただしSAの基礎を理解する段階では、まず詳細釣り合いを満たす方法を押さえるのが自然です。

4. Metropolis法

Metropolis法では、まず候補 $y$ を提案します。提案確率を $q(x,y)$ とし、ここでは対称な場合

$$q(x,y)=q(y,x)$$

を考えます。たとえば、Ising模型ならランダムに1つのスピンを選び、反転した配位を候補にする操作です。

候補 $y$ を受け入れる確率を

$$A_T(x,y)=min\{1,\exp [-\beta (E(y)-E(x))]\}$$

とします。$E(y)<E(x)$ なら、エネルギーが下がるので必ず受け入れます。$E(y)>E(x)$ なら、悪くなる移動ですが、確率 $e^{-\beta (E(y)-E(x))}$ で受け入れます。

遷移確率は

$$P_T(x,y)=q(x,y)A_T(x,y)(x\ne y)$$

です。棄却された分は、同じ状態にとどまる確率として

$$P_T(x,x)=1-\sum _{y\ne x}{P}_T(x,y)$$

に入ります。

詳細釣り合いは、2つの場合に分ければすぐ見えます。$E(y)>E(x)$ のとき、

$${\pi }_T(x)q(x,y)e^{-\beta (E(y)-E(x))}={\pi }_T(y)q(y,x)$$

です。逆向きの移動はエネルギーが下がるので受け入れ確率は1です。$q(x,y)=q(y,x)$ を使えば、両方向の流れが等しくなります。$E(y)<E(x)$ の場合も同じです。

提案分布が対称でない場合は、Metropolis--Hastings法になります。

$$A_T(x,y)=min\{1,\frac{{\pi }_T(y)q(y,x)}{{\pi }_T(x)q(x,y)}\}$$

これも詳細釣り合いを満たします。Metropolis法は、Boltzmann重みの比だけを使うので、分配関数 $Z_T$ を知らなくても動かせます。これが強いところです。

5. 熱浴法

熱浴法では、候補を出して受け入れるかどうかを決めるのではなく、ある変数を選び、その変数を条件付き分布から直接引き直します。

Isingスピン $\mathit{\sigma }=({\sigma }_1,\dots ,{\sigma }_N)$ を考えます。1つのサイト $i$ を選び、他のスピン ${\mathit{\sigma }}_{\setminus i}$ を固定したまま、${\sigma }_i$ だけを

$$\underset{T}{Pr}({\sigma }_i=s\mid {\mathit{\sigma }}_{\setminus i})=\frac{\exp [-\beta E({\sigma }_i=s,{\mathit{\sigma }}_{\setminus i})]}{\sum _{s^{\prime }=\pm 1}\exp [-\beta E({\sigma }_i=s^{\prime },{\mathit{\sigma }}_{\setminus i})]}(s=\pm 1)$$

からサンプルします。名前のとおり、その1つのスピンだけを、周囲を熱浴として見た平衡分布に置き直す方法です。

たとえば

$$E(\mathit{\sigma })=-\sum _{i<j}{J}_{ij}{\sigma }_i{\sigma }_j-\sum _i{h}_i{\sigma }_i$$

なら、サイト $i$ に働く局所場は

$$h_i^{\mathrm{e}\mathrm{f}\mathrm{f}}=h_i+\sum _{j\ne i}{J}_{ij}{\sigma }_j$$

です。このとき

$$\underset{T}{Pr}({\sigma }_i=+1\mid {\mathit{\sigma }}_{\setminus i})=\frac{1}{1+\exp (-2\beta h_i^{\mathrm{e}\mathrm{f}\mathrm{f}})}$$

となります。$\underset{T}{Pr}({\sigma }_i=-1\mid \cdots )$ はその余事象です。

熱浴法もBoltzmann分布を保ちます。全体の分布から見れば、1変数の条件付き分布を正しく使っているだけなので、Gibbsサンプリングそのものです。Metropolis法よりも受理・棄却の無駄が少ない場合がありますが、条件付き分布を簡単に計算できる構造が必要です。

6. SAのアルゴリズム

固定した温度でMCMCを走らせれば、十分長い時間の後に ${\pi }_T$ へ近づきます。SAでは温度を時間とともに下げます。したがって遷移行列も時間依存になります。

$${\mu }_{t+1}={\mu }_t{P}_{T_t},T_0>T_1>T_2>\cdots$$

高温では悪い移動も受け入れやすいので、局所最小から抜けやすいです。低温では悪い移動が抑えられ、低エネルギー状態の近くに滞在しやすいです。これがSAの探索の仕組みです。

手順としては、次のようになります。

1. 初期温度 $T_0$ と初期状態 $x_0$ を選びます。
2. 温度 $T_t$ でMetropolis法または熱浴法の1ステップを行います。
3. 温度を少し下げる。
4. 十分な回数繰り返し、最後に得られた低エネルギー状態を採用します。

実用では、たとえば幾何冷却

$$T_{t+1}=r{T}_t,0<r<1$$

を使うことが多いです。$r$ を1に近づければゆっくり冷え、探索は丁寧になりますが時間がかかります。$r$ を小さくすると速く冷えますが、局所最小に捕まりやすくなります。

ここで気をつけたいのは、SAは「温度を下げれば何となく最適解に行く」方法ではないということです。各温度で分布が十分に混ざる前に次の温度へ進むと、分布は平衡分布からずれていきます。低温になるほど山を越える確率は小さくなるので、早く冷やしすぎると、間違った谷に入ったまま出られなくなります。

7. Geman--Gemanの定理

SAの理論で有名なのが、Geman--Gemanの定理です。もともとは画像復元の文脈で、Gibbs分布、Markov random field、Gibbs samplerを結び、温度を下げることで最大事後確率推定へ到達することを示した仕事です。

定理の雰囲気を、有限状態の最適化問題の言葉で書きます。状態 $x$ から、より低いエネルギーの状態へ行くには、途中で一度エネルギーの高い山を越えなければならないことがあります。経路 $\omega :x\to y$ の高さを

$$\mathrm{height}(\omega )=\underset{z\in \omega }{max}E(z)$$

とし、$x$ から $y$ へ行くために必要な最低の山の高さを

$$\mathrm{\Phi }(x,y)=\underset{\omega :x\to y}{min}\mathrm{height}(\omega )$$

とします。状態 $x$ が局所最小で、そこからより低い状態へ抜けるために必要な深さを

$$d(x)=\underset{y:E(y)<E(x)}{min}[\mathrm{\Phi }(x,y)-E(x)]$$

と定義します。大ざっぱに言えば、$d(x)$ は「その谷から脱出するために越えるべき一番低い峠の高さ」です。最も深い局所最小の深さを

$$d_{\ast }=\underset{x\notin \mathcal{G}}{max}d(x)$$

とします。

Geman--Geman型の収束条件は、温度を

$$T_t=\frac{c}{\log (t+t_0)}$$

のように下げるとき、定数 $c$ を十分大きく取れば、分布は最適解集合へ収束する、というものです。典型的には、$c$ は最も深い局所最小を脱出するための障壁 $d_{\ast }$ より大きく取る必要があります。$k_{\mathrm{B}}$ を明示する書き方では、$c/k_{\mathrm{B}}$ のように定数の置き方が変わります。

$$c>d_{\ast }⟹Pr(x_t\in \mathcal{G})\to 1(t\to \mathrm{\infty })$$

なぜ対数なのかは、局所最小からの脱出確率を見ると感じがつかめます。高さ $d$ の山を越える確率は、Boltzmann因子として

$$\exp (-\frac{d}{k_{\mathrm{B}}{T}_t})$$

程度です。$T_t=c/\log t$ なら、

$$\exp (-\frac{d}{k_{\mathrm{B}}{T}_t})=t^{-d/(k_{\mathrm{B}}c)}$$

となります。$c$ が十分大きければ、この脱出機会は無限時間の中で消え切らず、いずれ深い谷からも抜けられる。これが定理の直観です。

ただし、この温度スケジュールは実用上は非常に遅いです。理論は「どれだけ遅ければ確実か」を教えますが、そのまま実装して速いとは限りません。実際のSAでは幾何冷却や適応的な冷却を使い、得られた解の質と計算時間を見ながら調整することが多いです。定理は実用レシピというより、SAが局所探索以上のことをするために必要な遅さを示す基準です。

8. 古典分布を量子基底状態に写す

ここから、SAと量子断熱定理の関係を見ます。古典分布 ${\pi }_T$ から、量子状態

$$|\psi (T)⟩=\sum _{x\in \mathrm{\Omega }}\sqrt{{\pi }_T(x)}|x⟩=\frac{1}{\sqrt{Z_T}}\sum _{x\in \mathrm{\Omega }}\exp (-\frac{\beta E(x)}{2})|x⟩$$

を作ります。これはGibbs分布の平方根を振幅に持つ状態です。$E(x)$ のような古典観測量、つまり $|x⟩$ 基底で対角な演算子 $\hat{A}$ については、

$$⟨\psi (T)|\hat{A}|\psi (T)⟩=\sum _x{\pi }_T(x)A(x)$$

となります。量子状態の期待値が、古典Boltzmann分布での平均と一致します。

詳細釣り合いを満たすMarkov遷移行列 $P_T$ があるとします。${\mathrm{\Pi }}_T$ を

$${\mathrm{\Pi }}_T=\mathrm{diag}({\pi }_T(x))$$

とすると、詳細釣り合いにより

$$S_T={\mathrm{\Pi }}_T^{1/2}{P}_T{\mathrm{\Pi }}_T^{-1/2}$$

は対称行列になります。そこで

$${\hat{H}}_q(T)=I-S_T$$

という量子ハミルトニアンを作ります。$P_T$ の最大固有値は1なので、${\hat{H}}_q(T)$ の最低固有値は0です。その基底状態は、まさに $|\psi (T)⟩$ になります。

$${\hat{H}}_q(T)|\psi (T)⟩=0$$

この写像では、古典MCMCの平衡分布が、量子ハミルトニアンの基底状態になります。温度 $T$ を変えるSAは、${\hat{H}}_q(T)$ という量子ハミルトニアンを時間依存でゆっくり変える過程として読めます。

さらに、$P_T$ の第2固有値を ${\lambda }_1(T)$ とすると、Markov連鎖のスペクトルギャップは

$${\mathrm{\Delta }}_{\mathrm{M}\mathrm{C}}(T)=1-{\lambda }_1(T)$$

です。一方、${\hat{H}}_q(T)=I-S_T$ の量子ギャップも

$${\mathrm{\Delta }}_q(T)=1-{\lambda }_1(T)$$

です。つまり

$${\mathrm{\Delta }}_q(T)={\mathrm{\Delta }}_{\mathrm{M}\mathrm{C}}(T)$$

です。これはとても大きな対応です。古典MCMCで「混ざりにくい」ことは、量子ハミルトニアンで「ギャップが小さい」こととして見えます。

9. 断熱定理からGeman--Geman条件を見る

量子断熱定理は、ハミルトニアンを十分ゆっくり変えれば、系は瞬間的な基底状態にとどまる、という定理です。ここではハミルトニアンが ${\hat{H}}_q(T(t))$ なので、基底状態は $|\psi (T(t))⟩$ です。

断熱条件の典型的な形は

$$\left|\frac{⟨m(T)|{\partial }_T{\hat{H}}_q(T)|\psi (T)⟩}{{\mathrm{\Delta }}_m(T{)}^2}\frac{dT}{dt}\right|\ll 1$$

です。$|m(T)⟩$ は励起状態、${\mathrm{\Delta }}_m(T)$ は基底状態とのエネルギー差です。この式の意味は明快です。ギャップが小さいところでは、温度をよりゆっくり変えなければなりません。

古典の言葉に戻すと、これは「Markov連鎖が混ざる前に温度を変えてはいけない」という条件です。なぜなら、量子ギャップ ${\mathrm{\Delta }}_q(T)$ はMarkov連鎖の混合を支配するギャップ ${\mathrm{\Delta }}_{\mathrm{M}\mathrm{C}}(T)$ と同じだからです。SAの準平衡条件と、量子断熱条件は、同じ対象を別の言葉で見ています。

Somma, Batista, Ortiz の古典--量子写像では、この考えを一般の古典スピン系に対して整理できます。古典ハミルトニアンを $\hat{H}$ とし、Gibbs状態の平方根

$$|\psi (T)⟩\propto \exp (-\frac{\beta \hat{H}}{2})\sum _x|x⟩$$

を基底状態にもつ量子ハミルトニアンを作ります。このハミルトニアンの温度依存性を断熱的に追わせると、古典系は各時刻のBoltzmann分布に対応する状態を保ちます。

最悪の場合のギャップ評価を使うと、断熱条件の積分から

$$T(t)\simeq \frac{pN}{k_{\mathrm{B}}\log (\alpha t+1)}$$

が得られます。ここで $N$ は系の大きさ、$p$ は1回の局所更新で関わるエネルギースケールを押さえる定数、$\alpha$ は精度や系サイズに依存する定数です。大きな $t$ では

$$T(t)\sim \frac{pN}{k_{\mathrm{B}}\log t}$$

です。これはGeman--Geman型の対数冷却条件と同じ形です。

ここで「同じ」という言葉は、かなり具体的です。SAの証明では、温度を下げてもMarkov連鎖がその時々の平衡分布から大きく遅れないことを示します。量子の証明では、${\hat{H}}_q(T)$ の基底状態 $|\psi (T)⟩$ から励起状態へ漏れないことを示します。けれども $|\psi (T)⟩$ の振幅の二乗が ${\pi }_T$ であり、${\hat{H}}_q(T)$ のギャップがMarkov連鎖のギャップなので、両者は同じ準平衡追随条件を述べています。

$$\text{SAの準平衡追随}⟺\text{写像された量子系の断熱追随}$$

この対応を通すと、Geman--Gemanの定理は、量子断熱定理の古典側の姿として読めます。

10. QAとの距離感

通常の量子アニーリングは、たとえば

$${\hat{H}}_{\mathrm{Q}\mathrm{A}}(\mathrm{\Gamma })=\hat{H}-\mathrm{\Gamma }\sum _i{\hat{\sigma }}_i^x$$

のようなハミルトニアンから出発し、横磁場 $\mathrm{\Gamma }$ を大きな値から0へ下げます。これはSAの温度を下げる操作とよく似ていますが、時間発展中の状態が、一般に元の古典ハミルトニアンのBoltzmann分布を表すわけではありません。

一方で、古典--量子写像を使うと、SAもQAも「ハミルトニアン空間の経路」として同じ枠組みに入ります。SAは温度 $T$ を変える経路です。通常のQAは横磁場 $\mathrm{\Gamma }$ を変える経路です。

$$\text{SA: }{\hat{H}}_q(T)\text{ に沿って }T\downarrow 0,\text{QA: }{\hat{H}}_{\mathrm{Q}\mathrm{A}}(\mathrm{\Gamma })\text{ に沿って }\mathrm{\Gamma }\downarrow 0$$

経路が違えば、途中で出会うギャップも違います。したがって計算時間も変わりえます。QAが速いかどうかは、量子であるという名前だけでは決まりません。どのハミルトニアン経路を通り、その経路でギャップがどう閉じるかで決まります。

有限温度の古典分布を目標にする拡張QAを作るには、終点で $|\psi (T)⟩$ を基底状態にもつハミルトニアンに一致する経路を選べばよいです。その場合、横磁場のスケジュールにも断熱条件がかかります。最悪の場合の評価では、横磁場 $\gamma (t)$ に対して

$$\gamma (t)\simeq {[(2N-1)\overline{\alpha }t]}^{-1/(2N-1)}$$

のようなスケールが出ます。これは別の経路に対する断熱条件です。ただし、最終的に必要な横磁場が温度に対して指数的に小さくなる場合には、SAに対する明確な優位性はこの評価だけからは出ません。

11. 拡張QAを式で見る

ここで、古典分布を量子基底状態に埋め込む計算をもう少し丁寧に見ます。最初の学びどころは、詳細釣り合い条件です。詳細釣り合いは単に「平衡分布を保つ便利な条件」ではなく、Markov遷移をHermitianな量子問題へ移すための対称化条件でもあります。

行列 $P_{\beta }(x,y)$ がBoltzmann分布 ${\pi }_{\beta }(x)\propto e^{-\beta E(x)}$ に関して詳細釣り合い

$${\pi }_{\beta }(x)P_{\beta }(x,y)={\pi }_{\beta }(y)P_{\beta }(y,x)$$

を満たすとします。対角行列 ${\mathrm{\Pi }}_{\beta }=\mathrm{diag}({\pi }_{\beta }(x))$ を使い、

$$S_{\beta }={\mathrm{\Pi }}_{\beta }^{1/2}{P}_{\beta }{\mathrm{\Pi }}_{\beta }^{-1/2},(S_{\beta }{)}_{xy}=\sqrt{\frac{{\pi }_{\beta }(x)}{{\pi }_{\beta }(y)}}{P}_{\beta }(x,y)$$

と定義します。このとき、反対向きの行列要素は

$$(S_{\beta }{)}_{yx}=\sqrt{\frac{{\pi }_{\beta }(y)}{{\pi }_{\beta }(x)}}{P}_{\beta }(y,x)=\sqrt{\frac{{\pi }_{\beta }(x)}{{\pi }_{\beta }(y)}}{P}_{\beta }(x,y)=(S_{\beta }{)}_{xy}$$

です。途中で使ったのは詳細釣り合いだけです。したがって $S_{\beta }$ は実対称、量子力学の言葉ではHermitianです。相似変換なので、$S_{\beta }$ と $P_{\beta }$ の固有値は同じです。

さらに $P_{\beta }$ が確率遷移行列なので $\sum _y{P}_{\beta }(x,y)=1$ です。$\sqrt{{\pi }_{\beta }}$ を成分にもつベクトルを $|\sqrt{{\pi }_{\beta }}⟩$ と書くと、

$$S_{\beta }|\sqrt{{\pi }_{\beta }}⟩=|\sqrt{{\pi }_{\beta }}⟩$$

が成り立ちます。そこで

$${\hat{H}}_q(\beta )=I-S_{\beta }$$

と置けば、

$${\hat{H}}_q(\beta )|\sqrt{{\pi }_{\beta }}⟩=0$$

です。Markov連鎖の平衡分布が、量子ハミルトニアンの基底状態になります。詳細釣り合いが破れていると、同じ相似変換をしても一般にはHermitianになりません。ここが、詳細釣り合いが教科書的に重視される大きな理由の一つです。

Somma--Batista--Ortizの構成では、この抽象的な対応をスピンハミルトニアンとして具体的に書きます。古典エネルギー $E[\mathit{\sigma }]$ を、${\sigma }_j$ を ${\hat{\sigma }}_j^z$ に置き換えた対角ハミルトニアン $\hat{H}$ と見ます。有限温度のGibbs分布に対応する量子状態は

$$|{\psi }_{\beta }⟩=\frac{1}{\sqrt{Z_{\beta }}}{e}^{-\beta \hat{H}/2}\sum _{\mathit{\sigma }}|\mathit{\sigma }⟩$$

です。$|\mathit{\sigma }⟩$ は ${\hat{\sigma }}^z$ の同時固有状態です。$\hat{A}$ が ${\hat{\sigma }}^z$ 基底で対角なら、$|{\psi }_{\beta }⟩$ での期待値は古典Gibbs平均と一致します。

次に、サイト $j$ のスピン反転 ${\hat{\sigma }}_j^x$ に対して、$\hat{H}$ を

$$\hat{H}={\hat{H}}_{\overline{j}}+{\hat{H}}_j,{\hat{\sigma }}_j^x{\hat{H}}_{\overline{j}}{\hat{\sigma }}_j^x={\hat{H}}_{\overline{j}},{\hat{\sigma }}_j^x{\hat{H}}_j{\hat{\sigma }}_j^x=-{\hat{H}}_j$$

と分けます。${\hat{H}}_j$ は、サイト $j$ の反転で符号が変わる項、つまり ${\hat{\sigma }}_j^z$ を奇数個含む局所エネルギーです。Ising模型なら、サイト $j$ にかかる相互作用や局所場の部分です。

${\hat{H}}_{\overline{j}}$ と ${\hat{H}}_j$ はどちらも ${\hat{\sigma }}^z$ だけで書かれるので互いに可換です。したがって

$${\hat{\sigma }}_j^x{e}^{-\beta \hat{H}/2}{\hat{\sigma }}_j^x=e^{-\beta ({\hat{H}}_{\overline{j}}-{\hat{H}}_j)/2}=e^{\beta {\hat{H}}_j}{e}^{-\beta \hat{H}/2}$$

となります。また、一様重ね合わせはスピン反転で不変です。

$${\hat{\sigma }}_j^x\sum _{\mathit{\sigma }}|\mathit{\sigma }⟩=\sum _{\mathit{\sigma }}|\mathit{\sigma }⟩$$

そこで

$${\hat{H}}_q^j(\beta )={\hat{\sigma }}_j^x-e^{\beta {\hat{H}}_j}$$

を定義すると、

$${\hat{H}}_q^j(\beta )|{\psi }_{\beta }⟩=0$$

が従います。これを全サイトで足し合わせ、

$${\hat{H}}_q(\beta )=-\chi \sum _j{\hat{H}}_q^j(\beta )=\chi \sum _j(e^{\beta {\hat{H}}_j}-{\hat{\sigma }}_j^x)$$

と置きます。ここで $\chi =e^{-\beta p}$ は、低温でハミルトニアンの大きさが発散しないように入れる規格化因子で、$p$ は ${\hat{H}}_j$ の典型的な上限を押さえる定数です。このハミルトニアンは対角項 $e^{\beta {\hat{H}}_j}$ と横磁場項 $-{\hat{\sigma }}_j^x$ からなります。${\hat{\sigma }}^z$ 基底では非対角成分が非正になるので、Perron--Frobeniusの議論が効き、$T>0$ では正成分をもつ基底状態が一意に決まります。その基底状態が $|{\psi }_{\beta }⟩$ です。

高温極限では $\beta \to 0$ なので $e^{\beta {\hat{H}}_j}\simeq I$、$\chi \simeq 1$ です。

$${\hat{H}}_q(\beta \to 0)\simeq N-\sum _j{\hat{\sigma }}_j^x$$

基底状態は全スピンが $x$ 方向にそろった状態、つまり ${\hat{\sigma }}^z$ 基底の一様重ね合わせです。古典側では完全に混ざった高温分布に対応します。

低温側では $|{\psi }_{\beta }⟩$ の重みが古典基底状態へ集中します。つまり、温度 $T$ を下げながら ${\hat{H}}_q(\beta )$ の基底状態を断熱的に追えば、SAと同じく低エネルギー状態へ近づくことになります。

ここから拡張QAが自然に出ます。目標温度 $\beta$ を固定しておき、同じ対角項を持つ

$${\tilde{H}}_q(\gamma )=\chi \sum _j{e}^{\beta {\hat{H}}_j}-\gamma \sum _j{\hat{\sigma }}_j^x$$

を考えます。$\gamma$ が十分大きいと横磁場が支配的で、基底状態はほぼ一様重ね合わせです。一方、終点を

$$\gamma =\chi$$

に取れば、

$${\tilde{H}}_q(\chi )=\chi \sum _j(e^{\beta {\hat{H}}_j}-{\hat{\sigma }}_j^x)={\hat{H}}_q(\beta )$$

となります。したがって、$\gamma$ を大きな値から $\chi$ まで断熱的に下げれば、終点で有限温度Gibbs分布の平方根状態 $|{\psi }_{\beta }⟩$ に到達します。通常のQAが $T=0$ の最適化を目標にするのに対し、ここでは有限温度の熱力学状態そのものを目標にしています。

この経路で必要な時間は、${\tilde{H}}_q(\gamma )$ のギャップに支配されます。最悪の場合の評価として、

$$\mathrm{\Delta }(\gamma )\ge 2\sqrt{2\pi N}{e}^{-N}(1+c{)}^{-N}{\gamma }^N$$

という下限が使われます。これを断熱条件に入れると、横磁場の十分ゆっくりした変化として

$$\gamma (t)\simeq {[(2N-1)\overline{\alpha }t]}^{-1/(2N-1)}$$

が得られます。終点は $\gamma (\mathcal{T})=\chi =e^{-\beta p}$ です。つまり、目標温度を低くすると、到達すべき横磁場は指数的に小さくなります。このため、最悪評価だけを見る限り、拡張QAがSAを一般に上回るとは言えません。ただし、問題ごとのギャップがこの最悪評価より大きいなら、別のスケールが出る余地があります。

なお、この拡張QAは量子計算機だけの話ではありません。Suzuki--Trotter表示を使えば、横磁場量子系を1次元余分に増えた古典系としてサンプルできます。1次元Ising型の例では、有効古典エネルギーは

$$\overline{E}[\sigma ]=\frac{\tilde{\beta }}{L}\sum _{k=1}^L\sum _{ij}{\tilde{J}}_{ij}(\beta ){\sigma }_{ik}{\sigma }_{jk}+\xi (\beta ,t)\sum _{k=1}^L\sum _i{\sigma }_{ik}{\sigma }_{i,k+1}$$

の形になります。$k$ はTrotter方向、$L$ はスライス数です。Trotter方向の結合は

$$\xi (\beta ,t)=\frac{1}{2}\log \coth \left(\frac{\tilde{\beta }\chi \gamma (t)}{L}\right)$$

です。$\gamma (t)$ を下げるとTrotter方向の結合が強くなります。横磁場の量子揺らぎが、余分な古典方向の相関として現れるわけです。

12. 平衡分布への追従とMarkov連鎖の緩和

Toshiyuki Tanakaによる「Reclassification of quantified classical simulated annealing」は、上の量子風の議論を、もう一度古典Markov連鎖の言葉に戻して読むための仕事です。量子断熱定理を使ったように見える対数冷却の議論が、実は「平衡分布という動く標的を、Markov連鎖の緩和が追いかける」という古典的な絵として読み直せます。

有限状態集合 $S$ 上の連続時間Markov連鎖を考えます。平衡分布は

$${\overline{\rho }}_i=\frac{e^{-\beta E_i}}{Z},Z=\sum _{i\in S}{e}^{-\beta E_i}$$

です。辺集合 $L$ をもつ連結グラフ上で、遷移率を

$$m_{ij}=\{\begin{array}{ll}{w}_{ij}{e}^{\beta (E_j-E_i)/2},& (ij)\in L,\\ -{\displaystyle \sum _{k:(ik)\in L}{m}_{ki},}& i=j,\\ 0,& \text{otherwise}\end{array}$$

と置きます。$w_{ij}=w_{ji}>0$ です。この定義では

$$\dot{\mathit{\rho }}=M\mathit{\rho }$$

で時間発展します。詳細釣り合いを直接確認すると、

$$m_{ij}{\overline{\rho }}_j=w_{ij}{e}^{\beta (E_j-E_i)/2}\frac{e^{-\beta E_j}}{Z}=\frac{w_{ij}}{Z}{e}^{-\beta (E_i+E_j)/2}=m_{ji}{\overline{\rho }}_i$$

です。指数の半分ずつの分配が、左右をぴたりとそろえています。

$\alpha$-表現によって平衡分布への追従を調べます。ここで用いるのは $\alpha$-表現です。

$${\psi }_i^{(\alpha )}=\frac{2}{1-\alpha }{\rho }_i^{(1-\alpha )/2}$$

$\alpha =0$ では

$${\psi }_i^{(0)}=2\sqrt{{\rho }_i}$$

となり、これはまさにSomma--Batista--Ortizで出てきた「確率の平方根を振幅にする」表現です。定数2は幾何学的な規約で、対称化の本質には影響しません。

対角行列 ${\mathrm{\Psi }}^{(\alpha )}=\mathrm{diag}({\psi }_i^{(\alpha )})$ を使い、

$$H^{(\alpha )}={\left({\mathrm{\Psi }}^{(\alpha )}\right)}^{-1}M{\mathrm{\Psi }}^{(\alpha )}$$

と置きます。これは相似変換なので、$H^{(\alpha )}$ と $M$ の固有値は同じです。平衡分布で評価した行列要素は

$${\overline{h}}_{ij}^{(-\alpha )}=\{\begin{array}{ll}{w}_{ij}{e}^{\alpha \beta (E_i-E_j)/2},& (ij)\in L,\\ -{\displaystyle \sum _{k:(ik)\in L}{w}_{ki}{e}^{\beta (E_i-E_k)/2},}& i=j,\\ 0,& \text{otherwise}\end{array}$$

です。ここで $\alpha =0$ と置くと、非対角成分は

$${\overline{h}}_{ij}^{(0)}=w_{ij}=w_{ji}={\overline{h}}_{ji}^{(0)}((ij)\in L)$$

となります。これが0-representationの特別さです。確率の平方根を使った表現では、詳細釣り合いを満たすMarkov生成行列が対称行列として見えます。量子ハミルトニアンに翻訳すれば、Hermitianな時間発展の問題として扱えます。量子と古典の対応の核は、ここにあります。

さらに、平衡分布の近くで微小ずれ $\delta {\mathit{\psi }}^{(\alpha )}$ を考えると、局所線形化により

$$\delta {\dot{\mathit{\psi }}}^{(\alpha )}={\overline{H}}^{(-\alpha )}\delta {\mathit{\psi }}^{(\alpha )}$$

となります。$\alpha =0$ では ${\overline{H}}^{(0)}$ が対称なので、固有値は実数です。最大固有値は0で、その他の固有値は負です。したがって、平衡分布からのずれは、負の固有値に沿って指数的に緩和します。

SAでは $\beta$ が時間とともに変わるので、平衡分布そのものが動く標的になります。Markov連鎖の分布は、その標的を追いかける。追いつけるかどうかは、緩和速度と標的の移動速度の比較です。最大負固有値 $\lambda$ に対して

$$\lambda \le -\delta e^{-\beta N(d+d^{\prime })/2}$$

という形の評価を用います。ここで $d$ はエネルギー差の上限、$d^{\prime }$ は遷移率の $\beta$ 依存を押さえる定数、$\delta$ は正の定数です。低温では緩和が指数的に遅くなる、という直観そのものです。

一方、瞬間平衡分布の平方根ベクトルの速度は

$${\Vert {\dot{\overline{\mathit{\psi }}}}^{(0)}\Vert }^2=\mathrm{Cov}(E){\dot{\beta }}^2\le C^2{e}^{-\beta g}{\dot{\beta }}^2$$

と評価されます。$g$ は最低エネルギーと第2最低エネルギーの差です。標的は $\dot{\beta }$ が大きいほど速く動きますが、低温では共分散が小さくなり、速度にも指数因子が現れます。

標的との距離を $r\sim r_0{t}^{-\gamma }$ と仮定すると、追跡が成り立つための十分条件は

$$\delta r_0{e}^{-\beta N(d+d^{\prime })/2}{t}^{-\gamma }>C{e}^{-\beta g/2}\dot{\beta }$$

です。左辺は追いかける側の緩和速度、右辺は動く平衡分布の速度です。この不等式を満たすように $\beta (t)$ を増やせば、分布は瞬間平衡から大きく離れません。

大きな $t$ で解くと、

$$\beta (t)<\frac{2(1-\gamma )}{N(d+d^{\prime })-g}\log t+O(1)$$

となります。さらに整合条件から $\gamma =g/[N(d+d^{\prime })]$ が選ばれ、支配項だけを残すと

$$T(t)=\beta (t{)}^{-1}>\frac{N(d+d^{\prime })}{2\log t}$$

が得られます。これは逆対数型の冷却条件です。

この読み方のよいところは、量子断熱定理の言葉を使わなくても、同じスケールが見えることです。断熱定理では「ギャップが小さいところではハミルトニアンをゆっくり動かす」と言います。古典Markov連鎖では「緩和が遅い低温では、平衡分布の標的をゆっくり動かす」と言います。0-representationで両者の行列が同じ固有値をもつため、この二つは同じ数理を別々の顔で見ていることになります。

この補遺で押さえたい核は、競争の勝敗ではありません。SAの対数冷却は、古典Markov連鎖の収束定理として出てきます。同時に、古典分布を基底状態に埋め込むと、同じ条件が量子断熱定理として出てきます。温度を下げる古典過程と、ハミルトニアンをゆっくり動かす量子過程は、写像を通すと同じ「遅れずについていく」条件を共有しています。

参考文献: [1]。

参考文献: [2]。

参考文献: [3]。

参考文献: [4]。

参考文献: [5]。

参考文献

1. S. Kirkpatrick, C. D. Gelatt, M. P. Vecchi, “Optimization by Simulated Annealing,” Science 220, 671–680 (1983). 出典

2. Stuart Geman, Donald Geman, “Stochastic Relaxation, Gibbs Distributions, and the Bayesian Restoration of Images,” IEEE Transactions on Pattern Analysis and Machine Intelligence PAMI-6, 721–741 (1984). 出典

3. R. D. Somma, C. D. Batista, G. Ortiz, “Quantum Approach to Classical Statistical Mechanics,” Physical Review Letters 99, 030603 (2007). 出典

4. Bruce Hajek, “Cooling Schedules for Optimal Annealing,” Mathematics of Operations Research 13, 311–329 (1988). 出典

5. Toshiyuki Tanaka, “Re'class'ification of 'quant'ified classical simulated annealing,” Journal of Physics: Conference Series 143, 012020 (2009). 出典