組合せ問題のQUBO定式化

代表的な問題を QUBO に落とすときの型。

Max-Cut#

最も素直。変換もペナルティも要らない。

\max \frac{1}{2} \sum_{(i, j)} w_{i j} (1 - s_{i} s_{j})

そのままイジング模型。 QAOA の標準ベンチマークになっている理由。

H = {(\sum_{i} a_{i} s_{i})}^{2}

これも制約なし。ただし全変数が結合する完全結合になる。

$x_{i, t} = 1$ を「時刻 $t$ に都市 $i$ にいる」と定義する。 $n$ 都市に $n^{2}$ 変数が要る。

H = A \sum_{i} (\sum_{t} x_{i, t} - 1)^{2} + A \sum_{t} (\sum_{i} x_{i, t} - 1)^{2} + B \sum_{i, j, t} d_{i j} x_{i, t} x_{j, t + 1}

前 2 項が制約（各都市はちょうど 1 回、各時刻はちょうど 1 都市）、第 3 項が経路長。 $A > B \cdot \max d_{i j}$ が必要条件。

同じ問題でも定式化次第で解けるかが変わる。見るべき点は 3 つ。

Lucas は主要な NP 完全問題について、必要な変数数まで含めた定式化を体系的に与えており、この分野の実質的な出発点になっている。

Andrew Lucas. Ising formulations of many NP problems. Frontiers in Physics 2, 2014. https://doi.org/10.3389/fphy.2014.00005
Fred Glover, Gary Kochenberger, Yu Du. A Tutorial on Formulating and Using QUBO Models. 2019. https://arxiv.org/abs/1811.11538