QUBO最適化

0-1 変数の二次式を最小化するという、たった一つの形式。 Quadratic Unconstrained Binary Optimization。

$$\underset{x\in {\{\mathrm{0,1}\}}^n}{\min }{x}^{\top }Qx$$

制約が無い（unconstrained）のが定義に含まれる点が重要で、 制約はペナルティ項として 目的関数に取り込む。

なぜこの形が重要なのか#

多くの NP 困難な組合せ問題が、 この単一の形式に書き直せる。Lucas は主要な NP 完全問題群について イジング形式（QUBO と等価）を体系的に与えた。

つまり QUBO を解く装置を 1 つ作れば、多くの問題に使える。 量子アニーリングマシンや QAOA、専用の古典ハードウェア（イジングマシン）が QUBO を入口にしているのはこのため。

中身#

• QUBO — 形式そのもの
• イジングモデル — 物理側の等価な表現
• 両者の変換
• 制約条件のQUBO化
• ペナルティ項
• 組合せ問題のQUBO定式化

参考文献#

• 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