MULT20015 Elements of Quantum Computing Lecture 15
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 15
Week 8
Lecture 15
15.1 Grover’s algorithm: Overview and intuition 15.2 The Oracle
15.3 Inversion about the mean
15.4 Example Quantum Search
Lecture 16
16.1 Grover’s algorithm Example 16.2 Probability of success
16.3 Geometric interpretation
Practice class 8
Grover’s algorithm using QUI
MULT20015 Elements of Quantum Computing Lecture 15
Recap: Post-Quantum Cryptography & QKD
Post-Quantum Cryptography Quantum Key Distribution
BB84 Protocol
MULT20015 Elements of Quantum Computing Lecture 15
15.1 Grover’s algorithm: Overview and intuition
MULT20015 Lecture 15
MULT20015 Elements of Quantum Computing Lecture 15
Grover’s Algorithm (1996)
• Unordered search, find marked item among many
• Classically, this requires N/2 queries to the oracle
• Quantum mechanically, requires only O(√N) queries.
Simple problem = search for one integer marked by the oracle. High level structure:
|0i |0i |0i |0i
Lov Grover
H
H
H
H
H
H
H
H
H
…
H
H
H
Inversion (2|0><0|-I)
Oracle
MULT20015 Elements of Quantum Computing Lecture 15
Unstructured search problems
Given a set of N elements 𝑋 = 𝑥!,𝑥",...,𝑥#$" and a Boolean function 𝑓: 𝑋 → {0,1},
find an element 𝑥 ∈ 𝑋 such that 𝑓(𝑥) = 1.
• Unstructured means that we cannot assume how 𝑥!, 𝑥", ... , 𝑥#$" are ordered.
• The function 𝑓 verifies the property that we are interested to find.
– Important: The function 𝑓 does not compute a solution, it only verifies if the given input satisfies the property of interest.
– The function 𝑓 can be thought as an “oracle” that verifies if an input is a solution.
MULT20015 Elements of Quantum Computing Lecture 15
Unstructured search problems
• Example: Alice (A) wants to find a coffee shop within 5 mins of walking distance.
3
4
Cafe 2 is 5.7 minutes away
7
2 5.7 4.5 6.2 5
0 5.8 A
5.2 6.2
71
6
6.4
• Set 𝑋 =
– Set 𝑋 is not ordered by travel time
0,1,2, ... , 7
• 𝑓(𝑥)=21,ifbme(x)≤5
denotes the search space
0, otherwise
– In general, the function 𝑓 does not need to know about the search space.
• Solution 𝑥=4 (Cafe 4 is the only one that is less than 5 minutes away)
• The function 𝑓 is like a blackbox (similar to Deutsch-Jozsa and Simon’s algorithms).
MULT20015 Elements of Quantum Computing Lecture 15
Grover’s algorithm: Intuition
Equal superposition Solution has higher probability
|0i |0i |0i |0i
H
H
H
H
Iteration 1
Iteration 2
...
Iteration k
Alice’s coffee problem
Basisvectors: 01234567 01234567 01234567 Intuition: Each iteration amplifies the amplitude of solution vectors.
Inversion about mean
Apply Oracle, flip the sign of soln.
Amplitude
Amplitude
Amplitude
MULT20015 Elements of Quantum Computing Lecture 15
Iteration j
Apply Oracle,
flip the sign of solution (mark the state)
Inversion about mean
|0i H |0i H |0i H |0i H
Grover’s algorithm: Intuition
......
Maps every amplitude Mean−𝛿 to Mean+𝛿
Mean
Iter 1
Alice’s coffee problem
Mean
01234567 01234567
Mean
Iter k
Intuition:
Flipping the sign of the amplitude of solution vector reduces the mean.
Inversion about the mean increases the amplitude of solution vector.
01234567
Amplitude
Amplitude
Amplitude
MULT20015 Elements of Quantum Computing Lecture 15
15.2 The Oracle
MULT20015 Lecture 15
MULT20015 Elements of Quantum Computing Lecture 15
The Oracle
The task of recognizing the correct solution goes to the “oracle”.
|xi
|yi |y f(x)i
𝑈𝑓
|xi
x
Designed to flip the last bit if the input, x, is a solution
The oracle is just a Boolean function (as seen in previous lectures)
Oracle identifies marked state
Binary function, or “oracle” Identifying a marked state, m
MULT20015 Elements of Quantum Computing Lecture 15
An example Oracle
𝑥
The oracle 𝑈𝑓 flips the target qubit if the input, x = 10 (i.e., 2 in decimal).
Oracle 𝑈𝑓
MULT20015 Elements of Quantum Computing Lecture 15
Oracle on 0 state
𝑥
0
Let’s see what happens when we apply to an equal superposition (in 𝑥 register):
𝑥0 =00+01+10+11 0 2
00 0 + 01 0 + 10 0 + 11 0 2
00 0 + 01 0 + 10 1 + 11 0 2
Identifies the solution state, but does not flip its sign (yet).
= 𝑈𝑓(𝑥0) =
MULT20015 Elements of Quantum Computing
Lecture 15
Oracle on equal superposition state
ActingXgateontargetqubit: X− =X 0 − 1 = 1 − 0 =−− 22
𝑥 − = 00 + 01 + 10 + 11 − 2
00 − + 01 − − 10 − + 11 − 2
Marks the solution state, and flips its sign.
Oracle qubit unchanged!
𝑈𝑓(𝑥 −) =
𝑥
0−1 2
MULT20015 Elements of Quantum Computing Lecture 15
Example: Oracle recognizing the state “2 = 10 ”
x
|0i |1i p2
Phase kickback
|00i ! |00i |01i ! |01i |10i ! |10i |11i ! |11i
The effect on each of the 4 states in the 2-qubit control register, x:
26 1 0 0 0 37
640 1 0 075=I 2|10ih10|
0 0 1 0 0001
MULT20015 Elements of Quantum Computing Lecture 15
The marked state
In general: 𝑥 − %! −1 𝑓 𝑥 𝑥 −
• If𝑓(𝑥)=0,𝑥−%! 𝑥−
• If𝑓(𝑥)=1,𝑥−%!−𝑥−
Initially in Grover’s algorithm, we will be searching for a single (integer) solution, m. In that case the effect of the oracle on the control register is:
26 1 0 0 0 37 64 0 1 0 0 75
0 0 1 0 0001
Here, as in future slides, we are only writing out the control qubits (in this case 2 qubits only).
-1 in the mth position
MULT20015 Elements of Quantum Computing Lecture 15
Example: Oracle recognizing the state “2 = 10 ”
x
|0i |1i p2
In practice we can implement the oracle without the oracle qubit using a controlled-Z gate (ex. Show the circuit right marks the
state 10 i.e. 𝑚=2 ).
Ex. Step through and check it is the same as above
Phase kickback
|00i ! |00i |01i ! |01i |10i ! |10i |11i ! |11i
MULT20015 Elements of Quantum Computing Lecture 15
15.3 Inversion about mean
MULT20015 Lecture 15
MULT20015 Elements of Quantum Computing Lecture 15
Iteration j
Apply Oracle,
flip the sign of solution (mark the state)
Inversion about mean
|0i H |0i H |0i H |0i H
Grover’s algorithm: Intuition
......
Maps every amplitude Mean−𝛿 to Mean+𝛿
Mean
01234567
Inversion about the mean increases the amplitude of solution vector.
Iter 1
Alice’s coffee problem
Mean
01234567 01234567
Mean
Iter k
Intuition:
Flipping the sign of the amplitude of solution vector reduces the mean.
Amplitude
Amplitude
Amplitude
MULT20015 Elements of Quantum Computing Lecture 15
Grover’s algorithm: Inversion around mean
• Maps every amplitude Mean−𝛿 to Mean+𝛿
• Consider a component 𝑎&|𝑥&⟩ of the overall state
Let 𝑎& = 𝐴 − 𝛿& where 𝐴 is the mean of amplitudes. Alternatively, 𝛿& = 𝐴 − 𝑎&.
Therefore,𝐴+𝛿& =𝐴+ 𝐴 −𝑎& =2𝐴 −𝑎&
• Equivalent transformation:
∑#$" 𝑎 |𝑥 ⟩ → ∑#$"(2𝐴 − 𝑎 )|𝑥 ⟩ &'!&& &'! &&
MULT20015 Elements of Quantum Computing Lecture 15
Aside - Grover’s algorithm: Inversion around mean
•
Transformation is linear.
∑#$" 𝑎 |𝑥 ⟩ → ∑#$"(2𝐴 − 𝑎 )|𝑥 ⟩ &'!&& &'! &&
𝑁2−1 𝑁2 ... 𝑁2
2 2 − 1 ... 2 𝑁𝑁 𝑁
⋮⋮⋮⋮
22...2−1 𝑁𝑁𝑁
We will call this matrix D
•
A quick calculation convinces us of this:
𝑁2−1𝑁2...𝑁2 222 2 2 2 𝑎`# 𝑎`# =𝑎# 𝑁−1 +𝑎$ 𝑁 +⋯+𝑎%&$ 𝑁
𝑎# 𝑎$ ⋮
𝑎%&$
𝑁 𝑁−1 ... 𝑁 = 𝑎`$ =𝑎 2 +𝑎 2 +⋯+𝑎 2 −𝑎 ⋮⋮⋮⋮ ⋮ #𝑁$𝑁%&$𝑁#
2 2 2 𝑎`%&$ =2'!('"(⋯('#$" −𝑎#
𝑁 𝑁 ...𝑁−1 =2𝐴−𝑎% #
This is not examinable (interest only)
MULT20015 Elements of Quantum Computing Lecture 15
Aside - Grover’s algorithm: Inversion around mean
• This transformation can be implemented in 𝑂 𝑛 = 𝑂(𝑙𝑜𝑔2 𝑁 ) gates.
Inversion
H
Conditional Phase shift:
0→0 𝑥 →−𝑥 for 𝑥 > 0
H
H
H
H
H
• The matrix D can be implemented as −
S0 where S0 is the matrix below.
26 1 0 0 0 . . . 37
6 0 1 0 0 …7 h 0 | = 64 0 0 1 0 . . . 75
Phase inversion of 0 vector.
0001… … … … … …
• For the curious (the derivation below is not examinable).
– Operator corresponding to the phase shift is 2 0 0 − 𝐼
– (20 0 −𝐼) =2𝜓 𝜓 −𝐼where 𝜓 istheequalsuperpositionofstates.
–2𝜓 𝜓 −𝐼appliedtogeneralstate∑#$”𝑎|𝑥⟩yields∑#$”(2𝐴−𝑎)|𝑥⟩ &’! & & &’! & &
i
MULT20015 Elements of Quantum Computing Lecture 15
Grover’s algorithm: Inversion around mean
Equal superposition
Solution has higher probability
“Inversion about the mean”
|0i |0i |0i |0i
H
H
H
H
H
H
H
H
H
…
H
H
H
The oracle
Iteration k
One iteration of Grover’s algorithm
Inversion
Oracle
MULT20015 Elements of Quantum Computing Lecture 15
15.4 Example Quantum Search
MULT20015 Lecture 15
MULT20015 Elements of Quantum Computing Lecture 15
Grover search with one marked state
https://codepen.io/samtonetto/full/BVOGmW
MULT20015 Elements of Quantum Computing Lecture 15
Invert the marked state
Note: The mean is reduced. Next step is inversion about the mean.
MULT20015 Elements of Quantum Computing Lecture 15
Inversion about the mean
MULT20015 Elements of Quantum Computing Lecture 15
MULT20015 Elements of Quantum Computing Lecture 15
MULT20015 Elements of Quantum Computing Lecture 15
MULT20015 Elements of Quantum Computing Lecture 15
MULT20015 Elements of Quantum Computing Lecture 15
Week 8
Lecture 15
15.1 Grover’s algorithm: Intuition 15.2 The Oracle
15.3 Inversion about the mean 15.4 Example Quantum Search
Lecture 16
16.1 Grover’s algorithm Examples 16.2 Probability of success
16.3 Geometric interpretation
Practice class 8
Grover’s algorithm using QUI
MULT20015 Elements of Quantum Computing Lecture 15
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