＜↑｜猫でもわかる量子アニーリングの理論｜↓＞

本記事の目標：

量子アニーリングの概要とアルゴリズムをわかりやすく説明する

★想定読者は，理系学部の授業を受けた学生以上です．

こちらの本をもとに説明していきます．

リンク

この本は量子アニーリングの提唱者である西森秀稔さんによって書かれており，過不足なく，かなり分かりやすくまとめてあります．

大学の基礎物理を学んだ人には理解できるようになっていると思います．

概要：『量子アニーリング』は最適化手法のひとつ
ハードとソフトの両面からの研究がある
量子アニーリングのアルゴリズム
実際に古典コンピュータでシミュレーションするには

概要：『量子アニーリング』は最適化手法のひとつ

量子アニーリングとは何かを説明する前に，最適化という言葉を説明しておく必要があります．

最適化問題とは，制約の下で何かを最大もしくは最小にしたいとき，その解を見つけることです．

最大，最小にしたい関数を目的関数や評価関数と呼びます．

つまり，下の図のようなグラフが最小になる矢印のところを見つける問題です．

縦軸が目的関数，横軸が解の候補です．

特に，変数が離散的である場合を組合せ最適化問題と言います．すなわち，上の図において解はとびとびの値のどれかであり，それを探す問題が組合せ最適化問題です．

組合せ最適化問題には，いくつかの点を訪れて戻ってくる巡回セールスマン問題，箱にできるだけ良いものを詰めるナップザック問題などがあります．

組合せ最適化は，多くの場合，問題の規模が大きくなると解の候補が莫大に増え，一つ一つ解を見ていくというのはコンピュータでも実質的に不可能となります．

そのため，一つ一つの解を見るのではなく，実質的な時間で「それなりに」良い解を求める手法がたくさん提案されており，

量子アニーリングも，この組合せ最適化問題を解くための手法のひとつです．

後で述べるように，組合せ最適化問題の解はスピンという物理学の概念で置き換えて考えることができます．

そして，物理学の自然な法則をまねてスピンを従わせる（アルゴリズムを組む）ことで，スピンの状態（解）を計算しようという考えに基づいた最適化手法として，アニーリング法が提案されています．

低エネルギー状態に落ち着いた時のスピンの状態を最適解とするのがアニーリング法です．

組合せ最適化を物理現象に見立てる

最適解の候補　⇔　スピン

目的関数　⇔　エネルギー（ハミルトニアン）

計算アルゴリズム　⇔　物理法則

すでに良く知られているシミュレテッドアニーリングは温度を下げていって，熱ゆらぎを持つエネルギーが低くなったときの状態を解とする，古典的な物理学を利用した方法です．

赤の線は解の動きを表しています．

一方，量子アニーリングは磁場を下げていって，量子ゆらぎを持つエネルギーが小さくなったときの状態を解とする，量子力学の効果を利用した方法です．

青の部分は解の存在確率を表しています．

ハードとソフトの両面からの研究がある

量子アニーリングに関して述べるには，ハードウェアとソフトウェアの両方から議論する必要があります．

上で述べた話はただ単に物理現象を模した計算方法ではなく，実際にスピンと磁場を利用した量子アニーリングマシン（量子コンピュータの一種）を用いて計算されるからです．

量子アニーリングマシンを用いて計算することで，古典的なコンピュータ（いま我々が使っている，0と1ですべてが記述されるコンピュータ）よりも高速に解くことができるとされています（これについての議論は，他の記事でします）．

※量子アニーリングマシンは組合せ最適化のみ解けることに注意．連続最適化や他の計算については量子ゲート方式の量子コンピュータを使用する．

量子アニーリング式のマシンは，D-Wave社によって開発されており，利用することもできます．

一方で，量子アニーリングのアルゴリズム自体にも議論の余地があるとされています．

古典コンピュータで量子アニーリング計算を行うと，シミュレテッドアニーリング（古典物理的なアルゴリズム）よりも高速に解ける場合があるからです．

つまり，ハードウェアとして古典コンピュータを用いてシミュレーションするとしても，アルゴリズム（量子効果を模した計算方法）自体に研究の余地があるとされています．

量子アニーリングのアルゴリズム

いよいよ，量子アニーリングのアルゴリズムについて説明していきます．

まずざっくりと

以降で説明する内容を，ざっくりと説明します．

量子アニーリングは，以下の図のように，はじめは横磁場（外部磁場）によって平坦なポテンシャル（エネルギー）をつくり，そこにどの解も等しい確率で存在するとします．

そして，外部磁場をだんだんと弱めていき，もとのポテンシャルに近づけていき，自然と最適解の確率が最大となるという仕組みです．

この解の動きはどのように計算するのかというと，シュレディンガー方程式に従って発展させます．つまり，各計算ステップにおけるポテンシャルに対して，固有ベクトルを求めます（詳しくはあとで説明します）．

最終的に外部磁場が０になったときのポテンシャルに対する固有ベクトルが最適解となります．

（準備）量子力学を簡単に

量子アニーリングの理解に必要な量子力学にの知識について少し解説しておきます．

重ね合わせ

量子力学では，ミクロな物の状態（例えば，電子の位置や電子スピンの向き）ははっきりと観測できないために，状態を確率的に扱います．つまり，「電子は右のあたりに0.4の確率で存在して，左のあたりに0.6の確率で存在する」といったように扱います．

そして，その状態は次のように重ね合わせで表します．

｜電子の状態＞=　 $\sqrt{0.4}×|right>　+　\sqrt{0.6}×|left>$

この｜電子の状態＞のことを波動関数と呼び，電子の存在確率密度の片割れ（片割れなので係数は平方根になっている）を意味しますが，量子力学を学んだことがないひとは，とりあえず電子の状態を表すものなんだなと思っておけばOKです．

電子や原子にはスピンと呼ばれるものがあり，それもミクロな状態のひとつなので，同様に状態の重ね合わせで表現します．

上では電子の位置について述べましたが，位置は固定されているとして，スピンの向きだけが分からないと仮定します．

例えば，一つの電子を考えましょう．電子スピンの候補として，上向きスピンと下向きスピンの２つの状態があります．電子がどちらのスピンをもっているか分からず，上向きスピンと下向きスピンが等しい確率で存在する場合は，

|電子>　=　 $\sqrt{0.5}×|\uparrow>+\sqrt{0.5}×|\downarrow>$

とします．

スピンを行列で表現する

上で述べた $|\uparrow>$ や $|\downarrow>$ はケットベクトルと呼ばれ，各々は

$|\uparrow> = \left( \begin{array}{cc} 1\\ 0\\ \end{array} \right)$

$|\downarrow> = \left( \begin{array}{cc} 0\\ 1\\ \end{array} \right)$

です．一方， $<\uparrow|$ や $<\downarrow|$ のような書き方はブラベクトルと呼ばれ，ケットベクトルの複素共役をとって転置したものです．

これらスピンは，パウリ行列と呼ばれるスピン演算子の固有ベクトルとなっています．

z方向（上下方向）のパウリ行列は

$\hat \sigma^z= \left( \begin{array}{cc} 1&0\\ 0&-1\\ \end{array} \right)$

であり，これに上下スピンを作用させると固有値は

$\hat \sigma^z |\uparrow>= \left( \begin{array}{cc} 1&0\\ 0&-1\\ \end{array} \right) \left( \begin{array}{cc} 1\\ 0\\ \end{array} \right) = 1\times\left( \begin{array}{cc} 1\\ 0\\ \end{array} \right)=1\times|\uparrow>$

$\hat \sigma^z |\downarrow>= \left( \begin{array}{cc} 1&0\\ 0&-1\\ \end{array} \right) \left( \begin{array}{cc} 0\\ 1\\ \end{array} \right) = -1\times\left( \begin{array}{cc} 0\\ 1\\ \end{array} \right)=-1\times|\downarrow>$

のように，１とー１になります．

後で述べるように，ほとんどの組合せ最適化は１とー１をとる変数で記述できるので，これら上下スピンを組合せ最適化を定式化することができます．

とにかくパウリ行列 $\hat \sigma^z$ にスピンを作用させたら，１もくしは－１の固有値が出るとだけ理解しておけばOKです．

シュレディンガー方程式

量子力学の基礎方程式として，シュレディンガー方程式があります．

シュレディンガー方程式は，以下のように書かれます．

$\hat H |\psi> = \hat E |\psi>$

ただし， $\hat H$ はハミルトニアン， $\hat E =i\hbar \frac{\partial}{\partial t}$ はエネルギー演算子です．どちらも演算子で，波動関数 $|\psi>$ を作用させて初めて意味を持ちます．

このシュレディンガー方程式は，自然が従う方程式なので，実際に世に存在する電子や原子などのミクロなものはこれに従って存在しています．

この方程式により，波動関数（量子状態）がハミルトニアンに対してどのように時間発展するのかが分かります．

上のシュレディンガー方程式は時間に依存しますが，時間に依存しない場合は，以下のように書けます．

$\hat H |\psi> = E |\psi>$

ほとんど変わらないように見えますが，エネルギー演算子 $\hat E$ が定数 $E$ になっています．この式はハミルトニアン $\hat H$ に対して， $|\psi>$ を固有状態， $E$ を固有値とした固有方程式となっていることがわかります．

この時間依存しないシュレディンガー方程式は単にシュレディンガー方程式と呼ばれることが多いです．

量子アニーリングでは，時間依存しないシュレディンガー方程式が常に成り立つ程度にゆっくりと外部磁場を弱め，ハミルトニアンを変化させます．

つまり，量子アニーリングの過程では上の固有方程式（時間依存しないシュレディンガー方程式）を解き，固有値，固有状態を求めればよいことになります．

それでは，いよいよ量子アニーリングの流れについて説明していきます．

とはいっても，おおまかな流れはすでに上で述べました．

解きたい組合せ最適化を量子アニーリングで解ける形に直し（Step1），外部磁場が加わったハミルトニアンに対するシュレディンガー方程式を，外部磁場を弱めながら解いていき，外部磁場が０になったときの固有状態を最適解とする（Step2）流れです．

量子アニーリング Step１．問題をイジング形にする

量子アニーリングを実行するには，解きたい最適化問題の目的関数を，イジング模型と呼ばれる，スピンが並んだもののハミルトニアンの形にします．

以下は，イジング模型の説明です．

イジング模型の説明

一番簡単なイジング模型のハミルトニアンは，以下の形で表します．

$\hat H = -\sum_{i<j} J_{ij} \hat\sigma_i^z \hat\sigma_j^z$

$J_{ij}$ はスピン $i$ とスピン $j$ の相互作用の強さを表します． $\hat\sigma_i^z$ はスピン $i$ のパウリ行列であり，先ほど述べたように，波動関数を作用させると固有値１もしくは－１を吐き出します．

$\hat\sigma_i^z$ は具体的には，

$\hat\sigma_i^z=I_1 \otimes I_2 \otimes \cdots \otimes \left( \begin{array}{cc} 1&0\\ 0&-1\\ \end{array} \right)_i \otimes \cdots I_N$

です．

$I_k$ は2×2の単位で， $\otimes$ は直積です．直積の計算方法については，こちらをご覧ください．https://atsblog.org/tyokuseki-matrix/

とはいえ，直積のような，難しい行列計算をわざわざする必要はありません． $\hat\sigma_i^z$ は単にスピン $i$ にだけ作用する演算子です．

例えば，2つのスピンがあったとして，それを $|\uparrow\downarrow>$ （1つ目のスピンが上向き，2つ目のスピンが下向き）のように表すと，

$\hat\sigma_1^z|\uparrow\downarrow>=|\uparrow\downarrow>$

（スピン１だけに作用して，固有値１を吐き出した）

$\hat\sigma_2^z|\uparrow\downarrow>=-|\uparrow\downarrow>$

（スピン２だけに作用して，固有値ー１を吐き出した）

となるだけです．

ハミルトニアン $\hat H$ を見ればわかるように，２個のスピン $i,j$ に対して $J_{ij}>0$ のときは，２個のスピンは同じ向きを向いたほうがエネルギーが小さくなります．反対に， $J_{ij}<0$ のときは，反対向きを向いたほうがエネルギーが小さくなります．

具体例

ここで，具体例で見てみましょう．スピンが3つである場合を考えます．パターンとしては，2×2×2＝8通りあり，この8通りからハミルトニアンが最小になるものを見つけます．

各スピンの相互作用 $J_{ij}$ は， $J_{12}=1,J_{23}=-2,J_{31}=5$ とします．

すると，この場合，ハミルトニアンは

$\hat H = - \hat\sigma_1^z \hat\sigma_2^z +2 \hat\sigma_2^z \hat\sigma_3^z -5 \hat\sigma_3^z \hat\sigma_1^z$

となります．では，各スピンを作用せます．例えば， $|\uparrow\downarrow\downarrow>$ を作用させると，

$\begin{split} \hat H |\uparrow\downarrow\downarrow>= (-\hat\sigma_1^z \hat\sigma_2^z +2 \hat\sigma_2^z \hat\sigma_3^z -5 \hat\sigma_3^z \hat\sigma_1^z )|\uparrow\downarrow\downarrow> = (1+2+5)|\uparrow\downarrow\downarrow> = 8|\uparrow\downarrow\downarrow>\end{split}$

となり，固有値（イジング模型のエネルギーに相当するもの）は8になります．

同様に，すべてのスピン状態について調べると，

$\hat H|\uparrow\uparrow\uparrow>= -4|\uparrow\uparrow\uparrow>$

$\hat H|\uparrow\downarrow\uparrow>= -6|\uparrow\downarrow\uparrow>$

$\hat H|\uparrow\downarrow\downarrow>= 8|\uparrow\downarrow\downarrow>$

$\hat H|\downarrow\uparrow\downarrow>= -6|\downarrow\uparrow\downarrow>$

$\hat H|\uparrow\uparrow\downarrow>= 2|\uparrow\uparrow\downarrow>$

$\hat H|\downarrow\uparrow\uparrow>= 6|\downarrow\uparrow\uparrow>$

$\hat H|\downarrow\downarrow\uparrow>= 2|\downarrow\downarrow\uparrow>$

$\hat H|\downarrow\downarrow\downarrow>= -4|\downarrow\downarrow\downarrow>$

となり，最小の固有値-6をとる $|\uparrow\downarrow\uparrow>,|\downarrow\uparrow\downarrow>$ の状態が最適解になります．

このように，3つの変数（スピン）だけでも，最適解を探すのは大変ですね（対称性を利用すればもう少し計算量が減りますが）．

このような全てのスピン状態を書き出す大変な作業をしなくても，シュレディンガー方程式という自然法則を応用して最適解を見つけるというのが，量子アニーリングです．

ここでは述べたのはスピン同士の2体相互作用のみを考慮したハミルトニアンですが，ハミルトニアンをパウリ行列 $\hat\sigma_i^z$ で表すことさえできれば，他の形のハミルトニアンでも量子アニーリングを行うことができます．

さて，解きたい組合せ最適化問題の目的関数を，上で説明したイジング模型のハミルトニアンの形にします．

ここでは例として，代表的な組合せ最適化問題である巡回セールスマン問題（TSP）を扱いましょう．

巡回セールスマン問題をイジング模型に書き直す

巡回セールスマン問題は，複数の都市を訪れ，同じ場所に戻ってくる問題です．

この組合せの数は都市の数 $N$ に対して $(N-1)!/2$ 通りあるので，しらみつぶしに調べていくのは困難なため，アニーリング法などの最適化手法を用いて計算します．

目的関数は，その総移動距離であり，都市 $i$ と都市 $j$ の間の距離を $c_{ij}$ とすると，

$J = \sum_{i,j}^N c_{ij}x_{ij}$

です．ただし， $x_{ij}$ は都市 $i$ と都市 $j$ に行く選択をしたなら１，行かない選択をしたなら０をとる変数です．つまり，この $x_{ij}$ のパターンの中から，目的関数が最小になるものを探すことが目標となります．

上の目的関数は，以下のようにも書くことができます．

$J = \sum_{i,j}^N\sum_{k=1}^N c_{ij}x_{i,k}x_{j,k+1}$

$k$ は都市を周る順番を表しており， $x_{i,k}$ は $k$ 番目に都市 $i$ を訪れたなら１，そうでないなら０です．このように書くことで， $x_{i,k}$ と $x_{j,k+1}$ がどちらも１をとるときにのみ $c_{ij}$ が目的関数に加算されます．

例えば，上の図について書くと， $x_{i,k}$ は以下のように値を取ります．

	０	１	２	３	４	５	６	７
１	１	０	０	０	０	０	０	０
２	０	１	０	０	０	０	０	０
３	０	０	０	０	０	１	０	０
４	０	０	０	０	０	０	１	０
５	０	０	０	０	０	０	０	１
６	０	０	０	０	１	０	０	０
７	０	０	１	０	０	０	０	０
８	０	０	０	１	０	０	０	０
１	１	０	０	０	０	０	０	０

列番号は都市，行番号は周る順番です．

この表を見てわかるように，この問題では，1周する間に各都市は一度だけ訪れ（表において各列に１は１つだけ），各時点で訪れる都市は１つだけ（表において各行において１は１つだけ）という制約があります．

すなわち，制約条件は，全ての都市について $\sum_{k}x_{i,k} = 1$ ，全ての時刻において $\sum_{i}x_{i,k} = 1$ が成り立つことです．

目的関数を最小化したときにこれらの制約が自然に満たされるように，目的関数を

$J = \sum_{i,j}\sum_{k=1} c_{ij}x_{i,k}x_{j,k+1}+\alpha\sum_{i}(\sum_{k}x_{i,k} - 1)^2 + \beta\sum_{k}(\sum_{i}x_{i,k} - 1)^2$

とします． $\alpha, \beta$ は制約が満たされるくらい十分大きな係数です．この目的関数を最小化したとき，第二項，第三項は０に近づくので，制約が満たされることになります．

さて，この目的関数は０と１の値をとる変数のみで記述されており，イジング模型のハミルトニアンと似ていることがわかります．

ただし，スピンはー１，１をとるため，０，１に変換しなければなりません．－１，１を０，１に変換するには

$x = (1+\sigma) / 2$

とすれば， $\sigma = -1$ のときに $x = 0$ , $\sigma = 1$ のときに $x = 1$ となります．

この変換は最適化を行った後に変換してもよいですし， $x$ を目的関数に代入して $\sigma$ の関数で表しても，

$\hat J = \sum_{i,j}\sum_{k=1} c_{ij}\sigma_{i,k}\sigma_{j,k+1}+\alpha\sum_{i}(\sum_{k}\sigma_{i,k} - 1)^2 + \beta\sum_{k}(\sum_{i}\sigma_{i,k} - 1)^2 + (const)$

と，変数 $\sigma$ によらない定数 $(const)$ がくっつく形になるだけあり，最小化する過程ではこの定数は意味をなさないため，目的関数は変数をー１，１だと思っても本質的には変わらず，結局，巡回セールスマン問題の目的関数と同じ形の

$\hat J = \sum_{i,j}\sum_{k=1} c_{ij}\hat\sigma_{i,k}^z\hat\sigma_{j,k+1}^z+\alpha\sum_{i}(\sum_{k}\hat\sigma_{i,k}^z - 1)^2 + \beta\sum_{k}(\sum_{i}\hat\sigma_{i,k}^z - 1)^2$

をハミルトニアンとして用いればよいことになります．

ただし，量子アニーリングでは目的関数ではなく，ハミルトニアン（演算子）に対する固有値が最小になるように計算するので， $\sigma$ は演算子であるパウリ行列に書き直しました．

さて，これで巡回セールスマン問題の目的関数をイジング模型のハミルトニアンに書き直すことができました（とはいえ，大きな変更は加えていませんが）．

このように，あらゆる組合せ問題はイジング模型のハミルトニアンとして書き直すことができ，書き直すことで量子アニーリングを実行することができます．

外部磁場を加える

量子アニーリングでは，このイジング模型のハミルトニアンに，外部磁場によるハミルトニアンを加えます．

もとの解きたい問題のハミルトニアンを $\hat H_c$ とすると（先ほどの巡回セールスマン問題の例で言えば， $\hat H_c$ は $J$ ），量子アニーリングのハミルトニアンは

$\hat H = \hat H_c - \Gamma\sum_{i}^{N}\hat\sigma_i^x$

のようにします． $\hat H_q=-\Gamma\sum_{i}^{N}\hat\sigma_i^x$ は横磁場のハミルトニアンです．

$\Gamma$ は磁場の強さ， $\hat\sigma^x$ はx方向横方向のパウリ行列で，

$\hat\sigma^x = \left( \begin{array}{cc} 0&1\\ 1&0\\ \end{array} \right)$

です．z成分のパウリ行列と同様， $\hat\sigma_i^x$ はスピン $i$ のみに作用します．一応定義を書いておくと，

$\hat\sigma_i^x=I_1 \otimes I_2 \otimes \cdots \otimes \left( \begin{array}{cc} 0&1\\ 1&0\\ \end{array} \right)_i \otimes \cdots I_N$

です．

ここで，一つのスピンに対するx成分のパウリ行列 $\hat\sigma^x$ の意味について考えてみます．上向きスピン，下向きスピンを作用させてみると，

$\hat\sigma^x |\uparrow>=\left( \begin{array}{cc} 0&1\\ 1&0\\ \end{array} \right) \left( \begin{array}{cc} 1\\ 0\\ \end{array} \right) = \left( \begin{array}{cc} 0\\ 1\\ \end{array} \right)=|\downarrow>$

$\hat\sigma^x |\downarrow>=\left( \begin{array}{cc} 0&1\\ 1&0\\ \end{array} \right) \left( \begin{array}{cc} 0\\ 1\\ \end{array} \right) = \left( \begin{array}{cc} 1\\ 0\\ \end{array} \right)=|\uparrow>$

となり，スピンを上下反転させることが分かります．

また，上下スピンを重ね合わせたスピン状態

$|+> = \frac{1}{\sqrt 2}(|\uparrow>+|\downarrow>)=\frac{1}{\sqrt 2}\left( \begin{array}{cc} 1\\ 1\\ \end{array} \right)$

$|-> = \frac{1}{\sqrt 2}(|\uparrow>-|\downarrow>)=\frac{1}{\sqrt 2}\left( \begin{array}{cc} 1\\ -1\\ \end{array} \right)$

を $\hat\sigma_i^x$ に作用させると，

$\hat\sigma^x|+> = \left( \begin{array}{cc} 0&1\\ 1&0\\ \end{array} \right)\frac{1}{\sqrt 2}\left( \begin{array}{cc} 1\\ 1\\ \end{array} \right)=\frac{1}{\sqrt 2}\left( \begin{array}{cc} 1\\ 1\\ \end{array} \right)$

$\hat\sigma^x|-> = \left( \begin{array}{cc} 0&1\\ 1&0\\ \end{array} \right)\frac{1}{\sqrt 2}\left( \begin{array}{cc} 1\\ -1\\ \end{array} \right)=-\frac{1}{\sqrt 2}\left( \begin{array}{cc} 1\\ -1\\ \end{array} \right)$

となり， $|+>,|->$ は $\hat\sigma_i^x$ の固有値になっていることが分かります．

すなわち，横磁場を受けたスピンは，上下スピンが等確率で重なっている状態であるということが分かります．

量子アニーリングでは，この横磁場を弱めていくことで，本来求めたいハミルトニアンの形に徐々に近づけていきます．

量子アニーリングの Step２．外部磁場を下げながらシュレディンガー方程式を解く

量子アニーリングのアルゴリズムの手順は次の通りです．

量子アニーリングのアルゴリズム

０．ステップ $t=0$ で $\hat H(0) = \hat H_q(0) = - \Gamma(0)\sum_{i}^{N}\hat\sigma_i^x$ とし，初期解を $|\psi>=(\frac{1}{2})^{N/2}\prod_{i=1}^{N}(|\uparrow>_i+|\downarrow>_i)$ とする．

１． $t=t+1$ とし，ハミルトニアン $\hat H(t)=\hat H_c(t)-\Gamma(t)\sum_{i}^{N}\hat\sigma_i^x$ に対してシュレディンガー方程式を用いて固有値，固有状態を求める（正確には，状態を時間発展させる）．このとき， $\Gamma$ は小さくなる．

２．終了条件（ $\Gamma$ が十分小さくなる， $\hat H = \hat H_c$ となる）を満たせば終了．そうでないなら，１に戻る．

これを詳しく説明していきます．

初期解

量子アニーリング開始時のハミルトニアン $\hat H(t=0)$ は， $\hat H_c(t=0)=0$ ， $\hat H_q(t=0)$ は十分大きな値にしておきます．つまり，初期ステップ（時刻）でのハミルトニアンは $\hat H(0)=\hat H_q(0) = - \Gamma(0) \sum_{i}^{N}\hat\sigma_i^x$ です．例えば，十分大きな定数 $T$ を用いて

$\hat H(t) = \frac{t}{T} \hat H_c - (1-\frac{t}{T}) \sum_{i}^{N}\hat\sigma_i^x$

としておけば， $\hat H(t=0) \simeq \hat H_q$ ， $\hat H(t=T) \simeq \hat H_c$ となります．この場合，ステップ $t=T$ が終了条件となります．

初期解 $|\phi>$ は， $\hat H_q(t)=- \Gamma(t) \sum_{i}^{N}\hat\sigma_i^x$ のみに対する解であり，これはすべてのスピン状態を等確率で重ね合わせたものになるので，

$|\psi>=(\frac{1}{2})^{N/2}\prod_{i=1}^{N}(|\uparrow>_i+|\downarrow>_i)$

です（2個下の図の左の青い部分）．

これは， $\hat \sigma_i^z$ の±１の固有状態 $|\uparrow>_i, |\downarrow>_i)$ を書くサイト $i$ について積を取ったものであり，これを展開すると，すべてのスピン状態を等確率 $(\frac{1}{2})^{N/2}$ で足し合わせたものになっています．

磁場を弱める

$\Gamma(t)$ を小さくしていき，その都度，シュレディンガー方程式を解いて固有状態（スピン状態，解）を求めいていきます（ただし，後で述べるように，古典コンピュータではシュレディンガー方程式を毎回解く（状態を時間発展させる）のは現実的ではないので，他の方法を用います）．

そして， $\Gamma=0$ ，つまり横磁場が０となったときの各スピンの状態（z方向に上向きか下向きか）が，（不思議と？）最適解となっているというわけです．

ハミルトニアンと各スピンのz成分の確率に注目して言えば，ハミルトニアンは始めは $\hat H_c=0$ であり，初期解はすべてのスピン状態は等確率をとっているので，平坦なハミルトニアンに等確率で状態が存在していることになり，最終状態では $\hat H$ は本来の形になり，特定のスピン状態が高い確率で存在しているというイメージです．