QUBO — 知識ノート

\min_{x \in {0,1}^{n}} x^{⊤} Q x = \sum_{i \leq j} Q_{i j} x_{i} x_{j}

$Q$ は上三角（または対称）行列。変数は 0 か 1 の二値。

一次の項は要らない#

$x_{i} \in {0,1}$ なので $x_{i}^{2} = x_{i}$ 。つまり対角成分 $Q_{i i} x_{i}^{2}$ が一次の項 $Q_{i i} x_{i}$ になる。 一次と二次を分けて書く必要がないのはこのため。

三次以上の項があっても、補助変数を導入すれば二次に落とせる（次数削減、quadratization）。ただし変数が増える。

二次に限る理由はハードウェア側にある。量子アニーラもイジングマシンも2 体相互作用しか実装できない。物理的に実現しやすい形が二次だった、という順序。

QUBO は NP 困難。 $Q$ が任意なら Max-Cut を含むので当然。

一方で $Q$ に構造があれば解ける場合もある。たとえば $Q$ の非対角成分がすべて非正なら、最小カット問題に帰着して多項式時間で解ける。

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