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.
となります.