入力データ作成
概要
「定式化」を行った数分割問題について、入力データを作成します。機械的な操作ですが、本記事では基本的な事項をおさえていきます。
STEP1. 入力データは$J_{ij}$のリスト
定式化ではイジングモデルを考え、コスト関数$H$を定義しました。
$i,j$といった指数は$S$の中の$i$番目,$j$番目の要素という意味です。この例題では数字が19個あるので$i=1,2,3,…,19$となります。$j$も同様です。(ただし$i≠j$)
イジング変数$\sigma_i$（スピンとも呼ばれます）は、$i$番目の要素を$S_A$に入れたか$S_B$に入れたかを表すもので、$S_A$に入れた場合に$\sigma_i=+1$と、$S_B$に入れた場合に$\sigma_i=-1$とすることと定式化しました。
このとき、ある組合せ$\sigma_1,\sigma_2,...,\sigma_N$に対するコスト関数$H$を計算するためには、$a_ia_j$の部分が分かっている必要があります。つまり、すべての$i,j$の組み合わせに対する$a_ia_j$の計算値が、アニーリングマシンに対する入力データとなります。$a_ia_j$の部分は、$J_{ij}$とも呼ばれます。
$$ \text{数分割問題の入力データ} \\ J_{ij} = a_ia_j $$
ところで、$J_{ij}$は、どのような意味があるのでしょうか。
下図左がイジングモデル全体だとした場合、ひとつの$J_{ij}=a_ia_j$は右側の拡大図であらわされるように、イジング変数$\sigma_i$と$\sigma_j$の間に働く影響の強さを表していると考えられます。このスピンとスピンの間に働く力を相互作用といいます。
コスト関数とイジングモデルの関係のイメージ
アニーリングマシンの最適化処理とは、$\sigma_1,\sigma_2,...,\sigma_{19}$のそれぞれに$+1$か$-1$を当てはめた組合せのうち最もコストの低いものを見つけ出すことです。コストを計算するために与える情報は $J_{ij}=a_ia_j$、つまり相互作用です。アニーリングマシンが必要としている入力データとは相互作用のことなのです。
STEP 2. 数分割問題での$J_{ij}$を計算してみよう
数分割問題での相互作用$J_{ij}$を具体的に計算していきましょう。
以下のように、要素1から要素19までまんべんなく掛け合わせることで与えるべき相互作用がすべて得られます。
$$ J_{12} = a_1 \centerdot a_2 = 3 \times 1=3 \\ J_{13} = a_1 \centerdot a_3 = 3 \times 4=12 \\ J_{14} = a_1 \centerdot a_4 = 3 \times 15=45 \\ \centerdot \\ \centerdot \\ \centerdot \\ J_{1819} = a_{18} \centerdot a_{19} = 28 \times 84=2,352 $$
図では省略してありますが、相互作用の総数は $19×(19-1)/2=152$個あります。$152$個の値をアニーリングマシンに入力する必要があります。
STEP3. 要素が増えると大量のデータが必要となる
要素数の2乗に比例して計算量が増える場合、数学的な表現では$\mathcal{O}$（オーダ：計算量のこと）が$N^2$であるという言い方をします。つまり、数分割問題ではイジングモデルの相互作用のオーダは$N^2$と言えます。
上の図に示す通り、要素数が19個の場合でも、イジングモデルの相互作用の係数が$152$個も必要であることがわかりました。もし要素の数が100個であった場合には、$100(100-1)/2=4950$個にも上ります。$\mathcal{O}(N^2)$となったのはどうしてでしょう。数分割問題の定式化では、すべての要素同士がつながっているので（全結合）、その相互作用は要素$x$要素分だけ必要となるためです。
定式化を要素間の関係をシンプルに、つまり掛け合わせが出てこないようにできれば、その分だけ相互作用の数が減り、入力データも減らすことができます。ちなみに、どの要素同士も相互作用できる場合に全結合と言います。
まとめ
- 入力データの作成とは、$J_{ij}$をすべて計算すること
- 入力データとは相互作用を表す数値であり、要素数が増えると2乗のオーダで増える可能性がある
- 要素間の関係がシンプルな場合には、相互作用の数はそれほど多くない場合もある
