HUBO および QUBO

高次無制約二値最適化（HUBO）問題は、二値変数上の多項式によって定義されます。 目的は、多項式の値を最小化する、すべての変数に対する二値 ${0,1}$ の割り当てを見つけることです。

以下の多項式は HUBO インスタンスの一例です：

この多項式は、$(a,b,c,d) = (0,1,0,1)$ のとき最小値 $-3$ を達成する。 このような割り当てを見つけることが、この多項式に対する HUBO 問題である。

二次無制約二値最適化（QUBO）問題は、多項式の次数の上限を2に制限したHUBOの特殊なケースである。

通常、最適化問題は目的関数と制約条件の集合から成り、いずれも変数の関数として表現される。 これらは、全ての制約を満たしつつ目的関数を最小化（または最大化）する変数値の割り当てを見つけることを目的とする。

これに対し、HUBOおよびQUBO問題は目的関数のみで構成され、明示的な制約を持たない。 この単純な問題構造により、ソルバーは高度に加速されたSIMDスタイルの並列性を活用して効率的に解を探索できる。 さらに、ペナルティ項を用いて制約を目的関数に組み込むことが可能なため、多くの制約付き最適化問題は同等のHUBOまたはQUBO問題として再定式化できる。

QUBO++はC++で実装されたモデル化・解法ツールである。 これによりユーザーは組み合わせ最適化問題をHUBOまたはQUBO多項式として定式化し、解くことができる。 QUBO++には3つの組み込みソルバーも含まれる。