$\mid a,b,0 \rangle = \mid a,b,a+b \rangle$ を実現します。 $a=a_0*2^0+a_1*2^1$ と $b=b_0*2^0+b_1*2^1$ と $c=c_0*2^0+c_1*2^1+c_2*2^2$ を用意します。 a+bをする際に答えのcは1量子ビット増やしておく必要があります。

a0 ----------------
a1 ----------------
b0 ----------------
b1 ----------------
c0 ----------------
c1 ----------------
c2 ----------------

こんな感じで回路をスタートさせます。まずは桁上がりを全て実装してみます。まずはa0,b0の桁上がりをc1に反映します。次にa1,b1,c1の桁上がりを3つのCCNOTを使って反映します。

a0 -*--------------
a1 -|-*-*----------
b0 -*-|-|----------
b1 -|-*-|-*--------
c0 -|-|-|-|--------
c1 -X-|-*-*--------
c2 ---X-X-X--------

そして最後に各くらいの数字を揃えます。

a0 -*-----------*------
a1 -|-*-*---*---|------
b0 -*-|-|---|---|-*----
b1 -|-*-|-*-|-*-|-|----
c0 -|-|-|-|-|-|-X-X----
c1 -X-|-*-*-X-X--------
c2 ---X-X-X------------

これでできました。あとはa0,a1,b0,b1に数字を入れていけば任意の加算ができます。任意の数字はXゲートで入れていきます。 0+0,0+1,1+0,1+1,0+2,2+0,1+2,2+1,2+2,2+3,3+2,3+3あたりまでできます。

トフォリゲートはccx[c,c,x]で、cx回路はcx[c,x]でかけます。また、サーキットを別々で作って足し合わせてrun()すると使えます。下記はデータ入力の部分と実行部分を分けて足し合わせてます。


from blueqat import Circuit 

#加算回路
a=Circuit().ccx[0,2,5].ccx[1,3,6].ccx[1,5,6].ccx[3,5,6].cx[1,5].cx[3,5].cx[0,4].cx[2,4].m[:]

#0+1
(Circuit().x[2] + a).run(shots=100)
#Counter({'0010100': 100})

#1+0
(Circuit().x[0] + a).run(shots=100)
#Counter({'1000100': 100})

#1+1
(Circuit().x[0,2]).run(shots=100)
#Counter({'1010010': 100})

#0+2
(Circuit().x[3]+a).run(shots=100)
#Counter({'0001010': 100})

#2+0
(Circuit().x[1]+a).run(shots=100)
#Counter({'0100010': 100})

#1+2
(Circuit().x[0,3]+a).run(shots=100)
#Counter({'1001110': 100})                                                                       

#2+1
(Circuit().x[1,2]+a).run(shots=100)
#Counter({'0110110': 100})

#2+2
(Circuit().x[1,3]+a).run(shots=100)
#Counter({'0101001': 100})
                                                                                
#2+3
(Circuit().x[1:4]+a).run(shots=100)
#Counter({'0111101': 100})

#3+2
(Circuit().x[0,1,3]+a).run(shots=100)
#Counter({'1101101': 100})

#3+3
(Circuit().x[0:4]+a).run(shots=100)
#Counter({'1111011': 100})

Counter({'1111011': 100})

減算器について

減算器は加算器を逆にすればいいようです。ただ、実際にどのように動作するのかわからないといけないので、確認してみます。先ほどの回路を全く逆にしてみます。

a0 ---*-----------*----
a1 ---|---*---*-*-|----
b0 -*-|---|---|-|-*----
b1 -|-|-*-|-*-|-*-|----
c0 -X-X-|-|-|-|-|-|----
c1 -----X-X-*-*-|-X----
c2 ---------X-X-X------

コードで書くと、CNOTが先に来て、CCNOT群が後に来ます。測定して結果を見てみると、ここで具体例で3-3をしてみます。


#減算回路
b =Circuit().cx[2,4].cx[0,4].cx[3,5].cx[1,5].ccx[3,5,6].ccx[1,5,6].ccx[1,3,6].ccx[0,2,5].m[:]

#3-3
(Circuit().x[0,1,4,5] + b).run(shots=100)
#Counter({'1100000': 100})

Counter({'1100000': 100})

c-aをしていますが、c-aの値がcに上書きされて出てきています。同様にa+b=cでc-bをしてみます。


#3-1
(Circuit().x[2,4,5] + b).run(shots=100)
#Counter({'0010010': 100})

Counter({'0010010': 100})

これもcが上書きされて答えの2がでました。最後にcに3をaとbに1をセットしてみます。


#3-1-1
(Circuit().x[0,2,4,5] + b).run(shots=100)
#Counter({'1010100': 100})

Counter({'1010100': 100})

cに3-1-1がセットされました。

基本的な加算と減算をみました。基本的には上記もしくは上記の改造をすることで、任意の桁数の二進数の数字の加算ができます。トフォリゲートを駆使して0の位から大きな位に計算を進め、再度大きな位から0の位に戻ってCNOTを活用することでできるようです。

コードの改善今回は大幅なコードの改善に成功しました。

以前は、トフォリを作るのにこんな感じでしたが、


from blueqat import Circuit 
import math  
tof1 = Circuit().h[5].cx[2,5].rz(-math.pi/4)[5].cx[0,5].rz(math.pi/4)[5].cx[2,5].rz(-math.pi/4)[5].cx[0,5].rz(-math.pi/4)[2].rz(math.pi/4)[5].cx[0,2].h[5].rz(math.pi/4)[0].rz(-math.pi/4)[2].cx[0,2]
tof2 = Circuit().h[6].cx[3,6].rz(-math.pi/4)[6].cx[1,6].rz(math.pi/4)[6].cx[3,6].rz(-math.pi/4)[6].cx[1,6].rz(-math.pi/4)[3].rz(math.pi/4)[6].cx[1,3].h[6].rz(math.pi/4)[1].rz(-math.pi/4)[3].cx[1,3]
tof3 = Circuit().h[6].cx[5,6].rz(-math.pi/4)[6].cx[1,6].rz(math.pi/4)[6].cx[5,6].rz(-math.pi/4)[6].cx[1,6].rz(-math.pi/4)[5].rz(math.pi/4)[6].cx[1,5].h[6].rz(math.pi/4)[1].rz(-math.pi/4)[5].cx[1,5]
tof4 = Circuit().h[6].cx[5,6].rz(-math.pi/4)[6].cx[3,6].rz(math.pi/4)[6].cx[5,6].rz(-math.pi/4)[6].cx[3,6].rz(-math.pi/4)[5].rz(math.pi/4)[6].cx[3,5].h[6].rz(math.pi/4)[3].rz(-math.pi/4)[5].cx[3,5]
after = Circuit().cx[1,5].cx[3,5].cx[0,4].cx[2,4]
measure = Circuit().m[:]
c01 = Circuit().x[2]                                                                                                                 
e = c01 + tof1 + tof2 + tof3 + tof4 + after + measure
e.run(shots=1)
#(0, 0, 1, 0, 1, 0, 0)

Counter({'0010100': 1})

新しいのは、


from blueqat import Circuit 
#加算回路
a=Circuit().ccx[0,2,5].ccx[1,3,6].ccx[1,5,6].ccx[3,5,6].cx[1,5].cx[3,5].cx[0,4].cx[2,4].m[:]
#0+1
(Circuit().x[2] + a).run(shots=100)
#Counter({'0010100': 100})

Counter({'0010100': 100})

これでいけました。

加算器

次は工夫をして、|a,b> => |a,a+b>というように量子ビットを節約して加算を行なってみます。作る回路はまずは1ビットでやってみます。

0+0=0,1+0=1,0+1=1,1+1=2

を実装してみます。

入力a,入力b,入力c=0,出力a,出力a+b,出力桁上がりcとして、この順番で、

となればokです。回路は、コントロールゲート*の記号でターゲットゲートがXとなってcxとccx（トフォリ）を表現して

a --*--*-- a 
b --*--X-- a+b
c --X----- c

blueqatコードとしては、ccxとcxをつかい、


#足し算回路
a = Circuit().ccx[0,1,2].cx[0,1].m[:]

#000の入力
(Circuit() + a).run(shots=100)
#Counter({'000': 100})
#出力も000

#100の入力
(Circuit().x[0] + a).run(shots=100)                                   
#Counter({'110': 100})
#出力は110

#010の入力
(Circuit().x[1] + a).run(shots=100)                                   
#Counter({'010': 100})
#出力は010

#110の入力
(Circuit().x[0,1] + a).run(shots=100)                                 
#Counter({'101': 100})

Counter({'101': 100})

できました。これが、上から、

0+0=0
1+0=1
0+1=1
1+1=2

となりました。

一般化

大きくしてみます。1995年の有名な論文がありますので参考にします。

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/abs/quant-ph/9511018

これが一般化された加算器です。図中のCarryとSumはこうなります。

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

a+bを実現しますが、 $a_0*2^0+a_1*2^1+a_2*2^2,…+b_0*2^0+b_1*2^1+b_2*2^2,… =$ のようにビットを使って計算をします。ビット数節約のために、bの値が上書きされて、a+bとなって出てきます。

1量子ビット同士の足し算

a+bを考えますが、aもbも1量子ビットの場合の一般化は、4量子ビットを使って下記のようになります。*はコントロールビットを表します。a0とb0に数字を入れると、b0が上書きされて、|c0,a0,b0,b1> ==> |c0,a0,a0+b0,b1>となってでてきます。b2は桁上がりです。

c0 --?--------*--------*-- c0
a0 --?--*--*--|--*--*--|-- a0
b0 --?--*--X--*--X--X--X-- a0+b0
b1 --?--X-----X----------- b1

コードで書くと、


from blueqat import Circuit

a = Circuit().ccx[1,2,3].cx[1,2].ccx[0,2,3].cx[1,2].cx[1,2].cx[0,2].m[:]
(Circuit() + a).run(shots=100)

#Counter({'0000': 100})

Counter({'0000': 100})

最初の?に何も入れないで実行すると、0000 -> 0000となります。これはあってます。0+0=0


(Circuit().x[1] + a).run(shots=100)
#Counter({'0110': 100})

Counter({'0110': 100})

これもあってます、0100 -> 0110となって答えが01となっています。


(Circuit().x[2] + a).run(shots=100)
#Counter({'0010': 100})

Counter({'0010': 100})

これもあっています。0010 -> 0010となり、0+1 = 01となります。


(Circuit().x[1,2] + a).run(shots=100)
#Counter({'0101': 100})

Counter({'0101': 100})

これもあっています。0110 -> 0101となり、1+1 = 10となり、桁上がりに成功しています。

2量子ビット同士の足し算

次に２量子ビット使ってみます。今度は７量子ビット使います。

c0 --?------*-------------*-------*- c0
a0 --?--*-*-|-------------|-*-*-*-|- a0
b0 --?--*-X-*-------------*-X-*-X-X- a0+b0
c1 --?--X---X-----*-----*-X---X----- c1
a1 --?--------*-*-|-*-*-|----------- a1
b1 --?--------*-X-*-X-X-X----------- a1+b1
b2 --?--------X---X----------------- b2

コードは、


a = Circuit().ccx[1,2,3].cx[1,2].ccx[0,2,3].ccx[4,5,6].cx[4,5].ccx[3,5,6].cx[4,5].cx[4,5].cx[3,5].ccx[0,2,3].cx[1,2].ccx[1,2,3].cx[1,2].cx[0,2].m[:]
(Circuit()+a).run(shots=100)
#Counter({'0000000': 100})

Counter({'0000000': 100})

00+00=000

次に、例えば、3+3 = ?をすると、


(Circuit().x[1,2,4,5]+a).run(shots=100)
#Counter({'0100111': 100})

Counter({'0100111': 100})

11+11 = 110これにより3+3=6

これは全加算器が一般化されているので、どんどん上に拡張していくことで大きな数を実装することができます。

ちなみに回路を逆に組むことで減算ができます。

減算

いまの２ビット回路を組んで、4-2をしてみます。これは先ほどの回路を逆にするだけです。

コードは、


a = Circuit().cx[0,2].cx[1,2].ccx[1,2,3].cx[1,2].ccx[0,2,3].cx[3,5].cx[4,5].cx[4,5].ccx[3,5,6].cx[4,5].ccx[4,5,6].ccx[0,2,3].cx[1,2].ccx[1,2,3].m[:]
(Circuit().x[4,5,6]+a).run(shots=100)
#Counter({'0000101': 100})

Counter({'0000101': 100})

こうなりました。a1=1となり、4-2=2となりました。b2の桁上がりは逆算できないようでしたのでこれは自分で0にしないといけないかもしれません。

Hゲート使うまずHゲートを使ってみます。足し算が重ね合わせを使うので答えがどれが出るかわかりません。


a = Circuit().ccx[1,2,3].cx[1,2].ccx[0,2,3].ccx[4,5,6].cx[4,5].ccx[3,5,6].cx[4,5].cx[4,5].cx[3,5].ccx[0,2,3].cx[1,2].ccx[1,2,3].cx[1,2].cx[0,2].m[:]
(Circuit().h[1,2,4,5]+a).run(shots=100)

Counter({'0110010': 8,

         '0100101': 8,

         '0000110': 4,

         '0010010': 5,

         '0110000': 7,

         '0100001': 5,

         '0010101': 10,

         '0100111': 9,

         '0100010': 6,

         '0110110': 6,

         '0010000': 2,

         '0010110': 4,

         '0000101': 8,

         '0110101': 8,

         '0000000': 5,

         '0000010': 5})

Counter({'0100101': 8,
         '0100111': 6,
         '0000101': 7,
         '0010110': 7,
         '0110010': 10,
         '0010000': 8,
         '0000000': 6,
         '0000010': 5,
         '0000110': 6,
         '0010010': 7,
         '0110101': 8,
         '0100001': 5,
         '0100010': 5,
         '0110110': 7,
         '0110000': 3,
         '0010101': 2})

このように重ね合わせを使ってたくさんの足し算をすることができました。答えは100回計算してばらつきを見ました。

10進数同士

10進数を計算してみます。加算と減算

carryなどつくる

最初に作ってしまいます。一番上の量子ビットの番号が決まればあとのも決まります。


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]

あとは使いたいときに足し合わせるだけです。


(carry(0)+carry(3)+Circuit().cx[4,5]+sum(3)+carry_reverse(0)+sum(0)).m[:].run(shots=100)
#Counter({'0000000': 100})

Counter({'0000000': 100})

これは１ビットの足し算回路。こんな感じで使います。


x = carry(0)+carry(3)+Circuit().cx[4,5]+sum(3)+carry_reverse(0)+sum(0)
(Circuit().x[1,4]+x).m[:].run(shots=100)                              
#Counter({'0110110': 100})

Counter({'0110110': 100})

こちらは1+2=3。入力はxゲートを適用します。

２進数を１０進数に直す使いにくいので直しちゃいます。


def tobinary(A):
    return bin(A)[2:] 

tobinary(10)                                                                                    
#'1010'

'1010'

足し算の桁数をそろえる桁数を取得して桁数を合わせます。


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

digits(2,2)                                                                                     
#'0000110'

'0000110'

桁数に合わせてXゲートを適用


def tox(a): 
     cir = Circuit(len(a)) 
     for i in range(len(a)): 
         if a[i] == "1": 
             cir += Circuit().x[i] 
     return cir

tox("101").m[:].run(shots=100)                                                                  
#Counter({'101': 100})

Counter({'101': 100})

きちんと反映されてます。これらを組み合わせて、任意の10進数を入れるとXゲートが作動してデータが量子回路に準備されます。


#5と2
tox(digits(5,2)).m[:].run(shots=100) 
#Counter({'0100010100': 100})

Counter({'0100010100': 100})


#70と90
tox(digits(70,90)).m[:].run(shots=1) 
#Counter({'0000110100010010000110': 1})

Counter({'0000110100010010000110': 1})

これで10進数をいれて2進数の回路が上記の一般化加算器回路の通りに並びました。

求めた2進数を10進数に戻す出た解は2進数ですので、10進数に直します。


def todecimal(A):
    return int(str(A),2) 

todecimal(10) 
#2

なおりました。次に量子回路のabcの並び順からbを順番に取り出していきます。


#0000101からbを選ぶには、
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)

一般化回路

早速adder（とreverse adder）とsumを組みあわせて先ほどの入力を処理します。まずは最初のadderを実装します。adderはビット数に合わせて調整します。


def plus(a,b): 
     qubits = len(digits(a,b)) 
     cir1 = tox(digits(a,b)) 
     digi = int((len(digits(a,b))-1)/3) 

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

     cir3 = Circuit(qubits).cx[-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)
  
     result = (cir1 + cir2 + cir3 + cir4).m[:].run(shots=1) 
     return getb(result.most_common()[0][0])

ついにできた！

計算してみましょう

計算してみます


plus(2,2)
#4


plus(13,15)
#28


plus(70,90)
#160

意外と計算時間かかりますが、全てゲートで加算器ができました！やってみてください。コード全体は下記です。


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] 

#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 plus(a,b): 
     qubits = len(digits(a,b)) 
     cir1 = tox(digits(a,b)) 
     digi = int((len(digits(a,b))-1)/3) 

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

     cir3 = Circuit(qubits).cx[-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)
  
     result = (cir1 + cir2 + cir3 + cir4).m[:].run(shots=1) 
     return getb(result.most_common()[0][0])

引き算

引き算は実は回路を逆から使うことで実現できますので、それをみてみたいと思います。


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

あまり回路

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

参考

こちらの論文が参考になります。有名みたいです。 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

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

前回からの変更点は出力を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をもう１つ加えてNに対応したリセット回路を作れるように準備してみます。


#3つの10進数を2進数に直して、桁を揃えてモジュロ回路の順にビットを並べ替える。一番下に判定用のビットを１つ加える。

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'

'011000001001'


digits2(2,2,4)
#'00001100000010001'

'00001100000010001'


digits2(1,2,4)
#'0100010000001'

'01000100000010001'

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

回路の最初の方を実装

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

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

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


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進数に直して、桁を揃えてモジュロ回路の順にビットを並べ替える。一番下に判定用のビットを１つ加える。
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})

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})

Counter({'00000101000100001': 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)


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


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


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


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


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


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


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

以上です！

量子ゲートで加算、減算、モジュロ演算

Yuichiro Minato

はじめに.css-1yssqf7{opacity:0.6;border:0;border-color:inherit;border-style:solid;border-bottom-width:1px;width:100%;margin-top:var(--chakra-space-2);}

２進数での桁上がり

量子ビットを使った数字の表現

参考

まず2量子ビット同士の加算