Ising Modelと量子アニーリング
Ising(イジング)模型は強磁性などの物性を説明する簡単な模型で、各格子点に電子のスピンを置く。スピンは微小磁石のように振舞い、上向き、あるいは下向きの状態を取る。
-
Ising模型は格子点に微小磁石のように振舞うスピンを置く。外部磁界がない状態ではスピンはランダムな向きをとる
外部磁界が無く、スピン間の影響がなければスピンの向きはランダムになる。しかし、スピンのペアが同じ方向を向いていればそのペアのエネルギーは低く、逆の方向を向いていれば寄与するエネルギーは大きいので、冷却して系のエネルギーが小さくなっていくと、エネルギーの小さいスピンの分布に変わっていく。系のエネルギーは、スピンのペアを総当たりで考え、全ペアのエネルギーの合計である。
ちょっと話題は変わるが、金属の加工でアニーリング(Annealing)という処理がある。金属の鍛造や切削加工などを行うと歪みが残る。これをいったん、高い温度に加熱し、そこから徐々に冷ましていく処理をアニールという。また、この処理は日本語では焼き鈍しという。アニールを行うと、歪みが緩和されてエネルギーの低い状態になる。
焼き鈍しの場合は、冷えるにしたがってエネルギーが低い状態に落ち着いて行く。
ここで話を戻して、Ising模型の各格子点のスピンの状態をTSPの訪問経路に対応させ、その時の系のエネルギーを経路の全長に対応するようにしておけば、最低エネルギーの状態に落ち着いた時の各格子点のスピンの状態が最短の旅行経路を示す解になっている。というのがアニーリングによって組み合わせ最適化問題の解を得るというやり方の基本的な考え方である。経路とスピンをどのように対応させるかは、この先で述べる。
このアニールをコンピュータシミュレーションで行うのがシミュレーテッドアニーリング(Simulated Annealing:SA)である。ただし、自然に冷却すれば、エネルギー最低の状態に落ち着くかというと、そう上手くは行かない。
格子点のスピンの分布でエネルギーは不連続に変わり、山あり谷ありの状態になるので、局所的な最適点に捕まってしまうと、少しスピンの分布を変えてもエネルギーが増えてしまい、全体的な最低エネルギー点には到達できないということが起こる。そうなると、全体最適点を見つけることはできない。
なお、次の図では系のエネルギーは連続した曲線になっているが、実際にはスピンの状態は定義された点でしか値をもたない不連続な曲線である。また、図の都合上、スピンの状態は1次元で表しているが、前の図のように2次元のスピンの分布の場合は、このグラフのスピン分布も2次元にして、系のエネルギーは第3の次元にした方が良い。
-
局所的なエネルギー勾配を見てエネルギーの低い方向に移動するだけでは、局所最適点に捕まって、全体的なエネルギー最適点を見つけられないということが起こる
このような問題を軽減するため、SAでは局所最適点で止まっている場合には、もう一度エネルギーを与えて状態の変化を活発にして、山を乗り越えさせる。そして、以前よりエネルギーの低い状態が見つかれば、そこから近隣にさらにエネルギーの低い状態が無いかを探すということが行なわれる。
この再加熱であるが、アニールの初期には大きなエネルギーを与え、高い山でも乗り越えられるようにし、エネルギーが低くなるにつれて再加熱の程度を下げていくというようなことが行なわれる。
しかし、格子点が多くなると、エネルギーの変化は複雑になり局所的な最低エネルギー点も増えてくる。このため、アニーリングあるいはシミュレーテッドニーリングで最低エネルギーの状態にたどり着けるとは限らない。
1998年に東京工業大学の西森秀稔教授と当時学生であった門脇氏が考えた理論が、このアニーリングを量子的に行うこととなることが分かり、カナダのD-Wave社が超電導の量子アニールマシンを商用化している。
量子的にアニールを行うと、各格子点のスピンはもつれ状態になっており、ある意味、山で隔てられた近隣の低エネルギーの谷を見つけて、量子トンネル効果で移動できるので、より効率的に低いエネルギー状態を見つけることができる。
アニーリングでは全体最適点が見つかるとは限らないが、TSPの場合を考えてみると、全体最適点に近い、例えば距離が1%長いだけというような解が、実用的な時間で見つかれば良いというケースが大部分である。したがって、アニーリングマシンも最適点を見つけられなくても、実用的な時間で、かなり良い解を見つけることができれば十分であると考えられている。
(次回は6月6日に掲載します)
