量子アニーリングで不等式制約を実現する方法

量子アニーリングで不等式制約を実現する方法

量子アニーリングは、エネルギー最小化を通じて最適解を探索する手法です。しかし、量子アニーリングマシン（たとえばD-Wave）はもともと制約なしの最適化問題（QUBO形式）しか扱えません。そこで、現実の問題でよく出てくる不等式制約をどのように実装するかが重要になります。本記事では、スラック変数を利用して不等式制約を等式制約に変換し、QUBOに組み込む方法について解説します。

---

1. 不等式制約の背景

1.1 不等式制約とは

たとえば、以下のような不等式制約があるとします：

$$x1+x2≤1 x_1 + x_2 \leq 1$$

この制約は、2つのバイナリ変数 (x_1) と (x_2) のうち、同時にどちらも1になることを禁止するものです。実際、可能な組み合わせは以下の通りです：

• $$(x1,x2)=(0,0)(x_1, x_2) = (0,0)$$
• $$(x1,x2)=(0,1)(x_1, x_2) = (0,1)$$
• $$(x1,x2)=(1,0)(x_1, x_2) = (1,0)$$
• $$(1,1)は制約違反(1,1) は制約違反$$

1.2 なぜ変換が必要か

量子アニーリングのQUBO（Quadratic Unconstrained Binary Optimization）形式では、すべての制約をエネルギー関数に組み込み、エネルギー最小化の枠組みで問題を解くため、不等式制約のような直接的な制約は扱えません。そのため、不等式を等式に変換し、ペナルティ項として加える手法が採用されます。

---

2. スラック変数による等式変換

2.1 基本的なアイデア

不等式制約 $x1+x2≤1x_1 + x_2 \leq 1$ を等式に変換するため、スラック変数 $ss$ を導入します。具体的には：

$$x1+x2+s=1 x_1 + x_2 + s = 1$$

ここで、$ss$ はバイナリ変数として定義されます。各組み合わせの場合の必要な$ss$の値は以下の通りです：

$x1x_1$	$x2x_2$	必要な $ss$
0	0	1
0	1	0
1	0	0
1	1	不可能（スラック変数では表現できない）

この変換により、$x1=1x_1 = 1$かつ $x2=1x_2 = 1$となる解は、どのような$ss$をとっても等式が成立せず、エネルギー的に不利な解となるため、自然に排除されます。

2.2 より一般的な例： $x1+x2+x3≤3x_1+x_2+x_3 \leq 3$

より大きな数値の不等式制約の場合、スラック変数は整数変数となる必要があります。例えば、

$$x1+x2+x3≤3 x_1+x_2+x_3 \leq 3$$

とした場合、等式に変換するには：

$$x1+x2+x3+s=3 x_1+x_2+x_3 + s = 3$$

となります。しかし、量子アニーリングではバイナリ変数のみを扱うため、ここでの ( s ) はバイナリエンコーディング（例えば2ビットで0～3の整数を表す）を使います。具体的には、

$$s=s1+2s2 s = s_1 + 2s_2$$

とし、最終的な等式は：

$$x1+x2+x3+s1+2s2=3 x_1+x_2+x_3 + s_1 + 2s_2 = 3$$

となります。

---

3. ペナルティ関数とQUBO形式

3.1 ペナルティ関数の構築

等式制約を満たすようにペナルティ関数を設計します。例えば、$x1+x2+s=1x_1+x_2+s=1$の場合は、

$$P(x1+x2+s−1)2 P \left(x_1+x_2+s-1\right)^2$$

というペナルティ項を目的関数に加えます。ここで $PP$ は十分大きな正の定数で、制約違反時にエネルギーを大きく上昇させる役割を持ちます。

同様に、$x_1+x_2+x_3+s_1+2s_2=3 $の場合は、

$$P(x1+x2+x3+s1+2s2−3)2 P \left(x_1+x_2+x_3+s_1+2s_2-3\right)^2$$

という形になります。

3.2 QUBO形式への展開

ペナルティ項は二乗項として展開され、QUBOの一般形

$$E(x)=∑iQiixi+∑i<jQijxixj E(x) = \sum_{i} Q_{ii} x_i + \sum_{i<j} Q_{ij} x_i x_j$$

に落とし込まれます。バイナリ変数の性質$x2=xx^2=x$を利用して整理することで、各項が線形・二次項に分解され、最終的にQUBO行列$QQ$が得られます。

例えば、$x1+x2+s=1x_1+x_2+s=1$のペナルティ項の場合、

$$P(x1+x2+s−1)2=P(x1+x2+s+2x1x2+2x1s+2x2s−2x1−2x2−2s+1) P (x_1+x_2+s-1)^2 = P \Bigl(x_1+x_2+s+2x_1x_2+2x_1s+2x_2s-2x_1-2x_2-2s+1\Bigr)$$

となり、これをもとに各変数間の係数が決定されます。これにより、量子アニーリングマシンはエネルギー最小化の過程で制約を満たす解（すなわちペナルティ項がゼロの解）を探索します。

---

4. 量子アニーリングのエネルギー最小化と制約の実現

量子アニーリングはシステム全体のエネルギーを最小化することで解を探索します。ペナルティ項を含むエネルギー関数では、制約が守られる場合にエネルギーが低く、制約違反の場合は高いエネルギーとなります。したがって、エネルギー最小化のプロセスの中で、自然と制約を満たす解が選ばれることになります。

この考え方により、量子アニーリングでも不等式制約を間接的に実現できるのです。

---

5. まとめ

• 不等式制約の課題: 量子アニーリングでは直接不等式を扱えないため、等式制約に変換する必要がある。
• スラック変数の導入: 不等式 $x1+x2≤1x_1+x_2 \leq 1$ は $x1+x2+s=1x_1+x_2+s=1$と変換し、$ss$ の値により制約違反を排除する。
• ペナルティ関数の利用: ペナルティ項 $P(x1+x2+s−1)2P(x_1+x_2+s-1)^2$を加えることで、制約違反した解のエネルギーが上昇し、最小化プロセスで除外される。
• QUBO形式への落とし込み: 展開したペナルティ関数を用いてQUBO行列を構築することで、量子アニーリングマシンに問題を入力できる。
• 一般化: $x1+x2+x3≤3x_1+x_2+x_3 \leq 3$の場合は、スラック変数 $ss$をビットエンコード（例：$s=s1+2s2s=s_1+2s_2$して等式 $x1+x2+x3+s1+2s2=3x_1+x_2+x_3+s_1+2s_2=3$ とする。

この方法を応用すれば、さまざまな不等式制約も量子アニーリングに組み込むことが可能になります。