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{split} \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} \end{split}\]

この展開により項数は大幅に増加します. 一般に,\(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\) を再現します.