このページでは、数の分割問題と呼ばれるNP完全な問題をイジングモデルで表現する方法について述べます。
問題の定式化 #
\(N\) 個の正の数の集合 \(S = \{n_1, n_2, \ldots, n_N \}\) が与えられます。 この集合を二つの非交な部分集合 \(R\) と \(S - R\) に分けて、 \(R\) 内の数の和と \(S-R\) 内の数の和を等しくすることができるでしょうか？
問題の具体例 #
具体的な問題を考えてみましょう。整数の集合 \(S=\{1,10,5,7,7\}\) を考えます。このとき、 \(S\) を \(A=\{1,7,7\}\) と \(B=\{10,5\}\) のように分割すると、 \(A\) に含まれる整数の和と \(B\) に含まれる整数の和はともに15となるので、この問題の答えはYESです。
次に、整数の集合 \(S=\{10,5,7,7\}\) を考えます。このとき、 \(S\) に含まれる整数の和は29であり、 \(S\) には整数しか含まれないので明らかに答えはNOです。
イジングモデルへの変形 #
この問題を解くイジングモデルのエネルギー関数は以下のように構築されます。
まず、 \(S\) の一つ一つの要素 \(n_i\) にイジングスピン変数 \(s_i = \pm 1\) を設定しましょう。 また、ある正の定数 \(A > 0\) を取りましょう。 するとエネルギー関数は \[ H = A \left( \sum_{i=1}^N n_i s_i \right) ^2 \] と記述されます。
エネルギー関数の最小化により数の分割問題が解けるのは何故か #
先ほど定義したエネルギー関数を最小化することで、本当に数の分割問題が解けているのでしょうか？ これは次のようにして確かめることができます。
エネルギー関数が最小化され、 \(H=0\) が達成されたとします。 このとき、 \(s_i= +1\) となっている \(n_i\) を集めて集合 \(R = \{ n_i | s_i = +1 \} \) を作り、残りの \(s_i= -1\) となっている \(n_i\) を集めて集合 \(S - R = \{ n_i | s_i = -1 \} \) を作りましょう。 \(H\) は以下のように変形されますから、確かにこの二つの集合内の数の和は等しく、数の分割問題が解けたことになります。 \[ H = A \left( \sum_{i=1}^N n_i s_i \right) ^2 = A \left( \sum_{s_i = +1} n_i - \sum_{s_i = -1} n_i \right)^2 = A \left( \sum_{n_i \in R} n_i - \sum_{n_i \in S - R} n_i \right)^2 = 0 \]
おまけ #
-
エネルギー関数を最小化して得られた解は”縮退（degeneracy）”しています。 というのも、 \(s_i = +1\) である方を \(R\) とっても良いし、逆に \(s_i=-1\) である方を \(R\) ととっても構いません。 つまり、二つの基底状態が一つの解を表してしまっています。 しかし、これは \(n\) 個のイジングスピン変数のうち一つを決め打つことで回避できるので大した問題ではありません。
-
元の数の分割問題は判定問題です。 しかし、エネルギー関数を得られる解は元の集合の実際の分割になっています。 これは素晴らしいことです。 往々にして、判定問題はNP完全であっても、その問題の実際の解を求める最適化問題はNP困難です。（NP完全な問題よりも難しい問題のクラス） エネルギー関数の最小化によって余計なコストをかけることなく、判定問題だけでなく最適化問題が解けることには大きな嬉しさがあるのです。
-
“エネルギー関数を最小化して、最小値が０でなかったらどうするの？“と思った方はいませんか？ それは素晴らしい洞察です。 実際、エネルギー関数を最小化して得られる最小値が０でなければ、考えている数の分割問題には解が無いということです。 しかし、エネルギー関数の最小化を通して得られた集合 \(R\) と \(S-R\) はある意味最も”良い”分割になっています。 （それぞれの集合内の数の和がなるべく近いようになっています。） エネルギー関数の最小化を通して、解が無くとも解に最も近いものが見つかるのです。
参考文献 #
A. Lucas, “Ising formulations of many NP problems” (open access)