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$ 個の項が生成されます（項が否定リテラルのみで構成される場合は定数項も含まれます）。

QUBO++ は nHUBO モデルを作成できます。 QUBO++ に同梱された3つのソルバーはすべて、通常の HUBO モデルへ変換することなく、否定リテラルをネイティブに処理します。 これにより式の評価コストが大幅に削減され、探索性能が向上します。

HUBO を等価な QUBO に変換する

外部ソルバーの中には（一部の物理アニーラや QUBO 専用バックエンドなど）、二次の モデルしか受け付けないものがあります。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$ を再現します。