Quantum circuit for addition
Introduction
In this post we will be implementing a quantum adder circuit using Qelvin. The circuit is presented in this paper written by L. Ruiz-Perez and J. C. Garcia-Escartin and it takes advantage of the Quantum Fourier Transform (QFT).
Theory
Quantum Fourier Transform
In a n qubit system, the Quantum Fourier Transform acting on an orthonormal basis state |j⟩, n=1,2,...,n can be expressed as
j⟩↦1√2n2n−1∑k=0ei2πkj2n|k⟩,and the corresponding inverse QFT takes form
k⟩↦1√2n2n−1∑j=0e−i2πkj2n|j⟩.QFT adder
Consider integers 0≤a,b≤2n−1 represented by n qubit states |a⟩ and |b⟩ respectively. The total number of qubits in the adder circuit totals to 2n+1, n qubits for each state representing a integer and one additional qubit for the carry bit. Thus the whole register the circuit operates on is
a1a2...an⟩|0⟩|b1b2...bn⟩,where a1a2...an=a1⋅20+a2⋅21+...+an⋅2n and b1b2...bn=b1⋅20+b2⋅21+...+bn⋅2n are the binary representations of a and b. Not that the register stores the integers in big-endian format.
The next part focuses on register |a1a2...an⟩|0⟩. We first apply a QFT to obtain state (no SWAP gates applied)
a1a2...an⟩|0⟩↦QFT1√2n+12n∑k=0ei2πka2n+1|k⟩=(|0⟩+e−i2πa2n+1|1⟩)⊗(|0⟩+e−i2πa2n|1⟩)⊗...⊗(|0⟩+e−i2πa21|1⟩)=|ϕn+1(a)|ϕn(a)⟩...|ϕ1(a)⟩,where ϕk(a)=1√2(|0⟩+ei2πa2k|1⟩). Note that
ei2πa2k=ei2πa1⋅20+a2⋅21+...+an⋅2n−12k=ei2π(a1⋅2−k+a2⋅2−k+1+..+ak⋅20)=ei2π0.akak−1...a1,where 0.akak−1...a1 is the binary fraction. This implies that ϕk(a) contains the lower k binary digits of a. Next we define a controlled rotation gate
Rj=[100001000010000ei2π2j].For each |ϕk(a)⟩, 0<k<n we apply k controlled rotation gates where R1 is controlled by |bk⟩, R2 by |bk−1⟩ and so on. To state ϕn+1(a) we apply n controlled rotation gates such that R2 controlled by |bn⟩, R3 controlled by |bn−1⟩ and so on.
Let us examine how applying these gates affects |ϕk(a)⟩. Let Rbij be a rotation gate controlled by bi. We get
Rb1k...Rbk−12Rbk1|ϕk(a)⟩=Rb1k...Rbk−121√2(|0⟩+ei2π(0.akak−1...a1+bk⋅2−1)|1⟩)...=1√2(|0⟩+ei2π(0.akak−1...a1+bk⋅2−1+bk−1⋅2−2+...+b1⋅2−k)|1⟩)=1√2(|0⟩+ei2π(0.akak−1...a1+0.bkbk−1...b1)|1⟩)=ϕk(a+b).Now by applying the described procedure to every state in the QFT register we end up with state
ϕn+1(a+b)⟩|ϕn(a+b)⟩...ϕ1(a+b)⟩,and by applying the inverse QFT on the register we end up with state |a+b⟩.
Implementation
Say we want to add integers a=1=102 and b=3=112 (big-endian notation). We initialize a state |10⟩|0⟩|11⟩.
import numpy as np
from qelvin import QRegister, QCircuit
# number of qubits representing b
N_b = 2
# number of qubits representing a + one qubit representing the carry bit
N_fft = 3
N = N_b + N_fft
psi = QRegister(N, 0b10011) # |a|0|b|=|10|0|11
circ = QCircuit(psi)
Next we perform QFT on |a⟩|0⟩.
for j in range(N_b, N):
for k in range(N_b, j):
circ.cp(np.pi/float(2**(j-k)), j, k)
circ.h(j)
print(circ)
circ.run()
Below is the circuit produced by this snippet. H is the Hadamard gate and Rj is represented by P(2.0*pi/2**j).
q0-------------------------------------------------------------------------
q1-------------------------------------------------------------------------
--------- --------- ---------
| || | | |
q2---| H ||P(+1.571)|-----------|P(+0.785)|--------------------------
| || | | |
--------- --------- ---------
| --------- | ---------
| | | | | |
q3-------------------o-----| H |-----|-----|P(+1.571)|---------------
| | | | |
--------- | ---------
| | ---------
| | | |
q4-----------------------------------------o----------o-----| H |----
| |
---------
After this we apply the controlled rotation gates.
for j in range(0, N_b+1):
for k in range(0, N_b):
theta = 2.0*np.pi*2**(-(k+1+N_b-j+1-N_b))
circ.cp(theta, k, N_b+j)
print(circ)
circ.run()
Below is the circuit produced by this snippet.
q0--------o---------------------o---------------------o--------------------
| | |
| | |
| | |
| | |
q1--------|----------o----------|----------o----------|----------o---------
| | | | | |
| | | | | |
--------- --------- | | | |
| || | | | | |
q2---|P(+1.571)||P(+0.785)|-----|----------|----------|----------|---------
| || | | | | |
--------- --------- | | | |
--------- --------- | |
| || | | |
q3-------------------------|P(+3.142)||P(+1.571)|-----|----------|---------
| || | | |
--------- --------- | |
--------- ---------
| || |
q4-----------------------------------------------|P(+0.000)||P(+3.142)|----
| || |
--------- ---------
Finally we apply the inverse QFT on state |ϕ(a+b)⟩.
for j in reversed(range(N_b, N)):
circ.h(j)
for k in reversed(range(N_b, j)):
circ.cp(-np.pi/float(2**(j-k)), j, k)
print(circ)
circ.run()
Below is the circuit produced by this snippet.
q0-------------------------------------------------------------------------
q1-------------------------------------------------------------------------
--------- --------- ---------
| | | || |
q2-------------------------|P(-0.785)|-----------|P(-1.571)|| H |----
| | | || |
--------- --------- ---------
--------- | --------- |
| | | | | |
q3--------------|P(-1.571)|-----|-----| H |-----o--------------------
| | | | |
--------- | ---------
--------- | |
| | | |
q4---| H |-----o----------o------------------------------------------
| |
---------
Let us now print the final state.
psi_out = circ.state()
print("Final state:")
print(psi_out)
(real, imag) = psi_out[0b00111]
prob = real*real + imag*imag
print(f"Probability for state |a+b|b|=|001|11|: {prob}")
Printed state is presented below.
Final state:
[ 0.000+0.000*j 0.000+0.000*j 0.000+0.000*j -0.000+0.000*j 0.000+0.000*j
0.000+0.000*j 0.000+0.000*j 1.000-0.000*j 0.000+0.000*j 0.000+0.000*j
0.000+0.000*j -0.000+0.000*j 0.000+0.000*j 0.000+0.000*j 0.000+0.000*j
0.000+0.000*j 0.000+0.000*j 0.000+0.000*j 0.000+0.000*j -0.000+0.000*j
0.000+0.000*j 0.000+0.000*j 0.000+0.000*j 0.000+0.000*j 0.000+0.000*j
0.000+0.000*j 0.000+0.000*j -0.000+0.000*j 0.000+0.000*j 0.000+0.000*j
0.000+0.000*j 0.000+0.000*j ]
Probability for state |a+b|b|=|001|11|: 1.0000000000000004
And there we have it! We have succesfully computed the sum a+b=1+3=4=0012.