@yuichirominato 2019.02.09更新 61views

[shor] Decimal number of adder mod circuit on blueqat


Introduction

We implemented the basic adder circuit of decimal number before. Now we try on the adder mod.

Reference

It looks very famous paper.

Quantum Networks for Elementary Arithmetic Operations
V. Vedral, A. Barenco, A. Ekert
(Submitted on 16 Nov 1995)
https://arxiv.org/abs/quant-ph/9511018

Looking at the circuit

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

It looks not difficult. Let’s just implement.

Now we want |a,b> to |a,a+b mod N>

Steps

The result of the calculation depends on the size of a+b.

if a+b>N

0<a,b<N then 0<a+b<2N then 0<a+b-N<N

a+b-N = (a+b) mod N

if a+b<N

a+b = (a+b) mod N

by using this rule we can easily implement the circuit.

(sorry we have some japanese comment in the image…)

We need some extra bits.

Example

For understanding we think about very basic example.

if 3+5>7

(3+5) mod 7 = 3+5-7 = 1

if 3+5<11

(3+5) mod 11 = 3+5 = 8

We want to realize this calculation using quantum circuits and this is adder mod.

Prepare N

Now we need array of bits to realize the adder mod circuit.

We have c,a,b for basic adder modules. and n for N natural number. t is just one qubit for detecting the overflow of the subtractor. and again I just add another N for simplify the circuit.

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

n0 --
n2 --

t  --

n0 --
n2 --
#Convert 3 input of a,b,N to binary number. Arrange the number of qubits to the biggest number N among a,b,N

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
digits2(1,1,2)
'011000001001'

digits2(2,2,4)
'00001100000010001'

digits2(1,2,4)
'0100010000001'

We just finished preparation.

The beginning part

Now we try to check the steps.

  1. Make an array of bits using a,b,N and add additinal ancilla bit finally.
  2. a+b
  3. swap
  4. N-b
  5. detect the overflow and connect the last bit with cx gate.
  6. Reset N to 0 by using |t> qubit.
  7. Restore N
  8. etc…

It looks easy to implement.

from blueqat import Circuit

#carry circuit
def carry(a):
    return Circuit().ccx[a+1,a+2,a+3].cx[a+1,a+2].ccx[a,a+2,a+3]

#reverse carry circuit
def carry_reverse(a):
    return Circuit().ccx[a,a+2,a+3].cx[a+1,a+2].ccx[a+1,a+2,a+3]

#sum of bits
def sum(a):
    return Circuit().cx[a+1,a+2].cx[a,a+2] 

#reverse sum of bits
def sum_reverse(a):
    return Circuit().cx[a,a+2].cx[a+1,a+2]

#decimal to binary
def tobinary(A):
    return bin(A)[2:] 

#arrange length of binary bits to N
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

#Convert input of binary to X gate operation
def tox(a): 
     cir = Circuit(len(a)) 
     for i in range(len(a)): 
         if a[i] == "1": 
             cir += Circuit().x[i] 
     return cir

#adder
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

#subtractor
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

#swap a and 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

#binary to decimal
def todecimal(A):
    return int(str(A),2) 

#get only the result from the array of bits
def getb(result,n): 
     str = ""
     digi = len(tobinary(n)) 
     for i in range(digi): 
         str += result[3*(digi-i)-1]
     return todecimal(str)

We finished checking the basic parts of the circuits.

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

Subtractor

We realize 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)

Let’s just try…

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

It works.

overflow、reset、adder、swap

First detection of overflow bit

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)

Now we didn’t reset the bit for overflow but it not affect to the result.

Let’s try to use!

#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

It works!

Recommend


CONTACT

info@mdrft.com

Back To Top

量子コンピュータ一般

量子ゲートアルゴリズム

量子アニーリング一般

量子アニーリングアルゴリズム

BlueqatSDKの使い方