【減算】10進数の減算回路を加算の逆順で実現


はじめに

前のブログで10進数の足し算を実装しました。任意の10進数を入れると計算できます。量子ビットは増えるほどに指数で計算量が増えますので、現在の計算機で桁数の多い計算は大変です。引き算は実は回路を逆から使うことで実現できますので、それをみてみたいと思います。


参考

前の記事です。詳しく書きました。コードも載っています。

https://qiita.com/YuichiroMinato/items/217a2ad8edebe037e64e

私たちが必要としている回路は足し算回路を右から左にすると引き算ができます。

パーツは揃ってる並べ替えて検証するだけ

パーツは前回の足し算で作りましたのでそれを使います。ビットの合計の逆回路だけ加えました。

from blueqat import Circuit

#ビットのキャリー回路
def carry(a):
return Circuit().ccx[a+1,a+2,a+3].cx[a+1,a+2].ccx[a,a+2,a+3]

#ビットのキャリー回路の逆
def carry_reverse(a):
return Circuit().ccx[a,a+2,a+3].cx[a+1,a+2].ccx[a+1,a+2,a+3]

#ビットの合計
def sum(a):
return Circuit().cx[a+1,a+2].cx[a,a+2]

#ビットの合計の逆
def sum_reverse(a):
return Circuit().cx[a,a+2].cx[a+1,a+2]

#10進数を2進数に
def tobinary(A):
return bin(A)[2:]

#2つの10進数を2進数に直して、桁を揃えて加算回路の順にビットを並べ替える
def digits(a,b):
aa = tobinary(a)
bb = tobinary(b)
alen = len(aa)
blen = len(bb)
maxlen = max(alen,blen)
if alen>blen:
bb = bb.zfill(alen)
elif blen>alen:
aa = aa.zfill(blen)

str = ''
for i in range(maxlen):
str += '0' + aa[maxlen-i-1] + bb[maxlen-i-1]
str += '0'
return str

#ビット文字列をXゲートを使ったデータ入力回路に変換
def tox(a):
cir = Circuit(len(a))
for i in range(len(a)):
if a[i] == "1":
cir += Circuit().x[i]
return cir

#2進数を10進数に
def todecimal(A):
return int(str(A),2)

#減算回路から解だけを抜き出す
def getb(result):
str = result[-1]
digi = int((len(result)-1)/3)
for i in range(digi):
str += result[-2-i*3]
return todecimal(str)

今回作るのは、メインの引き算回路だけです。

早速回路を

def minus(a,ab): 

qubits = len(digits(a,ab))
cir1 = tox(digits(a,ab))
digi = int((len(digits(a,ab))-1)/3)

cir4 = Circuit(qubits)
for i in range(digi-1):
cir4 += sum_reverse(i*3)
cir4 += carry(i*3)

cir3 = sum_reverse((digi-1)*3) + Circuit(qubits).cx[-3,-2]

cir2 = Circuit(qubits)
for i in range(digi):
cir2 += carry_reverse((digi-1-i)*3)

result = (cir1 + cir4 + cir3 + cir2).m[:].run(shots=1)
return getb(result.most_common()[0][0])


早速計算

不思議な感じですがこれでできるそうです。第二引数から第一引数を引きます。

#8-2

minus(2,8)
6

#4-2
minus(2,4)
2

#16-2
minus(2,16)
14

#22-2
minus(2,22)
20

#50-2
minus(2,50)
48

#50-24
minus(24,50)
26


まとめ

意外と簡単にできました。だいぶコツをつかんだようです。このまま頑張ればshorのアルゴリズムが実装できそうです。