スピン変数の積の線形表現

3422 ワード
線形計画法 線形計画法 テキストリンク

2つのスピン変数$s_1 s_2$ の積の線形表現を考えます.

y = s_1 s_2 \quad (s_1, s_2 \in \{-1, 1\})

結論から言うと, 下記のようになります.

\left\{
\begin{array}{ll}
y \leq \ \ \  s_1 - s_2 + 1 \\
y \leq -      s_1 + s_2 + 1 \\
y \geq \ \ \  s_1 + s_2 - 1 \\
y \geq -      s_1 - s_2 - 1\\
y \in \mathbb{Z}
\end{array}
\right.

証明

$s_1$ $s_2$ $y \leq s_1-s_2+1$ $y \leq -s_1+s_2+1$ $y \geq s_1+s_2-1$ $y \geq -s_1-s_2-1$ $y \in \mathbb{Z}$
1 1 $y \leq 1 $ $y \leq 1 $ $y \geq 1 $ $y \geq -3$ 1
1 -1 $y \leq 3 $ $y \leq -1$ $y \geq -1$ $y \geq -1$ -1
-1 1 $y \leq -1$ $y \leq 3 $ $y \geq -1$ $y \geq -1$ -1
-1 -1 $y \leq 1 $ $y \leq 1 $ $y \geq -3$ $y \geq 1 $ 1

導出

$(x_1, x_2, y)$がとりうる組み合わせ
$(1, 1, 1), (1, -1, -1), (-1, 1, -1), (-1, -1, 1)$ の整数点を含み,
$(1, 1, \mathbb{Z}\setminus \{1\}), (1, -1, \mathbb{Z}\setminus \{-1\}), (-1, 1, \mathbb{Z}\setminus \{-1\}), (-1, -1, \mathbb{Z}\setminus \{1\})$を含まない
凸領域を生成する, ここで$(1, 1, \mathbb{Z}\setminus \{1\})$ は $\{(1,1,y); y \in \mathbb{Z} \setminus \{1\}\}$を表します.

バイナリ変数の積からの導出

よく知られた

z = b_1 b_2 \quad (b_1, b_2 \in \{0, 1\})

バイナリ変数の積の線形表現

\left\{
\begin{array}{ll}
z \leq b_1 \\
z \leq b_2 \\
z \geq b_1+b_2-1 \\
z \in \{0, 1\}\\
\end{array}
\right.

を用いた導出も可能です. この場合, $z \in \{0, 1\}$を$z \geq 0$に置き換えておくのがミソで,

\begin{align}
y &= s_1 s_2 \\
  &= 4\left(\frac{1+s_1}{2}\right)\left(\frac{1+s_2}{2}\right) - \left(s_1+s_2+1\right)
\end{align}

ここで

z := \left(\frac{1+s_1}{2}\right)\left(\frac{1+s_2}{2}\right)

に対して, 右辺はバイナリ変数の積になっているので, 上記の制約群で線形化したのち

y = 4 z - (s_1+s_2+1) \iff z = \frac{1}{4}\left(y + \left( s_1+s_2+1 \right)\right)

を用いて$y$について整理すると最初の制約群が出てきます.

スピン変数とバイナリ変数の積

ちなみに

y = s b \quad (s \in \{-1, 1\}, b \in \{0, 1\})

は

\left\{
\begin{array}{ll}
y \leq b \\
y \leq s-b+1 \\
y \geq s+b-1\\
y \geq -b\\
y \in \mathbb{Z}
\end{array}
\right.

となります.