イジングエディタで数分割問題を解こう

概要

CMOSアニーリングマシンの実行ではWEB-APIからCMOSアニーリングマシンで4つの数を分割する方法を説明していますが、同じことをイジングエディタでも実行することができます。イジングエディタはCMOSアニーリングマシンの動きを視覚的に表現した学習ツールですが、CMOSアニーリングマシンに何を入力し、どのように解を得るのかを目で見ながら確認するためには他にないツールとなっています。

• 事前準備このページを読む前に、定式化と入力データ作成を読んでください。
• 想定読者アニーリングマシンをWEB-APIで実行する前にもう少しアニーリングマシンの処理を理解したい人、自分で実行しなくてもアニーリングマシンの処理を理解したい人

イジングエディタに入力するデータ（相互作用）を準備する

イジングエディタの値とは、頂点や辺に割り当てる値です。イジングモデルの頂点は、$s=±1$を取るスピン変数であり、$+1$なのか$-1$なのかはアニーリングによって得られる結果が示します。では頂点に入力する値というのは何の値かというと、外部磁場係数$h_i$です。外部磁場係数$h_i$はコスト関数に1次の項があることを表します。今回解く数分割問題のコスト関数には1次の項がないため、外部磁場$h_i$として入力する数値はありません。

一方、辺として入力する値は相互作用です。相互作用は、アニーリングマシンに必須の入力データです。

イジングエディタでは、入力できる値は$-3,-2,-1,0,1,2,3$に限られます。よって、相互作用も外部磁場もこの範囲で入力する必要があります。

それではイジングモデルのコスト関数を満たし、かつイジングエディタの仕様を満たす値を準備します。まず数分割問題のコスト関数をイジングモデルとして立てたのが、以下の式でした。この問題では$a_ia_j$が相互作用です（入力データ作成）。

ここで分割する数を決めていくことにしましょう。相互作用の制約は$-3≦a_ia_j≦3$（$a_ia_j$は整数）なのでここでは$(a_1,a_2,a_3,a_4)=(-1,-1,1,2)$の4つの数を分割する場合の相互作用をすべて計算します。できるだけ合計が等しくなるように2つのグループに分けると、合計が$1$のグループと$0$のグループになるはずです。また、まずい結果であればどうなるかも想定できます。合計がそれぞれ$3$と$-2$に分かれた場合です。まず要素に以下の通り名前をつけ、次に、図を使ってイジングエディタのどこにどの相互作用をいれるか決めましょう。

格子状のイジングエディタには4つの数分割の全ての相互作用を入力できることがわかります。6本あります。

$J_{12},J_{13},・・・$の各相互作用は以下のようになります。

その配置のままイジングエディタに入力します。下記のようになります。

ここで、もし分割する数に2や3を同時に2個以上選んでしまっていたら相互作用として4や6や9が必要になるため、入力できないことがわかります。

STEP UP

よくある間違い：イジングエディタの頂点には分割したい数を入力しないのか?

頂点に入力するのは外部磁場係数$h_i$という係数であり、分割したい数ではありません。コスト関数に1次の項（$=\sigma$が2個ではなく1個だけの項）がある場合はこの係数が外部磁場係数です。数分割問題のコスト関数では、$\sigma$を2個掛け合わせた項（2次の項）だけです。そのためイジングエディタの頂点には何も入力しないのが正解です。例として、下のコスト関数の場合は外部磁場係数3があります。

よくある疑問：分割したい数をイジングエディタに入力しないのに格子状に並べたのはなぜか?

それは、相互作用係数の配置が重要だからです。相互作用は値だけではなく、位置も揃わなければ意味がありません。同じ値でも位置がいい加減になると、分割したい数という前提が崩れてしまうのです。

実行する

実行ボタンを押します。
OUTPUTのウィンドウに、スピンの向きが表示されます。同じ向きのスピンが同じグループになるということです。

上記のようになった場合は$(-1,2)$と$(-1,1)$に分かれています。数の合計はそれぞれ$1$と$0$です。

その後も何度も実行ボタンを押すことができます。1回目とまったく同じこともあります。

上記の場合は位置が変わりましたが2つある$-1$が交換されただけですね。数の合計はそれぞれ$1$と$0$です。

上記の場合は1個と3個に分かれました。合計は、上向き↑グループが$1$だけ、下向き↓グループは$(-1,-1,2)$なのでその合計は$0$です。

なんと、こんなのもあります。すべて下向き↓グループになってしまいました。$(-1,-1,1,2)$ですから合計は$1$です。他方のグループは、要素が無しですから合計は$0$。数の合計はそれぞれ$1$と$0$です。

何度実行しても、合計が$3$と$-2$に分かれることはありません。どうやらうまく最適化できているということがわかりました。

間違った値を入れたらどうなる？

間違った値を入れても実行処理は行います。つまり分割したい数の値を掛け合わせた値と異なる数値を辺に入力してもエラーが出るわけではなく、とりあえずスピンは確定してOUTPUTされます。しかしその場合、スピンの向きに意味があるかといえば、ありません。正確な値を入力することが解を得るために重要なのです。

まとめ

• アニーリングマシンの最適化処理で得られる解は、どのスピンが上向きあるいは下向きかの組み合わせである。
• イジングエディタは、スピンの外部磁場係数および相互作用係数を-3から3の間で入力して、イジングモデルの問題を解くことができる。
• 実行するたびに出てくる解（スピンの向き）は異なるが、エネルギーはどれも最小で、最適解^*が得られていることがわかる。
  *本来、最適解のみを導き出すとは限らず、今回の結果は問題が小さいことが理由で最適解のみを示しています。
• 間違った入力データを入れたとしてもエラーを返してくれるわけではない。

関連リンク

• CMOSアニーリングマシンの実行
• 疎結合と全結合（前編）
• 疎結合と全結合（後編）