Combinatorial optimization problem
二次制約なしバイナリ最適化 ( QUBO ) は、 制約なしバイナリ二次計画法 ( UBQP )とも呼ばれ、 金融 や 経済から 機械学習 まで 幅広い用途を持つ 組み合わせ 最適化問題 です。 [1] QUBO は NP 困難な問題であり、 最大カット 、 グラフ彩色 、 分割問題 など、 理論計算機科学 の多くの古典的な問題に対して 、QUBO への埋め込みが定式化されています。 [2] [3] 機械学習モデルの埋め込みには、 サポートベクターマシン 、 クラスタリング 、 確率グラフィカルモデル などがあります。 [4]さらに、 イジングモデル との密接な関係により、QUBO は 断熱量子計算 の中心的な問題クラスを構成し、 量子アニーリング と呼ばれる物理的プロセスを通じて解決されます 。 [5]
意味 2進 数字（または ビット ） の集合を とすると、 は 固定長 の2進ベクトルの集合となる 。 対称行列 または上 三角行列 が与えられ、その要素が 各添字のペアの重みを定義すると、 各2進ベクトルに値を割り当てる関数を 次のように 定義できる。 B = { 0 , 1 } {\displaystyle \mathbb {B} =\lbrace 0,1\rbrace } B n {\displaystyle \mathbb {B} ^{n}} n ∈ N {\displaystyle n\in \mathbb {N} } Q ∈ R n × n {\displaystyle {\boldsymbol {Q}}\in \mathbb {R} ^{n\times n}} Q i j {\displaystyle Q_{ij}} i , j ∈ { 1 , … , n } {\displaystyle i,j\in \lbrace 1,\dots ,n\rbrace } f Q : B n → R {\displaystyle f_{\boldsymbol {Q}}:\mathbb {B} ^{n}\rightarrow \mathbb {R} } x {\displaystyle {\boldsymbol {x}}}
f Q ( x ) = x ⊺ Q x = ∑ i = 1 n ∑ j = 1 n Q i j x i x j . {\displaystyle f_{\boldsymbol {Q}}({\boldsymbol {x}})={\boldsymbol {x}}^{\intercal }{\boldsymbol {Qx}}=\sum _{i=1}^{n}\sum _{j=1}^{n}Q_{ij}x_{i}x_{j}.} あるいは、線形部分と二次関数部分は次のように分離できる。
f Q ′ , q ( x ) = x ⊺ Q ′ x + q ⊺ x , {\displaystyle f_{{\boldsymbol {Q}}',{\boldsymbol {q}}}({\boldsymbol {x}})={\boldsymbol {x}}^{\intercal }{\boldsymbol {Q}}'{\boldsymbol {x}}+{\boldsymbol {q}}^{\intercal }{\boldsymbol {x}},} ここで 、 および です。これは 、すべてのバイナリ値 に対して diag 演算子を使用 することで、 前の定義と同等になります 。 Q ′ ∈ R n × n {\displaystyle {\boldsymbol {Q}}'\in \mathbb {R} ^{n\times n}} q ∈ R n {\displaystyle {\boldsymbol {q}}\in \mathbb {R} ^{n}} Q = Q ′ + diag [ q ] {\displaystyle {\boldsymbol {Q}}={\boldsymbol {Q}}'+\operatorname {diag} [{\boldsymbol {q}}]} x = x ⋅ x {\displaystyle x=x\cdot x} x {\displaystyle x}
直感的に言えば、と の両方が成り立つ場合に 重み が追加されます。QUBO問題は 、 、 つまり を最小化する バイナリベクトルを見つけることです 。 Q i j {\displaystyle Q_{ij}} x i = 1 {\displaystyle x_{i}=1} x j = 1 {\displaystyle x_{j}=1} x ∗ {\displaystyle {\boldsymbol {x}}^{*}} f Q {\displaystyle f_{\boldsymbol {Q}}} ∀ x ∈ B n : f Q ( x ∗ ) ≤ f Q ( x ) {\displaystyle \forall {\boldsymbol {x}}\in \mathbb {B} ^{n}:~f_{\boldsymbol {Q}}({\boldsymbol {x}}^{*})\leq f_{\boldsymbol {Q}}({\boldsymbol {x}})}
一般に、 は一意ではないため、 に関して等しい値を持つ最小ベクトルの集合が存在する可能性があります。QUBOの複雑さは、 が に対して指数 関数的に増加する ため、評価すべき候補となる2値ベクトルの数に起因します 。 x ∗ {\displaystyle {\boldsymbol {x}}^{*}} f Q {\displaystyle f_{\boldsymbol {Q}}} | B n | = 2 n {\displaystyle \left|\mathbb {B} ^{n}\right|=2^{n}} n {\displaystyle n}
QUBO はを最大化する 問題として定義されることもあり 、これは を最小化する問題と同等です 。 f Q {\displaystyle f_{\boldsymbol {Q}}} f − Q = − f Q {\displaystyle f_{-{\boldsymbol {Q}}}=-f_{\boldsymbol {Q}}}
プロパティ QUBOは正の因子に対してスケール不変であり 、最適値は 変化しない。 α > 0 {\displaystyle \alpha >0} x ∗ {\displaystyle {\boldsymbol {x}}^{*}}
f α Q ( x ) = x ⊺ ( α Q ) x = α ( x ⊺ Q x ) = α f Q ( x ) {\displaystyle f_{\alpha {\boldsymbol {Q}}}({\boldsymbol {x}})={\boldsymbol {x}}^{\intercal }(\alpha {\boldsymbol {Q}}){\boldsymbol {x}}=\alpha ({\boldsymbol {x}}^{\intercal }{\boldsymbol {Qx}})=\alpha f_{\boldsymbol {Q}}({\boldsymbol {x}})} 。 QUBOは一般形では NP困難 であり、いかなる多項式時間アルゴリズムでも効率的に解くことはできない。 [6] しかし、多項式的に解ける特殊なケースがあり、その場合は 特定の性質を持つ。 [7] 例えば： Q {\displaystyle {\boldsymbol {Q}}}
すべての係数が正であれば、最適値は自明に です 。同様に、すべての係数が負であれば、最適値は です 。 x ∗ = ( 0 , … , 0 ) ⊺ {\displaystyle {\boldsymbol {x}}^{*}=(0,\dots ,0)^{\intercal }} x ∗ = ( 1 , … , 1 ) ⊺ {\displaystyle {\boldsymbol {x}}^{*}=(1,\dots ,1)^{\intercal }} が対角 の 場合 、ビットは独立に最適化でき、問題は で解けます 。最適な変数割り当ては、 の場合は 、 それ以外の場合は となります。 Q {\displaystyle {\boldsymbol {Q}}} O ( n ) {\displaystyle {\mathcal {O}}(n)} x i ∗ = 1 {\displaystyle x_{i}^{*}=1} Q i i < 0 {\displaystyle Q_{ii}<0} x i ∗ = 0 {\displaystyle x_{i}^{*}=0} のすべての非対角要素が 非正であれば、対応するQUBO問題は多項式時間で解ける。 [8] Q {\displaystyle {\boldsymbol {Q}}} QUBOは、 CPLEX や Gurobi Optimizerなどの 整数線形計画法 ソルバー を用いて解くことができます 。これは、QUBOを線形制約付き2値最適化問題として再定式化できるため可能です。これを実現するには、積を 2値変数に置き換え 、制約 、、 を追加します。また、 を0と1の範囲内の連続変数に 緩和 できる ことに注意してください。 x i x j {\displaystyle x_{i}x_{j}} z i j ∈ B {\displaystyle z_{ij}\in \mathbb {B} } x i ≥ z i j {\displaystyle x_{i}\geq z_{ij}} x j ≥ z i j {\displaystyle x_{j}\geq z_{ij}} x i + x j − 1 ≤ z i j {\displaystyle x_{i}+x_{j}-1\leq z_{ij}} z i j {\displaystyle z_{ij}}
アプリケーション QUBOは構造的には単純ですが、計算量的には困難な最適化問題です。様々な科学分野における幅広い最適化問題を符号化するために使用できます。 [9]
最大カット 頂点集合 と辺 を持つ グラフが与えられたとき 、 最大カット (max-cut) 問題は、 と の間の辺の数が最大化されるような 2 つの部分集合を 見つける こと です 。 G = ( V , E ) {\displaystyle G=(V,E)} V = { 1 , … , n } {\displaystyle V=\lbrace 1,\dots ,n\rbrace } E ⊆ V × V {\displaystyle E\subseteq V\times V} S , T ⊆ V {\displaystyle S,T\subseteq V} T = V ∖ S {\displaystyle T=V\setminus S} S {\displaystyle S} T {\displaystyle T}
より一般的な 重み付き最大カット 問題は、 の辺の重み を仮定し 、 と の間の辺の重みの合計を最大化する 分割 を求める。 すなわち、 w i j ≥ 0 ∀ i , j ∈ V {\displaystyle w_{ij}\geq 0~\forall i,j\in V} ( i , j ) ∉ E ⇒ w i j = 0 {\displaystyle (i,j)\notin E\Rightarrow w_{ij}=0} S , T ⊆ V {\displaystyle S,T\subseteq V} S {\displaystyle S} T {\displaystyle T}
max S ⊆ V ∑ i ∈ S , j ∉ S w i j . {\displaystyle \max _{S\subseteq V}\sum _{i\in S,j\notin S}w_{ij}.} すべてを 設定すると 、これは上記の元の最大カット問題と同等になります。そのため、以下ではこのより一般的な形式に焦点を当てます。 w i j = 1 {\displaystyle w_{ij}=1} ( i , j ) ∈ E {\displaystyle (i,j)\in E}
の各頂点に対して、 かつ の場合 には と 解釈される 2値変数を導入します 。 であるため 、すべてのはちょうど1つの集合に属します。つまり、2値ベクトル と を2つの部分集合に分割する部分集合 との間には1:1の対応関係があります 。 i ∈ V {\displaystyle i\in V} x i {\displaystyle x_{i}} x i = 0 {\displaystyle x_{i}=0} i ∈ S {\displaystyle i\in S} x i = 1 {\displaystyle x_{i}=1} i ∈ T {\displaystyle i\in T} T = V ∖ S {\displaystyle T=V\setminus S} i {\displaystyle i} x ∈ B n {\displaystyle {\boldsymbol {x}}\in \mathbb {B} ^{n}} V {\displaystyle V}
任意の に対して、 式 が1 と評価されるのは、 と が 異なる部分集合にある 場合のみであり、これは の論理 XOR と等価である。 と しよう 。上記の式を行列ベクトル形式に拡張すると、次の式が得られる。 i , j ∈ V {\displaystyle i,j\in V} x i ( 1 − x j ) + ( 1 − x i ) x j {\displaystyle x_{i}(1-x_{j})+(1-x_{i})x_{j}} i {\displaystyle i} j {\displaystyle j} W ∈ R + n × n {\displaystyle {\boldsymbol {W}}\in \mathbb {R} _{+}^{n\times n}} W i j = w i j ∀ i , j ∈ V {\displaystyle W_{ij}=w_{ij}~\forall i,j\in V}
x ⊺ W ( 1 − x ) + ( 1 − x ) ⊺ W x = − 2 x ⊺ W x + ( W 1 + W ⊺ 1 ) ⊺ x {\displaystyle {\boldsymbol {x}}^{\intercal }{\boldsymbol {W}}({\boldsymbol {1}}-{\boldsymbol {x}})+({\boldsymbol {1}}-{\boldsymbol {x}})^{\intercal }{\boldsymbol {Wx}}=-2{\boldsymbol {x}}^{\intercal }{\boldsymbol {Wx}}+({\boldsymbol {W1}}+{\boldsymbol {W}}^{\intercal }{\boldsymbol {1}})^{\intercal }{\boldsymbol {x}}} は、 と の間のすべての辺の重みの和である 。これは 上の2次関数なので 、これはQUBO問題であり、そのパラメータ行列は上記の式から次のように読み取ることができる。 S {\displaystyle S} T {\displaystyle T} 1 = ( 1 , 1 , … , 1 ) ⊺ ∈ R n {\displaystyle {\boldsymbol {1}}=(1,1,\dots ,1)^{\intercal }\in \mathbb {R} ^{n}} x {\displaystyle {\boldsymbol {x}}}
Q = 2 W − diag [ W 1 + W ⊺ 1 ] , {\displaystyle {\boldsymbol {Q}}=2{\boldsymbol {W}}-\operatorname {diag} [{\boldsymbol {W1}}+{\boldsymbol {W}}^{\intercal }{\boldsymbol {1}}],} 符号を反転して最小化問題にします。
クラスター分析
20個の点を持つクラスタリング問題の視覚的表現：同じ色の円は同じクラスターに属します。それぞれの円は、対応するQUBO問題における2値変数として理解できます。
次に、クラスター分析 の問題を考えます。この問題では、次元空間 の点 の集合が与えられ、各点を 2 つのクラスまたは クラスター のいずれかに割り当て 、同じクラスター内の点が互いに類似するようにします。この例では、 とを設定します 。データは行列 として与えられ 、各行には 2 つの 直交座標 が含まれます。2 つのクラスターについては、 の- 番目の行 に対応する点に バイナリ変数を割り当てて、その点が最初のクラスター ( ) に属するか、2 番目のクラスター ( ) に属するかを示すことができます。結果として、20 個のバイナリ変数が得られ、これが すべての点のクラスター割り当てに対応する バイナリ ベクトルを形成します(図を参照)。 N {\displaystyle N} d {\displaystyle d} N = 20 {\displaystyle N=20} d = 2 {\displaystyle d=2} X ∈ R 20 × 2 {\displaystyle {\boldsymbol {X}}\in \mathbb {R} ^{20\times 2}} x i ∈ B {\displaystyle x_{i}\in \mathbb {B} } i {\displaystyle i} X {\displaystyle {\boldsymbol {X}}} x i = 0 {\displaystyle x_{i}=0} x i = 1 {\displaystyle x_{i}=1} x ∈ B 20 {\displaystyle {\boldsymbol {x}}\in \mathbb {B} ^{20}}
クラスタリングを導く一つの方法は、点間のペアワイズ距離を考慮することです。クラスタ割り当て が与えられた場合、点 と が同じクラスタに属する場合、 式 は 1と評価されます 。同様に、 はそれらが異なるクラスタに属することを示します。 点 との間の ユークリッド距離 を とすると 、すなわち、 x {\displaystyle {\boldsymbol {x}}} x i x j + ( 1 − x i ) ( 1 − x j ) {\displaystyle x_{i}x_{j}+(1-x_{i})(1-x_{j})} i {\displaystyle i} j {\displaystyle j} x i ( 1 − x j ) + ( 1 − x i ) x j = 1 {\displaystyle x_{i}(1-x_{j})+(1-x_{i})x_{j}=1} d i j > 0 {\displaystyle d_{ij}>0} i {\displaystyle i} j {\displaystyle j}
d i j = X i ⊺ X j {\displaystyle d_{ij}={\sqrt {{\boldsymbol {X}}_{i}^{\intercal }{\boldsymbol {X}}_{j}}}} 、 は の - 行目 です 。 X i {\displaystyle {\boldsymbol {X}}_{i}} i {\displaystyle i} X {\displaystyle {\boldsymbol {X}}}
最小化するためのコスト関数を定義するには、点 と が 同じクラスターに属する場合はそれらの正の距離 を加算し 、異なるクラスターに属する場合はそれを減算します。このように、最適解は、離れた点を異なるクラスターに、近い点を同じクラスターに配置する傾向があります。 i {\displaystyle i} j {\displaystyle j} d i j {\displaystyle d_{ij}}
全ての に対して と する 。割り当て が与えられた場合 、そのようなコスト関数は次のように与えられる。 D ∈ R N × N {\displaystyle {\boldsymbol {D}}\in \mathbb {R} ^{N\times N}} D i j = d i j / 2 {\displaystyle D_{ij}=d_{ij}/2} i , j ∈ { 1 , … , n } {\displaystyle i,j\in \lbrace 1,\dots ,n\rbrace } x ∈ B N {\displaystyle {\boldsymbol {x}}\in \mathbb {B} ^{N}}
f ( x ) = x ⊺ D x − x ⊺ D ( 1 − x ) − ( 1 − x ) ⊺ D x + ( 1 − x ) ⊺ D ( 1 − x ) = 4 x ⊺ D x − 4 1 ⊺ D x + 1 ⊺ D 1 , {\displaystyle {\begin{aligned}f({\boldsymbol {x}})&={\boldsymbol {x}}^{\intercal }{\boldsymbol {Dx}}-{\boldsymbol {x}}^{\intercal }{\boldsymbol {D}}({\boldsymbol {1}}-{\boldsymbol {x}})-({\boldsymbol {1}}-{\boldsymbol {x}})^{\intercal }{\boldsymbol {Dx}}+({\boldsymbol {1}}-{\boldsymbol {x}})^{\intercal }{\boldsymbol {D}}({\boldsymbol {1}}-{\boldsymbol {x}})\\&=4{\boldsymbol {x}}^{\intercal }{\boldsymbol {D}}{\boldsymbol {x}}-4{\boldsymbol {1}}^{\intercal }{\boldsymbol {D}}{\boldsymbol {x}}+{\boldsymbol {1}}^{\intercal }{\boldsymbol {D1}},\end{aligned}}} どこ 。 1 = ( 1 , 1 , … , 1 ) ⊺ ∈ R N {\displaystyle {\boldsymbol {1}}=(1,1,\dots ,1)^{\intercal }\in \mathbb {R} ^{N}}
2行目から、この式はQUBO問題に再配置できることがわかります。
Q = 4 D − 4 diag [ D 1 ] {\displaystyle {\boldsymbol {Q}}=4{\boldsymbol {D}}-4\operatorname {diag} [{\boldsymbol {D1}}]} 定数項を無視します 。これらのパラメータを用いることで、このQUBOインスタンスを最小化するバイナリベクトルは、 上記のコスト関数に関して最適なクラスター割り当てに対応します。 1 ⊺ D 1 {\displaystyle {\boldsymbol {1}}^{\intercal }{\boldsymbol {D1}}} Q {\displaystyle {\boldsymbol {Q}}}
イジングモデルへの接続 QUBOは イジング模型 と非常に密接に関連しており、計算上は同等である。イジング模型の ハミルトニアン関数 は次のように定義される。
H ( σ ) = σ ⊺ J σ + h ⊺ σ = ∑ i , j J i j σ i σ j + ∑ j h j σ j {\displaystyle H({\boldsymbol {\sigma }})={\boldsymbol {\sigma }}^{\intercal }{\boldsymbol {J}}{\boldsymbol {\sigma }}+{\boldsymbol {h}}^{\intercal }{\boldsymbol {\sigma }}=\sum _{i,j}J_{ij}\sigma _{i}\sigma _{j}+\sum _{j}h_{j}\sigma _{j}} すべての に対して 実数値パラメータを持ちます 。 スピン変数は ではなく からの値を持つバイナリ変数です 。この定式化は簡略化されていることに注意してください。なぜなら、物理学の文脈では、 は通常 、サイズ の複素数値行列である パウリ演算子 ですが、ここではバイナリ変数として扱うからです。イジング模型ハミルトニアンの多くの定式化では、さらに、変数が格子状に配置されていると仮定します。格子内では、隣接する変数のペアのみが非ゼロの係数を持つことができます。ここでは、 とが隣接していない 場合は と を単純に仮定します 。 h j , J i j {\displaystyle h_{j},J_{ij}} i , j {\displaystyle i,j} σ j {\displaystyle \sigma _{j}} { − 1 , + 1 } {\displaystyle \lbrace -1,+1\rbrace } B {\displaystyle \mathbb {B} } σ i {\displaystyle \sigma _{i}} 2 n × 2 n {\displaystyle 2^{n}\times 2^{n}} ⟨ i j ⟩ {\displaystyle \langle i~j\rangle } J i j = 0 {\displaystyle J_{ij}=0} i {\displaystyle i} j {\displaystyle j}
等価性を適用すると 、同等のQUBO問題が得られる [10] σ = 1 − 2 x {\displaystyle \sigma =1-2x}
σ ⊺ J σ + h ⊺ σ = ( 1 − 2 x ) ⊺ J ( 1 − 2 x ) + h ⊺ ( 1 − 2 x ) = 4 x ⊺ J x − 4 1 ⊺ J x + 1 ⊺ J 1 − 2 h ⊺ x + h ⊺ 1 = x ⊺ ( 4 J ) x − ( 4 J ⊺ 1 + 2 h ) ⊺ x + 1 ⊺ J 1 + h ⊺ 1 ⏟ const. , {\displaystyle {\begin{aligned}&{\boldsymbol {\sigma }}^{\intercal }{\boldsymbol {J}}{\boldsymbol {\sigma }}+{\boldsymbol {h}}^{\intercal }{\boldsymbol {\sigma }}\\&=({\boldsymbol {1}}-2{\boldsymbol {x}})^{\intercal }{\boldsymbol {J}}({\boldsymbol {1}}-2{\boldsymbol {x}})+{\boldsymbol {h}}^{\intercal }({\boldsymbol {1}}-2{\boldsymbol {x}})\\&=4{\boldsymbol {x}}^{\intercal }{\boldsymbol {J}}{\boldsymbol {x}}-4{\boldsymbol {1}}^{\intercal }{\boldsymbol {Jx}}+{\boldsymbol {1}}^{\intercal }{\boldsymbol {J1}}-2{\boldsymbol {h}}^{\intercal }{\boldsymbol {x}}+{\boldsymbol {h}}^{\intercal }{\boldsymbol {1}}\\&={\boldsymbol {x}}^{\intercal }(4{\boldsymbol {J}}){\boldsymbol {x}}-(4{\boldsymbol {J}}^{\intercal }{\boldsymbol {1}}+2{\boldsymbol {h}})^{\intercal }{\boldsymbol {x}}+\underbrace {{\boldsymbol {1}}^{\intercal }{\boldsymbol {J1}}+{\boldsymbol {h}}^{\intercal }{\boldsymbol {1}}} _{\text{const.}},\end{aligned}}} その重み行列 は次のように与えられる。 Q {\displaystyle {\boldsymbol {Q}}}
Q = 4 J − diag [ 4 J ⊺ 1 + 2 h ] , {\displaystyle {\boldsymbol {Q}}=4{\boldsymbol {J}}-\operatorname {diag} [4{\boldsymbol {J}}^{\intercal }{\boldsymbol {1}}+2{\boldsymbol {h}}],} ここでも定数項は無視されるが、これは最小化には影響しない。恒等式 を用いて 、行列 を持つQUBO問題は、 同じ手法で等価なイジングモデルに変換することができ、以下の式が得られる。 x = ( 1 − σ ) / 2 {\displaystyle x=(1-\sigma )/2} Q {\displaystyle {\boldsymbol {Q}}}
J = Q / 4 , h = − ( Q 1 + Q ⊺ 1 ) / 4 , {\displaystyle {\begin{aligned}{\boldsymbol {J}}&={\boldsymbol {Q}}/4,&{\boldsymbol {h}}&=-({\boldsymbol {Q1}}+{\boldsymbol {Q}}^{\intercal }{\boldsymbol {1}})/4,\end{aligned}}} および定数オフセット 。 [10] 1 ⊺ Q 1 / 4 {\displaystyle {\boldsymbol {1}}^{\intercal }{\boldsymbol {Q1}}/4}
参考文献 ^ Kochenberger, Gary; Hao, Jin-Kao; Glover, Fred; Lewis, Mark; Lu, Zhipeng; Wang, Haibo; Wang, Yang (2014). 「制約なし二項二次計画問題：概観」 (PDF) . Journal of Combinatorial Optimization . 28 : 58–81 . doi :10.1007/s10878-014-9734-0. S2CID 16808394. ^ Glover, Fred; Kochenberger, Gary (2019). 「QUBOモデルの定式化と使用に関するチュートリアル」. arXiv : 1811.11538 [cs.DS]. ^ Lucas, Andrew (2014). 「多くのNP問題のイジング定式化」. Frontiers in Physics . 2 : 5. arXiv : 1302.5843 . Bibcode :2014FrP.....2....5L. doi : 10.3389/fphy.2014.00005 . ^ Mücke, Sascha; Piatkowski, Nico; Morik, Katharina (2019). 「少しずつ学ぶ：機械学習のエッセンスの抽出」 （PDF） . LWDA . S2CID 202760166. 2020年2月27日時点のオリジナル （PDF） からのアーカイブ。 ^ Tom Simonite (2013年5月8日). 「D-Waveの量子コンピュータが競争に参戦、勝利」. MIT Technology Review. 2015年9月24日時点のオリジナルよりアーカイブ 。 2013年 5月12日 閲覧。 ^ AP Punnen（編）、二次制約なしバイナリ最適化問題：理論、アルゴリズム、アプリケーション、Springer、Springer、2022年。 ^ Çela, E., Punnen, AP (2022). QUBOの複雑性と多項式的に解ける特殊なケース. Punnen, AP (編) 『二次制約なし二項最適化問題』. Springer, Cham. https://doi.org/10.1007/978-3-031-04520-2_3 ^ Punnen (2022)の定理3.16を参照。著者らは QUBOの 最大化バージョンを想定していることに注意してください。 ^ Ratke, Daniel (2021-06-10). 「QUBO定式化の一覧」 . 2022年12月16日 閲覧 。 ^ ab Mücke、S. (2025)。機械学習における量子古典最適化。シェーカー・フェルラグ。 https://d-nb.info/1368090214
外部リンク 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). Elsevier: 3746– 3753. doi :10.1016/j.dam.2009.07.009. PMC 2808708. PMID 20161596 . 広島大学・NTTデータグループ：「ABS2 GPU QUBOソルバー搭載QUBO++」#ソフトウェア。 
![{\displaystyle {\boldsymbol {Q}}={\boldsymbol {Q}}'+\operatorname {diag} [{\boldsymbol {q}}]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/cb7a760b282165df1c98351060c0889957342a4b)
![{\displaystyle {\boldsymbol {Q}}=2{\boldsymbol {W}}-\operatorname {diag} [{\boldsymbol {W1}}+{\boldsymbol {W}}^{\intercal }{\boldsymbol {1}}],}](https://wikimedia.org/api/rest_v1/media/math/render/svg/57e2894392995586c948ff65fed23a8a02a07b8b)
![{\displaystyle {\boldsymbol {Q}}=4{\boldsymbol {D}}-4\operatorname {diag} [{\boldsymbol {D1}}]}](https://wikimedia.org/api/rest_v1/media/math/render/svg/f6bb302443c516e90d0cce7fe93edafc71780e1c)
![{\displaystyle {\boldsymbol {Q}}=4{\boldsymbol {J}}-\operatorname {diag} [4{\boldsymbol {J}}^{\intercal }{\boldsymbol {1}}+2{\boldsymbol {h}}],}](https://wikimedia.org/api/rest_v1/media/math/render/svg/4eecacf104b654f710b7b77e2aa23b98bc8e4aa2)
