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

Tweet

はじめに

前のブログで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:] 

#２つの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のアルゴリズムが実装できそうです。

Tweet

Recommended