イジングモデル

イジングモデル

執筆済 最適化QUBOイジング模型

スピンが ±1 の 2 値を取り、隣接するスピン間に相互作用があるという統計物理の模型。

H(s)=−∑i<jJijsisj−∑ihisi,si∈{−1,+1}
  • Jij … 結合定数。正なら同じ向きが得（強磁性）、負なら逆向きが得（反強磁性）
  • hi … 局所磁場。スピンを一方へ傾ける外部の力

最適化との関係#

H を最小にするスピン配置を求めることが、そのまま QUBOと等価な組合せ最適化になる。 変換は si=2xi−1 という一次の置き換えだけ。

フラストレーション#

すべての相互作用を同時に満たせない状況。 三角形の 3 辺すべてが反強磁性だと、どう配置しても 1 辺は不満が残る。

フラストレーションがあると基底状態が多数になり、 エネルギー地形が凹凸だらけになる。これが 局所最適解の多さに対応する。 スピングラスと呼ばれるこの状態の基底状態探索が NP 困難であることが、 組合せ最適化の難しさの物理的な言い換えになっている。

歴史#

強磁性を説明するために Lenz が考案し、Ising が 1925 年に 1 次元の場合を解いた（相転移は起きないという結論）。 Onsager が 1944 年に 2 次元の厳密解を与え、相転移の存在を示した。 3 次元は厳密解が知られていない。

参考文献#