QUBO入門

QUBOはさまざまな最適化問題に使われています。

具体的に見てみましょう。

箱の表にそれぞれ \(x_{0}, x_{1}, x_{2}\) と書かれた3つの箱があるときに、その中からいくつかの箱を選ぶ問題を考えます。

まず、箱が選ばれた場合を1、選ばれなかった場合を0と決めます。 \(x_{0}\) の箱を選んだ場合、\(x_{0} = 1, x_{1} = 0, x_{2} = 0\) と表現します。 コンピュータで扱い易いように、これを配列で表現するとx=[1,0,0]のようになります。

今回解きたい問題が「3個から任意の2個を選ぶ」という問題だとします。 この問題を解くために関数E(x)を考えるのですが、正しい選び方をした場合に関数E(x)が最小になるような関数を考えます。 今回は、次の関数を考えました。

\[E(x) = (x_{0} + x_{1} + x_{2} - 2) ^ 2\]

どうなるか見てみましょう。

  • \(x_{0}\) だけ選んだ場合、\(E(x) = (1 + 0 + 0 - 2) ^ 2 = (-1) ^ 2 = 1\) になります。
  • \(x_{0}\)\(x_{1}\) を選んだ場合、\(E(x) = (1 + 1 + 0 - 2) ^ 2 = (0) ^ 2 = 0\) になります。
  • 3つとも選んだ場合、\(E(x) = (1 + 1 + 1 - 2) ^ 2 = (1) ^ 2 = 1\) になります。

2つ選んだときだけ、最小値である0をとりますので、ここで考えたE(x)はこの問題を解くために最適な関数のようです。 このE(x)を少し展開していきます。

\[\begin{split}E(x) &= (x_{0} + x_{1} + x_{2} - 2) ^ 2 \\ &= (x_{0} + x_{1} + x_{2} - 2) (x_{0} + x_{1} + x_{2} - 2) \\ &= x_{0} ^ 2 + x_{1} ^ 2 + x_{2} ^ 2 + 2 x_{0} x_{1} + 2 x_{0} x_{2} + 2 x_{1} x_{2} - 4 x_{0} - 4 x_{1} - 4 x_{2} + 4\end{split}\]

ここで、xは0か1の値しか取らないことを思い出してください。その場合、\(x = x ^ 2 = x x\) と変換することができます。 それを使うと上記の式は、さらに次のように変形できます。

\[\begin{split}E(x) &= x_{0} ^ 2 + x_{1} ^ 2 + x_{2} ^ 2 + 2 x_{0} x_{1} + 2 x_{0} x_{2} + 2 x_{1} x_{2} - 4 x_{0} - 4 x_{1} - 4 x_{2} + 4 \\ &= x_{0} ^ 2 + x_{1} ^ 2 + x_{2} ^ 2 + 2 x_{0} x_{1} + 2 x_{0} x_{2} + 2 x_{1} x_{2} - 4 x_{0} x_{0} - 4 x_{1} x_{1} - 4 x_{2} x_{2} + 4 \\ &= -3 x_{0} x_{0} −3 x_{1} x_{1} -3 x_{2} x_{2} + 2 x_{0} x_{1} + 2 x_{0} x_{2} + 2 x_{1} x_{2} + 4\end{split}\]

ここで、上記のE(x)を計算するために、次の様なマトリックスを考えます。

  \(x_{0}\) \(x_{1}\) \(x_{2}\)
\(x_{0}\)      
\(x_{1}\)      
\(x_{2}\)      

上記の式の最初の部分は \(x_{0}\)\(x_{0}\) をかけたものを-3倍するということですよね。なので、マトリックスの \(x_{0}\)\(x_{0}\) が交わるところに-3と入れます。

  \(x_{0}\) \(x_{1}\) \(x_{2}\)
\(x_{0}\) -3    
\(x_{1}\)      
\(x_{2}\)      

次の2つも \(x_{1}\)\(x_{1}\) の交点、 \(x_{2}\)\(x_{2}\) の交点にそれぞれ-3を入れます。

  \(x_{0}\) \(x_{1}\) \(x_{2}\)
\(x_{0}\) -3    
\(x_{1}\)   -3  
\(x_{2}\)     -3

その次は \(x_{0}\)\(x_{1}\) をかけたものを2倍するということなので、 \(x_{0}\)\(x_{1}\) が交わるところに2といれます。

  \(x_{0}\) \(x_{1}\) \(x_{2}\)
\(x_{0}\) -3 2  
\(x_{1}\)   -3  
\(x_{2}\)     -3

次の2つも \(x_{0}\)\(x_{2}\) の交点、 \(x_{1}\)\(x_{2}\) の交点にそれぞれ2を入れます。 最後の4は定数なので、エネルギーの最小値を求める際には影響しないので、無視します。

結果としてできたマトリックスはつぎのようになります。実はこれが「3つの箱から任意の2つを選ぶ」問題を解くためのQUBOなのです。

  \(x_{0}\) \(x_{1}\) \(x_{2}\)
\(x_{0}\) -3 2 2
\(x_{1}\)   -3 2
\(x_{2}\)     -3

このQUBOを使ってWildqatのシミュレーティッドアニーリングに解かせるコードは次のようになります。

import wildqat as wq
a = wq.opt()
a.qubo = [[-3,2,2], [0,-3,2], [0,0,-3]]
answer = a.sa()
print(answer)

実行してみると、[1,1,0]と表示されました。これは \(x_{0}\)\(x_{1}\) が選ばれたことを表します。 「3つの箱から任意の2つを選ぶ」問題がちゃんと解けていますね。 今回の場合、実行する毎に違う答えが表示されます。 それは、今回の問題が、3つの箱から2つを選ぶ問題であり、その答えは実際に3通りあるからです。

手順の復習

問題の解き方を整理すると次のようになります。

  1. その問題が解けたときに、最小になる関数E(x)を考えます。
  2. E(x)を式展開してQUBOマトリックスを作成します。
  3. QUBOマトリックスをWildqatに与えて、シミュレーティッドアニーリングで解かせます。

この中で難しいのは1.ですが、チュートリアル に問題とその関数の例が多数掲載されていますので、その中から合うものを見つけると良いでしょう。

QUBOをより深く理解する

QUBOの行番号を \(i\) 、列番号を \(j\) とし、QUBOの各要素を \(Q_{ij}\) と表すとE(x)は次の様に表現できます。

\[E(x) = \sum_{i} \sum_{j} Q_{ij} x_{i} x_{j}\]

ここで \(Q_{ij}\) がまさにQUBOです。上の方でE(x)を計算している最後の式をよく見てみると、この形になっていることが分かると思います。

Wikipedia の説明(英語)も参考にしてください。