量子アニーリングで全加算器を作り、加算を行う

ふと思いました。
量子ゲートではよく足し算を計算することをデモすることがあるのですが、
量子アニーリングでは足し算を計算させることをちゃんと説明しているのは少ないなと。
なら、作ってみようと思いました。

はじめに

足し算を行うために必要なのは、全加算器をひたすら繋げていくことだけです。
量子アニーリングでどのように組めばいいのかを考えます。
加算器については、説明してくれている人がいるので、そちらに任せます。

量子アニーリング全加算器

普通の回路同様、1,0のビット単位で計算を考えます。
単純にand, xorを実装することはできないので、以下のように考えます。
$a_i$：$a$の$i$桁の値
$b_i$：$b$の$i$桁の値
$c_i$：$c$の$i$桁の値
$s_i$：$i$桁の繰り上げ

 a_i + b_i + s_{i-1} = c_i + 2s_i

この時に

s_{-1} = 0\\
\sum_i\{(a_i + b_i + s_{i-1} - c_i - 2s_i)^2\} = 0

が成り立つようにすれば良い。

これを展開すると

a_i + b_i + s_{i-1} + c_i + 4s_i \\
+ 2a_ib_i + 2a_is_{i-1} +2b_is_{i-1} +4c_is_i\\
- 2a_ic_i - 4a_is_i 
- 2b_ic_i - 4b_is_i 
- 2s_{i-1}c_i - 4s_{i-1}s_i \\
 = 0

となる。
これをpythonで書くと

dict_qubo[(f"A{i}", f"A{i}")] = 0.2
dict_qubo[(f"B{i}", f"B{i}")] = 0.2
dict_qubo[(f"s{i+1}", f"s{i+1}")] = 0.8
dict_qubo[(f"R{i}", f"R{i}")] = 0.2
dict_qubo[(f"A{i}", f"B{i}")] = 0.4
dict_qubo[(f"A{i}", f"R{i}")] = -0.4
dict_qubo[(f"B{i}", f"R{i}")] = -0.4
dict_qubo[(f"A{i}", f"s{i+1}")] = -0.8
dict_qubo[(f"B{i}", f"s{i+1}")] = -0.8
dict_qubo[(f"R{i}", f"s{i+1}")] = 0.8
if i != 0:
    dict_qubo[(f"s{i}", f"s{i}")] += 0.2
    dict_qubo[(f"A{i}", f"s{i}")] = 0.4
    dict_qubo[(f"B{i}", f"s{i}")] = 0.4
    dict_qubo[(f"R{i}", f"s{i}")] = -0.4
    dict_qubo[(f"s{i}", f"s{i+1}")] = -0.8

となる。
ちなみに、桁数はD-Waveに乗る限り載せられます。
(Advantageであれば、$2^{500}$同士の計算も可能であることを確認しています。ただ、正しい結果が返ってくることとは別です。)

実装したコードは、下記に置いておきます。
https://github.com/yuzo63/dwave_adder

実行結果

最大値を$2^5$(n_digits=5)なら、

16 + 16 = 32
8 + 30 = 38
7 + 16 = 23
8 + 4 = 12
…
30 + 19 = 49
25 + 23 = 48
13 + 19 = 32
正しい結果　　： 49 / 100
正しいパターン： 48

最大値を$2^{50}$(n_digits=50)にしたとき、

166594504156925 + 700719128793454 = 867313632950379
962493425599632 + 867630342215456 = 1830123767815088
正しい結果　　： 2 / 1000
正しいパターン： 2

何回か計算をすればわかると思いますが、同じ結果にはならず毎度違う結果になると思います。

わかること

今回、計算の際に、a,b,cの値を指定せずに計算を行っています。
つまりは　$0$~$2^n$と$0$~$2^n$のどれかが確率的に計算されることになります。
これがよく量子コンピュータは並列で計算されているといわれる所以です。
(実際は計算行った際に観測しているので結果1つしか返ってこないんですけどね。。。)
特定の足し算や特定の解を持つ足し算の組み合わせを知りたい場合は、a,b,cをそれぞれ固定する必要がありますが、それはまた今後。

参考

実装したコード
https://github.com/yuzo63/dwave_adder

先駆者たち
https://qiita.com/abenben/items/1ccc51cd5d9ba18b30c1
https://qiita.com/YuichiroMinato/items/e5ed269c0a18d19d8390
https://qiita.com/navitime_tech/items/a9ec5784901c7f8bfb57
https://docs.dwavesys.com/docs/latest/c_handbook_8.html