@yuichirominato 2018.06.20更新

D-Waveで1+1と1+0と0+1と0+0を一緒に計算してみた結果、、、

イジング 四則演算 量子アニーリング

はじめに

イジングモデルを活用した問題では、様々な問題を解くことができます。そのうちの1つに四則演算も無理やり解くことができます。それは問題を最小値問題に落とし込み解くのですが、無駄が多い分面白いテクニックも使うことができます。1+1,1+0,0+1,0+0を同じ式で同時に計算しながら任意の問題の答えを出すことができます。今回はD-Waveの実機で試してみたいと思います。

引用元:https://www.dwavesys.com/resources/media-resources

引用元:https://www.dwavesys.com/resources/media-resources

詳細はカナダのホームページを参照してくださいませ。
https://www.dwavesys.com/

日本語サイトもあります。
http://dwavejapan.com/

具体的に何をするのか

普通は$1+1=$とか$1+0=$とかを別々に計算しますが、D-Waveで1度の立式で全ての場合の数が出るようにプログラミングして計算結果を取り出してみます。

仕組み

今回求めたいのは簡単にいうと$a+b=c$となるような$a,b,c$を全部求めたいということです。

$a=q_0,b=q_1,c=q_2+2q_3$と二進数表記することで、これを実現できます。イジングモデルでは問題を最小値問題に置き換えることで計算ができます。今回は足し算を最小値問題に置き換えて、

$
H = (a+b-c)^2
$

を計算し、上記の式が$0$となれば答えが出せます。まずは量子ビットを代入します。

$
H = (q_0+q_1-q_2-2q_3)^2=q_0^2+2q_0q_1-2q_0q_2-4q_0q_3+q_1^2-2q_1q_2-4q_1q_3+q_2^2 +4q_2q_3+4q_3^2
$

そして、バイナリのルール$q_i^2 = q_i$より、

$
H = 2q_0q_1 – 2q_0q_2 – 4q_0q_3 + q_0 – 2q_1q_2 – 4q_1q_3 + q_1 + 4q_2q_3 + q_2 + 4q_3
$

QUBOmatrixへ

これをmatrixに直します。4量子ビット使っているので、matrixは4*4です。

$$
\begin{array}
– & q_0 & q_1 & q_2 & q_3 \\
q_0 & 1 & 2 & -2 & -4 \\
q_1 & & 1 & -2 & -4 \\
q_2 & & & 1 & 4 \\
q_3 & & & & 4 \\
\end{array}
$$

イジングmatrixへ

通常はミドルウェア自動変換されます。

$$
\begin{array}
– & q_0 & q_1 & q_2 & q_3 \\
q_0 & -0.5 & 0.5 & -0.5 & -1 \\
q_1 & & -0.5 & -0.5 & -1 \\
q_2 & & & 0.5 & 1 \\
q_3 & & & & 1 \\
\end{array}
$$

この値をD-Waveにいれます。

4量子ビットの完全結合をD-Waveで表現する

今回は4量子ビットの全結合ですので、D-Waveのキメラグラフでは少し工夫して6量子ビット使います。(図が使い回しなのでxになってますが、、、)

計算した結果、、、

同じエネルギー配置の答えが4つでました。

成功か!と思いきや、、、答えを順番に開いていくと失敗の答えが出てきました。

これは図中の1と5はコピーをしているはずなのに、きちんとコピーされていませんでした。明らかに式がなりたちません。

なぜ失敗したのか

実は失敗の原因は明らかです。
1、4量子ビットの完全結合を実現するために6量子ビットを使用しており、その余分な2量子ビットを生成するためのコピー操作がうまくいっていません。
2、コピー操作は相互作用項と呼ばれる値を-1に設定しますが、足し算の演算で使われている相互作用項-1とおなじになってしまい、優先順位がついていない。

つまり、コピーを優先して、それから足し算が成り立つような微妙なバランスが必要になります。

再度挑戦

調整の仕方はざっくりですが、イジングmatrixを1/2してみます。

$$
\begin{array}
– & q_0 & q_1 & q_2 & q_3 \\
q_0 & -0.25 & 0.25 & -0.25 & -0.5 \\
q_1 & & -0.25 & -0.25 & -0.5 \\
q_2 & & & 0.25 & 0.5 \\
q_3 & & & & 0.5 \\
\end{array}
$$

これで再度挑戦してみます。

D-Waveにかけてみると、、、

大成功です!
1度に100回計算してみました。応答も瞬間で答えが戻ってきます。

4つの答えに分布が出ました。多少出やすい回答などもありますが。


速度も十分早いです。

答えを見てみます。

これは$0+0=0$ですね。

次、

$0+1=1$

次、

$1+0=1$

最後、

$1+1=2$

結果

最小値問題に落とし込むことで、$a+b=c$を解くことができました。
試行回数を増やすことで一度に計算結果を求めることができ、かつエネルギー状態を見ることで同じ式を解いていることがわかります。大成功でした。

Wildqatのコードに落とし込んで見る

最後にこちらを実際のpyhtonコードに落とし込んで、Wildqatで計算をしてみます。

https://github.com/mdrft/Wildqat

QUBOを入力して計算するだけ

上記で作ったハミルトニアンのQUBOmatrixを代入して計算するだけです。

import wildqat as wq                                                                                                                           
a = wq.opt()                                                                                                                                   
a.qubo = [[1,2,-2,-4],[0,1,-2,-4],[0,0,1,4],[0,0,0,4]]                                                                                         
a.sa()
                                                                                                                                     
2.3724892139434814
[0, 0, 0, 0]

上記のように実行をすると様々な答えが毎回異なったもので戻ってきます。それらを集計して答えとして選びます。上記で紹介しているのは[0,0,0,0]ですが、それ以外でも0101や0110など条件を満たす答えが計算するごとにでてきます。

あわせて読みたい