量子アニーリングの理論を学んでみる-その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量子アニーリングを語るための、数学的準備(数式)

に続きます。