制約条件のQUBO化 — 知識ノート

QUBO は定義上制約を持てない（Unconstrained）。制約は目的関数に取り込むしかない。

等式制約#

$\sum_{i} a_{i} x_{i} = b$ は、違反量の二乗を足す。

P {(\sum_{i} a_{i} x_{i} - b)}^{2}

満たされていれば 0、破れば正の値。 $P$ がペナルティ係数。

One-hot 制約（ $n$ 個からちょうど 1 つ選ぶ）は特に頻出。

P {(\sum_{i} x_{i} - 1)}^{2}

$\sum_{i} a_{i} x_{i} \leq b$ は、そのままでは二乗できない。 スラック変数を足して等式にする。

\sum_{i} a_{i} x_{i} + \sum_{k} 2^{k} y_{k} = b

$y_{k}$ は 0-1 変数で、二進数表現で $0 \sim b$ の任意の値を作る。これで等式制約に帰着できるが、変数が $⌈ \log_{2} b ⌉$ 個増える。

不等式制約の多い問題を QUBO 化すると、変数が急増する。量子アニーラの量子ビット数には限りがあり、さらに埋め込みの際に 1 論理ビットが複数の物理ビットに展開されるため、実際に扱える問題規模はカタログ上のビット数よりずっと小さくなる。

ナップサック問題が量子アニーリングの題材として扱いにくいのはこの理由。

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