原論文和譯及び解說 Geman-Gemanの定理 (シュミレーテッドアニーリングの収束定理)

原論文:http://image.diku.dk/imagecanon/material/GemanPAMI84.pdf

まずは論文概要や導入の概略を見てみましょう。原論文そのものは、劣化画像の復元のための手段としてシュミレーテッドアニーリングを捉えていることを念頭に置いておくと理解しやすいでしょう。原論文に数式などの不備や書き間違いが多少あるので、そこは修正しています。また、シュミレーテッドアニーリングそのものの理解にあまり必要ないと思われる章は飛ばしています。補足は、私が書いたものです。

 

1)直近の「近傍」のピクセルと境界要素の現在の値に基づいて、画像に局所的な変更が加えられます。この変更はランダムであり、ローカル条件付き確率分布からサンプリングすることにより生成されます。

2)局所条件付き分布は、「温度」と呼ばれるグローバル制御パラメータ\(T\)に依存します。低温では、局所条件付き分布は目的関数を増加させる状態に集中しますが、高温では分布は本質的に均一である。極限を考えると、\(T=0\)及び\(T=\infty\)は、それぞれ貪欲アルゴリズム(勾配上昇など)及び無向(つまり「純粋にランダム」)な変更に対応します。(高温は、隣接するピクセル間の疎結合と画像の混沌とした外観を引き起こします。低温では、結合はより緊密になり、画像はより規則的に見えます。)


3)我々の画像復元法は、確率的変化の多くが起こる高温で開始することにより、局所的な最大値を回避し、実際に目的関数を減少させます。緩和が進むと温度は徐々に低下し、過程は繰り返し改善されていくように振る舞います。(「焼き鈍し」をシュミレートしたこの温度の段階的低下は、特定の化学システムを低エネルギーの非常に規則的な状態に遷移させる過程です。)


我々の「アニーリング定理」は、事後分布のグローバルな最大値への収束を保証する温度を下げるためのスケジュールを規定しています。
このスケジュールは実際に適用するには遅すぎ、温度と時間の依存関係の関数形式を選択する際のガイドとしてのみ使用します。


また、私自身は引用論文は読んでいませんが、シュミレーテッドアニーリングの考え方の源流がどこにあるかも見て取れます。


温度と焼き鈍しのシュミレートを導入する発想は、Cerny[8]及び Kirkpatrick et al.[40]に依る。彼らはどちらも最適化問題に用いていて、Kirkpatrickはコンピュータ設計にも適用している。

[8] V. Cerny, “A thermodynamical approach to the traveling salesman problem: an efficient simulation algorithm,” preprint, Inst.
Phys. & Biophys., Comenius Univ., Bratislava, 1982.

[40] S. Kirkpatrick, C. D. Gellatt, Jr., and M. P. Vecchi, “Optimization by simulated annealing,” IBM Thomas J. Watson Research
Center, Yorktown Heights, NY, 1982.


いよいよ、定理の主張を見ていきます。

\(T\)が減少すると、事後分布からのサンプルは最小エネルギー構成に向かって強制されていきます。これらは、分布のモードに対応します。定理Bでこれを厳密にし、私たちの知る限り、この性質の最初の理論的結果です。大まかに言えば、\(k\)番目のサイト置換の実行に使用される温度\(T(k)\)(つまり、反復スキームの\(k\)番目のイメージ)が次の条件を満たす場合、

\[T(k)\geq \frac{c}{\log(1+k)}\]

すべての\(k\)について、\(c\)は\(k\)に依存しない定数であり、確率が1に収束する(\(k\rightarrow \infty\)とした)場合、アルゴリズムによって生成される構成は最小エネルギーの構成になります。
別の言い方をすれば、アルゴリズムは、最小エネルギー構成で分布が均一な尺度に収束するマルコフ連鎖を生成します。(確率1の収束は、一般に不可能であることを強調する必要があります。)

また、実際の収束率に関する定数\(c\)の性質についても議論します。

基本的に我々は、対数レートが最適であると考えます。


では定理の証明に関する話題に入っていきましょう。まずは数学的準備です。

3.グラフと近傍

\(S=\{s_1,s_2,…,s_N\}\)をサイトの集合とし、\(G=\{G_s,s \in S\}\)を\(S\)の近傍、つまり\(s \notin G_s,かつs\in G_r \Leftrightarrow r \in G_s\)を満たすような\(S\)の部分集合のそれぞれの集まりと定義する。

明らかに、\(G_s\)は\(s\)の近傍であり、\(\{S,G\}\)は普通の意味でのグラフを成す。

部分集合\(c  \subseteq S\)は、\(c\)のそれぞれのサイトの全てのペアが隣接している場合、クリークであり、\(C\)をクリーク\(c\)全ての集合とする。

 

4.マルコフ確率場とギブス分布

 

3章と同じように、\(\{S,G\}\)は任意のグラフを表す。\(X=\{X_s,s \in S\}\)を\(S\)を添え字集合としたランダムな値の族とする。

簡単のために、全ての\(s\)に対して\(X_s\in A\)なる\(A\equiv \{0,1,2,…,L-1\}\)のような共通の状態空間を想定する。

(補足:普通のシュミレーテッドアニーリングにおける、各サイトの取りうる値\(\{0,1\}\)に対応します。(quboの場合。量子ビットでは\(\{-1,1\}\)))

 

\(\Omega\)を全ての可能な構成の集合とする。

\[\Omega =\{ \omega = (x_{s_1},..,x_{s_N}):x_{s_i} \in A ,1 \leq i \leq N\}\]

(補足:普通のシュミレーテッドアニーリングでは、サイト数\(N\)のとき\(\Omega=\{(0,0,..,0),…(1,1,..,1)\}で、|\Omega|=2^N\)になりますね)

 

\(X\)は以下を満たすとき、\(G\)に関するMRF(マルコフ確率場)である。

全ての\(\omega \in \Omega\)に関して、\(P(X=\omega)>0\)

全ての\(S^{‘},S^{”} \subset S(r \neq s)\)と\((x_{s_1},..,x_{s_N})\in \Omega\)に関して、グラフ\(\{S,G\}\)上で\(B\)が\(S^{‘},S^{”}\)を分断している、つまり、\(S^{‘}\)から\(^{”}\)に行く全ての経路が\(B\)を通るとすると、

\(X(B)\)が与えられた時、\(X(S^{‘})\)と\(X(S^{”})\)は条件付き独立になる。

(補足:大域マルコフ性。上のは書き直してありますが、論文を見るときは論文の説明がまずいので、ウィキペディアの方を参考にして下さい。)

 

\(\{S,G\}\)に関するギブス分布は、以下の表式を持つ\(\Omega\)上の確率測度である。

\[\pi(\omega)=\frac{1}{Z}e^{-U(\omega)/T}\]

\(T\)は定数であり、\(U\)はエネルギー関数である。\(Z\)は規格化定数であり、

\[Z=\sum_{\omega}e^{-U(\omega)/T}\]

 分配関数と呼ばれる。

 

11.ギブスサンプラー:概要

 

一般的な計算上の問題は、

A)分布\(\pi\)からサンプルする

B)\(\Omega\)上で\(U\)を最小にする

C)期待される値を計算する

である。

 

時刻\(t\)で、\(X_{s_t}\)は\(A\)のいずれかの値である。各更新では、一つのサイトのみが値を変えることができる。つまり、\(X(t-1)\)と\(X(t)\)では一か所のサイトしか変化していない。\(n_1,n_2,..\)を、どのサイトが変化するために「訪問」されたかを示す数列とする。つまり、\(n_t \in S\)であり、\(i \neq n_t\)の時\(X_{s_i}(t)=X_{s_i}(t-1)\)である。

 

12.ギブスサンプラー:数学的基礎

 

定理A(省略)

一様マルコフ連鎖の収束性について述べています。ペロン・フロベニウスの定理の証明をもう一回やっているだけです。別の文献がいくらでもあります。

 

定理Bは、「アニーリングスケジュール」または温度低下率であり、システムを強制的に最低エネルギー状態にする。

\(\pi\)の\(T\)依存性を\(\pi_T\)と書き、\(T(t)\)をステージ\(t\)での温度とする。

最小エネルギー状態\(\Omega_0=\{\omega \in \Omega:U(\omega)=\min _{\eta}U(\eta)\}\)とし、

\(\pi_0\)を\(\Omega_0\)上の一様分布とする。

(補足:最小エネルギー状態が\(n\)個あるとき、最小エネルギー状態の取りうる確率が\(1/n\),それ以外が0になるような確率測度)

最後に、

\(U^*=\max_{\omega}U(\omega)\)

\(U_*=\min_{\omega}U(\omega)\)

\(\Delta=U^*-U_*\)

と定義する。

 

定理B(アニーリング)

全ての\(t=0,1,2…\)で\(S \subset \{n_{t+1},n_{t+2},…,n_{t+\tau}\}\)となる\(\tau>N\)の存在を仮定する。

(補足:そういう風にマルコフ連鎖を構成すればいいだけなので、容易に前提条件は満たせます。例えばそれぞれのサイトを順番に回るなど。)

 

\(T(t)\)を、以下を満たすような温度の減少列とする。

a)\(t \rightarrow \infty\)で\(T(t)\rightarrow 0\)

b)\(t_0\geq 2\)なる適当な整数に関して、全ての\(t \geq t_0\)で\(T(t)\geq N\Delta/\log t\)

を満たすならば、

任意の初期分布\(\eta\in \Omega\)と全ての\(\omega \in \Omega\)に関して、

\(\lim_{t\rightarrow \infty }P(X(t)=\omega|X(0)=\eta)=\pi_0(\omega)\)

 

定理C(エルゴード性)

省略。論文を参照してください。

 

定理B-証明

 

まずは二つの補題を示す。

(補足:非一様マルコフ連鎖の収束性について述べています。シュミレーテッドアニーリングや経路積分モンテカルロ法による量子アニーリング、Green関数モンテカルロ法による量子アニーリングなど、古典的に量子アニーリングをシュミレートする、本質的に非一様マルコフ連鎖と関連するアルゴリズムの全ての収束性について関係があります。量子アニーリングの収束定理参照。)

 

補題2

全ての\(t_0=0,1,2,…,\)に対して、

\(\lim_{t\rightarrow \infty}\sup _{\omega,\eta^\prime,\eta^{\prime \prime}}|P(X(t)=\omega|X(t_0)=\eta^\prime )-P(X(t)=\omega|X(t_0)=\eta^{\prime \prime}))|=0\)

 (補足:補題2と補題3を証明すれば、定理Bが証明されます。補題2の必要条件として定理Bの条件bが得られます。補題3の必要条件として、条件aが使われます。)

 

補題3

||は\(L_1\)距離を表す。

\(\lim_{t_0\rightarrow \infty}\sup_{t\geq t_0}||P(t|t_0,\eta)-\pi_0||=0\)

 

まず、これらの補題を如何に定理Bに適用するかを示す。\(\sup\)は\(\omega,\eta\)についてとる。

\(\limsup_{t\rightarrow \infty}||P(X(t)=\omega|X(0)=\eta)-\pi_0(\omega)||\)

\(=\limsup _{t_0 \rightarrow \infty }\limsup_{t\rightarrow \infty,t\geq t_0}\)

\(||\sum_{\eta^\prime} P(X(t)=\omega|X(t_0)=\eta) \cdot P(X(t_0)=\eta|X(0)=\omega)-\pi_0||\)

\(\leq \limsup _{t_0 \rightarrow \infty }\limsup_{t\rightarrow \infty,t\geq t_0}\)

\(||\sum_{\eta^\prime} P(X(t)=\omega|X(t_0)=\eta^\prime) \cdot P(X(t_0)=\eta^\prime|X(0)=\omega)-P(X(t)=\omega)|t_0,\pi_0)||\)

\(+||P(X(t)=\omega|X(t_0)=\pi_0)-\pi_0||\)

第二項は、補題3から0になる。第一項について、

 \(||\sum_{\eta^\prime} P(X(t)=\omega|X(t_0)=\eta) \cdot P(X(t_0)=\eta|X(0)=\omega))-P(X(t)=\omega)|t_0,\pi_0)||\)

\(=\sum_\omega \sup_{\eta^{\prime \prime}}|\sum_{\eta^\prime}(P(X(t)=\omega|X(t_0)=\eta^\prime) -P(X(t)=\omega|X(t_0)=\eta^{\prime\prime}) )\)

\(\times (P(X(t)=\eta^\prime|X(t_0)=\eta) -\pi_0(\eta^\prime))|\)

\(\leq 2\sum_\omega \sup_{\eta^\prime,\eta^{\prime\prime}}|P(X(t)=\omega|X(t_0)=\eta^\prime) -P(X(t)=\omega|X(t_0)=\eta^{\prime\prime}) |\)

よって、第一項も補題2から0になるから、補題2,3が成り立てば定理Bを示せることはわかった。

 

補題2の証明

\(\delta (t)=\inf_{1\leq i \leq N,(x_{s_1},…,x_{s_N})\in \Omega} \pi_{T(t)}(X_{s_i}=x_{s_i}|X_{s_j}=x_{s_j},i \neq j)\)

と定義する。

\(\delta (t)\geq \frac{e^{-U^*/T(t)}}{{e^{-U_*/T(t)}}}=e^{-\Delta/T(t)}\)

であることは容易に示せる。

(補足:ベイズの定理を用いる。論文では分母に\(L\)が来ていますが、必要ありません。どちらにせよ結果に影響はありません。)

 

今、\(k\)を固定して考え、\(m_i\)を以下のように定義する。

\(m_i=\sup \{t:t \leq T_k ,n_t=s_i\}\ ,\ 1\leq i \leq N\)

(補足:\(k\)は直観的に言えば、マルコフ連鎖で全てのサイトを今まで何周したかを表すものであることを思い出してください。つまり\(m_i\)は、\(k\)周目で”訪問”するサイト\(i\)の最後に”訪問”する時刻を表しています。)

 また、\(m_1>m_2>m_3>\cdots >m_N\)と仮定する。

(補足:そうなるように最初からマルコフ連鎖を構成すればよいだけです。逆に言えば、シュミレーテッドアニーリングのマルコフ連鎖を構成するときは、各サイトを順番に周って値を更新する必要があることを言っています。)

このとき、

\(P(X(T_k)=\omega|X(t_{k-1})=\omega^\prime)=P(X_{s_1}(m_1)=x_{s_1},\cdots X_{s_N}(m_N)=x_{s_N}|X(t_{k-1})=\omega^\prime)\)

\(=\prod _{j=1}^N P(X_{s_j}(m_j)=x_{s_j}|X_{s_{j+1}}(m_{j+1})=x_{s_{j+1}},\cdots ,X_{s_N}(m_N)=x_{s_N},X(T_{k-1})=\omega^\prime)\)(条件付き分布の定義から)

\(\geq \prod_{j=1}^N \delta(m_j)\)(\(\delta\) の定義から)

\(\geq  \prod_{j=1}^N e^{-\Delta/T(m_j)}\)

\(\geq \exp\{-\Delta N/(t_0+k\tau)\}\)(\(m_j \leq T_k=t_0+k\tau ,j=1,2,…,N\)であり、かつ\(Tは\)減少関数であるから)

\(\geq (t_0+k\tau)^{-1}\)(定理の仮定Bより。逆に言えば、以下の議論を追えば、このアニーリングスケジュールがシュミレーテッドアニーリングの収束の必要条件になることがわかります。)

 

\(t>t_0\)なる\(t\)に対して、\(K(t)\)を

\(K(t)=\sup\{k:T_k<t\}\)と定義する。

(補足:時刻\(t\)ですでに各サイトを何周回ったか)

 

\(\sup _{\omega,\eta^\prime,\eta^{\prime\prime}}|P(X(T_k)=\omega|X(t_0)=\eta^\prime)-P(X(T_k)=\omega|X(t_0)=\eta^{\prime\prime})|\)

\(\leq \prod_{k=1}^{K(t)} (1-(t_0+k\tau)^{-1})\)

 

\(t\rightarrow \infty \Rightarrow K(t) \rightarrow \infty\)であることと、

\(\prod_{k=1}^m (1-(t_0+k\tau)^{-1})\)

\(=\prod_{k=1}^m \exp \log (1-(t_0+k\tau)^{-1})\)

\(=\exp(\sum_{k=1}^m \log (1-(t_0+k\tau)^{-1}))\)

\(\leq \exp(\sum_{k=1}^m (t_0+k\tau)^{-1})\)(\(x>0\)で\(\log (1-x)<-x\)であることから)

\(\rightarrow 0(m \rightarrow \infty)\)

 

これより、補題2は示された。

 

補題3の証明

\(P(t,\omega|t_0,\pi_0)\)

\(=\sum_\eta P(t,\omega|X(t_0)=\eta)\pi_0 (\eta)\)

(補足:初期状態が\(\pi\)によって決定された後、時刻\(t\)で\(\omega\)である確率。証明を構成するためにこのような確率を考えますが、結局初期状態が何であっても収束することが示せればよいので、初期状態の選び方そのものは特殊な状況を考えて問題ないということを言っています。)

 

 \(P(t,\omega|t_0,\pi_0)\)を以下、\(P_{t_0,t}\)と略記する。

始めに、\(t>t_0\geq 0\)に対し、以下を示す。

\(||P_{t_0,t}-\pi_{T(t)}|| \leq ||P_{t_0,t-1}-\pi_{T(t)}||\)

 

簡単のために\(n_t=s_1\)として、

\(||P_{t_0,t}-\pi_{T(t)}||\)

\(=\sum _{(x_{s_1},…,x_{s_N})} |\pi_{T(t)}(X_{s_1}=x_{s_1}|X_s=x_s,s \neq s_1) \cdot P_{t_0,t-1}(X_s=x_s,s \neq s_1)-\pi_{T(t)} (X_s=x_s,s \in S)|\)

\(=\sum _{(x_{s_2},…,x_{s_N})}|P_{t_0,t-1}(X_s=x_s,s \neq s_1)-\pi_{T(t)} (X_s=x_s,s \in S)|\)

\(\leq \sum_{(x_{s_1},…,x_{s_N}) \in \Omega} |P_{t_0,t-1}(X_s=x_s,s \neq s_1)-\pi_{T(t)} (X_s=x_s,s \in S)|\)

\(=||P_{t_0,t-1}-\pi_{T(t)}||\)

 

次に、\(t \rightarrow \infty\)で\(||\pi_0-\pi_{T(t)}||\rightarrow 0\)を示す。

\(\pi_{T(t)} (\omega)=\frac{\exp(-U(\omega)/T(t))}{\sum_{\omega^\prime \in \Omega_0}\exp(-U(\omega)/T(t)+\sum_{\omega^\prime \in \Omega \backslash \Omega_0}\exp(-U(\omega)/T(t)}\)

\(=\frac{\exp(-(U(\omega)-U_*)/T(t))}{|\Omega_0|+\sum_{\omega^\prime \in \Omega \backslash \Omega_0}\exp(-(U(\omega)-U_*)/T(t)}\)

よって、\(t \rightarrow \infty\)の極限で、\(\pi_{T(t)} (\omega)\)は\(\Omega_0\)上の一様分布に近づく。

 

(原論文のこれ以降の説明は、ある一定より先は単調減少して0に近づく数列の和が有界であるなどと主張している(簡単な反例が挙げられる)ことや、\(\pi_T(t)\)の時間依存性についての議論がデタラメなので、修正しています。)

 

\(t>t_0\geq 0\)において、

\(||P_{t_0,t}-\pi_0||\leq||P_{t_0,t}-\pi_{T(t)}||+||\pi_{T(t)}-\pi_0|| \)

\(\leq ||P_{t_0,t_0}-\pi_T(t)||+||\pi_{T(t)}-\pi_0||\)(\(||P_{t_0,t}-\pi_{T(t)}|| \leq ||P_{t_0,t-1}-\pi_{T(t)}||\)であるから)

\(=||P_{t_0,t_0}-\pi_{T(t_0)}||+||\pi_{T(t_0)}-\pi_{T(t)}||+||\pi_{T(t)}-\pi_0||\)

 ここで、\(P_{t_0,t_0}=\pi_0\)であり、\(t\rightarrow \infty\)で\(||\pi_{T(t)}-\pi_0||\rightarrow 0\)であるから、上式の\(\lim_{t_0\rightarrow \infty}\sup_{t\geq t_0}\)をとれば良い。

量子アニーリングの理論を学んでみる-その1最適化問題とイジング模型(数式)

「量子アニーリングの基礎 西森秀稔 大関真之」という本を読み始めたので、学んだことのアウトプットも兼ねつつ、記事を書いてみることにしました。量子力学についてある程度知っている方を対象にしていますが、数学的素養があれば理解できると思います。

本記事「量子アニーリングの理論を学んでみる-その1最適化問題とイジング模型(数式)」では、最適化問題をイジング模型に帰着できる、つまり、なぜ最適化問題を量子アニーリングの方法で探索できるのかを示します。

 

量子アニーリングとは、端的に言えば、\(\pm1\)の値をとるスピンを利用して、最適化問題を解こうと言う技術のことです。

電子の、スピンという、物質の磁性に関係する物理量は、量子力学的に\(\pm 1\)の値だけとりうることが知られています。そして、系(取り扱う物質全体のなすものを一塊と見たもの)のエネルギーに関係する、ハミルトニアン\(H\)という関数が最小になる固有状態(これを基底状態と言います。)を目指すように系を操作します。ハミルトニアンを、解きたい最小化問題の関数と同じになるように最初から設定しておけば、これは最小化問題が解けたことになります。

この”系”をD-waveという会社が実用化し、既に市販されているのはニュースでご存知かも知れません。

その理論的背景を、数式を用いながら説明していきます。

 

イジング模型

イジング模型とは、磁場の作用する環境下における、複数の電子のなす系を抽象化したモデルです。

おのおのの電子のスピン\(\sigma_i\)は\(\pm1\)の値をとり得ますが、これを\(\pm1\)の値をとり得るイジング変数\(\sigma_i=(\pm1)\)と考えます。他にもイジング変数を実現する方法はありますが、この記事では電子の系を考えます。

電子スピン相互作用を考えます。\(i,j\)間の相互作用の比例定数を\(J_{ij}\)とすると、ハミルトニアンへの寄与として、

\[-J_{ij}\sigma_i \sigma_j\]

と書けます。これは、スピンがそろうと系のエネルギーへの寄与は小さくなり、逆を向けば大きくなることを表しています。(\(J_{ij}>0\)の場合、これは強磁性的相互作用と呼ばれます。負の場合は今言ったことが逆になります。)

また、おのおのの電子における局所磁場に関するハミルトニアンへの寄与も考えます。局所磁場とは、外部磁場と系(自分と周りの電子たちの作るスピン)が作る磁場を合わせた磁場の、そのおのおのの電子のいる地点での磁場です。比例定数を\(h_i\)として、

\[-h_i \sigma_i\]

と書けます。これも、磁場にスピンの向きがそろえばエネルギーへの寄与は小さくなり、逆を向けば大きくなることを表しています。

よって、系全体のハミルトニアンは、

\[H(\mathbb{\sigma})=-\sum_{i<j}J_{ij}\sigma_i \sigma_j-\sum_{i=1}^N h_i \sigma_i\]

と書けます。

第一項の\(i<j\)は、同じ組を2回数えないためのものです。

 

フラストレーション

単純な系として\(J_{ij}=const>0\)の場合を考えれば、系の基底状態は自明、全てのスピンが同じ値をとれば最適化問題が解けたことになります。実際の最適化問題はそんなに単純ではありません。ここで、フラストレーションという概念を導入します。

まず、局所磁場のない(\(h_i=0\))、電子が2つ(\(N=2\))の簡単な場合を考えてみましょう。相互作用のある(\(J_{ij}\neq0\)の)電子対を、ボンドと呼びます。

\[H=-J\sigma_1\sigma_2\]この場合は簡単で、\(J_{ij}>0\)の場合はスピンがそろえば、\(J_{ij}<0\)の場合はスピンが逆になれば系全体の基底状態を実現できます。局所的な基底状態が系全体の基底状態を実現する、という言い方もできます。

電子が3つ(\(N=3)\)の場合はどうでしょうか。

\[H=-J(\sigma_1\sigma_2+\sigma_2\sigma_3+\sigma_3\sigma_1)\]

\(J_{ij}=const<0\)とします。うち2つは、スピンが逆になれば局所的には基底状態を実現できます。ところが、もう1つの電子を考えると、これはどっちを向こうが、どちらかもう一方の電子と同じ向きになってしまいます。これがフラストレーションです。フラストレーションとは、全体の基底状態が実現しているとき、必ずしも局所的な基底状態が実現されているとは限らないということです。

フラストレーションが発生すると、エネルギーの縮退(異なる状態が同じエネルギーを持ちうること)が起きます。例の電子3つの系では、\(\sigma_i=\pm1(i=1,2,3)\)ですから異なる状態の数は8つありますが、全てのスピンが同じ向きを持つ場合の2つ以外は、全て基底状態になります。

 

最適化問題とイジング模型

ところで、みなさんは電子のスピンと2進数が、相性がいいのに気がついたでしょうか。つまり、\(0\)をスピン\(-1\),\(1\)をスピン\(+1\)に対応させればよいのですから、2進変数を\(q=0,1\)とすれば、\(q=\frac{\sigma+1}{2}(\sigma=2q-1)\)と考えればよいだけです。

 

最適化問題(組み合わせ最小化問題)、つまり\(F(q_0,q_1,…q_N)\)の最小化(最大化の時は符号を逆転すればよい)について考えるために、テーラー展開

\[F(q_0,q_1,…q_N)=c_0+ \sum_{i=1}^N c_i^{(1)}q_i+\sum_{i,j}c_{ij}^{(2)}q_i q_j+\sum_{i,j,k} c_{ijk}^{(3)}q_i q_j q_k +\cdots\]

を、電子のスピンで表現することを考えます。上式に\(q_i=\frac{\sigma_i+1}{2}\)を代入すると、\(\sigma^2=1\)の関係から\(N+1\)次以上の項が消え、以下の式に変換できることがわかります。

\[F(\sigma_0,\sigma_1,…\sigma_N)=c^\prime_0+\sum_{i=1}^N c_i^{\prime(1)}\sigma_i+\sum_{i<j}c_{ij}^{\prime(2)}\sigma_i \sigma_j+\sum_{i<j<k} c_{ijk}^{\prime(3)}\sigma_i \sigma_j \sigma_k +\cdots+ c_{123\cdots N}^{(N)}\sigma_1 \sigma_2 \cdots \sigma_N\]

よって最適化問題は、多体相互作用を持つイジング模型の基底状態を探す問題に帰着できることが分かりました。

量子アニーリングの理論を学んでみる-その2量子アニーリングを語るための、数学的準備(数式)

に続きます。

量子アニーリングの理論を学んでみる-その2量子アニーリングを語るための数学的準備(数式)

量子アニーリングの理論を学んでみるシリーズ

量子アニーリングの理論を学んでみる-その1最適化問題とイジング模型(数式)

の続きです。

前回、最適化問題を量子アニーリングの手法で解ける、つまり最適化問題はイジング模型の基底状態を求めることに帰着できることを学びました。

次の記事では、量子アニーリングの手法でどのように計算するか、具体的にどのようにして基底状態を求めるのかを説明します。

まずこの記事で、そのために必要な程度に、量子力学を簡単に説明します。量子力学をある程度知っている人は、あまり読む必要はないかもしれません。下の()は興味のある方だけ読んでください。

 

(個人的に、論理を誤魔化して議論を進めるのが好きではないので、一応これを書いておきます。量子力学では、ヒルベルト空間\(\mathcal{H}\)における抽象的なベクトルの元として、系の状態を表現します。物理量は、ヒルベルト空間\(\mathcal{H}\)の元に対する作用素として定義されます。ただ、この記事では元が非可算無限個ある状態空間(例えば、粒子の運動)を考える必要がないので(可算無限でさえも)、この抽象的なベクトルは馴染み深い、普通のベクトル\(\mathbb{C}^N\)に対応付けて考えることができます。この場合、作用素は行列で表現できます。とくにスピンに関しては、状態空間の次元がたったの\(2\)なので、\(\mathbb{C}^2\)ととることができます。他の量子コンピュータの教科書を見てみても、量子力学の枠組みに関してはこの記事の程度の説明です。詳細は、「現代の量子力学 J・Jサクライ」などが詳しいです。以下は、このような枠組みのもとでの状態の一つの表現形式であり、多くの量子力学の教科書で採用されています。)

 

これから量子力学を語るために、まずはそのための言葉を準備しましょう。

\(z\)方向のスピンの\(\pm1\)に対応するベクトルを、

\[\mid \uparrow \rangle=\begin{pmatrix} 1\\0\end{pmatrix},\mid \downarrow \rangle =\begin{pmatrix}0\\1\end{pmatrix}\]

とおきます。

次に、パウリ行列と呼ばれる、スピンを表現するための行列を導入します。

\[\sigma_z=\begin{pmatrix}1 & 0 \\ 0 &-1\end{pmatrix}\]

これを、上で導入したベクトルたちに作用させると、

\[\sigma_z \mid \uparrow \rangle=\begin{pmatrix}1 & 0 \\ 0 &-1\end{pmatrix} \begin{pmatrix} 1\\0\end{pmatrix}=\begin{pmatrix} 1\\0\end{pmatrix}\]

\[\sigma_z \mid \downarrow \rangle =\begin{pmatrix}1 & 0 \\ 0 &-1\end{pmatrix} \begin{pmatrix}0\\1\end{pmatrix}=-\begin{pmatrix}0\\1\end{pmatrix}\]

となりますから、これらは固有値\(\pm1\)に対応する固有ベクトルになっていることがわかります。この固有値こそ、スピンの実際にとりうる値を表しています。

これら固有ベクトルの、規格化された(\(\alpha^2+\beta^2=1\)とした)線形結合

\[\mid \psi \rangle =\alpha \mid \uparrow \rangle+\beta \mid \downarrow \rangle \]

は、状態の重ね合わせを表現します。

規格化とは、全体の確率を\(1\)にするためのものです。今まで例に挙げてきた状態ベクトルも、全て規格化されています。実は、このベクトル\(\mid \psi \rangle\)に現れた\(\alpha^2\)は上向きスピン、\(\beta^2\)は下向きスピンを観測する確率になっています。それが量子力学の枠組みです。規格化とは、これらの和が\(1\)になるように設定することです。(正確には、一般に係数\(\alpha\)は複素数のため、係数の絶対値の二乗\(\mid \alpha \mid^2\)です。)

また、\(x\)方向のスピンを表す行列

\[\sigma_x=\begin{pmatrix}0 & 1 \\ 1 &0\end{pmatrix}  \]

を導入します。

この行列の\(\pm1\)に対応する固有ベクトルは、
\[\mid + \rangle=\begin{pmatrix}1\\1\end{pmatrix},\mid – \rangle=\begin{pmatrix}1\\-1\end{pmatrix}\]

です。確認してみてください。

\(\sigma_y\)も、もちろんありますがここでは使わないので省略します。

 

また量子力学の枠組みにおいて最も重要な仮定、時間に依存する状態ベクトルのシュレディンガー方程式は、

\[i\frac{\partial}{\partial t}\mid \psi(t)\rangle=\hat{H}(t)\mid\psi(t)\rangle\]

です。

時間に依存しないシュレディンガー方程式は、

\[\hat{H}\mid\psi\rangle=E\mid\psi\rangle\]

です。

詳しい解説は量子力学の専門書に譲りますが、これらの式にそこまで深く立ち入る必要もないので、これで十分でしょう。

量子アニーリングの理論を学んでみる-その3実際に、どのように量子計算を実行するのか(数式)

に続きます。

 

量子アニーリングの理論を学んでみる-その3実際に、どのように量子計算を実行するのか(数式)

前々回では、最適化問題を量子アニーリングの手法で解ける、つまり最適化問題はイジング模型の基底状態を求めることに帰着できることを学びました。

前回では、この記事の理解に必要な、多少の量子力学を解説しました。

この記事では、実際に、どのようにして量子アニーリングの計算を実行するのか、つまりイジング模型の基底状態をいかにしてもとめるかを解説します。

量子アニーリングの理論を学んでみる-その2量子アニーリングを語るための数学的準備(数式)

の続きです。

 

目標は、イジング模型

\[\hat{H}_0=-\sum_{i<j}\hat{\sigma}_i^z \hat{\sigma}_j^z\]

の基底状態を求めることでした。ちなみに量子力学では、表現したいものがただの数ではない(演算子や行列など)であることを強調するため、上に\(\hat{}\)をつける習慣があります。

そこで、時間とともに変化するハミルトニアン

\[\hat{H}(t)=-\sum_{i<j}\hat{\sigma}_i^z \hat{\sigma}_j^z-\Gamma(t)\sum_i^N \hat{\sigma}_i^x=\hat{H}_0-\Gamma(t)\sum_i^N \hat{\sigma}_i^x\]

を導入します。

添え字\(i\)は、それぞれの電子(サイト)のみにしか作用しないことを表します。もとの\(z\)軸方向のみのハミルトニアンに加え、電子に\(x\)方向に磁場がかかっている状況と同じですから、横磁場イジング模型のハミルトニアンと呼ばれます。

初期状態として、\(\Gamma(0)\)が第一項に比べて十分大きい場合を選ぶと、ハミルトニアンは

\[\hat{H}(0)=-\Gamma(0)\sum_i^N \hat{\sigma}_i^x\]

となり、この基底状態は自明、それぞれのサイトの基底状態の積(複数のサイトの状態を同時に表しすためのもの。\(\otimes\)を用いる。)であるから、\(\mid +\rangle=\frac{\mid \uparrow\rangle+\mid\downarrow\rangle}{\sqrt{2}}\)を用いて、

\[\mid \psi (0)\rangle=\mid++\cdots+\rangle=\mid+\rangle_1 \otimes \mid+\rangle_2 \otimes \cdots \otimes \mid+\rangle_N=\prod_{i=1}^N \mid + \rangle_i=\frac{1}{2^{\frac{N}{2}}}\prod_{i=1}^N(\mid \uparrow\rangle_i+\mid\downarrow\rangle_i)\]

となります。

これは、

\[\mid \psi (0)\rangle=\frac{1}{2^{\frac{N}{2}}}(\mid\uparrow\uparrow\cdots\uparrow\rangle+\cdots\mid\downarrow\downarrow\cdots\downarrow\rangle)\]

とも表せるように、サイト\(1\)から\(N\)までがそれぞれ上スピンか下スピンであるかの、全ての組み合わせ\(2^N\)個を等しく足し合わせたものです。もとめたいイジング模型のハミルトニアン\(\hat{H}_0\)を求めたいのだから、同じ重みの状態から出発するのは理に適います。

あとは、\(\hat{H}(t)=-\sum_{i<j}\hat{\sigma}_i^z \hat{\sigma}_j^z-\Gamma(t)\sum_i^N \hat{\sigma}_i^x\)における\(\Gamma(t)\)を徐々に\(0\)に近づければ、系は(状態ベクトルの時間に依存する)シュレーディンガー方程式

\[i\frac{\partial}{\partial t}\mid \psi(t)\rangle=\hat{H}(t)\mid\psi(t)\rangle\]

に従い、自然に、求めたいハミルトニアン\(\hat{H}_0\)の基底状態へと変化します。

各時刻において、\(\Gamma(t)\)の変化が十分小さい(これを、量子断熱と言います)ならば、各時刻における状態は、時間に依存しないシュレディンガー方程式

\[\hat{H}(t)\mid\psi(t)\rangle=E(t)\mid\psi(t)\rangle\]

と近似できる(ほぼ等しいと見なせる)から、基底状態の探索において、全ての時刻におけるハミルトニアンの基底状態をなめらかに移りながら変化していきます。

ちなみに、この近似ができる条件を、量子断熱条件と言います。

この条件の詳しい導出は、「量子アニーリングの基礎 西森秀稔 大関真之」を参照して下さい。