二次制約なしバイナリ最適化

二次制約なしバイナリ最適化( QUBO ) は、制約なしバイナリ二次計画法( UBQP )とも呼ばれ、金融や経済から機械学習まで幅広い用途を持つ組み合わせ最適化問題です。^[1] QUBO はNP 困難な問題であり、最大カット、グラフ彩色、分割問題など、理論計算機科学の多くの古典的な問題に対して、QUBO への埋め込みが定式化されています。^{[2] [3]} 機械学習モデルの埋め込みには、サポートベクターマシン、クラスタリング、確率的グラフィカルモデルなどがあります。^{[4]さらに、}イジングモデル との密接な関係により、QUBO は断熱量子計算の中心的な問題クラスを構成し、量子アニーリングと呼ばれる物理的プロセスを通じて解決されます。^[5]

固定長のバイナリベクトルの集合は で表され、はバイナリ値（またはビット）の集合です。実数値の上三角行列が与えられ、その要素はバイナリベクトル内の各インデックスのペアの重みを定義します。各バイナリベクトルに値を割り当てる 関数を次のように定義できます。${\displaystyle n>0}$${\displaystyle \mathbb {B} ^{n}}$${\displaystyle \mathbb {B} =\lbrace 0,1\rbrace }$ ${\displaystyle Q\in \mathbb {R} ^{n\times n}}$${\displaystyle Q_{ij}}$${\displaystyle i,j\in \lbrace 1,\dots ,n\rbrace }$${\displaystyle f_{Q}:\mathbb {B} ^{n}\rightarrow \mathbb {R} }$

${\displaystyle f_{Q}(x)=x^{\top }Qx=\sum _{i=1}^{n}\sum _{j=i}^{n}Q_{ij}x_{i}x_{j}}$

直感的には、との両方の値が 1 の場合に重みが追加されます。 のとき、すべてのについて と同様に、の場合に値が追加されます。 ${\displaystyle Q_{ij}}$${\displaystyle x_{i}}$${\displaystyle x_{j}}$${\displaystyle i=j}$${\displaystyle Q_{ii}}$${\displaystyle x_{i}=1}$${\displaystyle x_{i}x_{i}=x_{i}}$${\displaystyle x_{i}\in \mathbb {B} }$

QUBO問題は、に関して最小となる2進ベクトルを見つけることである。すなわち、 ${\displaystyle x^{*}}$${\displaystyle f_{Q}}$

${\displaystyle \forall x\in \mathbb {B} ^{n}:~f_{Q}(x^{*})\leq f_{Q}(x)}$

一般に、は一意ではないため、 に関して等しい値を持つ最小化ベクトルの集合が存在する可能性があります。QUBO の複雑さは、 がに対して指数関数的に増加するため、評価される候補のバイナリ ベクトルの数から生じます。 ${\displaystyle x^{*}}$${\displaystyle f_{Q}}$${\displaystyle |\mathbb {B} ^{n}|=2^{n}}$${\displaystyle n}$

QUBO はを最大化する 問題として定義されることもあります。これは を最小化する問題と同等です。 ${\displaystyle f_{Q}}$${\displaystyle f_{-Q}=-f_{Q}}$

QUBOは正の因子に対してスケール不変であり、最適値は変化しない。 ${\displaystyle \alpha >0}$${\displaystyle x^{*}}$

${\displaystyle f_{\alpha Q}(x)=\sum _{i\leq j}(\alpha Q_{ij})x_{i}x_{j}=\alpha \sum _{i\leq j} Q_{ij}x_{i}x_{j}=\alpha f_{Q}(x)}$

QUBOは一般的な形式ではNP困難であり、多項式時間アルゴリズムでは効率的に解くことができません。^[6] しかし、多項式的に解ける特殊なケースがあり、特定の特性を持っています。 ^[7]たとえば、 ${\displaystyle Q}$

• すべての係数が正の場合、最適値は であることが自明です。同様に、すべての係数が負の場合、最適値は です。${\displaystyle x^{*}=(0,\dots ,0)}$${\displaystyle x^{*}=(1,\dots ,1)}$
• が対角の場合、ビットは独立に最適化でき、問題は で解けます。最適な変数割り当ては、の場合は単純に、それ以外の場合は です。${\displaystyle Q}$${\displaystyle {\mathcal {O}}(n)}$${\displaystyle x_{i}^{*}=1}$${\displaystyle Q_{ii}$${\displaystyle x_{i}^{*}=0}$
• のすべての非対角要素が非正であれば、対応するQUBO問題は多項式時間で解ける。^[8]${\displaystyle Q}$

QUBO は、 CPLEXやGurobi Optimizerなどの整数線形計画法ソルバーを使用して解くことができます。これは、QUBO を線形制約付きバイナリ最適化問題として再定式化できるため可能です。これを実現するには、積を追加のバイナリ変数に置き換え、制約、およびを追加します。 は、境界 0 と 1 内の連続変数に 緩和することもできることに注意してください。${\displaystyle x_{i}x_{j}}$${\displaystyle z_{ij}\in \{0,1\}}$${\displaystyle x_{i}\geq z_{ij}}$${\displaystyle x_{j}\geq z_{ij}}$${\displaystyle x_{i}+x_{j}-1\leq z_{ij}}$${\displaystyle z_{ij}}$

QUBOは構造的には単純ですが、計算上は困難な最適化問題です。さまざまな科学分野の幅広い最適化問題をエンコードするために使用できます。^[9]

QUBO を使用して最適化問題をエンコードする方法の例として、クラスター分析の問題を考えます。ここでは、2D 空間内の 20 個のポイントのセットが与えられます。これは、各行に 2 つの直交座標が含まれる行列 で表されます。同じクラスター内のポイントが互いに類似するように、各ポイントを 2 つのクラスまたはクラスター のいずれかに割り当てます。2 つのクラスターの場合、の - 番目の行に対応するポイントにバイナリ変数を割り当てて、そのポイントが最初のクラスター ( ) に属するか、2 番目のクラスター ( ) に属するかを示すことができます。その結果、20 個のバイナリ変数が得られ、これがすべてのポイントのクラスター割り当てに対応する バイナリ ベクトルを形成します(図を参照)。${\displaystyle D\in \mathbb {R} ^{20\times 2}}$${\displaystyle x_{i}\in \mathbb {B} }$${\displaystyle i}$${\displaystyle D}$${\displaystyle x_{i}=0}$${\displaystyle x_{i}=1}$${\displaystyle x\in \mathbb {B} ^{20}}$

クラスタリングを導く 1 つの方法は、ポイント間のペアワイズ距離を考慮することです。クラスター割り当て が与えられた場合、ポイントと が同じクラスター内にある場合、またはのいずれかが1 と評価されます。同様に、または のいずれかが は、それらが異なるクラスター内にあることを示します。ポイントと間のユークリッド距離を で表します。最小化するためのコスト関数を定義するには、ポイントと が同じクラスター内にある場合はそれらの正の距離 を加算し、異なるクラスター内にある場合はそれを減算します。このように、最適なソリューションでは、離れているポイントを異なるクラスターに配置し、近いポイントを同じクラスターに配置する傾向があります。したがって、コスト関数は次のようになります。 ${\displaystyle x}$${\displaystyle x_{i}x_{j}}$${\displaystyle (1-x_{i})(1-x_{j})}$${\displaystyle i}$${\displaystyle j}$${\displaystyle x_{i}(1-x_{j})}$${\displaystyle (1-x_{i})x_{j}}$${\displaystyle d_{ij}\geq 0}$${\displaystyle i}$${\displaystyle j}$${\displaystyle i}$${\displaystyle j}$${\displaystyle d_{ij}}$

${\displaystyle {\begin{aligned}f(x)&=\sum _{i<j}d_{ij}(x_{i}x_{j}+(1-x_{i})(1-x_{j}))-d_{ij}(x_{i}(1-x_{j})+(1-x_{i})x_{j})\\&=\sum _{i<j}\left[4d_{ij}x_{i}x_{j}-2d_{ij}x_{i}-2d_{ij}x_{j}+d_{ij}\right]\end{aligned}}}$

2 行目から、QUBO パラメータは次のように並べ替えることで簡単に見つけることができます。

${\displaystyle {\begin{aligned}Q_{ij}&={\begin{cases}d_{ij}&{\text{if }}i\neq j\\-\left(\sum \limits _{k=1}^{i-1}d_{ki}+\sum \limits _{\ell =i+1}^{n}d_{i\ell }\right)&{\text{if }}i=j\end{cases}}\end{aligned}}}$

これらのパラメータを使用すると、最適な QUBO ソリューションは、上記のコスト関数に関して最適なクラスターに対応します。

QUBOはイジング模型と非常に密接に関連しており、計算上は同等である。イジング模型のハミルトニアン関数は次のように定義される。

${\displaystyle H(\sigma )=-\sum _{\langle i~j\rangle }J_{ij}\sigma _{i}\sigma _{j}-\mu \sum _{j}h_{j}\sigma _{j}}$

はすべての に対して実数値パラメータを持ちます。スピン変数はではなく からの値を持つバイナリです。さらに、イジングモデルでは、変数は通常、隣接する変数のペアのみが非ゼロの係数を持つことができる格子に配置されます。恒等式を適用すると、同等のQUBO問題が得られます。^[2]${\displaystyle h_{j},J_{ij},\mu }$${\displaystyle i,j}$ ${\displaystyle \sigma _{j}}$${\displaystyle \lbrace -1,+1\rbrace }$${\displaystyle \mathbb {B} }$${\displaystyle \langle i~j\rangle }$${\displaystyle \sigma \mapsto 2x-1}$

${\displaystyle {\begin{aligned}f(x)&=\sum _{\langle i~j\rangle }-J_{ij}(2x_{i}-1)(2x_{j}-1)+\sum _{j}\mu h_{j}(2x_{j}-1)\\&=\sum _{\langle i~j\rangle }(-4J_{ij}x_{i}x_{j}+2J_{ij}x_{i}+2J_{ij}x_{j}-J_{ij})+\sum _{j}(2\mu h_{j}x_{j}-\mu h_{j})&&{\text{using }}x_{j}=x_{j}x_{j}\\&=\sum _{\langle i~j\rangle }(-4J_{ij}x_{i}x_{j})+\sum _{\langle i~j\rangle }2J_{ij}x_{i}+\sum _{\langle i~j\rangle }2J_{ij}x_{j}+\sum _{j}2\mu h_{j}x_{j}-\sum _{\langle i~j\rangle }J_{ij}-\sum _{j}\mu h_{j}\\&=\sum _{\langle i~j\rangle }(-4J_{ij}x_{i}x_{j})+\sum _{\langle j~i\rangle }2J_{ji}x_{j}+\sum _{\langle i~j\rangle }2J_{ij}x_{j}+\sum _{j}2\mu h_{j}x_{j}-\sum _{\langle i~j\rangle }J_{ij}-\sum _{j}\mu h_{j}&&{\text{using }}\sum _{\langle i~j\rangle }=\sum _{\langle j~i\rangle }\\&=\sum _{\langle i~j\rangle }(-4J_{ij}x_{i}x_{j})+\sum _{j}\sum _{\langle k=j~i\rangle }2J_{ki}x_{j}+\sum _{j}\sum _{\langle i~k=j\rangle }2J_{ik}x_{j}+\sum _{j}2\mu h_{j}x_{j}-\sum _{\langle i~j\rangle }J_{ij}-\sum _{j}\mu h_{j}\\&=\sum _{\langle i~j\rangle }(-4J_{ij}x_{i}x_{j})+\sum _{j}\left(\sum _{\langle i~k=j\rangle }(2J_{ki}+2J_{ik})+2\mu h_{j}\right)x_{j}-\sum _{\langle i~j\rangle }J_{ij}-\sum _{j}\mu h_{j}&&{\text{using }}\sum _{\langle k=j~i\rangle }=\sum _{\langle i~k=j\rangle }\\&=\sum _{i=1}^{n}\sum _{j=1}^{i}Q_{ij}x_{i}x_{j}+C\end{aligned}}}$

どこ

${\displaystyle {\begin{aligned}Q_{ij}&={\begin{cases}-4J_{ij}&{\text{if }}i\neq j\\\sum _{\langle i~k=j\rangle }(2J_{ki}+2J_{ik})+2\mu h_{j}&{\text{if }}i=j\end{cases}}\\C&=-\sum _{\langle i~j\rangle }J_{ij}-\sum _{j}\mu h_{j}\end{aligned}}}$

バイナリ変数の場合、という事実を使用します。 ${\displaystyle x_{j}=x_{j}x_{j}}$

定数は最適値の位置を変えないので、最適化の際には無視することができ、元のハミルトン関数値を回復する場合にのみ重要です。 ${\displaystyle C}$${\displaystyle x^{*}}$

• QUBO ベンチマーク (QUBO の正確な解を求めるソフトウェア パッケージのベンチマーク。有名な Mittelmann ベンチマーク コレクションの一部)

• Endre Boros、Peter L Hammer、Gabriel Tavares (2007 年 4 月)。「二次制約なしバイナリ最適化 (QUBO) のローカル検索ヒューリスティック」。Journal of Heuristics。13 ( 2 )。Association for Computing Machinery: 99–132。doi : 10.1007 /s10732-007-9009-3。S2CID  32887708。2013年5 月 12 日閲覧。
• Di Wang & Robert Kleinberg (2009 年 11 月)。「マルチコモディティフローによる 2 次制約なしバイナリ最適化問題の解析」。離散 応用数学。157 ( 18 )。エルゼビア: 3746–3753。doi :10.1016/j.dam.2009.07.009。PMC 2808708。PMID 20161596。