前のブログで10進数の足し算を実装しました。任意の10進数を入れると計算できます。量子ビットは増えるほどに指数で計算量が増えますので、現在の計算機で桁数の多い計算は大変です。引き算は実は回路を逆から使うことで実現できますので、それをみてみたいと思います。
前の記事です。詳しく書きました。コードも載っています。
https://blog.mdrft.com/post/2141
私たちが必要としている回路は下記のようなものですが、右から左にすると引き算ができます。
パーツは前回の足し算で作りましたのでそれを使います。ビットの合計の逆回路だけ加えました。
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のアルゴリズムが実装できそうです。
Tweetinfo@mdrft.com