QUBO＋＋入門：項数爆発を防ぐ否定リテラルのネイティブサポート
> Source: Zenn_Python
Execute Primary Source
// Problem
QUBO/HUBOで否定リテラル $\bar{x}$ を $1-x$ に置き換えて展開すると、$n$ 個の否定リテラルの積から $2^n-1$ 個の項が発生する。この項数爆発は、メモリ使用量や求解時間の増大を招き、大規模な問題の解決を困難にする。
// Approach
QUBO++は否定リテラルをそのままの形で保持するネイティブサポートを備える。`simplify_as_binary()` においても、3次以上の項に含まれる否定リテラルは展開せず保持する。ソルバーもこれらを直接扱うことで、展開による項数爆発を回避する。
// Result
NAE-SATの例では、展開時に128項（簡約後75項）を要するケースでも、QUBO++ではわずか8項で表現可能であった。否定リテラルを保持することで、数学的な定義を自然に実装しつつ、計算リソースを大幅に節約できる。
Senior Engineer Insight
> 高次項の展開回避は、定式化の柔軟性と計算効率を両立させる重要な技術である。ソルバー側が否定リテラルを含む高次項を直接扱える設計である点は、実用上の大きな強みである。