HUBO の QUBO への変換

HUBO（高次の制約なし二値最適化）の式は 3 次以上の項を含みうるのに対し、 QUBO（二次の制約なし二値最適化）の式は次数が 2 以下に制限されます。

QUBO++ 同梱の 3 つのソルバー（EasySolver・ExhaustiveSolver・ABS3Solver）は HUBO をそのまま扱えるため変換は不要です。しかし、外部のバックエンドの多く — 物理アニーラや Gurobi・SCIP・D-Wave などの QUBO 専用オプティマイザ — は二次のモデルしか受け付けません。これらに渡すには、HUBO を等価な QUBO に書き換える必要があります。

reduce() 関数はこの変換を行います。次数が 2 を超えるすべての項を、新しい 補助二値変数を導入して次数 2 以下の式に書き換えます。

`reduce()` 関数

reduce() はグローバル関数（非破壊）とメンバ関数（in-place）の両方が提供されます。

qbpp::reduce(f) は f と等価な次数 2 以下の新しい式を返します。
f.reduce() は f をその場で更新して返します。
qbpp::reduce(a) は式の Array も受け付けます（要素ごとに変換）。

#include <qbpp/qbpp.hpp>

int main() {
  auto a = qbpp::var("a");
  auto b = qbpp::var("b");
  auto c = qbpp::var("c");
  qbpp::Expr f = a * b * c;          // 3 次（cubic）の HUBO 項
  qbpp::Expr g = qbpp::reduce(f);    // 等価な QUBO
  std::cout << "f = " << f << std::endl;
  std::cout << "g = " << g << std::endl;
  std::cout << "max_degree = " << g.max_degree() << std::endl;
}

このプログラムの出力:

f = a*b*c
g = {r0} +a*b +a*c -a*{r0} +b*c -b*{r0} -c*{r0}
max_degree = 2

3 次の項 a*b*c が二次の式になりました。{r0} は新たに導入された補助二値変数です。 reduce() は補助変数を {r0}・{r1}・… と波括弧付きで自動命名するため、ユーザー変数と衝突しません。

等価性の保証

reduce() は最適値を保存します。元の変数の任意の割当 x に対して、変換後の式を補助変数について最小化した値が、元の HUBO の値に一致します。

\[f(x) = \min_{\text{aux}} g(x, \text{aux})\]

したがって g の大域最小値（元の変数と補助変数をあわせた全体の最小値）は f の大域最小値に等しく、g の最小解を元の変数に射影したものは f の最小解になります。これにより、reduce(f) を QUBO 専用バックエンドに渡し、結果を元の変数で読み取ることが安全にできます。

変換の仕組み

reduce() は高次の各項を独立に書き換えます。次数 $d$ の項 $c\,x_1 x_2 \cdots x_d$ を考え、$S = x_1 + x_2 + \cdots + x_d$ をその変数のうち 1 である個数とします。

正の係数（$c > 0$）— Ishikawa の規則

補助整数 $a \in [0, d-2]$ を導入し（内部的には約 $\lceil \log_2 (d-1) \rceil$ 個の二値変数で表現）、項を次のように書き換えます。

\[c\,x_1 x_2 \cdots x_d \;=\; \frac{c\,(S-a)(S-a-1)}{2}.\]

$\tfrac{(S-a)(S-a-1)}{2} = \binom{S-a}{2}$ は $S-a \in \lbrace 0, 1\rbrace$ のとき 0、それ以外では正になります。したがって $a$ について最小化すると、元の積が再現されます。

すべての変数が 1（$S = d$）のとき、補助整数は最大でも $a = d-2$ までしか取れず、 $S-a = 2$ で値 $\binom{2}{2} = 1$ — 積に等しい。
どれかの変数が 0（$S < d$）のとき、補助整数は $a = S$ または $a = S-1$ を取れて、 $\binom{0}{2} = \binom{1}{2} = 0$ — 積に等しい。

上限が $d-2$ である（補助整数が $d-1$ や $d$ に届かない）ことが、すべての変数が 1 のときに値を 1 に強制する鍵です。

上の cubic の例（$d = 3$）では、補助整数は単一の二値変数 {r0}（範囲 $[0,1]$）です。上で出力した変換後の式 g について {r0} を最小化すると、任意の割当で $a\,b\,c$ が再現されます。

$(a,b,c)$ の 1 の個数	$a\,b\,c$	`{r0}`=0 の $g$	`{r0}`=1 の $g$	`{r0}` について $\min$
0	0	0	1	0
1	0	0	0	0
2	0	1	0	0
3	1	3	1	1

補助変数はオプティマイザにとって「自由」で、エネルギーを最小にする値に落ち着きます。その値において、変換後の項は元の積に等しくなります。

負の係数（$c < 0$）— Freedman の規則

負の項は 1 個の補助二値変数 $w$ だけで済みます。

\[c\,x_1 x_2 \cdots x_d \;=\; c\,w\,\bigl(S - (d-1)\bigr).\]

$c < 0$ なので、最小化は $|c|\,w\,(S-(d-1))$ の最大化を意味します。すべての変数が 1 のとき、$S-(d-1) = 1$ で $w = 1$ を選ぶと $c$ — 積に等しい。それ以外では $S-(d-1) \le 0$ なので $w = 0$ で 0 — やはり積に等しくなります。

補助変数の個数

reduce() は補助変数を少なく抑えます。

項	規則	補助二値変数
正係数・次数 $d$	Ishikawa	約 $\lceil \log_2 (d-1) \rceil$ 個（$d=3,4$ で 1、$d=5\text{–}8$ で 2、$d=9\text{–}16$ で 3）
負係数・任意の次数	Freedman	ちょうど 1 個

否定リテラル

reduce() は否定リテラルを自動的に扱います。変換後の QUBO は正リテラルのみになります。例えば 4 次の項 ~a*b*c*d は、正リテラルと 1 個の補助変数からなる二次式に変換されます。

qbpp::Expr p = (~a) * b * c * d;
qbpp::Expr q = qbpp::reduce(p);   // 正リテラル + 補助変数 1 個

in-place 形式・配列形式

f.reduce() は f をその場で変換します。式の Array に対しては qbpp::reduce(arr)（または arr.reduce()）が各要素を変換し、Array<Dim, Expr> を返します。