# HUBO の QUBO への変換 :::{container} prog-cpp **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` も受け付けます（要素ごとに変換）. ```{literalinclude} /../programFiles/cppPrograms/advanced/hubo_to_qubo-program1.cpp :language: cpp :caption: hubo_to_qubo-program1.cpp ``` このプログラムの出力: ```{include} /../programFiles/markDown/advanced/hubo_to_qubo.md :start-after: :end-before: ``` 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 個の補助変数からなる二次式に変換されます. ```{include} /../programFiles/markDown/advanced/hubo_to_qubo.md :start-after: :end-before: ``` ## in-place 形式・配列形式 `f.reduce()` は `f` をその場で変換します.式の `Array` に対しては `qbpp::reduce(arr)`（または `arr.reduce()`）が各要素を変換し,`Array` を 返します. ::: :::{container} prog-python **HUBO**（高次の制約なし二値最適化）の式は 3 次以上の項を含みうるのに対し, **QUBO**（二次の制約なし二値最適化）の式は次数が 2 以下に制限されます. PyQBPP 同梱のネイティブソルバー（`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` をその場で更新して返します（in-place 形式は `Expr` のみ.積の項 `Term` はグローバル形式 `qbpp.reduce(...)` に渡します）. - **`qbpp.reduce(a)`** は式の配列も受け付けます（要素ごとに変換）. ```{literalinclude} /../programFiles/pythonPrograms/advanced/hubo_to_qubo-program1.py :language: python :caption: hubo_to_qubo-program1.py ``` このプログラムの出力: ```{include} /../programFiles/markDown/advanced/hubo_to_qubo.md :start-after: :end-before: ``` 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 個の補助変数からなる二次式に変換されます. ```{include} /../programFiles/markDown/advanced/hubo_to_qubo.md :start-after: :end-before: ``` ## in-place 形式・配列形式 `f.reduce()` は `f` をその場で変換します.式の配列に対しては `qbpp.reduce(arr)`（または `arr.reduce()`）が各要素を変換します. :::