第3章 アニーリングマシンと2次式と離散値の関係
第2節 アニーリングマシンは2次の問題に向けた技術
前述した1次式は他の方法で簡単に解けるのに対し、2次式の最適化問題についてはアニーリングマシンで効率的に解くことができると考えられます。第1節で説明した通り、2次式とは変数を2個かけあわせた項があるというものです。第1章で説明した画像のノイズリダクションの定式化では$s_i$と$s_j$をかけた項$s_is_j$や$h_is_i$が存在するので、2次式ですね。では、この$s_is_j$があるとアニーリングマシンによってどのような効果が得られるのでしょう。
第1章では、アニーリングによりエネルギーが最も低くなる$s_i$（スピン）の状態を探すという話をしました。この時、$a_is_i$（$a_i$は係数）といういわゆる1次の項しかなかった場合、係数が正の値なら$s_i$が$-1$の方がコスト関数が低くなります。一方で係数が負の値なら$s_i$が$+1$の方がコスト関数が低くなります。つまり1次の項では係数は固定なので、$s_i$の値次第（$+1$か$-1$）で最適かどうかが決まるのです。一方で、$a_{ij}s_is_j$という2次の項では、係数$a_{ij}$が正であれば、$s_is_j$が負となる場合にエネルギーが負となり（低くなり）ます。$s_is_j$が負になるのは、$s_i$が正かつ$s_j$が負の場合、もしくは$s_i$が負かつ$s_j$が正の場合の2パターンとなりますね。逆に係数$a_{ij}$が負であれば$s_is_j$が正の場合がエネルギーが負となりますので、この場合は$s_i$が正かつ$s_j$が正、もしくは$s_i$が負かつ$s_j$が負の場合に最適解となります（イジングモデルでも説明の通り）。つまり、2次の$a_{ij}s_is_j$という項がある場合、$s_i$と$s_j$のペアは相手次第によりエネルギーを低くするか高くするか、すなわち最適解になるか否かが変わるということです。これは、$s_i$の値を決める時に非常に厄介です。相手の$s_j$も$s_i$の状態が決まらなければどっちの値になるのが最適かわからないわけで、お互いにらみ合った状態と言えるでしょうか。よって、従来の手法で解こうとするとこの2次の項を総当たりでシミュレーションするようなことが必要になり難しいのです。
