@yuichirominato 2019.02.04更新 270views

【剰余】あまりを求めるモジュロ演算を実装


はじめに

前回まで足し算と引き算ができました。これを利用してあまりを求める回路を作ります。

参考

こちらの論文が参考になります。有名みたいです。
Quantum Networks for Elementary Arithmetic Operations
V. Vedral, A. Barenco, A. Ekert
(Submitted on 16 Nov 1995)
https://arxiv.org/abs/quant-ph/9511018

回路をみる

https://arxiv.org/pdf/quant-ph/9511018.pdf

前回作った加算器と減算器を組み合わせることで簡単に作れそうです。早速やってみましょう。

https://blog.mdrft.com/post/2141

https://blog.mdrft.com/post/2290

前回からの変更点は出力を10進数に直す必要がないくらいだと思います。回路を改造してやってみましょう。前回の回路の出力は、|a,b>に対して|a,a+b>でした。今回は|a,b>を入れると、|a,a+b mod N>がでます。

実装手順

回路でどのようにa+b mod Nが実現されるのかはa+b<Nもしくはa+b>Nに依存しそうです。つまり、

a+b>Nなら0<a,b<Nより0<a+b<2Nよって0<a+b-N<Nよりa+b-N = (a+b) mod N

となり、

a+b<Nならa+b = (a+b) mod N

となるという場合分けを量子回路を使って無理やり行います。

余剰の量子ビットと加算器の最上位の量子ビットの値を使ってうまく場合分けをしています。a+b<Nの場合には余剰ビットを使わず余計な操作もありません。

簡単な例題

上記を理解するために簡単な小学校の算数をします。

3+5>7なら(3+5) mod 7 = 3+5-7 = 1で、

3+5<11なら(3+5) mod 11 = 3+5 = 8となります。

これを量子回路を使って実現しようというのが今回のモジュロ演算です。

Nを用意する

今回のモジュロ演算には、Nが必要です。aとbの回路の一番したにNを加えます。途中aをNと取り替えたりしていますので、0<a,b<Nなので、aやbの桁数はNに合わせた方が良さそうです。下記の一部回路を変更する必要ありそうでした。

今回は自然数Nを加えて、3つの10進数を2進数に直して、桁を揃えてモジュロ回路の順にビットを並べ替えるという変更が必要です。回路の参考として、

c0 --
a0 --
b0 --
c2 --
a2 --
b2 --
b4 --

n0 --
n2 --

t  --

n0 --
n2 --

上記のように一番下に追加して、元の回路に影響のないようにしてみます。また、オーバーフロー判定用の量子ビットtを用意し、今回はさらにそれに加えてNをもう1つ加えてNに対応したリセット回路を作れるように準備してみます。

#3つの10進数を2進数に直して、桁を揃えてモジュロ回路の順にビットを並べ替える。一番下に判定用のビットを1つ加える。
def digits2(a,b,n): 
     aa = tobinary(a)  
     bb = tobinary(b)  
     nn = tobinary(n)  
  
     nlen = len(nn)  
     aa = aa.zfill(nlen) 
     bb = bb.zfill(nlen) 
  
     str = '' 
     for i in range(nlen): 
         str += '0' + aa[nlen-i-1] + bb[nlen-i-1] 
     str += '0' 

     for i in range(nlen): 
         str += nn[nlen-i-1]  

     str += '0'

     for i in range(nlen): 
         str += nn[nlen-i-1] 

     return str

Nを導入し、桁をすべてNに揃えることで余計な計算が不要になりシンプルになりました。試してみます。

digits2(1,1,2)
'011000001001'

digits2(2,2,4)
'00001100000010001'

digits2(1,2,4)
'0100010000001'

これで準備ができました。

回路の最初の方を実装

全体のフローを整理し直してみます。

1、a,b,Nの入力に対して入力値を並べる仕組み。最後に補助ビットを1つ加える
2、aとbを足して出力をする回路を返す
3、swapを導入
4、Nからbを引いて出力する回路を返す
5、オーバーフローのビットと一番下の補助ビットをcxでつなぐ。事前にオーバーフローをxで反転してあとで戻しておく。
6、補助ビットの値によってNを0に初期化する回路を作る。Nは既知なのでオラクルで作るか、Nをはさんでccxする
7、Nをもどすかどうか
8、以下同様な感じ

あまり難しいところはありませんので丁寧に仕事をします。

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:] 

#3つの10進数を2進数に直して、桁を揃えてモジュロ回路の順にビットを並べ替える。一番下に判定用のビットを1つ加える。
def digits2(a,b,n): 
     aa = tobinary(a)  
     bb = tobinary(b)  
     nn = tobinary(n)  
  
     nlen = len(nn)  
     aa = aa.zfill(nlen) 
     bb = bb.zfill(nlen) 
  
     str = '' 
     for i in range(nlen): 
         str += '0' + aa[nlen-i-1] + bb[nlen-i-1] 
     str += '0' 

     for i in range(nlen): 
         str += nn[nlen-i-1]  

     str += '0'

     for i in range(nlen): 
         str += nn[nlen-i-1] 

     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

#足し算回路
def plus(a,b,n): 
     qubits = len(digits2(a,b,n))
     digi = len(tobinary(n))

     cir2 = Circuit(qubits)     
     for i in range(digi): 
         cir2 += carry(i*3) 

     cir3 = Circuit(qubits).cx[(digi-1)*3+1,(digi-1)*3+2] + sum((digi-1)*3)
  
     cir4 = Circuit(qubits) 
     for i in range(digi-1): 
         cir4 += carry_reverse((digi-i-2)*3) 
         cir4 += sum((digi-i-2)*3)
  
     cir_plus = cir2 + cir3 + cir4
     return cir_plus

#引き算回路
def minus(a,ab,n): 
     qubits = len(digits2(a,ab,n))
     digi = len(tobinary(n))

     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[(digi-1)*3+1,(digi-1)*3+2] 
 
     cir2 = Circuit(qubits)     
     for i in range(digi): 
         cir2 += carry_reverse((digi-1-i)*3) 
 
     cir_minus = cir4 + cir3 + cir2
     return cir_minus

#aとNを交換
def swap(n):
    digi = len(tobinary(n))
    cir = Circuit(5*digi+2)
    for i in range(digi):
        cir += Circuit(5*digi+2).cx[3*i+1,3*digi+1+i].cx[3*digi+1+i,3*i+1].cx[3*i+1,3*digi+1+i]
    return cir

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

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

基本パーツが揃ったので少しずつメインの回路を。

def adder_mod(a,b,n):
    result =(tox(digits2(a,b,n)) + plus(a,b,n) + swap(n)).m[:].run(shots=1) 
    print(result)

確かめると、

adder_mod(2,4,4)                                                                                                
Counter({'00000101100100001': 1})

きちんと加算されてからswapされてました。

引き算回路

つぎはN-bのところですね。

これの一番最後です。

def adder_mod(a,b,n):
    result =(tox(digits2(a,b,n)) + plus(a,b,n) + swap(n) + minus(a,b,n)).m[:].run(shots=1) 
    print(result)

この段階で試してみますと、、、

adder_mod(2,4,4)                                                                                                
Counter({'00000101010100001': 1})

確かに引き算がされています。

overflow、リセット、加算、swap

次の部分です。まずはoverflowの検出。

def adder_mod(a,b,n):
    digi = len(tobinary(n))
    part1 = tox(digits2(a,b,n)) + plus(a,b,n) + swap(n) + minus(a,b,n)
    part2 = Circuit(5*digi+2).x[digi*3].cx[digi*3,digi*4+1].x[digi*3]
    
    part3 = Circuit(5*digi+2)
    for i in range(digi):
        part3 += Circuit(5*digi+2).ccx[4*digi+2+i,4*digi+1,3*i+1]   

    result = (part1+part2+part3+plus(a,b,n)+part3+swap(n)).m[:].run(shots=1)
    return getb(result.most_common()[0][0],n)

そのあとはちょっと体力切れでtを0に初期化は今度の機会で、、、リセットしなくても今回は問題ないです。

早速使ってみる!

#4+4-5=3
adder_mod(4,4,5)                                                                                                                                                                                 
3

#4+5-5=4
adder_mod(4,5,5)                                                                                                                                                                                 
4

#4+5-6=3
adder_mod(4,5,6)                                                                                                                                                                                 
3

#1+5-6=0
adder_mod(1,5,6)                                                                                                                                                                                 
0

#2+5-6=1
adder_mod(2,5,6)                                                                                                                                                                                 
1

#2+3=5
adder_mod(2,3,6)                                                                                                                                                                                 
5

#2+3=5
adder_mod(2,3,10)                                                                                                                                                                                
5

#3+6
adder_mod(3,6,10)                                                                                                                                                                                
9

大丈夫そうです。以上です!次回はもっと進めてみます。