@yuichirominato 2018.07.24更新 43views

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

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

はじめに

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

イジングモデルについて

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

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

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

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

クリーク問題は、グラフ理論において、グラフ中のクリーク(任意の二頂点間に枝があるような頂点集合)を見つける問題。下記はグラフ中にKのクリークが存在するかどうかをみつけるハミルトニアン。1項目は頂点数をKに制約する条件。2項目の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]
$

(例題)下記のように6つのノードのネットワーク構造からクリーク数3を探します。

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

自然数分割問題は置く量子ビットを{-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*}
$

ここで、式を見やすくするために、6量子ビットの関係性を表すQUBOmatrixをつくります。縦横それぞれ6量子ビットの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は6量子ビットの完全結合をベースに作られているので、
それをD-Waveのキメライジングモデルに落とし込む必要性がああります。

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

キメラグラフへの落とし込み(22量子ビット)

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

コピーを作って確認する


上記太線部分だけを入力して見て(相互作用項-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

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

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

(例題)$n_i=[1,1,1,1]$を2つのグループに分割する。

まず、上記問題は4つの自然数を分割しますので、4量子ビット$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量子ビットを使用していますので、縦横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のキメラグラフと呼ばれる結合方法に対応した結合です。これをマシンに投げます。全部で6量子ビット使用します。

実際に投げてみると

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

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

以上です。

あわせて読みたい

SERVICE

汎用量子コンピュータ向けアプリケーション開発SDK

詳しく見る Githubで入手する(無料)

汎用量子コンピュータ向け高速シミュレータ

詳しく見る

量子コンピュータ向けクラウドサービス(準備中)

詳しく見る

イジングマシン向けアプリケーション開発SDK

詳しく見る Githubで入手する(無料)

COMMUNITY

量子コンピュータのことを学びたい、仕事としたいなどの情報交換の場を設け、コミュニティの形成を進めています。オフラインの勉強会と、オンラインのチャットコミュニティの2種類あります。オフラインのConnpassは1400名、オンラインのSlackは880名を超える参加があります。どちらも無料ですのでお気軽にご参加ください。

CONNPASS SLACK

CONTACT

弊社あての連絡はinfo@mdrft.comより用件を明記の上、メールで連絡を頂けますと幸いです。

ブログトップに戻る

Recent Posts