HUBO の QUBO への変換¶

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

Hi-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 以下の新しい式を返します.単一の積項も qbpp::reduce(2*a*b*c*d) のように直接渡せます（暗黙変換）.
f.reduce() は f をその場で更新して返します.
qbpp::reduce(a) は式の Array も受け付けます（要素ごとに変換）.

hubo_to_qubo-program1.cpp¶

#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]\) を導入し（内部的には約 \(\lfloor \log_2 (d-1) \rfloor\) 個の二値変数で表現）,項を次のように書き換えます.

\[ 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	約 \(\lfloor \log_2 (d-1) \rfloor\) 個（\(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> を返します.

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