はじめに
オンライン公開伴走型量子コンピューティング講座QA4U2卒業生のluna_moonlightです。
量子アニーリングでよく用いられるQUBOという形式は複数の制限があり、せっかく考えたコスト関数が量子アニーリングでは使えないということがあります。それを回避すべくこの記事では、QUBOへの変換テクニックについて解説していきます。
QUBOとは
QUBOとは、非制約二値変数二次最適化(Quadratic Unconstrained Binary Optimization)の頭文字をとったものです。QUBOでは、0と1の2つの値をとるM個のbinary変数x_1, x_2, \dots, x_Mに対して、二次形式の評価関数f:\{0, 1\}^M \to \Realsを最小にするように変数の組み合わせ\bm{x}=(x_1, x_2, \dots, x_M)を求めていきます。すなわち、
f(\bm{x})=\bm{x}Q\bm{x}^T=\sum_{i=1}^M\sum_{j=1}^M Q_{i,j}x_ix_j
を最小にする\bm{x}=(x_1, x_2, \dots, x_M)を求めます。ここで、行列Q \in \Reals ^ {M \times M}は、対角成分はx_iの重みを、非対角成分はx_i, x_j成分の相互作用を表しており、QUBO行列と呼ばれます。
QUBOへの変換テクニック
QUBOには主に以下のような制限があります。
- 二次形式の評価関数しか使えない
-
x \in \{0, 1\}の二値変数しか使えない
- 制約条件が使えない
これらの制限を克服するためのQUBO変換テクニックについて解説していきます。
定数項
以下のような定数項を含む評価関数は、二次形式ではないためQUBOで扱うことはできません。
f(\bm{x}) = \sum_{i=1}^M\sum_{j=1}^M Q_{i,j}x_ix_j + a
最小化問題において定数項は最適解に何も影響しないため、定数項を無視することで以下のような二次形式(QUBO形式)に変換することができます。
g(\bm{x}) = \sum_{i=1}^M\sum_{j=1}^M Q_{i,j}x_ix_j
最適解は変わりませんが、最適値は変化してしまうことに注意してください。
一次項
以下のような一次の評価関数は、二次形式ではないためQUBOで扱うことはできません。
ここで、x \in \{0, 1\}であることに注意すると、上の評価関数は以下のような二次形式(QUBO形式)に変換することができます。
三次項
以下のような三次の評価関数は、二次形式ではないためQUBOで扱うことはできません。
f(\bm{x}) = a x_0 x_1 x_2
三次項のときは、a > 0の場合とa < 0の場合で異なる変換が必要です。
a > 0の場合
a > 0の場合、新しいbinary変数yを導入して、以下のような評価関数を作成することで二次形式(QUBO形式)に変換することができます。
g(\begin{bmatrix} \bm{x} & y \end{bmatrix}) = a \Bigl\{y(x_0 + x_1 + x_2 - 1) + (x_0 x_1 + x_1 x_2 + x_2 x_0) - (x_0 + x_1 + x_2) + 1 \Bigr\}
すべての場合を列挙すると以下のようになり、最小値0を取るのは(x_0, x_1, x_2) = (0, 0, 0), (0, 0, 1), (0, 1, 0), (0, 1, 1), (1, 0, 0), (1, 0, 1), (1, 1, 0)で、これらは元の評価関数fの最適値、最適解と一致しています。
| x_0 |
x_1 |
x_2 |
y |
g(\begin{bmatrix} \bm{x} & y \end{bmatrix}) |
| 0 |
0 |
0 |
0 |
a > 0 |
| \textcolor{LimeGreen}{0} |
\textcolor{LimeGreen}{0} |
\textcolor{LimeGreen}{0} |
\textcolor{LimeGreen}{1} |
\textcolor{LimeGreen}{0} |
| \textcolor{LimeGreen}{0} |
\textcolor{LimeGreen}{0} |
\textcolor{LimeGreen}{1} |
\textcolor{LimeGreen}{0} |
\textcolor{LimeGreen}{0} |
| \textcolor{LimeGreen}{0} |
\textcolor{LimeGreen}{0} |
\textcolor{LimeGreen}{1} |
\textcolor{LimeGreen}{1} |
\textcolor{LimeGreen}{0} |
| \textcolor{LimeGreen}{0} |
\textcolor{LimeGreen}{1} |
\textcolor{LimeGreen}{0} |
\textcolor{LimeGreen}{0} |
\textcolor{LimeGreen}{0} |
| \textcolor{LimeGreen}{0} |
\textcolor{LimeGreen}{1} |
\textcolor{LimeGreen}{0} |
\textcolor{LimeGreen}{1} |
\textcolor{LimeGreen}{0} |
| \textcolor{LimeGreen}{0} |
\textcolor{LimeGreen}{1} |
\textcolor{LimeGreen}{1} |
\textcolor{LimeGreen}{0} |
\textcolor{LimeGreen}{0} |
| 0 |
1 |
1 |
1 |
a > 0 |
| \textcolor{LimeGreen}{1} |
\textcolor{LimeGreen}{0} |
\textcolor{LimeGreen}{0} |
\textcolor{LimeGreen}{0} |
\textcolor{LimeGreen}{0} |
| \textcolor{LimeGreen}{1} |
\textcolor{LimeGreen}{0} |
\textcolor{LimeGreen}{0} |
\textcolor{LimeGreen}{1} |
\textcolor{LimeGreen}{0} |
| \textcolor{LimeGreen}{0} |
\textcolor{LimeGreen}{0} |
\textcolor{LimeGreen}{1} |
\textcolor{LimeGreen}{0} |
\textcolor{LimeGreen}{0} |
| 1 |
0 |
1 |
1 |
a > 0 |
| \textcolor{LimeGreen}{1} |
\textcolor{LimeGreen}{1} |
\textcolor{LimeGreen}{0} |
\textcolor{LimeGreen}{0} |
\textcolor{LimeGreen}{0} |
| 1 |
1 |
0 |
1 |
a > 0 |
| 1 |
1 |
1 |
0 |
a > 0 |
| 1 |
1 |
1 |
1 |
3a > 0 |
a < 0の場合
a < 0の場合、新しいbinary変数yを導入して、以下のような評価関数を作成することで、二次形式(QUBO形式)に変換することができます。
g(\begin{bmatrix} \bm{x} & y \end{bmatrix}) = ay(x_0 + x_1 + x_2 - 2)
すべての場合を列挙すると以下のようになり、最小値aを取るのは(x_0, x_1, x_2) = (1, 1, 1)で、これらは元の評価関数fの最適値、最適解と一致しています。
| x_0 |
x_1 |
x_2 |
y |
g(\begin{bmatrix} \bm{x} & y \end{bmatrix}) |
| 0 |
0 |
0 |
0 |
0 |
| 0 |
0 |
0 |
1 |
-2a > 0 |
| 0 |
0 |
1 |
0 |
0 |
| 0 |
0 |
1 |
1 |
-a > 0 |
| 0 |
1 |
0 |
0 |
0 |
| 0 |
1 |
0 |
1 |
-a > 0 |
| 0 |
1 |
1 |
0 |
0 |
| 0 |
1 |
1 |
1 |
0 |
| 1 |
0 |
0 |
0 |
0 |
| 1 |
0 |
0 |
1 |
-a > 0 |
| 1 |
0 |
1 |
0 |
0 |
| 1 |
0 |
1 |
1 |
0 |
| 1 |
1 |
0 |
0 |
0 |
| 1 |
1 |
0 |
1 |
0 |
| 1 |
1 |
1 |
0 |
0 |
| \textcolor{LimeGreen}{1} |
\textcolor{LimeGreen}{1} |
\textcolor{LimeGreen}{1} |
\textcolor{LimeGreen}{1} |
\textcolor{LimeGreen}{a < 0} |
三次項以上
先ほどの変換方法は、三次項でしか使えないため四次以上の項の変換をすることはできません。そこで、x_0 x_1を1つのbinary変数yを用いて置換して次数下げを行うことを考えます。
新しいbinary変数yを導入して、以下のような制約項を追加することでy = x_0 x_1となるように次数下げすることができます。これを二次以下の項だけになるまで繰り返せばQUBO形式に変換できます。
C(\begin{bmatrix} x_0 & x_1 & y \end{bmatrix}) = x_0 x_1 - 2y(x_0 + x_1) + 3y
すべての場合を列挙すると以下のようになり、最小値を取るのは(x_0, x_1, y) = (0, 0, 0), (0, 1, 0), (1, 0, 0), (1, 1, 1)で、y = x_0 x_1が成立しているときのみだとわかります。
| x_0 |
x_1 |
y |
C(\begin{bmatrix} x_0 & x_1 & y \end{bmatrix}) |
| \textcolor{LimeGreen}{0} |
\textcolor{LimeGreen}{0} |
\textcolor{LimeGreen}{0} |
\textcolor{LimeGreen}{0} |
| 0 |
0 |
1 |
3 |
| \textcolor{LimeGreen}{0} |
\textcolor{LimeGreen}{1} |
\textcolor{LimeGreen}{0} |
\textcolor{LimeGreen}{0} |
| 0 |
1 |
1 |
1 |
| \textcolor{LimeGreen}{1} |
\textcolor{LimeGreen}{0} |
\textcolor{LimeGreen}{0} |
\textcolor{LimeGreen}{0} |
| 1 |
0 |
1 |
1 |
| 1 |
1 |
0 |
1 |
| \textcolor{LimeGreen}{1} |
\textcolor{LimeGreen}{1} |
\textcolor{LimeGreen}{1} |
\textcolor{LimeGreen}{0} |
例
試しに、以下のような四次の評価関数をQUBO形式に変換していきます。
f(\bm{x}) = a x_0 x_1 x_2 x_3
新しいbinary変数y_0, y_1をy_0 = x_0 x_1, y_1 = x_2 x_3となるように導入することで、以下のような二次形式(QUBO形式)に変換することができます。
g(\begin{bmatrix} \bm{x} & \bm{y} \end{bmatrix}) = a y_0 y_1 + \lambda(x_0 x_1 - 2y_0(x_0 + x_1) + 3y_0) + \lambda(x_2 x_3 - 2y_1(x_2 + x_3) + 3y_1)
すべての場合を列挙すると以下のようになり、a > 0のときに最小値0を取るのは(x_0, x_1, x_2, x_3) = (0, 0, 0, 0), (0, 0, 0, 1), (0, 0, 1, 0), (0, 0, 1, 1), (0, 1, 0, 0), (0, 1, 0, 1), (0, 1, 1, 0), (0, 1, 1, 1), (1, 0, 0, 0), (1, 0, 0, 1), (1, 0, 1, 0), (1, 0, 1, 1), (1, 1, 0, 0), (1, 1, 0, 1), (1, 1, 1, 0)で、これらは元の評価関数fの最適値、最適解と一致しています。また、a < 0の時に最小値aを取るのは(x_0, x_1, x_2, x_3) = (1, 1, 1, 1)で、この場合も元の評価関数fの最適値、最適解と一致します。
全列挙結果
| x_0 |
x_1 |
x_2 |
x_3 |
y_0 |
y_1 |
g(\begin{bmatrix} \bm{x} & \bm{y} \end{bmatrix}) |
| \textcolor{LimeGreen}{0} |
\textcolor{LimeGreen}{0} |
\textcolor{LimeGreen}{0} |
\textcolor{LimeGreen}{0} |
\textcolor{LimeGreen}{0} |
\textcolor{LimeGreen}{0} |
\textcolor{LimeGreen}{0} |
| 0 |
0 |
0 |
0 |
0 |
1 |
3\lambda |
| 0 |
0 |
0 |
0 |
1 |
0 |
3\lambda |
| 0 |
0 |
0 |
0 |
1 |
1 |
a + 6\lambda |
| \textcolor{LimeGreen}{0} |
\textcolor{LimeGreen}{0} |
\textcolor{LimeGreen}{0} |
\textcolor{LimeGreen}{1} |
\textcolor{LimeGreen}{0} |
\textcolor{LimeGreen}{0} |
\textcolor{LimeGreen}{0} |
| 0 |
0 |
0 |
1 |
0 |
1 |
\lambda |
| 0 |
0 |
0 |
1 |
1 |
0 |
3\lambda |
| 0 |
0 |
0 |
1 |
1 |
1 |
a + 4\lambda |
| \textcolor{LimeGreen}{0} |
\textcolor{LimeGreen}{0} |
\textcolor{LimeGreen}{1} |
\textcolor{LimeGreen}{0} |
\textcolor{LimeGreen}{0} |
\textcolor{LimeGreen}{0} |
\textcolor{LimeGreen}{0} |
| 0 |
0 |
1 |
0 |
0 |
1 |
\lambda |
| 0 |
0 |
1 |
0 |
1 |
0 |
3\lambda |
| 0 |
0 |
1 |
0 |
1 |
1 |
a + 4\lambda |
| 0 |
0 |
1 |
1 |
0 |
0 |
\lambda |
| \textcolor{LimeGreen}{0} |
\textcolor{LimeGreen}{0} |
\textcolor{LimeGreen}{1} |
\textcolor{LimeGreen}{1} |
\textcolor{LimeGreen}{0} |
\textcolor{LimeGreen}{1} |
\textcolor{LimeGreen}{0} |
| 0 |
0 |
1 |
1 |
1 |
0 |
4\lambda |
| 0 |
0 |
1 |
1 |
1 |
1 |
a + 3\lambda |
| \textcolor{LimeGreen}{0} |
\textcolor{LimeGreen}{1} |
\textcolor{LimeGreen}{0} |
\textcolor{LimeGreen}{0} |
\textcolor{LimeGreen}{0} |
\textcolor{LimeGreen}{0} |
\textcolor{LimeGreen}{0} |
| 0 |
1 |
0 |
0 |
0 |
1 |
3\lambda |
| 0 |
1 |
0 |
0 |
1 |
0 |
\lambda |
| 0 |
1 |
0 |
0 |
1 |
1 |
a + 4\lambda |
| \textcolor{LimeGreen}{0} |
\textcolor{LimeGreen}{1} |
\textcolor{LimeGreen}{0} |
\textcolor{LimeGreen}{1} |
\textcolor{LimeGreen}{0} |
\textcolor{LimeGreen}{0} |
\textcolor{LimeGreen}{0} |
| 0 |
1 |
0 |
1 |
0 |
1 |
\lambda |
| 0 |
1 |
0 |
1 |
1 |
0 |
\lambda |
| 0 |
1 |
0 |
1 |
1 |
1 |
a + 2\lambda |
| \textcolor{LimeGreen}{0} |
\textcolor{LimeGreen}{1} |
\textcolor{LimeGreen}{1} |
\textcolor{LimeGreen}{0} |
\textcolor{LimeGreen}{0} |
\textcolor{LimeGreen}{0} |
\textcolor{LimeGreen}{0} |
| 0 |
1 |
1 |
0 |
0 |
1 |
\lambda |
| 0 |
1 |
1 |
0 |
1 |
0 |
\lambda |
| 0 |
1 |
1 |
0 |
1 |
1 |
a + 2\lambda |
| 0 |
1 |
1 |
1 |
0 |
0 |
\lambda |
| \textcolor{LimeGreen}{0} |
\textcolor{LimeGreen}{1} |
\textcolor{LimeGreen}{1} |
\textcolor{LimeGreen}{1} |
\textcolor{LimeGreen}{0} |
\textcolor{LimeGreen}{1} |
\textcolor{LimeGreen}{0} |
| 0 |
1 |
1 |
1 |
1 |
0 |
2\lambda |
| 0 |
1 |
1 |
1 |
1 |
1 |
a + \lambda |
| \textcolor{LimeGreen}{1} |
\textcolor{LimeGreen}{0} |
\textcolor{LimeGreen}{0} |
\textcolor{LimeGreen}{0} |
\textcolor{LimeGreen}{0} |
\textcolor{LimeGreen}{0} |
\textcolor{LimeGreen}{0} |
| 1 |
0 |
0 |
0 |
0 |
1 |
3\lambda |
| 1 |
0 |
0 |
0 |
1 |
0 |
\lambda |
| 1 |
0 |
0 |
0 |
1 |
1 |
a + 4\lambda |
| \textcolor{LimeGreen}{1} |
\textcolor{LimeGreen}{0} |
\textcolor{LimeGreen}{0} |
\textcolor{LimeGreen}{1} |
\textcolor{LimeGreen}{0} |
\textcolor{LimeGreen}{0} |
\textcolor{LimeGreen}{0} |
| 1 |
0 |
0 |
1 |
0 |
1 |
\lambda |
| 1 |
0 |
0 |
1 |
1 |
0 |
\lambda |
| 1 |
0 |
0 |
1 |
1 |
1 |
a + 2\lambda |
| \textcolor{LimeGreen}{1} |
\textcolor{LimeGreen}{0} |
\textcolor{LimeGreen}{1} |
\textcolor{LimeGreen}{0} |
\textcolor{LimeGreen}{0} |
\textcolor{LimeGreen}{0} |
\textcolor{LimeGreen}{0} |
| 1 |
0 |
1 |
0 |
0 |
1 |
\lambda |
| 1 |
0 |
1 |
0 |
1 |
0 |
\lambda |
| 1 |
0 |
1 |
0 |
1 |
1 |
a + 2\lambda |
| 1 |
0 |
1 |
1 |
0 |
0 |
\lambda |
| \textcolor{LimeGreen}{1} |
\textcolor{LimeGreen}{0} |
\textcolor{LimeGreen}{1} |
\textcolor{LimeGreen}{1} |
\textcolor{LimeGreen}{0} |
\textcolor{LimeGreen}{1} |
\textcolor{LimeGreen}{0} |
| 1 |
0 |
1 |
1 |
1 |
0 |
2\lambda |
| 1 |
0 |
1 |
1 |
1 |
1 |
a + \lambda |
| 1 |
1 |
0 |
0 |
0 |
0 |
\lambda |
| 1 |
1 |
0 |
0 |
0 |
1 |
4\lambda |
| \textcolor{LimeGreen}{1} |
\textcolor{LimeGreen}{1} |
\textcolor{LimeGreen}{0} |
\textcolor{LimeGreen}{0} |
\textcolor{LimeGreen}{1} |
\textcolor{LimeGreen}{0} |
\textcolor{LimeGreen}{0} |
| 1 |
1 |
0 |
0 |
1 |
1 |
a + 3\lambda |
| 1 |
1 |
0 |
1 |
0 |
0 |
\lambda |
| 1 |
1 |
0 |
1 |
0 |
1 |
2\lambda |
| \textcolor{LimeGreen}{1} |
\textcolor{LimeGreen}{1} |
\textcolor{LimeGreen}{0} |
\textcolor{LimeGreen}{1} |
\textcolor{LimeGreen}{1} |
\textcolor{LimeGreen}{0} |
\textcolor{LimeGreen}{0} |
| 1 |
1 |
0 |
1 |
1 |
1 |
a + \lambda |
| 1 |
1 |
1 |
0 |
0 |
0 |
\lambda |
| 1 |
1 |
1 |
0 |
0 |
1 |
2\lambda |
| \textcolor{LimeGreen}{1} |
\textcolor{LimeGreen}{1} |
\textcolor{LimeGreen}{1} |
\textcolor{LimeGreen}{0} |
\textcolor{LimeGreen}{1} |
\textcolor{LimeGreen}{0} |
\textcolor{LimeGreen}{0} |
| 1 |
1 |
1 |
0 |
1 |
1 |
a + \lambda |
| 1 |
1 |
1 |
1 |
0 |
0 |
2\lambda |
| 1 |
1 |
1 |
1 |
0 |
1 |
\lambda |
| 1 |
1 |
1 |
1 |
1 |
0 |
\lambda |
| \textcolor{red}{1} |
\textcolor{red}{1} |
\textcolor{red}{1} |
\textcolor{red}{1} |
\textcolor{red}{1} |
\textcolor{red}{1} |
\textcolor{red}{a} |
イジングモデル
イジングモデルはQUBOと似ていますが、+1と-1の2つの値をとるM個のbinary変数\sigma_1, \sigma_2, \dots, \sigma_Mを使うという点で異なります。イジングモデルでは、評価関数f:\{-1, +1\}^M \to \Realsを最小にするように変数の組み合わせ\bm{\sigma}=(\sigma_1, \sigma_2, \dots, \sigma_M)を求めていきます。すなわち、
H(\bm{\sigma}) = -\sum_{i<j} J_{i, j} \sigma_i \sigma_j - \sum_{i}^M h_i \sigma_i
を最小にする\bm{\sigma}=(\sigma_1, \sigma_2, \dots, \sigma_M)を求めます。ここで、J_{i, j}は2つのイジング変数間の相互作用を、h_iは局所磁場を表しています。
以下のようなイジングモデルは、\sigma \in \{-1, +1\}のためQUBOで扱うことはできません。
H(\bm{\sigma}) = - \sigma_0 \sigma_1 - \sigma_0 - \sigma_1
\sigma = 2x - 1のように変数変換を行うと、イジングモデルとQUBOは等価に変換できます。よって、上のイジングモデルは以下のような0-1変数(QUBO形式)に変換することができます。
\begin{split}
f(\bm{x})
&= -(2x_0 - 1)(2x_1 - 1) - (2x_0 - 1) - (2x_1 - 1)\\
&= -4x_0 x_1 + 1
\end{split}
整数変数
以下のような整数変数の評価関数は、0-1変数ではないためQUBOで扱うことはできません。
f(\bm{z}) = a z_0 \quad (z_0 \in \Z)
整数変数をQUBOで表現する方法は、主に以下の2つがあります。
One-hot表現
One-hot表現とは、1ビットだけ1で他のビットは0で表されるビット列表現のことです。x_i=1のときにz_0=iと対応させることで、以下のような0-1変数(QUBO形式)に変換することができます。
ここで第二項は、1にするビットを1つに制限する制約項になっています。これについては等式制約の項目で詳しく解説します。
g(\bm{x}) = a\sum_{i=-\infty}^\infty i x_i + \lambda \left(\sum_{i=-\infty}^\infty x_i - 1\right)^2
実際には無限個のqubitを用意することはできないので、探索する範囲を制限して使用する必要があります。z_0 \in [b, c] \cap \Zの場合は以下のように変換します。
g(\bm{x}) = a\sum_{i=b}^c i x_i + \lambda \left(\sum_{i=b}^c x_i - 1\right)^2
2進数表現
\displaystyle \sum_{i=0}^\infty 2^i x_iのようにx_iを2進数のiビット目に対応させることで、非負整数をQUBOで表現することができます。整数変数(負の数も含む)の場合は、非負整数から非負整数を引き算することで、以下のような0-1変数(QUBO形式)に変換することができます。
g(\bm{x}) = a \left(\sum_{i=0}^\infty 2^i x_i - \sum_{i=0}^\infty 2^i y_i\right)
この方法についても無限個のqubitを用意することはできないので、探索する範囲を制限して使用する必要があります。z_0 \in [b, b + 2^c) \cap \Zの場合は以下のように変換します。
g(\bm{x}) = a \left(\sum_{i=0}^{c - 1} 2^i x_i + b\right)
実数変数
以下のような整数変数の評価関数は、0-1変数ではないためQUBOで扱うことはできません。
f(\bm{z}) = a r_0 \quad (r_0 \in \R)
整数の2進数表現を実数まで拡張することで、以下のような0-1変数(QUBO形式)に変換することができます。
g(\bm{x}) = a \left(\sum_{i=-\infty}^\infty 2^i x_i - \sum_{i=-\infty}^\infty 2^i y_i\right)
この方法についても無限個のqubitを用意することはできないので、探索する範囲や精度を制限して使用する必要があります。
等式制約
QUBOでは制約条件が使えないため、以下のような等式制約を含む最適化問題はQUBOで扱うことはできません。
\begin{split}
評価関数: &\sum_{i=1}^M\sum_{j=1}^M Q_{i,j}x_ix_j → \min\\
制約条件: &\sum_{i=1}^M a_i x_i = b\\
&x_i \in {0, 1}
\end{split}
以下のような制約項を考えると、最小化した際に等式の制約条件を満たしていることがわかります。
\begin{split}
C(\bm{x})
&= \left(\sum_{i=1}^M a_i x_i - b\right)^2\\
&= \left(\sum_{i=1}^M a_i x_i - b\right)\left(\sum_{i=1}^M a_i x_i - b\right)\\
&= \sum_{i=1}^M \sum_{j=1}^M a_i a_j x_i x_j - 2b \sum_{i=1}^M a_i x_i + b^2
\end{split}
先ほどの制約項を評価関数に追加し、制約条件を削除することで、以下のような制約条件のない形(QUBO形式)に変換することができます。このような方法を罰金法と呼びます。
\begin{split}
g(\bm{x})
&= \sum_{i=1}^M\sum_{j=1}^M Q_{i,j}x_ix_j + \lambda \left(\sum_{i=1}^M a_i x_i - b\right)^2\\
&= \sum_{i=1}^M\sum_{j=1}^M Q_{i,j}x_ix_j + \lambda \left(\sum_{i=1}^M \sum_{j=1}^M a_i a_j x_i x_j - 2b \sum_{i=1}^M a_i x_i + b^2\right)
\end{split}
例
試しに、以下のような等式制約が含まれる最適化問題をQUBO形式に変換していきます。
\begin{split}
評価関数: &x_0 - 2x_1 - 3x_2 → \min\\
制約条件: &x_0 + x_1 + x_2 = 1\\
&x_0, x_1, x_2 \in {0, 1}
\end{split}
罰金法により、以下のようなQUBO形式に変換することができます。
\begin{split}
g(\bm{x})
&= (x_0 - 2x_1 - 3x_2) + \lambda\Bigl\{(x_0 + x_1 + x_2) - 1\Bigr\}^2\\
&= (x_0 - 2x_1 - 3x_2) + \lambda\left(\sum_{i=0}^2\sum_{j=0}^2 x_i x_j - 2\sum_{i=0}^2 x_i + 1\right)\\
&= (x_0 - 2x_1 - 3x_2) + \lambda \Bigl\{(x_0x_0 + x_0x_1 + x_0x_2 + x_1x_0 + x_1x_1 + x_1x_2 + x_2x_0 + x_2x_1 + x_2x_2) -2(x_0 + x_1 + x_2) + 1 \Bigr\}
\end{split}
すべての場合を列挙すると以下のようになり、\lambdaがある程度大きいときに最小値-3を取るのは(x_0, x_1, x_2) = (0, 0, 1)で、制約条件を満たしつつ評価関数の最適値、最適解を求めることができています。
| x_0 |
x_1 |
x_2 |
g(\bm{x}) |
| 0 |
0 |
0 |
\lambda |
| \textcolor{LimeGreen}{0} |
\textcolor{LimeGreen}{0} |
\textcolor{LimeGreen}{1} |
\textcolor{LimeGreen}{-3} |
| 0 |
1 |
0 |
-2 |
| \textcolor{red}{0} |
\textcolor{red}{1} |
\textcolor{red}{1} |
\textcolor{red}{\lambda - 5} |
| 1 |
0 |
0 |
1 |
| 1 |
0 |
1 |
\lambda - 2 |
| 1 |
1 |
0 |
\lambda - 1 |
| 1 |
1 |
1 |
4\lambda - 4 |
不等式制約
QUBOでは制約条件が使えないため、以下のような不等式制約を含む最適化問題はQUBOで扱うことはできません。
\begin{split}
評価関数: &\sum_{i=1}^M\sum_{j=1}^M Q_{i,j}x_ix_j → \min\\
制約条件: &\sum_{i=1}^M a_i x_i \leq b\\
&x_i \in {0, 1}
\end{split}
ここで、実数変数s \geq 0を導入することで、不等式の自由度を吸収することができます。このような変数sをスラック変数と呼びます。スラック変数を導入することで、以下のように不等式制約を等式制約に変換できます。
\begin{split}
評価関数: &\sum_{i=1}^M\sum_{j=1}^M Q_{i,j}x_ix_j → \min\\
制約条件: &\sum_{i=1}^M a_i x_i + s = b\\
&x_i \in {0, 1}\\
&s \in \R_{\geq 0}
\end{split}
等式制約の最適化問題に変換することができたので、スラック変数sをbinary変数\bm{y}に変換した後に罰金法を適用することで、以下のような制約条件のない形(QUBO形式)に変換することができます。
\begin{split}
g(\begin{bmatrix} \bm{x} & \bm{y} \end{bmatrix})
&= \sum_{i=1}^M\sum_{j=1}^M Q_{i,j}x_ix_j + \lambda \left(\sum_{i=1}^M a_i x_i + \sum_{i=-\infty}^\infty 2^i y_i - b\right)^2\\
&= \sum_{i=1}^M\sum_{j=1}^M Q_{i,j}x_ix_j + \lambda \left(\sum_{i=1}^M \sum_{j=1}^M a_i a_j x_i x_j + \sum_{i=-\infty}^\infty\sum_{j=-\infty}^\infty 2^i 2^j y_i y_j + 2 \sum_{i=1}^M\sum_{j=-\infty}^\infty 2^j a_i x_i y_j - 2b \sum_{i=1}^M a_i x_i - 2b \sum_{i=-\infty}^\infty 2^i y_i + b^2\right)
\end{split}
例
試しに、以下のような不等式制約が含まれる最適化問題をQUBO形式に変換していきます。
\begin{split}
評価関数: &-x_0 - 2x_1 - 3x_2 → \min\\
制約条件: &x_0 + x_1 + x_2 \leq 2\\
&x_0, x_1, x_2 \in {0, 1}
\end{split}
まず、スラック変数sを導入することで、以下のように等式制約に変換します。
\begin{split}
評価関数: &-x_0 - 2x_1 - 3x_2 → \min\\
制約条件: &x_0 + x_1 + x_2 + s = 2\\
&x_0, x_1, x_2 \in {0, 1}\\
&s \in [0, 4) \cap \Z
\end{split}
最後にスラック変数sをbinary変数\bm{y}した後に罰金法を適用すると、以下のようなQUBO形式に変換することができます。
\begin{split}
g(\begin{bmatrix} \bm{x} & \bm{y} \end{bmatrix})
&= (-x_0 - 2x_1 - 3x_2) + \lambda\Bigl\{(x_0 + x_1 + x_2) + (y_0 + 2y_1) - 2\Bigr\}^2\\
&= (-x_0 - 2x_1 - 3x_2) + \lambda \left(\sum_{i=0}^2 \sum_{j=0}^2 x_ix_j + \sum_{i=0}^1\sum_{j=0}^1 2^i 2^j y_i y_j + 2 \sum_{i=0}^2\sum_{j=0}^1 2^j x_i y_j - 4\sum_{i=0}^2 x_i - 4\sum_{i=0}^1 2^i y_i + 4\right)\\
&= (-x_0 - 2x_1 - 3x_2) + \lambda \Bigl\{(x_0x_0 + x_0x_1 + x_0x_2 + x_1x_0 + x_1x_1 + x_1x_2 + x_2x_0 + x_2x_1 + x_2x_2) + (y_0y_0 + 2y_0y_1 + 2y_1y_0 + 4y_1y_1) + 2(x_0y_0 + 2x_0y_1 + x_1y_0 + 2x_1y_1 + x_2y_0 + 2x_2y_1) -4(x_0 + x_1 + x_2) -4(y_0 + 2y_1)+ 4\Bigr\}
\end{split}
すべての場合を列挙すると以下のようになり、\lambdaがある程度大きいときに最小値-5を取るのは(x_0, x_1, x_2) = (0, 1, 1)で、制約条件を満たしつつ評価関数の最適値、最適解を求めることができています。
全列挙結果
| x_0 |
x_1 |
x_2 |
y_0 |
y_1 |
g(\begin{bmatrix} \bm{x} & \bm{y} \end{bmatrix}) |
| 0 |
0 |
0 |
0 |
0 |
4\lambda |
| 0 |
0 |
0 |
0 |
1 |
0 |
| 0 |
0 |
0 |
1 |
0 |
\lambda |
| 0 |
0 |
0 |
1 |
1 |
\lambda |
| 0 |
0 |
1 |
0 |
0 |
\lambda - 3 |
| 0 |
0 |
1 |
0 |
1 |
\lambda - 3 |
| 0 |
0 |
1 |
1 |
0 |
-3 |
| 0 |
0 |
1 |
1 |
1 |
4\lambda - 3 |
| 0 |
1 |
0 |
0 |
0 |
\lambda - 2 |
| 0 |
1 |
0 |
0 |
1 |
\lambda - 2 |
| 0 |
1 |
0 |
1 |
0 |
-2 |
| 0 |
1 |
0 |
1 |
1 |
4\lambda - 2 |
| \textcolor{LimeGreen}{0} |
\textcolor{LimeGreen}{1} |
\textcolor{LimeGreen}{1} |
\textcolor{LimeGreen}{0} |
\textcolor{LimeGreen}{0} |
\textcolor{LimeGreen}{-5} |
| 0 |
1 |
1 |
0 |
1 |
4\lambda - 5 |
| 0 |
1 |
1 |
1 |
0 |
\lambda - 5 |
| 0 |
1 |
1 |
1 |
1 |
9\lambda - 5 |
| 1 |
0 |
0 |
0 |
0 |
\lambda - 1 |
| 1 |
0 |
0 |
0 |
1 |
\lambda - 1 |
| 1 |
0 |
0 |
1 |
0 |
-1 |
| 1 |
0 |
0 |
1 |
1 |
4\lambda - 1 |
| 1 |
0 |
1 |
0 |
0 |
-4 |
| 1 |
0 |
1 |
0 |
1 |
4\lambda - 4 |
| 1 |
0 |
1 |
1 |
0 |
\lambda - 4 |
| 1 |
0 |
1 |
1 |
1 |
9\lambda - 4 |
| 1 |
1 |
0 |
0 |
0 |
-3 |
| 1 |
1 |
0 |
0 |
1 |
4\lambda - 3 |
| 1 |
1 |
0 |
1 |
0 |
\lambda - 3 |
| 1 |
1 |
0 |
1 |
1 |
9\lambda - 3 |
| \textcolor{red}{1} |
\textcolor{red}{1} |
\textcolor{red}{1} |
\textcolor{red}{0} |
\textcolor{red}{0} |
\textcolor{red}{\lambda - 6} |
| 1 |
1 |
1 |
0 |
1 |
9\lambda - 6 |
| 1 |
1 |
1 |
1 |
0 |
4\lambda - 6 |
| 1 |
1 |
1 |
1 |
1 |
16\lambda - 6 |
max関数
以下のようなmax関数を含む評価関数は、二次形式ではないためQUBOで扱うことはできません。
f(\bm{x}) = \max(\sum_{i=1}^M a_i x_i, \sum_{i=1}^M b_i x_i)
ここで、実数変数rを導入することで、以下のような最適化問題に変換できます。
\begin{split}
評価関数: &r → \min\\
制約条件: &\max(\sum_{i=1}^M a_i x_i, \sum_{i=1}^M b_i x_i) \leq r\\
&x_i \in {0, 1}\\
&r \in \R
\end{split}
さらに、制約\displaystyle \max(\sum_{i=1}^M a_i x_i, \sum_{i=1}^M b_i x_i) \leq rは分割することができ、以下のような最適化問題に変換できます。
\begin{split}
評価関数: &r → \min\\
制約条件: &\sum_{i=1}^M a_i x_i \leq r\\
&\sum_{i=1}^M b_i x_i \leq r\\
&x_i \in {0, 1}\\
&r \in \R
\end{split}
あとは、不等式制約のときと同様です。
スラック変数s, t \geq 0を導入して、以下のような等式制約に変換します。
\begin{split}
評価関数: &r → \min\\
制約条件: &\sum_{i=1}^M a_i x_i + s = r\\
&\sum_{i=1}^M b_i x_i + t = r\\
&x_i \in {0, 1}\\
&s, t \in \R_{\geq 0}, r \in \R
\end{split}
最後に変数s, t, rをそれぞれbinary変数\bm{y}, \bm{z}, \begin{bmatrix}\bm{w} & \bm{v}\end{bmatrix}に変換した後に罰金法を適用することで、以下のような二次形式(QUBO形式)に変換することができます。
\begin{split}
g(\begin{bmatrix} \bm{x} & \bm{y} & \bm{z} & \bm{w} & \bm{v} \end{bmatrix})
&= \left(\sum_{i=-\infty}^\infty 2^i w_i - \sum_{i=-\infty}^\infty 2^i v_i\right) + \lambda \left\{\sum_{i=1}^M a_i x_i + \sum_{i=-\infty}^\infty 2^i y_i - \left(\sum_{i=-\infty}^\infty 2^i w_i - \sum_{i=-\infty}^\infty 2^i v_i\right)\right\}^2 + \lambda \left\{\sum_{i=1}^M b_i x_i + \sum_{i=-\infty}^\infty 2^i z_i - \left(\sum_{i=-\infty}^\infty 2^i w_i - \sum_{i=-\infty}^\infty 2^i v_i\right)\right\}^2\\
&= \left(\sum_{i=-\infty}^\infty 2^i w_i - \sum_{i=-\infty}^\infty 2^i v_i\right) + \lambda \left(\sum_{i=1}^M \sum_{j=1}^M a_i a_j x_i x_j + \sum_{i=-\infty}^\infty\sum_{j=-\infty}^\infty 2^i 2^j y_i y_j + \sum_{i=-\infty}^\infty\sum_{j=-\infty}^\infty 2^i 2^j w_i w_j + \sum_{i=-\infty}^\infty\sum_{j=-\infty}^\infty 2^i 2^j v_i v_j + 2 \sum_{i=1}^M\sum_{j=-\infty}^\infty 2^j a_i x_i y_j - 2\sum_{i=1}^M\sum_{j=-\infty}^\infty 2^j a_i x_i w_j + 2\sum_{i=1}^M\sum_{j=-\infty}^\infty 2^j a_i x_i v_j - 2\sum_{i=-\infty}^\infty\sum_{j=-\infty}^\infty 2^i 2^j y_i w_j + 2\sum_{i=-\infty}^\infty\sum_{j=-\infty}^\infty 2^i 2^j y_i v_j + 2\sum_{i=-\infty}^\infty\sum_{j=-\infty}^\infty 2^i 2^j w_i v_j\right) + \lambda \left(\sum_{i=1}^M \sum_{j=1}^M b_i b_j x_i x_j + \sum_{i=-\infty}^\infty\sum_{j=-\infty}^\infty 2^i 2^j z_i z_j + \sum_{i=-\infty}^\infty\sum_{j=-\infty}^\infty 2^i 2^j w_i w_j + \sum_{i=-\infty}^\infty\sum_{j=-\infty}^\infty 2^i 2^j v_i v_j + 2 \sum_{i=1}^M\sum_{j=-\infty}^\infty 2^j b_i x_i z_j - 2\sum_{i=1}^M\sum_{j=-\infty}^\infty 2^j b_i x_i w_j + 2\sum_{i=1}^M\sum_{j=-\infty}^\infty 2^j b_i x_i v_j - 2\sum_{i=-\infty}^\infty\sum_{j=-\infty}^\infty 2^i 2^j z_i w_j + 2\sum_{i=-\infty}^\infty\sum_{j=-\infty}^\infty 2^i 2^j z_i v_j + 2\sum_{i=-\infty}^\infty\sum_{j=-\infty}^\infty 2^i 2^j w_i v_j\right)
\end{split}
例
試しに、以下のようなmax関数を含む評価関数をQUBO形式に変換していきます。
f(\bm{x}) = \max(-x_0, -2x_0)
まず、変数rを導入してmax関数を分割すると、以下のような最適化問題に変換できます。
\begin{split}
評価関数: &r → \min\\
制約条件: &-x_0 \leq r\\
&-2x_0 \leq r\\
&x_0 \in {0, 1}\\
&r \in (-4, 0] \cap \Z
\end{split}
次に、スラック変数s, tを導入すると、以下のような最適化問題に変換できます。
\begin{split}
評価関数: &r → \min\\
制約条件: &-x_0 + s = r\\
&-2x_0 + t = r\\
&x_0 \in {0, 1}\\
&s, t \in [0, 4) \cap \Z, r \in (-4, 0] \cap \Z
\end{split}
最後に変数s, t, rをそれぞれbinary変数\bm{y}, \bm{z}, \bm{w}に変換した後に罰金法を適用すると、以下のようなQUBO形式に変換することができます。
\begin{split}
g(\begin{bmatrix} \bm{x} & \bm{y} & \bm{z} & \bm{w}\end{bmatrix})
&= (-w_0 - 2w_1) + \lambda \Bigl\{-x_0 + (y_0 + 2y_1) - (-w_0 - 2w_1)\Bigr\}^2 + \lambda \Bigl\{-2x_0 + (z_0 + 2z_1) - (-w_0 - 2w_1)\Bigr\}^2\\
&= (-w_0 - 2w_1) + \lambda \left(x_0x_0 + \sum_{i=0}^1\sum_{j=0}^1 2^i 2^j y_i y_j + \sum_{i=0}^1\sum_{j=0}^1 2^i 2^j w_i w_j + 2\sum_{i=0}^1 2^i (-x_0) y_i + 2\sum_{i=0}^1 2^i (-x_0) w_i + 2\sum_{i=0}^1\sum_{j=0}^1 2^i 2^j y_i w_j\right) + \lambda \left(4x_0x_0 + \sum_{i=0}^1\sum_{j=0}^1 2^i 2^j y_i y_j + \sum_{i=0}^1\sum_{j=0}^1 2^i 2^j w_i w_j + 2\sum_{i=0}^1 2^i (-2x_0) y_i + 2\sum_{i=0}^1 2^i (-2x_0) w_i + 2\sum_{i=0}^1\sum_{j=0}^1 2^i 2^j y_i w_j\right)\\
&= (-w_0 - 2w_1) + \lambda \Bigl\{x_0x_0 + (y_0y_0 + 2y_0y_1 + 2y_1y_0 + 4y_1y_1) + (w_0w_0 + 2w_0w_1 + 2w_1w_0 + 4w_1w_1) - 2(x_0y_0 + 2x_0y_1) - 2(x_0w_0 + 2x_0w_1) + 2(y_0w_0 + 2y_0w_1 + 2y_1w_0 + 4y_1w_1)\Bigr\} + \lambda \Bigl\{4x_0x_0 + (z_0z_0 + 2z_0z_1 + 2z_1z_0 + 4z_1z_1) + (w_0w_0 + 2w_0w_1 + 2w_1w_0 + 4w_1w_1) - 2(2x_0z_0 + 4x_0z_1) - 2(2x_0w_0 + 4x_0w_1) + 2(z_0w_0 + 2z_0w_1 + 2z_1w_0 + 4z_1w_1)\Bigr\}
\end{split}
すべての場合を列挙すると以下のようになり、\lambdaがある程度大きいときに最小値-1を取るのはx_0 = 1で、制約条件を満たしつつ評価関数の最適値、最適解を求めることができています。
全列挙結果
| x_0 |
y_0 |
y_1 |
z_0 |
z_1 |
w_0 |
w_1 |
g(\begin{bmatrix} \bm{x} & \bm{y} & \bm{z} & \bm{w}\end{bmatrix}) |
| 0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
| 0 |
0 |
0 |
0 |
0 |
0 |
1 |
8\lambda - 2 |
| 0 |
0 |
0 |
0 |
0 |
1 |
0 |
2\lambda - 1 |
| 0 |
0 |
0 |
0 |
0 |
1 |
1 |
18\lambda - 3 |
| 0 |
0 |
0 |
0 |
1 |
0 |
0 |
4\lambda |
| 0 |
0 |
0 |
0 |
1 |
0 |
1 |
20\lambda - 2 |
| 0 |
0 |
0 |
0 |
1 |
1 |
0 |
10\lambda - 1 |
| 0 |
0 |
0 |
0 |
1 |
1 |
1 |
34\lambda - 3 |
| 0 |
0 |
0 |
1 |
0 |
0 |
0 |
\lambda |
| 0 |
0 |
0 |
1 |
0 |
0 |
1 |
13\lambda - 2 |
| 0 |
0 |
0 |
1 |
0 |
1 |
0 |
5\lambda - 1 |
| 0 |
0 |
0 |
1 |
0 |
1 |
1 |
25\lambda - 3 |
| 0 |
0 |
0 |
1 |
1 |
0 |
0 |
9\lambda |
| 0 |
0 |
0 |
1 |
1 |
0 |
1 |
29\lambda - 2 |
| 0 |
0 |
0 |
1 |
1 |
1 |
0 |
17\lambda - 1 |
| 0 |
0 |
0 |
1 |
1 |
1 |
1 |
45\lambda - 3 |
| 0 |
0 |
1 |
0 |
0 |
0 |
0 |
4\lambda |
| 0 |
0 |
1 |
0 |
0 |
0 |
1 |
20\lambda - 2 |
| 0 |
0 |
1 |
0 |
0 |
1 |
0 |
10\lambda - 1 |
| 0 |
0 |
1 |
0 |
0 |
1 |
1 |
34\lambda - 3 |
| 0 |
0 |
1 |
0 |
1 |
0 |
0 |
8\lambda |
| 0 |
0 |
1 |
0 |
1 |
0 |
1 |
32\lambda - 2 |
| 0 |
0 |
1 |
0 |
1 |
1 |
0 |
18\lambda - 1 |
| 0 |
0 |
1 |
0 |
1 |
1 |
1 |
50\lambda - 3 |
| 0 |
0 |
1 |
1 |
0 |
0 |
0 |
5\lambda |
| 0 |
0 |
1 |
1 |
0 |
0 |
1 |
25\lambda - 2 |
| 0 |
0 |
1 |
1 |
0 |
1 |
0 |
13\lambda - 1 |
| 0 |
0 |
1 |
1 |
0 |
1 |
1 |
41\lambda - 3 |
| 0 |
0 |
1 |
1 |
1 |
0 |
0 |
13\lambda |
| 0 |
0 |
1 |
1 |
1 |
0 |
1 |
41\lambda - 2 |
| 0 |
0 |
1 |
1 |
1 |
1 |
0 |
25\lambda - 1 |
| 0 |
0 |
1 |
1 |
1 |
1 |
1 |
61\lambda - 3 |
| 0 |
1 |
0 |
0 |
0 |
0 |
0 |
\lambda |
| 0 |
1 |
0 |
0 |
0 |
0 |
1 |
13\lambda - 2 |
| 0 |
1 |
0 |
0 |
0 |
1 |
0 |
5\lambda - 1 |
| 0 |
1 |
0 |
0 |
0 |
1 |
1 |
25\lambda - 3 |
| 0 |
1 |
0 |
0 |
1 |
0 |
0 |
5\lambda |
| 0 |
1 |
0 |
0 |
1 |
0 |
1 |
25\lambda - 2 |
| 0 |
1 |
0 |
0 |
1 |
1 |
0 |
13\lambda - 1 |
| 0 |
1 |
0 |
0 |
1 |
1 |
1 |
41\lambda - 3 |
| 0 |
1 |
0 |
1 |
0 |
0 |
0 |
2\lambda |
| 0 |
1 |
0 |
1 |
0 |
0 |
1 |
18\lambda - 2 |
| 0 |
1 |
0 |
1 |
0 |
1 |
0 |
8\lambda - 1 |
| 0 |
1 |
0 |
1 |
0 |
1 |
1 |
32\lambda - 3 |
| 0 |
1 |
0 |
1 |
1 |
0 |
0 |
10\lambda |
| 0 |
1 |
0 |
1 |
1 |
0 |
1 |
34\lambda - 2 |
| 0 |
1 |
0 |
1 |
1 |
1 |
0 |
20\lambda - 1 |
| 0 |
1 |
0 |
1 |
1 |
1 |
1 |
52\lambda - 3 |
| 0 |
1 |
1 |
0 |
0 |
0 |
0 |
9\lambda |
| 0 |
1 |
1 |
0 |
0 |
0 |
1 |
29\lambda - 2 |
| 0 |
1 |
1 |
0 |
0 |
1 |
0 |
17\lambda - 1 |
| 0 |
1 |
1 |
0 |
0 |
1 |
1 |
45\lambda - 3 |
| 0 |
1 |
1 |
0 |
1 |
0 |
0 |
13\lambda |
| 0 |
1 |
1 |
0 |
1 |
0 |
1 |
41\lambda - 2 |
| 0 |
1 |
1 |
0 |
1 |
1 |
0 |
25\lambda - 1 |
| 0 |
1 |
1 |
0 |
1 |
1 |
1 |
61\lambda - 3 |
| 0 |
1 |
1 |
1 |
0 |
0 |
0 |
10\lambda |
| 0 |
1 |
1 |
1 |
0 |
0 |
1 |
34\lambda - 2 |
| 0 |
1 |
1 |
1 |
0 |
1 |
0 |
20\lambda - 1 |
| 0 |
1 |
1 |
1 |
0 |
1 |
1 |
52\lambda - 3 |
| 0 |
1 |
1 |
1 |
1 |
0 |
0 |
18\lambda |
| 0 |
1 |
1 |
1 |
1 |
0 |
1 |
50\lambda - 2 |
| 0 |
1 |
1 |
1 |
1 |
1 |
0 |
32\lambda - 1 |
| 0 |
1 |
1 |
1 |
1 |
1 |
1 |
72\lambda - 3 |
| 1 |
0 |
0 |
0 |
0 |
0 |
0 |
5\lambda |
| 1 |
0 |
0 |
0 |
0 |
0 |
1 |
\lambda - 2 |
| 1 |
0 |
0 |
0 |
0 |
1 |
0 |
\lambda - 1 |
| \textcolor{red}{1} |
\textcolor{red}{0} |
\textcolor{red}{0} |
\textcolor{red}{0} |
\textcolor{red}{0} |
\textcolor{red}{1} |
\textcolor{red}{1} |
\textcolor{red}{5\lambda - 3} |
| 1 |
0 |
0 |
0 |
1 |
0 |
0 |
\lambda |
| 1 |
0 |
0 |
0 |
1 |
0 |
1 |
5\lambda - 2 |
| 1 |
0 |
0 |
0 |
1 |
1 |
0 |
\lambda - 1 |
| 1 |
0 |
0 |
0 |
1 |
1 |
1 |
12\lambda - 3 |
| 1 |
0 |
0 |
1 |
0 |
0 |
0 |
2\lambda |
| 1 |
0 |
0 |
1 |
0 |
0 |
1 |
2\lambda - 2 |
| \textcolor{LimeGreen}{1} |
\textcolor{LimeGreen}{0} |
\textcolor{LimeGreen}{0} |
\textcolor{LimeGreen}{1} |
\textcolor{LimeGreen}{0} |
\textcolor{LimeGreen}{1} |
\textcolor{LimeGreen}{0} |
\textcolor{LimeGreen}{-1} |
| 1 |
0 |
0 |
1 |
0 |
1 |
1 |
8\lambda - 3 |
| 1 |
0 |
0 |
1 |
1 |
0 |
0 |
2\lambda |
| 1 |
0 |
0 |
1 |
1 |
0 |
1 |
10\lambda - 2 |
| 1 |
0 |
0 |
1 |
1 |
1 |
0 |
4\lambda - 1 |
| 1 |
0 |
0 |
1 |
1 |
1 |
1 |
20\lambda - 3 |
| 1 |
0 |
1 |
0 |
0 |
0 |
0 |
5\lambda |
| 1 |
0 |
1 |
0 |
0 |
0 |
1 |
9\lambda - 2 |
| 1 |
0 |
1 |
0 |
0 |
1 |
0 |
5\lambda - 1 |
| 1 |
0 |
1 |
0 |
0 |
1 |
1 |
17\lambda - 3 |
| 1 |
0 |
1 |
0 |
1 |
0 |
0 |
\lambda |
| 1 |
0 |
1 |
0 |
1 |
0 |
1 |
13\lambda - 2 |
| 1 |
0 |
1 |
0 |
1 |
1 |
0 |
5\lambda - 1 |
| 1 |
0 |
1 |
0 |
1 |
1 |
1 |
25\lambda - 3 |
| 1 |
0 |
1 |
1 |
0 |
0 |
0 |
2\lambda |
| 1 |
0 |
1 |
1 |
0 |
0 |
1 |
10\lambda - 2 |
| 1 |
0 |
1 |
1 |
0 |
1 |
0 |
4\lambda - 1 |
| 1 |
0 |
1 |
1 |
0 |
1 |
1 |
20\lambda - 3 |
| 1 |
0 |
1 |
1 |
1 |
0 |
0 |
2\lambda |
| 1 |
0 |
1 |
1 |
1 |
0 |
1 |
18\lambda - 2 |
| 1 |
0 |
1 |
1 |
1 |
1 |
0 |
8\lambda - 1 |
| 1 |
0 |
1 |
1 |
1 |
1 |
1 |
32\lambda - 3 |
| 1 |
1 |
0 |
0 |
0 |
0 |
0 |
4\lambda |
| 1 |
1 |
0 |
0 |
0 |
0 |
1 |
4\lambda - 2 |
| 1 |
1 |
0 |
0 |
0 |
1 |
0 |
2\lambda - 1 |
| 1 |
1 |
0 |
0 |
0 |
1 |
1 |
10\lambda - 3 |
| 1 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
| 1 |
1 |
0 |
0 |
1 |
0 |
1 |
8\lambda - 2 |
| 1 |
1 |
0 |
0 |
1 |
1 |
0 |
2\lambda - 1 |
| 1 |
1 |
0 |
0 |
1 |
1 |
1 |
18\lambda - 3 |
| 1 |
1 |
0 |
1 |
0 |
0 |
0 |
\lambda |
| 1 |
1 |
0 |
1 |
0 |
0 |
1 |
5\lambda - 2 |
| 1 |
1 |
0 |
1 |
0 |
1 |
0 |
\lambda - 1 |
| 1 |
1 |
0 |
1 |
0 |
1 |
1 |
13\lambda - 3 |
| 1 |
1 |
0 |
1 |
1 |
0 |
0 |
\lambda |
| 1 |
1 |
0 |
1 |
1 |
0 |
1 |
13\lambda - 2 |
| 1 |
1 |
0 |
1 |
1 |
1 |
0 |
5\lambda - 1 |
| 1 |
1 |
0 |
1 |
1 |
1 |
1 |
25\lambda - 3 |
| 1 |
1 |
1 |
0 |
0 |
0 |
0 |
8\lambda |
| 1 |
1 |
1 |
0 |
0 |
0 |
1 |
16\lambda - 2 |
| 1 |
1 |
1 |
0 |
0 |
1 |
0 |
10\lambda - 1 |
| 1 |
1 |
1 |
0 |
0 |
1 |
1 |
26\lambda - 3 |
| 1 |
1 |
1 |
0 |
1 |
0 |
0 |
4\lambda |
| 1 |
1 |
1 |
0 |
1 |
0 |
1 |
20\lambda - 2 |
| 1 |
1 |
1 |
0 |
1 |
1 |
0 |
10\lambda - 1 |
| 1 |
1 |
1 |
0 |
1 |
1 |
1 |
34\lambda - 3 |
| 1 |
1 |
1 |
1 |
0 |
0 |
0 |
5\lambda |
| 1 |
1 |
1 |
1 |
0 |
0 |
1 |
17\lambda - 2 |
| 1 |
1 |
1 |
1 |
0 |
1 |
0 |
9\lambda - 1 |
| 1 |
1 |
1 |
1 |
0 |
1 |
1 |
29\lambda - 3 |
| 1 |
1 |
1 |
1 |
1 |
0 |
0 |
5\lambda |
| 1 |
1 |
1 |
1 |
1 |
0 |
1 |
25\lambda - 2 |
| 1 |
1 |
1 |
1 |
1 |
1 |
0 |
13\lambda - 1 |
| 1 |
1 |
1 |
1 |
1 |
1 |
1 |
41\lambda - 3 |
絶対値関数
以下のような絶対値を含む評価関数は、二次形式ではないためQUBOで扱うことはできません。
f(\bm{x}) = \left|\sum_{i=1}^M a_i x_i - b\right|
ここで、実数変数r > 0を導入することで、以下のような最適化問題に変換できます。
\begin{split}
評価関数: &r → \min\\
制約条件: &\left|\sum_{i=1}^M a_i x_i - b\right| \leq r\\
&x_i \in {0, 1}\\
&r \in \R_{\geq 0}
\end{split}
次に絶対値の定義から、以下のような最適化問題に変換できます。
\begin{split}
評価関数: &r → \min\\
制約条件: &-r \leq \sum_{i=1}^M a_i x_i - b \leq r\\
&x_i \in {0, 1}\\
&r \in \R_{\geq 0}
\end{split}
さらに、制約\displaystyle -r \leq \sum_{i=1}^M a_i x_i - b \leq rは分割することができ、以下のような最適化問題に変換できます。
\begin{split}
評価関数: &r → \min\\
制約条件: &-r \leq \sum_{i=1}^M a_i x_i - b\\
&\sum_{i=1}^M a_i x_i - b \leq r\\
&x_i \in {0, 1}\\
&r \in \R_{\geq 0}
\end{split}
あとは、不等式制約の時と同様です。
スラック変数s, t \geq 0を導入して、以下のような等式制約に変換します。
\begin{split}
評価関数: &r → \min\\
制約条件: &-r + s = \sum_{i=1}^M a_i x_i - b\\
&\sum_{i=1}^M a_i x_i - b + t = r\\
&x_i \in {0, 1}\\
&s, t, r \in \R_{\geq 0}
\end{split}
最後に変数s, t, rをそれぞれbinary変数\bm{y}, \bm{z}, \bm{w}に変換した後に罰金法を適用することで、以下のような二次形式(QUBO形式)に変換することができます。
\begin{split}
g(\begin{bmatrix} \bm{x} & \bm{y} & \bm{z} & \bm{w} \end{bmatrix})
&= \sum_{i=-\infty}^\infty 2^i w_i + \lambda \left\{-\sum_{i=-\infty}^\infty 2^i w_i + \sum_{i=-\infty}^\infty 2^i y_i - \left(\sum_{i=-\infty}^\infty a_i x_i - b\right)\right\}^2 + \lambda \left\{\left(\sum_{i=1}^M a_i x_i - b\right) + \sum_{i=-\infty}^\infty 2^i z_i - \sum_{i=-\infty}^\infty 2^i w_i\right\}^2\\
&= \sum_{i=-\infty}^\infty 2^i w_i + \lambda \left(\sum_{i=-\infty}^\infty\sum_{j=-\infty}^\infty 2^i 2^j w_i w_j + \sum_{i=-\infty}^\infty\sum_{j=-\infty}^\infty 2^i 2^j y_i y_j + \sum_{i=-\infty}^\infty\sum_{j=-\infty}^\infty a_i a_j x_i x_j - 2\sum_{i=-\infty}^\infty\sum_{j=-\infty}^\infty 2^i 2^j w_i y_j + 2\sum_{i=-\infty}^\infty\sum_{j=-\infty}^\infty 2^i a_j w_i x_j - 2\sum_{i=-\infty}^\infty\sum_{j=-\infty}^\infty 2^i a_j y_i x_j - 2b\sum_{i=-\infty}^\infty 2^i w_i + 2b\sum_{i=-\infty}^\infty 2^i y_i - 2b\sum_{i=-\infty}^\infty a_i x_i + b^2\right) + \lambda \left(\sum_{i=-\infty}^\infty\sum_{j=-\infty}^\infty a_i a_j x_i x_j + \sum_{i=-\infty}^\infty\sum_{j=-\infty}^\infty 2^i 2^j z_i z_j + \sum_{i=-\infty}^\infty\sum_{j=-\infty}^\infty 2^i 2^j w_i w_j + 2\sum_{i=-\infty}^\infty\sum_{j=-\infty}^\infty 2^j a_i x_i z_j - 2\sum_{i=-\infty}^\infty\sum_{j=-\infty}^\infty 2^j a_i x_i w_j - 2\sum_{i=-\infty}^\infty\sum_{j=-\infty}^\infty 2^i 2^j z_i w_j - 2b\sum_{i=-\infty}^\infty a_i x_i - 2b\sum_{i=-\infty}^\infty 2^i z_i + 2b\sum_{i=-\infty}^\infty 2^i w_i + b^2\right)
\end{split}
例
試しに、以下のような絶対値を含む評価関数をQUBO形式に変換していきます。
まず、変数rを導入して絶対値関数を分割すると、以下のような最適化問題に変換できます。
\begin{split}
評価関数: &r → \min\\
制約条件: &-r \leq 2x_0 - 3\\
&2x_0 - 3 \leq r\\
&x_0 \in {0, 1}\\
&r \in [0, 4) \cap \Z
\end{split}
次に、スラック変数s, tを導入すると、以下のような最適化問題に変換できます。
\begin{split}
評価関数: &r → \min\\
制約条件: &-r + s = 2x_0 - 3\\
&2x_0 - 3 + t = r\\
&x_0 \in {0, 1}\\
&s, r \in [0, 4) \cap \Z, t \in [0, 8) \cap \Z
\end{split}
最後に変数s, t, rをそれぞれbinary変数\bm{y}, \bm{z}, \bm{w}に変換した後に罰金法を適用すると、以下のようなQUBO形式に変換することができます。
\begin{split}
g(\begin{bmatrix} \bm{x} & \bm{y} & \bm{z} & \bm{w}\end{bmatrix})
&= (w_0 + 2w_1) + \lambda \Bigl\{-(w_0 + 2w_1) + (y_0 + 2y_1) - (2x_0 - 3)\Bigr\}^2 + \lambda \Bigl\{(2x_0 - 3) + (z_0 + 2z_1 + 4z_2) - (w_0 + 2w_1)\Bigr\}^2\\
&= (w_0 + 2w_1) + \lambda \left(\sum_{i=0}^1\sum_{j=0}^1 2^i 2^j w_i w_j + \sum_{i=0}^1\sum_{j=0}^1 2^i 2^j y_i y_j + 4x_0x_0 - 2\sum_{i=0}^1\sum_{j=0}^1 2^i 2^j w_i y_j + 2\sum_{i=0}^1 2^i w_i (2x_0) - 2\sum_{i=0}^1 2^i y_i (2x_0) - 6\sum_{i=0}^1 2^i w_i + 6\sum_{i=0}^1 2^i y_i - 12x_0 + 9\right) + \lambda \left(4x_0 + \sum_{i=0}^2\sum_{j=0}^2 2^i 2^j z_i z_j + \sum_{i=0}^1\sum_{j=0}^1 2^i 2^j w_i w_j + 2\sum_{i=0}^2 2^i (2x_0) z_i - 2\sum_{i=0}^1 2^j (2x_0) w_j - 2\sum_{i=0}^2\sum_{j=0}^1 2^i 2^j z_i w_j - 12x_0 - 6\sum_{i=0}^2 2^i z_i + 6\sum_{i=0}^1 2^i w_i + 9\right)\\
&= (w_0 + 2w_1) + \lambda \Bigl\{(w_0w_0 + 2w_0w_1 + 2w_1w_0 + 4w_1w_1) + (y_0y_0 + 2y_0y_1 + 2y_1y_0 + 4y_1y_1) + 4x_0x_0 - 2(w_0y_0 + 2w_0y_1 + 2w_1y_0 + 4w_1y_1) + 2 (2w_0x_0 + 4w_1x_0) - 2(2y_0x_0 + 4y_1x_0) - 6(w_0 + 2w_1) + 6(y_0 + 2y_1) - 12x_0 + 9\Bigl\} + \lambda \Bigl\{4x_0x_0 + (z_0z_0 + 2z_0z_1 + 4z_0z_2 + 2z_1z_0 + 4z_1z_1 + 8z_1z_2 + 4z_2z_0 + 8z_2z_1 + 16z_2z_2) + (w_0w_0 + 2w_0w_1 + 2w_1w_0 + 4w_1w_1) + 2(2x_0z_0 + 4x_0z_1 + 8x_0z_2) - 2(2x_0w_0 + 4x_0w_1) - 2(z_0w_0 + 2z_0w_1 + 2z_1w_0 + 4z_1w_1 + 4z_2w_0 + 8z_2w_1) - 12x_0 - 6(z_0 + 2z_1 + 4z_2) + 6(w_0 + 2w_1) + 9\Bigr\}
\end{split}
すべての場合を列挙すると以下のようになり、最小値1を取るのはx_0 = 1で、制約条件を満たしつつ評価関数の最適値、最適解を求めることができています。
全列挙結果
| x_0 |
y_0 |
y_1 |
z_0 |
z_1 |
z_2 |
w_0 |
w_1 |
g(\begin{bmatrix} \bm{x} & \bm{y} & \bm{z} & \bm{w}\end{bmatrix}) |
| 0 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
18\lambda |
| 0 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
26\lambda + 2 |
| 0 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
20\lambda + 1 |
| 0 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
36\lambda + 3 |
| 0 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
10\lambda |
| 0 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
2\lambda + 2 |
| 0 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
4\lambda + 1 |
| 0 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
4\lambda + 3 |
| 0 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
10\lambda |
| 0 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
10\lambda + 2 |
| 0 |
0 |
0 |
0 |
1 |
0 |
1 |
0 |
8\lambda + 1 |
| 0 |
0 |
0 |
0 |
1 |
0 |
1 |
1 |
16\lambda + 3 |
| 0 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
18\lambda |
| 0 |
0 |
0 |
0 |
1 |
1 |
0 |
1 |
2\lambda + 2 |
| 0 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
8\lambda + 1 |
| 0 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
3 |
| 0 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
13\lambda |
| 0 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
17\lambda + 2 |
| 0 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
13\lambda + 1 |
| 0 |
0 |
0 |
1 |
0 |
0 |
1 |
1 |
25\lambda + 3 |
| 0 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
13\lambda |
| 0 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
\lambda + 2 |
| 0 |
0 |
0 |
1 |
0 |
1 |
1 |
0 |
5\lambda + 1 |
| 0 |
0 |
0 |
1 |
0 |
1 |
1 |
1 |
\lambda + 3 |
| 0 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
9\lambda |
| 0 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
5\lambda + 2 |
| 0 |
0 |
0 |
1 |
1 |
0 |
1 |
0 |
5\lambda + 1 |
| 0 |
0 |
0 |
1 |
1 |
0 |
1 |
1 |
9\lambda + 3 |
| 0 |
0 |
0 |
1 |
1 |
1 |
0 |
0 |
25\lambda |
| 0 |
0 |
0 |
1 |
1 |
1 |
0 |
1 |
5\lambda + 2 |
| 0 |
0 |
0 |
1 |
1 |
1 |
1 |
0 |
13\lambda + 1 |
| 0 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
\lambda + 3 |
| 0 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
34\lambda |
| 0 |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
34\lambda + 2 |
| 0 |
0 |
1 |
0 |
0 |
0 |
1 |
0 |
32\lambda + 1 |
| 0 |
0 |
1 |
0 |
0 |
0 |
1 |
1 |
40\lambda + 3 |
| 0 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
26\lambda |
| 0 |
0 |
1 |
0 |
0 |
1 |
0 |
1 |
10\lambda + 2 |
| 0 |
0 |
1 |
0 |
0 |
1 |
1 |
0 |
16\lambda + 1 |
| 0 |
0 |
1 |
0 |
0 |
1 |
1 |
1 |
8\lambda + 3 |
| 0 |
0 |
1 |
0 |
1 |
0 |
0 |
0 |
26\lambda |
| 0 |
0 |
1 |
0 |
1 |
0 |
0 |
1 |
18\lambda + 2 |
| 0 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
20\lambda + 1 |
| 0 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
20\lambda + 3 |
| 0 |
0 |
1 |
0 |
1 |
1 |
0 |
0 |
34\lambda |
| 0 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
10\lambda + 2 |
| 0 |
0 |
1 |
0 |
1 |
1 |
1 |
0 |
20\lambda + 1 |
| 0 |
0 |
1 |
0 |
1 |
1 |
1 |
1 |
4\lambda + 3 |
| 0 |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
29\lambda |
| 0 |
0 |
1 |
1 |
0 |
0 |
0 |
1 |
25\lambda + 2 |
| 0 |
0 |
1 |
1 |
0 |
0 |
1 |
0 |
25\lambda + 1 |
| 0 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
29\lambda + 3 |
| 0 |
0 |
1 |
1 |
0 |
1 |
0 |
0 |
29\lambda |
| 0 |
0 |
1 |
1 |
0 |
1 |
0 |
1 |
9\lambda + 2 |
| 0 |
0 |
1 |
1 |
0 |
1 |
1 |
0 |
17\lambda + 1 |
| 0 |
0 |
1 |
1 |
0 |
1 |
1 |
1 |
5\lambda + 3 |
| 0 |
0 |
1 |
1 |
1 |
0 |
0 |
0 |
25\lambda |
| 0 |
0 |
1 |
1 |
1 |
0 |
0 |
1 |
13\lambda + 2 |
| 0 |
0 |
1 |
1 |
1 |
0 |
1 |
0 |
17\lambda + 1 |
| 0 |
0 |
1 |
1 |
1 |
0 |
1 |
1 |
13\lambda + 3 |
| 0 |
0 |
1 |
1 |
1 |
1 |
0 |
0 |
41\lambda |
| 0 |
0 |
1 |
1 |
1 |
1 |
0 |
1 |
13\lambda + 2 |
| 0 |
0 |
1 |
1 |
1 |
1 |
1 |
0 |
25\lambda + 1 |
| 0 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
5\lambda + 3 |
| 0 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
25\lambda |
| 0 |
1 |
0 |
0 |
0 |
0 |
0 |
1 |
29\lambda + 2 |
| 0 |
1 |
0 |
0 |
0 |
0 |
1 |
0 |
25\lambda + 1 |
| 0 |
1 |
0 |
0 |
0 |
0 |
1 |
1 |
37\lambda + 3 |
| 0 |
1 |
0 |
0 |
0 |
1 |
0 |
0 |
17\lambda |
| 0 |
1 |
0 |
0 |
0 |
1 |
0 |
1 |
5\lambda + 2 |
| 0 |
1 |
0 |
0 |
0 |
1 |
0 |
0 |
9\lambda + 1 |
| 0 |
1 |
0 |
0 |
0 |
1 |
1 |
1 |
5\lambda + 3 |
| 0 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
17\lambda |
| 0 |
1 |
0 |
0 |
1 |
0 |
0 |
1 |
13\lambda + 2 |
| 0 |
1 |
0 |
0 |
1 |
0 |
1 |
0 |
13\lambda + 1 |
| 0 |
1 |
0 |
0 |
1 |
0 |
1 |
1 |
17\lambda + 3 |
| 0 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
25\lambda |
| 0 |
1 |
0 |
0 |
1 |
1 |
0 |
1 |
5\lambda + 2 |
| 0 |
1 |
0 |
0 |
1 |
1 |
1 |
0 |
13\lambda + 1 |
| 0 |
1 |
0 |
0 |
1 |
1 |
1 |
1 |
\lambda + 3 |
| 0 |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
20\lambda |
| 0 |
1 |
0 |
1 |
0 |
0 |
0 |
1 |
20\lambda + 2 |
| 0 |
1 |
0 |
1 |
0 |
0 |
1 |
0 |
18\lambda + 1 |
| 0 |
1 |
0 |
1 |
0 |
0 |
1 |
1 |
26\lambda + 3 |
| 0 |
1 |
0 |
1 |
0 |
1 |
0 |
0 |
20\lambda |
| 0 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
4\lambda + 2 |
| 0 |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
10\lambda + 1 |
| 0 |
1 |
0 |
1 |
0 |
1 |
1 |
1 |
2\lambda + 3 |
| 0 |
1 |
0 |
1 |
1 |
0 |
0 |
0 |
16\lambda |
| 0 |
1 |
0 |
1 |
1 |
0 |
0 |
1 |
8\lambda + 2 |
| 0 |
1 |
0 |
1 |
1 |
0 |
1 |
0 |
10\lambda + 1 |
| 0 |
1 |
0 |
1 |
1 |
0 |
1 |
1 |
10\lambda + 3 |
| 0 |
1 |
0 |
1 |
1 |
1 |
0 |
0 |
32\lambda |
| 0 |
1 |
0 |
1 |
1 |
1 |
0 |
1 |
8\lambda + 2 |
| 0 |
1 |
0 |
1 |
1 |
1 |
1 |
0 |
18\lambda + 1 |
| 0 |
1 |
0 |
1 |
1 |
1 |
1 |
1 |
2\lambda + 3 |
| 0 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
45\lambda |
| 0 |
1 |
1 |
0 |
0 |
0 |
0 |
1 |
41\lambda + 2 |
| 0 |
1 |
1 |
0 |
0 |
0 |
1 |
0 |
41\lambda + 1 |
| 0 |
1 |
1 |
0 |
0 |
0 |
1 |
1 |
45\lambda + 3 |
| 0 |
1 |
1 |
0 |
0 |
1 |
0 |
0 |
37\lambda |
| 0 |
1 |
1 |
0 |
0 |
1 |
0 |
1 |
17\lambda + 2 |
| 0 |
1 |
1 |
0 |
0 |
1 |
1 |
0 |
25\lambda + 1 |
| 0 |
1 |
1 |
0 |
0 |
1 |
1 |
1 |
13\lambda + 3 |
| 0 |
1 |
1 |
0 |
1 |
0 |
0 |
0 |
37\lambda |
| 0 |
1 |
1 |
0 |
1 |
0 |
0 |
1 |
25\lambda + 2 |
| 0 |
1 |
1 |
0 |
1 |
0 |
1 |
0 |
29\lambda + 1 |
| 0 |
1 |
1 |
0 |
1 |
0 |
1 |
1 |
25\lambda + 3 |
| 0 |
1 |
1 |
0 |
1 |
1 |
0 |
0 |
45\lambda |
| 0 |
1 |
1 |
0 |
1 |
1 |
0 |
1 |
17 |
| 0 |
1 |
1 |
0 |
1 |
1 |
1 |
0 |
29\lambda + 1 |
| 0 |
1 |
1 |
0 |
1 |
1 |
1 |
1 |
9\lambda + 3 |
| 0 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
40\lambda |
| 0 |
1 |
1 |
1 |
0 |
0 |
0 |
1 |
32\lambda + 2 |
| 0 |
1 |
1 |
1 |
0 |
0 |
1 |
0 |
34\lambda + 1 |
| 0 |
1 |
1 |
1 |
0 |
0 |
1 |
1 |
34\lambda + 3 |
| 0 |
1 |
1 |
1 |
0 |
1 |
0 |
0 |
40\lambda |
| 0 |
1 |
1 |
1 |
0 |
1 |
0 |
1 |
16\lambda + 2 |
| 0 |
1 |
1 |
1 |
0 |
1 |
1 |
0 |
26\lambda + 1 |
| 0 |
1 |
1 |
1 |
0 |
1 |
1 |
1 |
10\lambda + 3 |
| 0 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
36\lambda |
| 0 |
1 |
1 |
1 |
1 |
0 |
0 |
1 |
20\lambda + 2 |
| 0 |
1 |
1 |
1 |
1 |
0 |
1 |
0 |
26\lambda + 1 |
| 0 |
1 |
1 |
1 |
1 |
0 |
1 |
1 |
18\lambda + 3 |
| 0 |
1 |
1 |
1 |
1 |
1 |
0 |
0 |
52\lambda |
| 0 |
1 |
1 |
1 |
1 |
1 |
0 |
1 |
20\lambda + 2 |
| 0 |
1 |
1 |
1 |
1 |
1 |
1 |
0 |
34\lambda + 1 |
| 0 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
10\lambda + 3 |
| 1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
2\lambda |
| 1 |
0 |
0 |
0 |
0 |
0 |
0 |
1 |
10\lambda + 2 |
| 1 |
0 |
0 |
0 |
0 |
0 |
1 |
0 |
4\lambda + 1 |
| 1 |
0 |
0 |
0 |
0 |
0 |
1 |
1 |
20\lambda + 3 |
| 1 |
0 |
0 |
0 |
0 |
1 |
0 |
0 |
10\lambda |
| 1 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
2\lambda + 2 |
| 1 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
4\lambda + 1 |
| 1 |
0 |
0 |
0 |
0 |
1 |
1 |
1 |
4\lambda + 3 |
| 1 |
0 |
0 |
0 |
1 |
0 |
0 |
0 |
2\lambda |
| 1 |
0 |
0 |
0 |
1 |
0 |
0 |
1 |
2\lambda + 2 |
| \textcolor{LimeGreen}{1} |
\textcolor{LimeGreen}{0} |
\textcolor{LimeGreen}{0} |
\textcolor{LimeGreen}{0} |
\textcolor{LimeGreen}{1} |
\textcolor{LimeGreen}{0} |
\textcolor{LimeGreen}{1} |
\textcolor{LimeGreen}{0} |
\textcolor{LimeGreen}{1} |
| 1 |
0 |
0 |
0 |
1 |
0 |
1 |
1 |
8\lambda + 3 |
| 1 |
0 |
0 |
0 |
1 |
1 |
0 |
0 |
26\lambda |
| 1 |
0 |
0 |
0 |
1 |
1 |
0 |
1 |
10\lambda + 2 |
| 1 |
0 |
0 |
0 |
1 |
1 |
1 |
0 |
16\lambda + 1 |
| 1 |
0 |
0 |
0 |
1 |
1 |
1 |
1 |
8\lambda + 3 |
| 1 |
0 |
0 |
1 |
0 |
0 |
0 |
0 |
\lambda |
| 1 |
0 |
0 |
1 |
0 |
0 |
0 |
1 |
5\lambda + 2 |
| 1 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
\lambda + 1 |
| 1 |
0 |
0 |
1 |
0 |
0 |
1 |
1 |
13\lambda + 3 |
| 1 |
0 |
0 |
1 |
0 |
1 |
0 |
0 |
17\lambda |
| 1 |
0 |
0 |
1 |
0 |
1 |
0 |
1 |
5\lambda + 2 |
| 1 |
0 |
0 |
1 |
0 |
1 |
1 |
0 |
9\lambda + 1 |
| 1 |
0 |
0 |
1 |
0 |
1 |
1 |
1 |
5\lambda + 3 |
| 1 |
0 |
0 |
1 |
1 |
0 |
0 |
0 |
5\lambda |
| 1 |
0 |
0 |
1 |
1 |
0 |
0 |
1 |
\lambda + 2 |
| 1 |
0 |
0 |
1 |
1 |
0 |
1 |
0 |
\lambda + 1 |
| 1 |
0 |
0 |
1 |
1 |
0 |
1 |
1 |
5\lambda + 3 |
| 1 |
0 |
0 |
1 |
1 |
1 |
0 |
0 |
37\lambda |
| 1 |
0 |
0 |
1 |
1 |
1 |
0 |
1 |
17\lambda + 2 |
| 1 |
0 |
0 |
1 |
1 |
1 |
1 |
0 |
25\lambda + 1 |
| 1 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
13\lambda + 3 |
| 1 |
0 |
1 |
0 |
0 |
0 |
0 |
0 |
10\lambda |
| 1 |
0 |
1 |
0 |
0 |
0 |
0 |
1 |
10\lambda + 2 |
| 1 |
0 |
1 |
0 |
0 |
0 |
1 |
0 |
8\lambda + 1 |
| 1 |
0 |
1 |
0 |
0 |
0 |
1 |
1 |
16\lambda + 3 |
| 1 |
0 |
1 |
0 |
0 |
1 |
0 |
0 |
18\lambda |
| 1 |
0 |
1 |
0 |
0 |
1 |
0 |
1 |
2\lambda + 2 |
| 1 |
0 |
1 |
0 |
0 |
1 |
1 |
0 |
8\lambda + 1 |
| 1 |
0 |
1 |
0 |
0 |
1 |
1 |
1 |
3 |
| 1 |
0 |
1 |
0 |
1 |
0 |
0 |
0 |
10\lambda |
| 1 |
0 |
1 |
0 |
1 |
0 |
0 |
1 |
2\lambda + 2 |
| 1 |
0 |
1 |
0 |
1 |
0 |
1 |
0 |
4\lambda + 1 |
| 1 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
4\lambda + 3 |
| 1 |
0 |
1 |
0 |
1 |
1 |
0 |
0 |
34\lambda |
| 1 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
10\lambda + 2 |
| 1 |
0 |
1 |
0 |
1 |
1 |
1 |
0 |
20\lambda + 1 |
| 1 |
0 |
1 |
0 |
1 |
1 |
1 |
1 |
4\lambda + 3 |
| 1 |
0 |
1 |
1 |
0 |
0 |
0 |
0 |
9\lambda |
| 1 |
0 |
1 |
1 |
0 |
0 |
0 |
1 |
5\lambda + 2 |
| 1 |
0 |
1 |
1 |
0 |
0 |
1 |
0 |
5\lambda + 1 |
| 1 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
9\lambda + 3 |
| 1 |
0 |
1 |
1 |
0 |
1 |
0 |
0 |
25\lambda |
| 1 |
0 |
1 |
1 |
0 |
1 |
0 |
1 |
5\lambda + 2 |
| 1 |
0 |
1 |
1 |
0 |
1 |
1 |
0 |
13\lambda + 1 |
| 1 |
0 |
1 |
1 |
0 |
1 |
1 |
1 |
\lambda + 3 |
| 1 |
0 |
1 |
1 |
1 |
0 |
0 |
0 |
13\lambda |
| 1 |
0 |
1 |
1 |
1 |
0 |
0 |
1 |
\lambda + 2 |
| 1 |
0 |
1 |
1 |
1 |
0 |
1 |
0 |
5\lambda + 1 |
| 1 |
0 |
1 |
1 |
1 |
0 |
1 |
1 |
\lambda + 3 |
| 1 |
0 |
1 |
1 |
1 |
1 |
0 |
0 |
45\lambda |
| 1 |
0 |
1 |
1 |
1 |
1 |
0 |
1 |
17\lambda + 2 |
| 1 |
0 |
1 |
1 |
1 |
1 |
1 |
0 |
29\lambda + 1 |
| 1 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
9\lambda + 3 |
| 1 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
5\lambda |
| 1 |
1 |
0 |
0 |
0 |
0 |
0 |
1 |
9\lambda + 2 |
| 1 |
1 |
0 |
0 |
0 |
0 |
1 |
0 |
5\lambda + 1 |
| 1 |
1 |
0 |
0 |
0 |
0 |
1 |
1 |
17\lambda + 3 |
| 1 |
1 |
0 |
0 |
0 |
1 |
0 |
0 |
13\lambda |
| 1 |
1 |
0 |
0 |
0 |
1 |
0 |
1 |
\lambda + 2 |
| 1 |
1 |
0 |
0 |
0 |
1 |
0 |
0 |
5\lambda + 1 |
| 1 |
1 |
0 |
0 |
0 |
1 |
1 |
1 |
\lambda + 3 |
| 1 |
1 |
0 |
0 |
1 |
0 |
0 |
0 |
5\lambda |
| 1 |
1 |
0 |
0 |
1 |
0 |
0 |
1 |
\lambda + 2 |
| 1 |
1 |
0 |
0 |
1 |
0 |
1 |
0 |
\lambda + 1 |
| 1 |
1 |
0 |
0 |
1 |
0 |
1 |
1 |
5\lambda + 3 |
| 1 |
1 |
0 |
0 |
1 |
1 |
0 |
0 |
29\lambda |
| 1 |
1 |
0 |
0 |
1 |
1 |
0 |
1 |
9\lambda + 2 |
| 1 |
1 |
0 |
0 |
1 |
1 |
1 |
0 |
17\lambda + 1 |
| 1 |
1 |
0 |
0 |
1 |
1 |
1 |
1 |
5\lambda + 3 |
| 1 |
1 |
0 |
1 |
0 |
0 |
0 |
0 |
4\lambda |
| 1 |
1 |
0 |
1 |
0 |
0 |
0 |
1 |
4\lambda + 2 |
| 1 |
1 |
0 |
1 |
0 |
0 |
1 |
0 |
2\lambda + 1 |
| 1 |
1 |
0 |
1 |
0 |
0 |
1 |
1 |
10\lambda + 3 |
| 1 |
1 |
0 |
1 |
0 |
1 |
0 |
0 |
20\lambda |
| 1 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
4\lambda + 2 |
| 1 |
1 |
0 |
1 |
0 |
1 |
1 |
0 |
10\lambda + 1 |
| 1 |
1 |
0 |
1 |
0 |
1 |
1 |
1 |
2\lambda + 3 |
| 1 |
1 |
0 |
1 |
1 |
0 |
0 |
0 |
8\lambda |
| 1 |
1 |
0 |
1 |
1 |
0 |
0 |
1 |
2 |
| 1 |
1 |
0 |
1 |
1 |
0 |
1 |
0 |
2\lambda + 1 |
| 1 |
1 |
0 |
1 |
1 |
0 |
1 |
1 |
2\lambda + 3 |
| 1 |
1 |
0 |
1 |
1 |
1 |
0 |
0 |
40\lambda |
| 1 |
1 |
0 |
1 |
1 |
1 |
0 |
1 |
16\lambda + 2 |
| 1 |
1 |
0 |
1 |
1 |
1 |
1 |
0 |
26\lambda + 1 |
| 1 |
1 |
0 |
1 |
1 |
1 |
1 |
1 |
10\lambda + 3 |
| 1 |
1 |
1 |
0 |
0 |
0 |
0 |
0 |
17\lambda |
| 1 |
1 |
1 |
0 |
0 |
0 |
0 |
1 |
13\lambda + 2 |
| 1 |
1 |
1 |
0 |
0 |
0 |
1 |
0 |
13\lambda + 1 |
| 1 |
1 |
1 |
0 |
0 |
0 |
1 |
1 |
17\lambda + 3 |
| 1 |
1 |
1 |
0 |
0 |
1 |
0 |
0 |
25\lambda |
| 1 |
1 |
1 |
0 |
0 |
1 |
0 |
1 |
5\lambda + 2 |
| 1 |
1 |
1 |
0 |
0 |
1 |
1 |
0 |
13\lambda + 1 |
| 1 |
1 |
1 |
0 |
0 |
1 |
1 |
1 |
\lambda + 3 |
| 1 |
1 |
1 |
0 |
1 |
0 |
0 |
0 |
17\lambda |
| 1 |
1 |
1 |
0 |
1 |
0 |
0 |
1 |
5\lambda + 2 |
| 1 |
1 |
1 |
0 |
1 |
0 |
1 |
0 |
9\lambda + 1 |
| 1 |
1 |
1 |
0 |
1 |
0 |
1 |
1 |
5\lambda + 3 |
| 1 |
1 |
1 |
0 |
1 |
1 |
0 |
0 |
41\lambda |
| 1 |
1 |
1 |
0 |
1 |
1 |
0 |
1 |
13\lambda + 2 |
| 1 |
1 |
1 |
0 |
1 |
1 |
1 |
0 |
25\lambda + 1 |
| 1 |
1 |
1 |
0 |
1 |
1 |
1 |
1 |
5\lambda + 3 |
| 1 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
16\lambda |
| 1 |
1 |
1 |
1 |
0 |
0 |
0 |
1 |
8\lambda + 2 |
| 1 |
1 |
1 |
1 |
0 |
0 |
1 |
0 |
10\lambda + 1 |
| 1 |
1 |
1 |
1 |
0 |
0 |
1 |
1 |
10\lambda + 3 |
| 1 |
1 |
1 |
1 |
0 |
1 |
0 |
0 |
32\lambda |
| 1 |
1 |
1 |
1 |
0 |
1 |
0 |
1 |
8\lambda + 2 |
| 1 |
1 |
1 |
1 |
0 |
1 |
1 |
0 |
18\lambda + 1 |
| 1 |
1 |
1 |
1 |
0 |
1 |
1 |
1 |
2\lambda + 3 |
| 1 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
20\lambda |
| 1 |
1 |
1 |
1 |
1 |
0 |
0 |
1 |
4\lambda + 2 |
| 1 |
1 |
1 |
1 |
1 |
0 |
1 |
0 |
10\lambda + 1 |
| 1 |
1 |
1 |
1 |
1 |
0 |
1 |
1 |
2\lambda + 3 |
| 1 |
1 |
1 |
1 |
1 |
1 |
0 |
0 |
52\lambda |
| 1 |
1 |
1 |
1 |
1 |
1 |
0 |
1 |
20\lambda + 2 |
| 1 |
1 |
1 |
1 |
1 |
1 |
1 |
0 |
34\lambda + 1 |
| 1 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
10\lambda + 3 |
まとめ
この記事では、QUBOへの変換テクニックについて解説しました。
QUBOには多くの制限がありますが、今回紹介した変換を使うことでかなり克服できることがわかりました。最初に考案したコスト関数がQUBOの形式でなかったとしても、諦めずに適切な変換をして、量子アニーリングでの解法に挑戦してみましょう。
Discussion
すばらしいまとめありがとうございます。
なんでもQUBOでできるということですよね？
コメントありがとうございます!!
なんでもは言い過ぎかもしれませんが、かなり多くのコスト関数がQUBOに落とし込めるなとまとめていて気付きました。
実際に使ってみると最適解に全然収束しないとかの問題もある気がしています。