イジングモデルと巡回セールスマン問題

はじめに

　最近注目されている量子アニーリングについて概説する。

イジング模型

　最初に、イジング模型と呼ばれる模型について説明する。下図に示すような格子を定義し、格子点上に「スピン」が配置されている系を考える。

本稿ではスピンという言葉を、+1と-1のいずれか一方の値を持つ変数として用いる（量子力学的に厳密な定義には触れない）。これをスピン変数と呼ぼう。上図では+1を上向きスピン、-1を下向きスピンとして表した。図では2つの格子点 $i,j$ 上にしかスピンを描いていないが、全格子点上にスピンは配置されている。次に、任意の格子点のペア $(i,j)$ の間に重み（相互作用） $J_{ij}$ を導入し、次式を考える。

(1) $\begin{equation*} H({\bf \sigma})=-\sum_{i<j}J_{ij}\sigma_i\sigma_j \end{equation*}$

ここで、 $\sigma_i$ はスピン変数である。また、 ${\bf \sigma}=(\sigma_1,\sigma_2,\cdots)$ は格子点上の全スピン変数を表す。 $\sum_{i<j}$ は、重複を除いた全ペアについて和をとることを意味する。式(1)をイジング模型と呼ぶ。

　量子アニーリングなる手法（後述）で実現したい目的は、式(1)を最小にする ${\bf \sigma}=(\sigma_1,\sigma_2,\cdots)$ の組み合わせを見つけることである。この難しさを具体的に見るため、三角形の3つの頂点上にスピンが定義されたイジング模型を考える（下図参照）。ペア間の相互作用を定数 $J_{ij}=-1$ とする。このときイジング模型は次式となる。

(2) $\begin{equation*} H(\sigma_1,\sigma_2,\sigma_3)=\sigma_1\sigma_2+\sigma_2\sigma_3+\sigma_3\sigma_1 \end{equation*}$

上図は $(\sigma_1,\sigma_2,\sigma_3)=(+1,-1,+1)$ のときである。このとき

(3) $\begin{eqnarray*} \sigma_1\sigma_2&=&-1\\ \sigma_2\sigma_3&=&-1\\ \sigma_3\sigma_1&=&1 \end{eqnarray*}$

が成り立つので、 $H(\sigma_1,\sigma_2,\sigma_3)=-1$ である。上図の辺上に各スピン対の相互作用の大きさを示した。もう一度注意深く上の図を眺めると、 $(\sigma_1,\sigma_2)$ のペアのスピンはお互いに逆向きであり、 $\sigma_1\sigma_2$ は最小値-1になっている。同様に、 $(\sigma_2,\sigma_3)$ のペアも逆向きであり $\sigma_2\sigma_3$ は最小値-1になっている。最後のペア $(\sigma_3,\sigma_1)$ も逆向きにとれれば、総和である $H(\sigma_1,\sigma_2,\sigma_3)$ を最小にできるはずである。しかしながら、このペアを逆向きにとると、今度は $(\sigma_1,\sigma_2)$ のペアが同じ向きを向いてしまう。このような「あちらを立てればこちらが立たず」の状態をフラストレーションと呼ぶ。局所的な状態の最小値が系全体の最小値にならないことを示す言葉である。

　一般のイジング模型では、ペア間の相互作用 $J_{ij}$ は任意の実数値を取り得るため、式(1)を最小化するスピン変数の組を探す問題は大変難しい。式(1)を最小にするスピンの組を探すことを物理の言葉で「基底状態」を探すと言う。また、式(1)を「ハミルトニアン」、 $H(\sigma)$ の最小値を「基底エネルギー」と呼ぶ。

量子アニーリング

　イジング模型の基底状態を量子効果を用いて求める方法が量子アニーリングである。本稿では量子効果の詳細は割愛し、量子アニーリングの概略だけを説明する。最初に、次のイジング模型を考える。

(4) $\begin{equation*} H_0({\bf \sigma})=-\sum_{i<j}J_{ij}\sigma_i^z\sigma_j^z \end{equation*}$

ここで、 $\sigma_i^z$ はこれまでのような(-1,+1)のいずれかの値を取るスピン変数ではなく、パウリ行列の $z$ 軸成分と呼ばれるものである（ $2\times2$ の行列）。スピン変数をパウリ行列に置き換えることにより量子効果を取り入れることができる（そういうものであると認めてほしい）。量子アニーリングの目的は、 $H_0$ の基底状態 $\Psi_0$ を見つけることである。

　ところで、 $z$ 軸とは垂直な方向の $x$ 軸成分 $\sigma_i^x$ を考え、次のハミルトニアンも考える。

(5) $\begin{equation*} H_1({\bf \sigma})=-\sum_i\sigma_i^x \end{equation*}$

この項は、スピンの向き（ $z$ 軸方向）に対し垂直な方向に磁場をかけることにより生じるエネルギーなので、「横磁場項」と呼ばれる。この基底状態は簡単に求めることができる。いまこれを $\Psi_1$ と書くことにする。量子アニーリングでは、答えの分かっている自明な基底状態 $\Psi_1$ を、時間をかけてゆっくりと非自明な基底状態 $\Psi_0$ に変化させていく。これを実現するため、時間に依存する2つの係数 $A(t),B(t)$ を導入し、次のハミルトニアンを考える。

(6) $\begin{equation*} H({\bf \sigma})=A(t)H_0({\bf \sigma})+B(t)H_1({\bf \sigma}) \end{equation*}$

$A(t),B(t)$ の時間変化は下図の通りである。

非常に長い時間 $\tau$ をかけて $A(t),B(t)$ をゆっくりと変化させる。時刻 $t=0$ のハミルトニアンは $H_1$ であり自明な基底状態 $\Psi_1$ を持つ。その状態からゆっくりと $A(t),B(t)$ を変化せていくと、基底状態が $\Psi_0$ に変化していく（下図参照）。

この一連の手順を量子アニーリングと呼ぶ。ゆっくりと変化させないと励起状態（基底状態より高いエネルギーを持つ状態）に遷移してしまうので注意が必要である。ここで注目すべきことは、基底状態の変化は、自然の摂理に従って（すなわち量子力学の原理に従って）起こるということである。人間が調節するのは $A(t),B(t)$ だけである。 $A(t),B(t)$ さえ調節してやればあとは勝手に基底状態が決まるのである。

　最後に、量子アニーリングの対象となる実際のチップを示す（ここから引用した）。このチップ上に、本稿の一番最初に示した格子が実装され、その格子点上に量子力学的なスピンが配置されている。

　最適化問題をイジング模型に落とし込むことができれば、量子アニーリングを用いて、基底状態（最適なパラメータの組）を求めることできる。その一例として巡回セールスマン問題（Traveling Salesman Problem:TSP）を考える。

巡回セールスマン問題（TSP）

　決められた都市をすべて1度ずつ訪れて元の都市に戻ってくるための最短経路を探すのが巡回セールスマン問題である（下図参照）。

上図は5都市の巡回セールスマン問題である。AからEまでの点を結ぶ最短経路を探すことになる。5都市の巡回セールスマン問題をイジング模型で表すため、5×5の表を作る。

この表は、１番目にA都市を訪れ、2番目にE都市を訪れ、3番目にD都市を訪れることを表している。経路を1つ決めるとそれに対応する表を1つ作ることができる。いま、都市 $\alpha$ かつ $i$ 番目のマスに入れる変数を $q_{\alpha i}$ と書くことにする。また、都市 $\alpha$ と $\beta$ の間の距離を $d_{\alpha\beta}$ とすると、全経路の長さ $L$ は

(7) $\begin{equation*} L=\sum_{\alpha,\beta}\sum_{i=1}^{5}d_{\alpha\beta}\;q_{\alpha i}\;q_{\beta i+1} \end{equation*}$

となる。 $q_{\alpha i}$ は0か1であるから、 $q_{\alpha i}$ と $q_{\beta i+1}$ がともに1のときのみ、距離が加算される。さて、上の表をもう一度眺めると、各行の数字の和は常に1であることが分かる。これは、1度に訪れることできる場所は1か所だけであることを表している。さらに、各列の数字の和も常に1である。これは、各都市には1度だけ訪れることを表している。この2つの束縛条件を式(7)に追加する。

(8) $\begin{equation*} H_0=\sum_{\alpha,\beta}\sum_{i=1}^{N}d_{\alpha\beta}\;q_{\alpha i}\;q_{\beta i+1}+ a\sum_{\alpha}\left( \sum_{i=1}^Nq_{\alpha i}-1 \right)^2+ b\sum_{i=1}^N\left( \sum_{\alpha}q_{\alpha i}-1 \right)^2 \end{equation*}$

上式において、都市の数5を一般の数 $N$ に置き換えた。0と1の値を取る変数 $q_{\alpha i}$ を-1,+1の値を持つスピン変数に置き換えれば、イジング模型のハミルトニアンになる。さらに、パウリ行列に置き換えれば、量子アニーリングを用いて解くことができるハミルトニアンになる。 $a,b$ はそれぞれの束縛条件をどの程度重視するかを決める係数である。式(8)が式(6)の $H_0$ に相当する。ここに横磁場項 $H_1$ を加えて量子アニーリングを行い、最適解（ $H_0$ の基底状態）を見つけることになる。

量子アニーリングの現状

　TSPを含む最適化問題に適用される解法には以下の3つがある。

厳密解法：文字通り、厳密な解を求める方法である。

近似解法：厳密解からのずれが、ある範囲内に収まっていることが保証される解法（近似性能の保証がある解法）

発見的解法：近似性能の保証がない解法

今回説明した量子アニーリングが属するのは、3番目の発見的解法である。TSPは歴史の長い問題であり、現在では、85,900都市の厳密解と1,904,711都市の近似解が求められている。いずれも量子アニーリングを用いない手法である。また、普通のPCでも2392都市の厳密解を1分もかからずに解くことができる（動画）。さらに、このページでは、3次元のTSPの現状が紹介されている。これを見ると、1,331,906,450地点の3次元TSPの近似解が存在することが分かる。
　一方、現在の量子アニーリングで解けている最大の都市数はいくつなのかを調べたが、明確な数を記載したページが見つからなかった。ところで、量子アニーリングを従来のGPUやFPGAを用いて模倣したマシンを東芝が出している。これは現在の量子アニーリングよりも多くのスピンを扱うことができるので、TSPの都市数も量子アニーリングより大きくすることができるが、それでも数十都市が限界のようである（参照サイト）。

　量子アニーリングの優位性を謳うのにTSPを例に取り上げる記事を多く見かけるが、上で見るように正しい主張ではない。ビジネストークであると割り切る必要がある。最近、量子アニーリングを搭載したマシンを開発している唯一の企業であるD-wave社が、量子ゲート方式の開発も始めると言うアナウンスがあった（例えばこの記事）。量子アニーリングだけではビジネスが成り立たないと言うことであろう（おそらく）。