Simple Adder
Contents
Simple Adder¶
Adding 2 Qubits¶
If we want to add two single bits together, there are four possible outcomes. We require 2 bits for output. It we add \(1+1=2\) this cannot be stored in a single bit.
Input 1 |
Input 2 |
Result |
|---|---|---|
0 |
0 |
00 |
0 |
1 |
01 |
1 |
0 |
01 |
1 |
1 |
10 |
We break this two digit number up into two parts the result bit and the carry bit. The carry bit carries over to the next column.
A |
B |
Carry |
Result |
|---|---|---|---|
0 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
1 |
1 |
0 |
The result bit is just \(A \oplus B\). The carry bit is just \(A \wedge B\).
To make something we can extend to be a full adder, we need one more bit. We need to be able to carry in a bit from the previous computation to the next one.
A |
B |
Carry In |
Carry Out |
Result |
Summary |
|---|---|---|---|---|---|
0 |
0 |
0 |
0 |
0 |
\(0+0+0=0\) |
0 |
0 |
1 |
0 |
1 |
\(0+0+1=1\) |
0 |
1 |
0 |
0 |
1 |
\(0+1+0=1\) |
0 |
1 |
1 |
1 |
0 |
\(0+1+1=2\) |
1 |
0 |
0 |
0 |
1 |
\(1+0+0=1\) |
1 |
0 |
1 |
1 |
0 |
\(1+0+1=2\) |
1 |
1 |
0 |
1 |
0 |
\(1+1+0=2\) |
1 |
1 |
1 |
1 |
1 |
\(1+1+1=3\) |
We could try and translate this directly into logic gates and then implement those logic gates on the quantum circuit. This might not be the most efficient solution. The more gates and temporary qubits we use, the more complex our circuit becomes.
We need to think about the basic tools of the quantum circuit and how to take advantage of them. We have two very userful gates.
CCX(a,b,c) - if \(a \wedge b\) then apply X to \(c\)
CX(a,b) - if \(a\) then apply X to \(c\)
First, let us think about the carry bit. If \(A\) and \(B\) are both 1 then the sum is at least 2. If we ignore the carry in, we can just say CCX(a,b,carry out).
Let’s reorganize our truth table around the carry in bit.
A |
B |
Carry In |
Carry Out |
Result |
Summary |
|---|---|---|---|---|---|
0 |
0 |
0 |
0 |
0 |
\(0+0+0=0\) |
0 |
1 |
0 |
0 |
1 |
\(0+1+0=1\) |
1 |
0 |
0 |
0 |
1 |
\(1+0+0=1\) |
1 |
1 |
0 |
1 |
0 |
\(1+1+0=2\) |
0 |
0 |
1 |
0 |
1 |
\(0+0+1=1\) |
0 |
1 |
1 |
1 |
0 |
\(0+1+1=2\) |
1 |
0 |
1 |
1 |
0 |
\(1+0+1=2\) |
1 |
1 |
1 |
1 |
1 |
\(1+1+1=3\) |
The previous circuit will set the carry out correct for the first 4 rows. If the carry in is zero, we don’t need to do anything else. We can look more closely at the last four rows.
A |
B |
Answer So Far |
Carry In |
Carry Out |
|---|---|---|---|---|
0 |
0 |
0 |
1 |
0 |
0 |
1 |
0 |
1 |
1 |
1 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
1 |
1 |
Let’s think about when our carry out is wrong in this case. In the first and last row it is still correct. In the middle two rows, it is incorrect.
When do we need to change the answer so far? We need to change it when \(A\) or \(B\) is one, but not both. We can think of this as an if statement problem.
#This is what our first gate did
#Deal with the carry in
carryOut = A and B
temp = B
if A == 1:
temp = not B
#Now compare temp and the carry in
if temp and carryIn:
carryOut = not carryOut
We can look at the full truth table with these concepts added in. Notice that the result of the carry out is flipped in the correct situations.
A |
B |
\(A \wedge B\) |
temp |
Carry In |
Carry Out |
|---|---|---|---|---|---|
0 |
0 |
0 |
0 |
0 |
0 \((A \wedge B)\) |
0 |
1 |
0 |
1 |
0 |
0 \((A \wedge B)\) |
1 |
0 |
0 |
1 |
0 |
0 \((A \wedge B)\) |
1 |
1 |
1 |
0 |
0 |
1 \((A \wedge B)\) |
0 |
0 |
0 |
0 |
1 |
0 \((A \wedge B)\) |
0 |
1 |
0 |
1 |
1 |
1 If statement applies flip \(\neg(A \wedge B)\) |
1 |
0 |
0 |
1 |
1 |
1 If statement applies flip \(\neg(A \wedge B)\) |
1 |
1 |
1 |
0 |
1 |
1 \((A \wedge B)\) |
We can build these if statements using a CX and CCX gate.
We can add hadamard gates to the three inputs to generate the truth table. We also need to undo the change to \(q_1\) so that the output table is correct.
The results we get from the simulator are given below.
{'0100': 238, '1110': 275, '0000': 258,
'1101': 251, '0010': 252, '1111': 271,
'0001': 251, '1011': 252}
We can rewrite this in a truth table to verify.
\(q_0\) (A) |
\(q_1\) (B) |
\(q_2\) (Carry In) |
\(q_3\) (Carry Out) |
|---|---|---|---|
0 |
0 |
1 |
0 |
0 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
1 |
0 |
1 |
0 |
0 |
1 |
1 |
1 |
1 |
1 |
0 |
0 |
0 |
1 |
1 |
0 |
1 |
We have a working solution for the carry out. We next need to worry about the result bit. This is again sorted based on the carry in value.
A |
B |
Carry In |
Result |
|---|---|---|---|
0 |
0 |
0 |
0 |
0 |
1 |
0 |
1 |
1 |
0 |
0 |
1 |
1 |
1 |
0 |
0 |
0 |
0 |
1 |
1 |
0 |
1 |
1 |
0 |
1 |
0 |
1 |
0 |
1 |
1 |
1 |
1 |
Notice the the first four rows are \(A \oplus B\). Then the next four rows are \(\neg (A \oplus B)\).
We can think of this another way. When the carry is zero, it does not effect the result. If A is equal to zero, the result is B! If A is equal to 1, then the result is the opposite of B.
temp = b
if A==1:
temp = not b
We can then think about adding in the carry. If the value of this temp is 0 then the result is actually the carry in. If the value of the temp is 1, then the result is the opposite of the carry in. We even already computed this temp in the previous stage!
We can use the carry in wire as our output wire. We just need to add an extra CX gate. We add it after computation of the carry out, but before we undo the cx(0,1) application.
Looking at the output results, it may at first appear we have lost the information about what the original carry in was. We could resolve this my making two circuits and forcing the carry in to be 0 or 1. That is actually not required. We have enough information to determine the missing value of the carry from each result.
{'0100': 266, '0000': 249, '1010': 251,
'1001': 249, '0101': 226, '1111': 277,
'0110': 275, '1011': 255}
\(q_0\) (A) |
\(q_1\) (B) |
\(q_2\) (Result) |
\(q_3\) (Carry) |
Comments |
|---|---|---|---|---|
0 |
0 |
1 |
0 |
0+0 with Carry In 1 |
0 |
0 |
0 |
0 |
0+0 with Carry In 0 |
0 |
1 |
0 |
1 |
0+1 with Carry In 1 |
0 |
1 |
1 |
0 |
0+1 with Carry In 0 |
1 |
0 |
0 |
1 |
1+0 with Carry In 1 |
1 |
0 |
1 |
0 |
1+0 with Carry in 0 |
1 |
1 |
1 |
1 |
1+1 with Carry in 1 |
1 |
1 |
0 |
1 |
1+1 with Carry in 0 |
Making a Fuller Adder Circuit¶
Once we build a circuit like this, we can make it into a gate object in Python. This will allow us to reuse it. The following code makes the adder circuit into a gate.
#Make the Adder into a 4 Wire Gate
adder = QuantumRegister(4)
adder = QuantumCircuit(adder, name='adder')
adder.barrier(range(0,4))
adder.ccx(0,1,3)
adder.cx(0,1)
adder.ccx(1,2,3)
adder.cx(1,2)
adder.cx(0,1)
adder.barrier(range(0,4))
#Convert this circuit into a single gate
myAdder = adder.to_instruction()
The circuit is now displayed as a single large gate. We can append it to another circuit and match the wires.
qc = QuantumCircuit(4, 4)
#Wires:
#q0 - input 1
#q1 - input 2
#q2 - result
#q3 - carry out
qc.h(0)
qc.h(1)
qc.h(2)
qc.append(myAdder, [0, 1, 2, 3])
qc.barrier(range(0,4))
qc.measure(0,0)
qc.measure(1,1)
qc.measure(2,2)
qc.measure(3,3)
The display even shows the entire circuit as one gate.
You can ask qiskit to decompose the circuit into its component parts.
qc = qc.decompose()
This will display all the gates.
This makes it very easy to built a 2 bit adder. We can just use our gate.
We can test the adder by hard coding the inputs using the X gate or test all inputs using H gates.
The output of this experiment is given below.
{
'1011011': 135, '0010100': 119, '0000000': 136,
'0101000': 143, '0110110': 132, '1011110': 141,
'0111001': 124, '1001101': 116, '0010001': 122,
'0110011': 123, '0100010': 126, '0111100': 119,
'1000111': 128, '1001010': 129, '0100101': 121,
'1101111': 134
}
We can take each of these numbers apart to make sure they are correct.
Result |
Input 1 |
Input 2 |
Result |
|---|---|---|---|
1011011 |
11 |
10 |
101 |
0010100 |
00 |
01 |
001 |
0000000 |
00 |
00 |
000 |
0101000 |
00 |
10 |
010 |
0110110 |
10 |
01 |
011 |
1011110 |
10 |
11 |
101 |
0111001 |
01 |
10 |
011 |
1001101 |
01 |
11 |
100 |
0010001 |
01 |
00 |
001 |
0110011 |
11 |
00 |
011 |
0100010 |
10 |
00 |
010 |
0111100 |
00 |
11 |
011 |
1000111 |
11 |
01 |
100 |
1001010 |
10 |
10 |
100 |
0100101 |
01 |
01 |
010 |
1101111 |
11 |
11 |
110 |
The full source code is shown below.
from qiskit import *
from qiskit import BasicAer
#Make the Adder into a 4 Wire Circuit
adder = QuantumRegister(4)
adder = QuantumCircuit(adder, name='adder')
adder.barrier(range(0,4))
adder.ccx(0,1,3)
adder.cx(0,1)
adder.ccx(1,2,3)
adder.cx(1,2)
adder.cx(0,1)
adder.barrier(range(0,4))
#Convert this circuit into a single gate
myAdder = adder.to_instruction()
qc = QuantumCircuit(7, 7)
#Hard Code inputs to test
#00 + 00
#- Nothing to do
#01 + 00 (LSB last)
#qc.x(0)
#01 + 01
#qc.x(0)
#qc.x(2)
#11 + 01
#qc.x(0)
#qc.x(1)
#qc.x(2)
# or Hadamard the inputs
qc.h(0)
qc.h(1)
qc.h(2)
qc.h(3)
qc.barrier(range(0,7))
#Wires:
#q0 - input 1
#q1 - input 2
#q2 - result
#q3 - carry out
qc.append(myAdder, [0, 2, 4, 5])
qc.append(myAdder, [1, 3, 5, 6])
qc.barrier(range(0,7))
for x in range(0,7):
qc.measure(x,x)
#Run our simulation!
#Create Simulator
backend_sim = BasicAer.get_backend('qasm_simulator')
#Run 2,048 tests
job_sim = execute(qc,backend_sim,shots=2048)
#Get the results
result_sim = job_sim.result()
#Show the count of each outcome
counts = result_sim.get_counts()
print(counts)
qc.draw(output="mpl",filename="adder_07.png")
print(qc.draw(output="text"))
Conditional Examples¶
We are only taking advantage of the conditional properties of the CX and CCX gates in this circuit. We can try to understand the circuit using classical if statements.
The following function implements the same circuit using classical if statements. It would not have the same properties as a quantum state, but it does help explain the conditional logic.
def adder(a,b,carryIn,carryOut=False):
#Determine if a+b causes
#carry of 1
if a and b:
carryOut=not carryOut
#Is a XOR b true
#This means a+b=1
if a:
b = not b
#If a+b==1 and carryIn==1
#The carryOut is wrong
#1+1=10!
if b and carryIn:
carryOut = not carryOut
#if a+b!=1 then
#result = carryIn+0
#if a+b==1 then
#result = carryIn+1
if b:
carryIn = not carryIn
#Undo change to b
#to return in original state
if a:
b=not b
return (a,b,carryOut,carryIn)
We can run though the eight different possible inputs to this function to see how it works.
Case 0
A= False
B= False
Carry In= False
Result:
A= False
B= False
Carry Out= False
Result= False
(False, False, False, False)
0+0+0=00
Case 1
A= False
B= False
Carry In= True
Result:
A= False
B= False
Carry Out= False
Result= True
(False, False, False, True)
0+0+1=01
Case 2
A= False
B= True
Carry In= False
Result:
A= False
B= True
Carry Out= False
Result= True
(False, True, False, True)
0+1+0=01
Case 3
A= False
B= True
Carry In= True
Result:
A= False
B= True
Carry Out= True
Result= False
(False, True, True, False)
0+1+1=10
Case 4
A= True
B= False
Carry In= False
Result:
A= True
B= False
Carry Out= False
Result= True
(True, False, False, True)
1+0+0=01
Case 5
A= True
B= False
Carry In= True
Result:
A= True
B= False
Carry Out= True
Result= False
(True, False, True, False)
1+0+1=10
Case 6
A= True
B= True
Carry In= False
Result:
A= True
B= True
Carry Out= True
Result= False
(True, True, True, False)
1+1+0=10
Case 7
A= True
B= True
Carry In= True
Result:
A= True
B= True
Carry Out= True
Result= True
(True, True, True, True)
1+1+1=11
A full version of the Pythin script is shown below.
#Implementation of
#Quantum Ciruict using if
#statements to better
#understand CCX and CX
#in this application
def adder(a,b,carryIn,carryOut=False):
#Determine if a+b causes
#carry of 1
if a and b:
carryOut=not carryOut
#Is a XOR b true
#This means a+b=1
if a:
b = not b
#If a+b==1 and carryIn==1
#The carryOut is wrong
#1+1=10!
if b and carryIn:
carryOut = not carryOut
#if a+b!=1 then
#result = carryIn+0
#if a+b==1 then
#result = carryIn+1
if b:
carryIn = not carryIn
#Undo change to b
#to return in original state
if a:
b=not b
return (a,b,carryOut,carryIn)
#Generate all Possible Inputs
def options():
values=[]
for i in range(0,8):
temp=[False,False,False]
temp[2]=bool(i%2)
temp[1]=bool((i//2)%2)
temp[0]=bool((i//2//2)%2)
values.append(temp)
return values
#Prints as pretty binary
def binary(v,x):
a=int(v[0])
b=int(v[1])
c=int(v[2])
m=int(x[2])
n=int(x[3])
fmt="{:d}+{:d}+{:d}={:d}{:d}"
return fmt.format(a,b,c,m,n)
#Print all options as an example
if __name__=="__main__":
count=0
values = options()
for v in values:
print("Case",count)
print("A=",v[0])
print("B=",v[1])
print("Carry In=",v[2])
print("Result:")
x=adder(v[0],v[1],v[2])
print("A=",x[0])
print("B=",x[1])
print("Carry Out=",x[2])
print("Result=",x[3])
print(x)
print(binary(v,x))
print()
count+=1