D-WaveのQUBOでクリーク問題を、イジングで自然数分割問題を実装して解く

QUBO wildqat イジング 量子アニーリング
Tweet

はじめに

実際の量子コンピュータを活用して問題を解く際に質問がとても多いので、一連の手順をまとめておきます。今回は自分の会社で借りたD-Waveを活用しながら実際に問題を解く手順を確認します。

イジングモデルについて

http://blog.mdrft.com/post/6

イジングモデルの参考例題について

http://blog.mdrft.com/post/42

今回解く問題「クリーク問題/ Cliques」

クリーク問題は、グラフ理論において、グラフ中のクリーク（任意の二頂点間に枝があるような頂点集合）を見つける問題。下記はグラフ中にKのクリークが存在するかどうかをみつけるハミルトニアン。１項目は頂点数をKに制約する条件。２項目のBで囲まれた部分は選んだ頂点が完全グラフを構成している場合にコストがもっとも小さくなるようなエッジの数の条件です。クリーク数がKのものが存在する場合、ハミルトニアンH=0となります。

$
H = \left(K-\sum_v x_v\right)^2 + B\left[\frac{K(K-1)}{2}-\sum_{(u,v)\in E}x_u x_v\right]
$

（例題）下記のように６つのノードのネットワーク構造からクリーク数３を探します。

自然数分割問題と何が違うか

自然数分割問題は置く量子ビットを{-1,1}で考えました。今回考えるクリーク問題は量子ビットを{0,1}のバイナリー値でおきます。そうすることで考えやすい問題が増えます。その代わり途中式に変換が発生しますので、その辺りをフォローします。

まずは量子ビットを用意する

今回はノード数が6なので、6量子ビット用意します。
$x_i = [x_1,x_2,x_3,x_4,x_5,x_6]$

次に今回はクリーク数3ということで、上記の式のK=3とします。
そして、$x_i$を$x_1$から$x_6$まですべて代入すると、

$
\begin{eqnarray*}
H &=& \left(3-\sum_v x_v\right)^2 + B\left[\frac{3(3-1)}{2}-\sum_{(u,v)\in E}x_u x_v\right]\\
&=&(3-x_1-x_2-x_3-x_4-x_5-x_6)^2+B(3-x_1x_5-x_1x_2-x_2x_5-x_2x_3-x_3x_4-x_4x_5-x_4x_6)\\
&=&x_1^2 + 2x_1x_2 + 2x_1x_3 + 2x_1x_4 + 2x_1x_5 + 2x_1x_6 – 6x_1 + x2^2 + 2x_2x_3 + 2x_2x_4 + 2x_2x_5 + 2x_2x_6 – 6x_2 + x3^2 + 2x_3x_4 + 2x_3x_5 + 2x_3x_6 – 6x_3 + x_4^2 + 2x_4x_5 + 2x_4x_6 – 6x_4 + x5^2 + 2x_5x_6 – 6x_5 + x_6^2 – 6x_6 + 9 + B(3-x_1x_5-x_1x_2-x_2x_5-x_2x_3-x_3x_4-x_4x_5-x_4x_6)
\end{eqnarray*}
$

ここで$x_i$はバイナリー値より$x_i^2 = x_i$をつかって、かつ式をもう少し整理して、

$
\begin{eqnarray*}
H &=& (2-B)x_1x_2 + (2-B)x_1x_5 + (2-B)x_2x_3 + (2-B)x_2x_5 + (2-B)x_3x_4 + (2-B)x_4x_5 + (2-B)x_4x_6 + 2x_1x_3 + 2x_1x_4 + 2x_1x_6 – 5x_1 + 2x_2x_4 + 2x_2x_6 – 5x_2 + 2x_3x_5 + 2x_3x_6 – 5x_3 – 5x_4 + 2x_5x_6 – 5x_5 – 5x_6 + 9+3B
\end{eqnarray*}
$

ここで、式を見やすくするために、６量子ビットの関係性を表すQUBOmatrixをつくります。縦横それぞれ６量子ビットの6×6の行列を用意して、各項の相互作用Jijや磁場項hを行列の形にまとめます。

$
\begin{array}
-&x_1&x_2&x_3&x_4&x_5&x_6\\
x_1& -5 & 2-B & 2 & 2 & 2-B & 2\\
x_2& & -5 & 2-B & 2 & 2-B & 2\\
x_3& && -5&2-B & 2&2\\
x_4& &&& -5 & 2-B &2-B\\
x_5& &&&& -5 & 2\\
x_6& &&&&& -5
\end{array}
$

ここで上記Bはハイパーパラメータです。

QUBO変換

ここで、この問題は{0,1}のバイナリ値で作りました。そこでこの値を{-1,1}に変換する必要があります。変換方法は簡単で、$x_i=\frac{q_i+1}{2}$を代入します。

そちらの代入後をさらに一般化したのが下記の変換ルールです。

$
Jij = \frac{1}{4}Q_{i,j}\\
h_i = \frac{1}{2}Q_{i,i}+\frac{1}{4}\sum_{iD-waveへの入力

やはりここでも結合数を調整する必要性があります。
上記のmatrixは６量子ビットの完全結合をベースに作られているので、
それをD-Waveのキメライジングモデルに落とし込む必要性がああります。

もとの完全グラフ６ノード

キメラグラフへの落とし込み（２２量子ビット）

点線は接続してないエッジ、太線はコピーをするときのエッジ。
（*すみません、もっと少ない量子ビットでも実装できました。１７量子ビット別の機会に紹介します。）

コピーを作って確認する

上記太線部分だけを入力して見て（相互作用項-1を設定する）コピーが作成されていることを確認。

次にイジングmatrixで固定値のところを入力

基本的にイジングの行列を見てみると、ハイパーパラメータBがないところを確認し、
$x_1x_3,x_1x_4,x_1x_6,x_2x_4,x_2x_6,x_3x_5,x_3x_6,x_5x_6$の相互作用については、固定値なのでそれを入力してしまう。

最後にパラメータBを調整しながら変動値を入力

変動値を入力し、そして実行してみる。

今回はB=0.8にしてみて、エクセルで行列を計算して見ました。

結果

しっかりと最低エネルギー状態に$x_1=1,x_2=1,x_5=1$その他は$x_i=-1$を得ることができました。答えは、1,2,5の間にクリーク数3のクリークがあるとのことです。

つぎに自然数分割問題 / Number Partitioning

ある自然数の集合を２つのグループに分割し、それぞれのグループ内の自然数の和が同じになるような分割方法を探します。下記のハミルトニアンでは、N個の自然数の$i$番目を$n_i$として、グループAに属する時には$s_i=-1$、グループBに属する時には$s_i=1$と分類することで、２つのグループ内のそれぞれの和が等しい時に最小値問題で$H=0$となります。

$
H = (\sum_{i=1}^N n_i s_i)^2
$

（例題）$n_i=[1,1,1,1]$を２つのグループに分割する。

まず、上記問題は４つの自然数を分割しますので、４量子ビット$x_i = \\{x_0,x_1,x_2,x_3\\}$を用意します。

前述のハミルトニアンと呼ばれるコスト関数に実際に値を代入します。そして式展開します。

$
\begin{eqnarray*}
H&=&(1*x_0+1*x_1+1*x_2+1*x_3)^2\\
&=&(x_0+x_1+x_2+x_3)^2\\
&=&x_0^2+x_1^2+x_2^2+x_3^2+2x_0x_1+2x_0x_2+2x_0x_3+2x_1x_2+2x_1x_3+2x_2x_3\\
\end{eqnarray*}
$

次に取りうる値が-1か1なので、$x_i^2 = 1$のルールから、

$
\begin{eqnarray*}
H&=&1+1+1+1+2x_0x_2+2x_0x_3+2x_1x_2+2x_1x_3+2x_2x_3\\
&=&2x_0x_2+2x_0x_3+2x_1x_2+2x_1x_3+2x_2x_3+4\\
\end{eqnarray*}
$

となります。ここまできたらほぼ解けたようなようなものですが、この式を見やすく行列の形にします。今回は４量子ビットを使用していますので、縦横4量子ビットずつの行列を用意します。

$
\begin{array}
-&x_0&x_1&x_2&x_3\\
x_0& 0 & 2 & 2 & 2\\
x_1& & 0 & 2 & 2 \\
x_2& & & 0 & 2\\
x_3& & & & 0
\end{array}
$

行列には、$x_0とx_1$の係数は2なので、2をいれるなど非対角項に量子ビット間の関係性を示す相互作用項と呼ばれる値を展開した数式の係数を見ながら入れていきます。今回は$x_0$などの1次の項がないので非対角項のみが埋まります。

量子コンピュータに投げる

ここまでできれば、あとは各値を量子コンピュータに投げます。
値の設定と投入は簡単です。
RESTのAPIが用意されていますので、上記の値を設定してRESTのAPIでD-Wave社のエンドポイントに
tokenと一緒に投げます。

マシンへの投入の仕方は各社のマシンによって違いますが、D-Waveへ投入するには実はいくつかここからさらに工夫が必要です。

投げられる値のRange

上記のmatrixは0と2の値で構成されていますが、D-WaveのマシンはJij（相互作用項）に-1から1の間の値を設定する必要があります。この場合、値がおさまらないときには全体を割り算し、値が収まるようにします。上記全体を1/4して下記の行列を得てそれを投げるようにします。

$
\begin{array}
-&x_0&x_1&x_2&x_3\\
x_0& 0 & 0.5 & 0.5 & 0.5\\
x_1& & 0 & 0.5 & 0.5 \\
x_2& & & 0 & 0.5\\
x_3& & & & 0
\end{array}
$

キメラグラフへの対応

実はこれだけではD-Waveへは値は投げられません。D-Waveのマシンはキメラグラフと呼ばれる接続方法を採用しています。上記の行列は完全結合と呼ばれるグラフの形がなければ実装できません。完全結合と上記の行列の値の対応は下記の通りです。

この完全グラフをD-Waveのキメラグラフに対応させる必要性があります。対応させるには、量子ビットのコピーというテクニックを活用します。量子ビットをコピーするのは簡単で、-1を量子ビット間に設定することによってコピーができます。そうなると、左が完全結合、右側がD-Waveのキメラグラフと呼ばれる結合方法に対応した結合です。これをマシンに投げます。全部で６量子ビット使用します。

実際に投げてみると

よく質問がありますが、計算時間はネットワークの時間を除いてどんな問題でも20microsec固定です。投げてすぐに答えが戻って来ました。-1が青、+1が赤で、コピーした量子ビットを含めて答えが出せています。他にも答えがありますので、複数回計算すると確率的にいろんな答えが戻って来ます。

こちらをみると、$x_0=-1,x_1=+1,x_2=-1,x_3=+1$となり、$x_0とx_2$が同じグループ、$x_1とx_3$が同じグループに分割できました。

以上です。

Tweet

Recommended