MULT20015 Elements of Quantum Computing Lecture 8
Subject outline
Lecture topics (by week)
1 – Introduction to quantum computing and maths basics 2 – Single qubit representations and logic operations
3 – Two qubit states and logic gates
4 – Multi-qubit states and quantum arithmetic
5 – Basic quantum algorithms
6 – Period finding, cryptography and quantum factoring
7 – Shor’s algorithm, post-quantum crypto, quantum key distribution 8 – Quantum search algorithms
9 – Grover search applications, optimisation problems
10 – Solving optimisation problems on quantum computers
11 – Applications in quantum machine learning 12 – Real quantum computer devices
Assignment schedule:
#1: Hand out in Week 2
#2: Hand out in Week 8
MULT20015 Elements of Quantum Computing Lecture 8
Week 4
Lecture 7
7.1 Binary notation with multiple qubits
7.2 Quantum Registers
7.3 Hadamard gates and equal superposition 7.4 Quantum “Parallelism”
7.5 Multiqubit measurement
7.6 Toffoli gate
Lecture 8
8.1 Classical digital logic and universality
8.2 Reversible logic
8.3 Arithmetic operations on a quantum computer 8.4 Universality in quantum computing
Practice class 4
Multi-qubit states and operations
MULT20015 Elements of Quantum Computing Lecture 8
Recap: Lecture 7
Hadamard gates: Create an equal superposition state at the start of the algorithm
|0i
Xn 1 2 1
Quantum Registers: Group qubits together
|xi |yi
| i=|xi⌦|yi⌦|zi
or
|zi | i=|xi|yi|zi
H⊗n
| i=2n/2
i=0
|ii
Multiqubit measurement: Apply the collapse principle, and renormalize the state.
| i=a|00i+b|01i+c|10i+d|11i
0 a|00i + b|01i | i= p|a|2+|b|2
|ai |ai |bi |bi
|c0 i
Toffoli gate: Doubly controlled NOT gate
|ci
MULT20015 Elements of Quantum Computing Lecture 8
8.1 Classical Logic and Universality
MULT20015 Lecture 8
MULT20015 Elements of Quantum Computing Lecture 8
AND Gate
An example of a classical digital logic operation is the AND gate:
A B
AB
A
B
AB
0
0
0
0
1
0
1
0
0
1
1
1
Inputs
Output
MULT20015 Elements of Quantum Computing Lecture 8
OR Gate
Another example is the OR gate:
A B
A OR B
A
B
A OR B
0
0
0
0
1
1
1
0
1
1
1
1
Inputs
Output
MULT20015 Elements of Quantum Computing Lecture 8
NOT Gate
Our final example of a digital logic gate:
A
NOT A
A
NOT A
0
1
1
0
Input
Output
MULT20015 Elements of Quantum Computing Lecture 8
Implementing Boolean Functions
Combine several logic gates to create more complex Boolean functions.
AND
OR
AND NOT
A set of (classical) gates is said to be functionally complete (or “universal”) if every possible truth table (ie. Boolean function) can be expressed using members of the set.
MULT20015 Elements of Quantum Computing Lecture 8
Universality in classical logic
A set of (classical) gates is said to be functionally complete (or “universal”) if every possible truth table (ie. Boolean function) can be expressed using members of the set.
For example, in classical logic: {AND, OR, NOT} is universal.
AND OR NOT
Every logical circuit can be made from combinations of these gates. In fact, the NAND gate alone is universal. However, we cannot implement these gates directly in a quantum computer.
MULT20015 Elements of Quantum Computing Lecture 8
8.2 Reversible Logic Gates
MULT20015 Lecture 8
MULT20015 Elements of Quantum Computing Lecture 8
Quantum Computers are Reversible
All the operations we have seen a quantum computer can perform are reversible.
Eg. CNOT, X, Hadamard.
The only operation we have seen which a quantum computer performs
which is not reversible is measurement.
So quantum computers cannot directly perform AND, OR gates.
MULT20015 Elements of Quantum Computing Lecture 8
Irreversible Functions
AND or OR are irreversible.
A B
AB
A
B
AB
0
0
0
0
1
0
1
0
0
1
1
1
Irreversible functions are cannot be implemented directly on a quantum computer.
We cannot determine the inputs from the output.
MULT20015 Elements of Quantum Computing Lecture 8
Reversible Logic
Classically, if we would like to calculate some Boolean function, f, we can construct a circuit out of AND, OR and NOT gates. However, AND and OR gates are not reversible, and so can’t be implemented in a quantum computer.
But by use of reversible circuits and additional bits/qubits, we can express everything in terms of reversible gates (such as Toffoli):
|1i |1i
|ai
NOT a
|1i |1i
|a ̄i
MULT20015 Elements of Quantum Computing Lecture 8
Reversible Logic and the Toffoli Gate
a AND b a XOR b (NOT a) OR (NOT b)
|ai |ai |bi |bi
|0i |a ^ bi
|1i |1i |ai |ai
|bi |a bi
|ai |ai |bi |bi
|1i |¬a _ ¬bi
a
b
a⋀b
0
0
0
0
1
0
1
0
0
1
1
1
a
b
a⊕b
0
0
0
0
1
1
1
0
1
1
1
0
a
b
¬a ⋁ ¬b
0
0
1
0
1
1
1
0
1
1
1
0
The Toffoli gate is universal and reversible. In principle every classical Boolean function can be written in terms of reversible gates (such as Toffoli) which can be implemented on a quantum computer.
MULT20015 Elements of Quantum Computing Lecture 8
Implementing irreversible functions
Another strategy which you often see to make an irreversible function reversible is simply to propagate the inputs:
Input
Repeated at output
|xi |xi
Uf
|0i |f (x)i
You will see this pattern in several of the quantum algorithms we will study.
MULT20015 Elements of Quantum Computing Lecture 8
Implementing irreversible functions
Another strategy which you often see to make an irreversible function reversible is simply to propagate the inputs:
Input
Repeated at output
|xi |xi
Uf
|yi |y f(x)i
Must deal with all possible inputs, not just 0.
Add (bit-by-bit modulo 2) input and calculated f(x)
You will see this pattern in several of the quantum algorithms we will study.
MULT20015 Elements of Quantum Computing Lecture 8
8.3 Arithmetic on a Quantum Computer
MULT20015 Lecture 8
MULT20015 Elements of Quantum Computing Lecture 8
One Bit Adder
We can, for example, implement a one bit adder using only reversible gates:
|ai
|bi
|0i |0i
|ai |bi
|carryi |a + bi
We will now explain this circuit and in the lab we will extend this to a two bit adder.
MULT20015 Elements of Quantum Computing Lecture 8
0+0=0
|0i |0i
|0i
|0i |0i |0i |0i
002=0
|0i
0+0=0
MULT20015 Elements of Quantum Computing Lecture 8
0+1=1
|0i |0i |1i |1i
|0i |0i
|0i
0+1=1
012 = 1
|1i
MULT20015 Elements of Quantum Computing Lecture 8
1+0=1
|1i |1i
|0i |0i |0i |0i
|0i
1+0=1
012 = 1
|1i
MULT20015 Elements of Quantum Computing Lecture 8
1+1=2
|1i |1i
|1i |1i
1+1=2
|0i |0i
|1i
102 = 2
|0i
MULT20015 Elements of Quantum Computing Lecture 8
1+1 Quantum Style
Here is what happens when we add together numbers in superposition:
|0i + |1i p2
“+”
|1i |0i + |1i
p2 |1i
|0i |0i
Let’s do the walkthrough…
MULT20015 Elements of Quantum Computing Lecture 8
One Qubit adder – example
|0i
| i= p2 ⌦|1i⌦|0i⌦|0i
|0i + |1i p2
|1i |0i
|0i + |1i
MULT20015 Elements of Quantum Computing Lecture 8
One Qubit adder – example
|0i + |1i
| i= p2 ⌦|1i⌦|0i⌦|0i
|0i + |1i p2
|1i |0i
|0i flip
no flip
|0100i + |1101i |i= p2
MULT20015 Elements of Quantum Computing Lecture 8
One Qubit adder – example
|0i + |1i p2
|1i |0i
|0i
| i= p2 ⌦|1i⌦|0i⌦|0i
|0101i + |1100i |i= p2
|0i + |1i
|i= p2
flip flip |0100i + |1101i
MULT20015 Elements of Quantum Computing Lecture 8
One Qubit adder – example
|0i + |1i p2
|0i |0i
|1i
|i= p2
⌦|1i⌦|0i⌦|0i
|i= p2
|0101i + |1110i flip
| i=
|0i + |1i p2
|0101i + |1100i | i= noflip p2
|0100i + |1101i
MULT20015 Elements of Quantum Computing Lecture 8
One Qubit adder – example
|0i + |1i p2
|1i
|i= p2
|0i |0i
Or, considering the last two registers as a two-qubit register (binary notation):
|0101i + |1110i
|0101i + |1110i |i= p2
|0i |1i |1i + |1i |1i |2i | i= p2
Note: this is an entangled state.
0+1=1
1+1=2
MULT20015 Elements of Quantum Computing Lecture 8
Implementing irreversible functions
We cannot compute irreversible functions directly (not unitary). One strategy which you often see to make an irreversible function reversible is simply to propagate the input to the output:
Propagate inputs to output
|xi |xi
Uf
|0i
|f (x)i
Calculated f(x)
MULT20015 Elements of Quantum Computing Lecture 8
One Bit Adder
The adder is an example. Given a + b, we can’t uniquely determine a and b So we used this trick:
|ai
|bi
|0i |0i
|ai |bi
Propagated inputs to output
|carryi
Evaluated function
|a + bi
MULT20015 Elements of Quantum Computing Lecture 8
8.4 Universality in Quantum Computing
MULT20015 Lecture 8
MULT20015 Elements of Quantum Computing Lecture 8
Universality
In classical computing the NAND gate is universal, i.e. every Boolean function can be implemented as a sequence of NAND (NOT AND) gates:
In quantum computing every quantum circuit can be expressed as a sequence of:
hZi |0i
|1i
CNOT Single Qubit Rotations
hY i
hXi
MULT20015 Elements of Quantum Computing Lecture 8
Universality
In classical computing the NAND gate is universal, i.e. every Boolean function can be implemented as a sequence of NAND (NOT AND) gates:
In quantum computing every quantum circuit can be expressed as a sequence of:
CNOT Hadamard
T Gate (pi/8)
H
T
MULT20015 Elements of Quantum Computing Lecture 8
Subject outline
Lecture topics (by week)
1 – Introduction to quantum computing and maths basics 2 – Single qubit representations and logic operations
3 – Two qubit states and logic gates
4/5 – Multi-qubit states and quantum arithmetic
5/6 – Classical complexity and simple quantum algorithms 6/7 – Cryptography and Shor’s quantum factoring algorithm
7 – Post quantum cryptography and quantum key distribution 8 – Quantum search algorithms
9 – Quantum algorithms for option pricing
10 – Optimisation problems on quantum computers
11 – Portfolio optimisation using quantum computers 12 – Quantum machine learning
Assignment schedule:
#1: Hand out in Week 2 #2: Hand out in Week 8