程序代写CS代考 algorithm MULT20015 Elements of Quantum Computing Lecture 7

MULT20015 Elements of Quantum Computing Lecture 7
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 7
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 7
Lecture 6 recap: two-qubit logic and entanglement
CNOT
Controlled-Z (CZ)
!|i|i|i|i !|i |i |i|i
Rule: the qubits states are swapped.
e.g. Bell-state can’t be written as a product
|00i + |11i
p2 6= (a |0i + b |1i) ⌦ (c |0i + d |1i)
Entanglement:
Rule: The target is flipped iff the control qubit is “1”.
a|00i + b|01i + c|10i + d|11i a00 +b01 +d10 +c11
SWAP
Rule: the phase of the target flipped iff the control qubit is “1”.
a|00i + b|01i + c|10i + d|11i
a 00 + b 01 + c 10 d 11
a|00i + b|01i + c|10i + d|11i a00 +c01 +b10 +d11
!|i|i|i|i
QUI: computes entanglement entropy (EE)

MULT20015 Elements of Quantum Computing Lecture 7
7.1 Binary notation with multiple qubits
MULT20015 Lecture 7

MULT20015 Elements of Quantum Computing
Lecture 7
Recall from Lecture 1: Multi qubits – state counting
1 qubit:
2 qubits:
3 qubits:
4 qubits:
|0ñ, |1ñ
|0ñ, |1ñ
|0ñ, |1ñ
Binary combinations
|0ñ, |1ñ
binary representation of decimals 0 to 1
|00ñ, |01ñ, |10ñ, |11ñ
binary representation of decimals 0 to 3
|000ñ, |001ñ, |010ñ, |011ñ |100ñ, |101ñ, |110ñ, |111ñ
binary representation of decimals 0 to 7
|0000ñ, |0001ñ, |0010ñ, |0011ñ |0100ñ, |0101ñ, |0110ñ, |0111ñ |1000ñ, |1001ñ, |1010ñ, |1011ñ |1100ñ, |1101ñ, |1110ñ, |1111ñ
binary representation of decimals 0 to 15
|0ñ, |1ñ
|0ñ, |1ñ
|0ñ, |1ñ
|0ñ, |1ñ
|0ñ, |1ñ
|0ñ, |1ñ
|0ñ, |1ñ

MULT20015 Elements of Quantum Computing Lecture 7
Binary Notation with n qubits
Quantum computers, like classical computers, store numbers in binary.
Left: All the states possible for three bit/qubits.
If there are n qubits, then the number of possible states is:
N = 2n Specifically the integers,
0 .. 2n 1
Binary
Decimal
000
0
001
1
010
2
011
3
100
4
101
5
110
6
111
7

MULT20015 Elements of Quantum Computing Lecture 7
Binary and Decimal Notation
Binary: Decimal:
In general we use two representations in the QUI (N = 2n):
| i = a0…00 |0…00i + a0…01 |0…01i + a0…10 |0…10i + … + a1…1 |1…1i
| i=a0|0i+a1|1i+a2|2i+…+aN1|N1i | i=Xa|i

a = |a|ei✓

MULT20015 Elements of Quantum Computing
Lecture 7
Memory needed on a classical computer
If we use 128 bits (16 B) per complex number, then we need:
Qubits
Dimension (2n)
Memory required
1
2
256 bits = 32 B
2
4
64 B
6
64
1 kB
10
1,024
16 kB
20
1,048,576
16 MB
30
1,073,741,824
16 GB
40
1,099,511,627,776
16 TB
50
1,125,899,906,842,624
16 PB
60
1,152,921,504,606,846,976
16 EB
Memory required to store the quantum state of different numbers of qubits grows exponentially.

MULT20015 Elements of Quantum Computing Lecture 7
7.2 Quantum Registers
MULT20015 Lecture 7

MULT20015 Elements of Quantum Computing Lecture 7
Quantum Registers
We will often need to consider several different qubits grouped together. A group of several qubits is known as a register.
|0i |0i
|0i |0i
Several qubits
|0i
Quantum register
…

MULT20015 Elements of Quantum Computing Lecture 7
Multiple registers
|xi
|yi
|zi
And of course you can have superpositions over these states as well. An example:
Asbefore,if | i=XXaij|ii|ji ij
then |aij|2 =1 i,j
| i = |xi⌦|yi⌦|zi or
| i = |xi|yi|zi
111
| i=2|1i|5i+2|1i|6i+p2|3i|8i

MULT20015 Elements of Quantum Computing Lecture 7
7.3 Hadamard gates and equal superposition
MULT20015 Lecture 7

MULT20015 Elements of Quantum Computing Lecture 7
One Hadamard Gate
|0i
As we’ve seen before, this produces an equal superposition:
H|i | i = H|0i
|0i + |1i = p2

MULT20015 Elements of Quantum Computing Lecture 7
Two Hadamard Gates
|0i
|i
|0i This produces:
H
| i = H⌦H|00i
✓|0i + |1i◆ ✓|0i + |1i◆
= p2 ⌦ p2
= =
|00i + |01i + |10i + |11i 2
|0i+|1i+|2i+|3i 2
We have used digital notation here
H

MULT20015 Elements of Quantum Computing Lecture 7
Three Hadamard Gates
|0i |0i |0i
H
|i
H
H
This produces:
| i = H⌦H⌦H |0i|0i|0i
=
= =
✓|0i + |1i◆ ✓|0i + |1i◆ ✓|0i + |1i◆ p2 ⌦ p2 ⌦ p2
|000i + |001i + |010i + |011i + |100i + |101i + |110i + |111i 2p2
|0i+|1i+|2i+|3i+|4i+|5i+|6i+|7i 2p2

MULT20015 Elements of Quantum Computing Lecture 7
Hadamard gates and decimal notation
n qubits
|0i
|0i |0i
shorthand notation
H⊗n
|0i+|1i |0i+|1i |0i+|1i |i= p2 ⌦ p2 …⌦ p2
 1 n
| i = p2 (|00…0i + … + |11…1i)
|0i |0i
i.e. even superposition over binary rep of integers: i = 0 to 2n – 1
H
H
H
H
Xn 1 2 1
| i=2n/2
|ii
Equal superposition of states
i=0
…

MULT20015 Elements of Quantum Computing Lecture 7
7.4 Quantum “Parallelism”
MULT20015 Lecture 7

MULT20015 Elements of Quantum Computing Lecture 7
Calculating some function, f
Imagine that we had written some routine/circuit to calculate some function, f.
|xi |xi
Uf
|0i |f (x)i
On a classical computer, we can only evaluate the function for a single input, x, at a time. What would happen if we input a superposition in a quantum computer?

MULT20015 Elements of Quantum Computing Lecture 7
Quantum Parallelism
An equal superposition of inputs
Xn 1 2 1
| i=2n/2
|xi
x=0
|0i |0i
Xn U 0 121
|xi⌦|f(x)i
H⊗n
f | i=2n/2
x=0
The function evaluates all the inputs in superposition with just one application of Uf .

MULT20015 Elements of Quantum Computing Lecture 7
Quantum Parallelism Example
Consider evaluating the function: f(x) = x2
x
f(x)
0
0
1
1
2
4
3
9
4
16
5
25
6
36
7
49
Xn 1 2 1
| i=2n/2
|xi
x=0
|0i
|0i |0i
Xn U 0 121
|xi⌦|f(x)i
H⊗n
f | i=2n/2
x=0
The output also is a superposition, evaluated for each input:
0 |0i|0i+|1i|1i+|2i|4i+|3i|9i+|4i|16i+|5i|25i+|6i|36i+|7i|49i | i= 2p2
“Quantum parallelism” – evaluated on entire superposition in one application of the function.

MULT20015 Elements of Quantum Computing Lecture 7
7.5 Multiqubit Measurement
MULT20015 Lecture 7

MULT20015 Elements of Quantum Computing Lecture 7
Recap: Two-qubit measurement
Measurement on a two-qubit state:
1) Apply collapse principle to the measured state 2) Renormalize the state probabilities
For example, consider the general two-qubit state:
| i=a|00i+b|01i+c|10i+d|11i
If the first qubit were measured to be “0”, keep only those states and renormalize to get the | new state:
If the first qubit were measured to be “1”, keep only those states and renormalize to get the
new state: |
0
a |00i + b |01i
i = i =
p|a|2 + |b|2 c |10i + d |11i
0
p|c|2 + |d|2
normalization

MULT20015 Elements of Quantum Computing Lecture 7
Multi-qubit measurement
Measurement on a multi-qubit state:
1) Apply collapse principle to the measured state – keep only the
amplitudes compatible with the measurement.
2) Renormalize the state probabilities, so the probabilities sum to 1.
For example, consider the state:
111
| i=2|1i|5i+2|1i|6i+p2|3i|8i
Imagine that we measured the first register. There are two possible outcomes: “1” and “3”. What are the probabilities?
Note: multiple qubits in each register |xi |yi
|xi |yi

MULT20015 Elements of Quantum Computing Lecture 7
Multi-qubit measurement
Probability of measuring “1”:
111
| i=2|1i|5i+2|1i|6i+p2|3i|8i
✓1◆2 ✓1◆2 P1 = 2 + 2
1 2
✓ 1 ◆2 P3 = p2
1 2
Probability of measuring “3”:
=
=

MULT20015 Elements of Quantum Computing Lecture 7
Multi-qubit measurement
111
| i=2|1i|5i+2|1i|6i+p2|3i|8i
If the measurement outcome “1” were measured, the (unnormalized) state compatible with this is:
12 | 1 i | 5 i + 12 | 1 i | 6 i After normalization, the state becomes:
|
0
12 |1i|5i+ 12 |1i|6i i = q12 + 12
22
|1i |5i + |1i |6i = p2
| 0i

MULT20015 Elements of Quantum Computing Lecture 7
Multi-qubit measurement
111
| i=2|1i|5i+2|1i|6i+p2|3i|8i
If the measurement outcome “3” were measured, the (unnormalized) state
compatible with this is:
1
p2 |3i |8i After normalization, the state becomes:
1 |3i |8i 0 p2
| i=r⇣1⌘2 p2
| 0i
= |3i |8i

MULT20015 Elements of Quantum Computing Lecture 7
7.6 The Toffoli Gate
MULT20015 Lecture 7

MULT20015 Elements of Quantum Computing Lecture 7
Toffoli gate
Toffoli gate plus NOT is universal for classical computation. It was used in the proof that classical computation can be made reversible!
Control qubit Control qubit
Target qubit
Rule: the target is flipped iff both the control qubits are in “1” state.
How states transform:
|000i ! |001i ! |010i ! |011i ! |100i ! |101i ! |110i ! |111i !
|000i |001i |010i |011i |100i |101i |111i |110i
a|000i + b|001i + c|010i + d|011i e |100i + f |101i + g |110i + h |111i
! a |000i + b |001i + c |010i + d |011i e |100i + f |101i + h |110i + g |111i

MULT20015 Elements of Quantum Computing Lecture 7
Toffoli Gate
Control-Control-NOT gate
|ai |ai |bi |bi
a
b
c
c’
0
0
0
0
0
0
1
1
0
1
0
0
0
1
1
1
1
0
0
0
1
0
1
1
1
1
0
1
1
1
1
0
|ci
|c0 i Toffoli gate

MULT20015 Elements of Quantum Computing Lecture 7
Multiply Controlled operations in QUI
You can add controls on single qubit gates in QUI.
Right click on a gate and select
“Add Control on 1”
Click on the qubit where you would like a control. Repeat for as many controls as you would like.

MULT20015 Elements of Quantum Computing Lecture 7
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 – Classical complexity and simple quantum algorithms 6 – 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

Related Posts