# HUBO と QUBO **高次制約なしバイナリ最適化 (High-Order Unconstrained Binary Optimization, HUBO)** 問題は,バイナリ変数上の多項式によって定義されます. 目標は,多項式の値を最小化するようなバイナリ値 ${0,1}$ の割り当てを全変数に対して見つけることです. 以下の多項式は HUBO のインスタンスの例です： $$ \begin{aligned} f(a,b,c,d) &=1 -2a +45c +8d +4ab -13ac +2ad -10bc -12bd +2abc +5acd \end{aligned} $$ この多項式は $(a,b,c,d) = (0,1,0,1)$ のとき最小値 $-3$ を取ります. このような割り当てを見つけることが,この多項式に対する HUBO 問題です. **2次制約なしバイナリ最適化 (Quadratic Unconstrained Binary Optimization, QUBO)** 問題は,多項式の次数が2以下に制限された HUBO の特殊ケースです. 通常,最適化問題は目的関数と制約条件の集合で構成され,いずれも変数の関数として表現されます. すべての制約条件を満たしつつ,目的関数を最小化（または最大化）する変数値の割り当てを見つけることが目的です. 一方,HUBO および QUBO 問題は目的関数のみで構成され,明示的な制約条件を持ちません. このシンプルな問題構造により,ソルバーは高度に加速された SIMD スタイルの並列処理を活用して効率的に解を探索できます. さらに,ペナルティ項を用いて制約条件を目的関数に組み込めるため,多くの制約付き最適化問題を等価な HUBO または QUBO 問題として再定式化できます. ## 否定リテラルを含む HUBO (nHUBO) **否定リテラルを含む HUBO (nHUBO)** は,否定リテラルを含む項も持つことができる HUBO です. 例えば,以下のような項を含めることができます： $$ \overline{a}b\overline{c}\overline{d} $$ 従来の HUBO では,すべての変数 $x$ について関係式 $\overline{x}=1-x$ を用いて,否定リテラルを含まない項に変換する必要があります： $$ \begin{aligned} \overline{a}b\overline{c}\overline{d} &= (1-a)b(1-c)(1-d) \\ &=b -ab -bc -bd +abc +abd +bcd -abcd \end{aligned} $$ この展開により項数は大幅に増加します. 一般に,$n$ 個の否定リテラルを含む項を展開すると,$2^n$ 個の項が生成されます（項が否定リテラルのみで構成される場合は定数項も含まれます）. Hi-QUBO は nHUBO モデルを作成できます. Hi-QUBO に同梱された3つのソルバーはすべて,通常の HUBO モデルへ変換することなく,否定リテラルをネイティブに処理します. これにより式の評価コストが大幅に削減され,探索性能が向上します. ## HUBO を等価な QUBO に変換する 外部ソルバーの中には（一部の物理アニーラや QUBO 専用バックエンドなど）,二次の モデルしか受け付けないものがあります.Hi-QUBO は `reduce()` を提供しており,HUBO 式の 次数が 3 以上のすべての項を,新しい補助二値変数を導入して次数 2 以下の項に書き換えることで, **等価な QUBO** に変換します. C++ では free 関数 `qbpp::reduce(f)` が新しい式を返し,`f.reduce()` が `f` をその場で 変換します.Python では `qbpp.reduce(f)` が新しい式を返し,`f.reduce()` がその場で 変換します. この変換は最適値を保存します.元の変数の任意の割当に対して,変換後の QUBO を補助変数に ついて最小化した値が,元の HUBO の値に一致します.したがって QUBO の最小解を元の変数に 射影したものは,HUBO の最小解になります.否定リテラルを含む HUBO 式も自動的に処理され, 変換後の QUBO は正リテラルのみになります. 例えば三次の項 $abc$ は,$a$, $b$, $c$ と 1 個以上の補助変数についての二次式に変換され, 補助変数について最小化すると,$a$, $b$, $c$ の任意の割当に対して $abc$ を再現します.