MULT20015 Elements of Quantum Computing Lecture 16
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 16
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 16
Recap: Grover’s Algorithm
• 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 16
Recap: Grover’s algorithm
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 16
Iteration j
Apply Oracle,
flip the sign of solution (mark the state)
Inversion about mean
|0i H |0i H |0i H |0i H
Recap: Grover’s algorithm
......
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 16
Unstructured search problems
• Example: Alice (A) wants to find a coffee shop within 5 mins of walking distance.
Cafe 2 is 5.7 minutes away
7
2 5.7 4.5 6.2 5
0 5.8 A 6.4 6.2
3
4
5.2
• 𝑋= 0,1,2,...,7
– Set 𝑋 is not ordered by travel time
• 𝑓(𝑥)=-1,if_me(x)≤5 0, otherwise
71
6
– 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 16
Control on 1
Flips the sign if:
- Control 1 qubit is in 1 - Target qubit is in 1
The Oracle on QUI
• 000 → 000
• 001 → 001
• 010 → 010
• 011 → 011
• 100 → − 100 (Solution state x=4) • 101 → 001
• 110 → 010 • 111 → 011
3
4
5.2
0 5.8
7
2 5.7 4.5 6.2 5
6.4
A
6.2
6
71
Alice’s coffee example.
MULT20015 Elements of Quantum Computing Lecture 16
Conditional Phase Shift on QUI
• 000 →−000 • 001 → 001
• 010 → 010
• 011 → 011
• 100 → 100 • 101 → 001 • 110 → 010 • 111 → 011
Conditional Phase shift:
0→0 𝑥 →−𝑥 for 𝑥 > 0
Note: The QUI implementation does
0→−0
𝑥→𝑥
This is correct as global phase does not affect probabilities of measuring a state.
MULT20015 Elements of Quantum Computing Lecture 16
Solving Alice’s coffee problem on QUI
Oracle
Equal superposition
Marking of the solution state
0.125 Mean inversion (1st iteration) 0.781
MULT20015 Elements of Quantum Computing Lecture 16
Solving Alice’s coffee problem on QUI
Probabilities after first iteration
0.781
Marking of the solution state
0.781
Probability of finding a solution maximum after 2 iterations of Grover step.
Mean inversion (2nd iteration)
0.945
MULT20015 Elements of Quantum Computing Lecture 16
16.2 Probability of Success
MULT20015 Lecture 16
MULT20015 Elements of Quantum Computing Lecture 16
Number of Grover iterations
H
H
H
H
Iteration 1
Iteration 2
…
Iteration k
•
•
|0i |0i |0i |0i
Each iteration in Grover’s algorithm performs two steps: – Flip the sign of the solution state
– Inversion around the mean
After 𝑗th iteration the amplitude of solution states increase (under certain assumptions)
– 𝑀 ≪ 𝑁, where 𝑀 is the number of solutions.
–𝑗≤ !⁄ ”
What is the optimal value of k such that amplitude of solution state is highest?
Inversion about mean
Apply Oracle, flip the sign of soln.
MULT20015 Elements of Quantum Computing Lecture 16
Number of Grover iterations
H
H
H
H
Iteration 1
Iteration 2
…
Iteration k
• •
|0i |0i |0i |0i
Alternate perspective: Let 𝑡 denote the probability of picking a random value 𝑥∈{0,1,…,𝑁−1}suchthat𝑓 𝑥 =1.
The value of 𝑡 increases after 𝑗th iteration (under certain assumptions) – 𝑀 ≪ 𝑁, where 𝑀 is the number of solutions.
–𝑗≤ !⁄ ”
What is the optimal value of k such that probability t is highest?
Inversion about mean
Apply Oracle, flip the sign of soln.
MULT20015 Elements of Quantum Computing Lecture 16
|0i H |0i H |0i H |0i H
1 !+#
Number of Grover iterations
…
Iteration 1
Iteration 2
Probability 𝑡 = “! = 𝑚*2, where 𝑀 is the number of solutions. • Let|𝜓𝑀⟩ = #” ∑$∈& |𝑥⟩ and|𝜓𝑃⟩ = #’ ∑$∉& |𝑥⟩ where
– 𝑆isthesetofsolutions,𝑀isthenumberofsolutions,and𝑃=𝑁−𝑀.
– |𝜓𝑀⟩are the states that represent solution and |𝜓𝑃⟩ represent non-solution states.
|𝜓⟩= # ∑!+#|𝑥⟩= “|𝜓 ⟩+ ‘|𝜓⟩=𝑚|𝜓 ⟩+p|𝜓⟩ 0!$)* !𝑀!𝑃*𝑀*𝑃
|𝜓0⟩ =
𝑁 B |𝑥⟩ $)*
Iteration k-1
Iteration k
…
Each iteration changes the amplitudes.
Two basis states to understand Grover’s algorithm!
Apply Oracle, flip the sign of solution
Inversion about mean
Apply Oracle, flip the sign of solution
Inversion about mean
Apply Oracle, flip the sign of solution
Inversion about mean
Apply Oracle, flip the sign of solution
Inversion about mean
MULT20015 Elements of Quantum Computing Lecture 16
Alice’s coffee example
• Example: Alice wants to find a coffee shop within 5 mins of walking distance.
3
4
7
2 5.7 4.5 6.2 5
0 5.8 A
5.2 6.2
71
6
6.4
• |𝜓 ⟩ = # ∑!+# |𝑥⟩ = # ∑- |𝑥⟩ 0 !$)* ,$)*
=#,0+#,1+#,2+#,3+#,4+ #,5+#,6+ #,|7⟩ = #, 4 + #, 0 + #, 1 + #, 2 + #, 3 + #, 5 + #, 6 + #, 7
= #, |𝜓𝑀⟩ + -, |𝜓𝑃⟩
• Probability of finding solution = ( #,).= #, • Average amplitude = #, = 0.35355
Re-normalise the vector components of |𝜓𝑃⟩
MULT20015 Elements of Quantum Computing Lecture 16
|0i H |0i H |0i H |0i H
Number of Grover iterations
…
Probability 𝑡 = “! = 𝑚*2, where 𝑀 is the number of solutions.
Iteration 1
Iteration 2
• Effect of applying the oracle and flipping the sign of solution states: – First iteration: 𝑂: 𝑚*|𝜓𝑀⟩ + p*|𝜓𝑃⟩ → −𝑚*|𝜓𝑀⟩ + p*|𝜓𝑃⟩
– 𝑗th iteration:𝑂:𝑚/|𝜓𝑀⟩+p/|𝜓𝑃⟩→−𝑚/|𝜓𝑀⟩+p/|𝜓𝑃⟩
• Average amplitude:
–𝐴/=+ “0!1 ‘2!=+ “0!1 !+”2! !!
• Note: After applying the oracle, the amplitude changes sign but the probability 𝑡 does not change.
Iteration k-1
Iteration k
…
Apply Oracle, flip the sign of solution
Inversion about mean
Apply Oracle, flip the sign of solution
Inversion about mean
Apply Oracle, flip the sign of solution
Inversion about mean
Apply Oracle, flip the sign of solution
Inversion about mean
MULT20015 Elements of Quantum Computing Lecture 16
Alice’s coffee example
• Example: Alice wants to find a coffee shop within 5 mins of walking distance.
3
4
7
2 5.7 4.5 6.2 5
0 5.8 A
5.2 6.2
71
• 𝑂: 𝜓0
=−#,4+#,0+#,1+#,2+#,3+ #,5+#,6+ #,|7⟩
= − #,|𝜓𝑀⟩+ -,|𝜓𝑃⟩=−𝑚*|𝜓𝑀⟩+p*|𝜓𝑃
• Probability of finding solution = (− #,).= #, = 0.125 “#1- #
6.4
6
• Average amplitude A = $
,
$ = 0.265165
Average amplitude is calculated on original state.
MULT20015 Elements of Quantum Computing Lecture 16
|0i H |0i H |0i H |0i H
Number of Grover iterations
…
Iteration 1
Iteration 2
Probability 𝑡 = 𝑚2/1# =𝑠𝑖𝑛2
where 𝑗 is the number of iterations and sin 𝜃
Iteration k-1
2𝑗 + 1 𝜃 ,
Iteration k
…
• Inversion about the mean transforms:
– 𝑗th iteration: −𝑚/|𝜓𝑀⟩ + p/|𝜓𝑃⟩ → (2𝐴/ 𝑀 + 𝑚/)|𝜓𝑀⟩ + (2𝐴/
= 𝑚/1#|𝜓𝑀⟩ + p31#|𝜓𝑃⟩
• Solution to the recurrence equations: –𝑚/1#=sin 2𝑗+1𝜃 –𝑝/1#=cos 2𝑗+1𝜃
” !
= “⁄ !
𝑁 − 𝑀 − 𝑝/)|𝜓𝑃⟩
– sin 𝜃 =
Apply Oracle, flip the sign of solution
Inversion about mean
Apply Oracle, flip the sign of solution
Inversion about mean
Apply Oracle, flip the sign of solution
Inversion about mean
Apply Oracle, flip the sign of solution
Inversion about mean
MULT20015 Elements of Quantum Computing Lecture 16
Alice’s coffee example
• Example: Alice wants to find a coffee shop within 5 mins of walking distance.
3
4
7
2 5.7 4.5 6.2 5
0 5.8 A
5.2 6.2
71
6
6.4
• 𝜓1 =∑!+#(2𝐴−𝑎/)|𝑥/⟩ /)*
= 2𝐴+ #, 4 +(2𝐴− #,) 0 +(2𝐴− #,) 1 +(2𝐴− #,) 2 +(2𝐴− #,) 3 +(2𝐴− #,) 5 +(2𝐴− #,) 6 +(2𝐴− #,)|7⟩
= 2 𝐴 + # , | 𝜓 𝑀 ⟩ + 2 𝐴 7 − -, | 𝜓 𝑃 ⟩
• Probability of finding solution = (2𝐴 + #,).= (2∗0.265165 + #,).= 0.781249
MULT20015 Elements of Quantum Computing Lecture 16
How many iterations required?
Case: Single solution
For small angles,
1 sin ✓ = pN
✓ ⇡ pN
1
After 𝑘 iterations, we rotate to have only marked solutions: 2 𝑘 + 1 𝜃 = 𝜋2
𝑘 ≈ 𝜋4 𝑁
The number of steps, 𝑘, required scales as O(√N), and not with N as it would classically.
This is a “polynomial” rather than an “exponential” speedup.
MULT20015 Elements of Quantum Computing Lecture 16
How many iterations required?
Case: Multiple solutions
For small angles,
pM sin✓= pN
pM ✓ ⇡ pN
After 𝑘 iterations, we rotate to have only marked solutions: 2 𝑘 + 1 𝜃 = 𝜋2
𝑘 ≈ 𝜋4 𝑀𝑁
Having multiple solutions is faster than searching for a single marked solution.
MULT20015 Elements of Quantum Computing
Lecture 16
Alice’s coffee example: Many solutions
• Example: Alice wants to find a coffee shop within 5.5 mins of walking distance.
3
4
5.2
7
2 5.7 4.5 6.2 5
0 5.8 A 6.4 6.2
71
• 𝑋= 0,1,…,7
– 𝑋 is not ordered by travel time
• 𝑓(𝑥) = -1, if _me(x) ≤ 5.5 0, otherwise
6
Cafe 6 is 5.2 minutes away
– In general, the function 𝑓 does not need to know about the search space. • Solution 𝑥 ∈ {4, 6}
MULT20015 Elements of Quantum Computing
Lecture 16
Alice’s coffee example: Many solutions
Equal superposition
Probability of finding a solution maximum after 1 iterations of Grover step.
Marking of the solution state
Mean inversion
0.5 0.5
MULT20015 Elements of Quantum Computing Lecture 16
16.3 Geometric Interpretation
MULT20015 Lecture 16
MULT20015 Elements of Quantum Computing
Lecture 16
Geometric interpretation of Grover’s algorithm
|0i |0i |0i
H
H
H
H
H
H
H
H
H
H
H
H
H
H
H
Recall:
|𝜓⟩=#∑!+#|𝑥⟩= “|𝜓⟩+ ‘|𝜓⟩=𝑚|𝜓⟩+p|𝜓⟩
0!$)* !𝑀!𝑃*𝑀*𝑃
Solutions! Non-solutions
We only need to consider the amplitude of these two states in Grover’s algorithm. Every operation is also real, so we can plot on a circle.
Inversion
Oracle
Inversion
Oracle
MULT20015 Elements of Quantum Computing Lecture 16
Geometric Interpretation
|𝜓𝑀⟩
solutions
𝑚/
|𝜓⟩
= 𝑚/|𝜓𝑀⟩ + p/|𝜓𝑃⟩
|𝜓𝑃⟩
Non-solutions
𝜃
p/
Every state in Grover’s algorithm can be expressed as a superposition of these vectors
MULT20015 Elements of Quantum Computing Lecture 16
Equal superposition
|0i |0i |0i
H
H
H
H
H
H
H
H
H
H
H
H
H
H
H
Equal superposition state: |𝜓⟩=]∑^b]|𝑥⟩= c|𝜓⟩+ d𝜓
0^_`a ^𝑀^𝑃
= c |𝜓𝑀⟩ + ^bc |𝜓𝑃⟩ ^^
Inversion
Oracle
Inversion
Oracle
MULT20015 Elements of Quantum Computing Lecture 16
Equal Superposition
Consider the equal superposition:
𝜓0 = “|𝜓𝑀⟩+ !+”|𝜓𝑃⟩ !!
|𝜓𝑀⟩ solutions
pM pN
|𝜓𝑃⟩
Non-solutions
1
✓
pN M pN
pM sin✓= pN
MULT20015 Elements of Quantum Computing Lecture 16
Effect of the Oracle
|0i |0i |0i
H
H
H
H
H
H
H
H
H
H
H
H
H
H
H
State
Apply the oracle
The marked state
State
Flip
Inversion
Inversion
Oracle
Amplitude
Amplitude
MULT20015 Elements of Quantum Computing Lecture 16
Geometric Effect of Oracle
|𝜓/⟩ = 𝑚/|𝜓𝑀⟩ + p/|𝜓𝑃⟩
|𝜓𝑀⟩ solutions
𝜓/⟩
𝑚/
|𝜓𝑃⟩
Non-solutions
𝜃
MULT20015 Elements of Quantum Computing Lecture 16
Geometric Effect of Oracle
𝑂 : 𝑚/ | 𝜓 𝑀 ⟩ + p / | 𝜓 𝑃 ⟩ → − 𝑚/ | 𝜓 𝑀 ⟩ + p / | 𝜓 𝑃 ⟩
|𝜓𝑀⟩ solutions
𝜃 𝜃
𝑚/
|𝜓𝑃⟩
𝑚/ 𝑂(𝜓/⟩)
Non-solutions
MULT20015 Elements of Quantum Computing Lecture 16
Effect of inversion about the mean
The mean State
Inversion about the mean
The mean State
Amplitude
Amplitude
MULT20015 Elements of Quantum Computing Lecture 16
Geometric Effect of Oracle
−𝑚/|𝜓𝑀⟩ + p/|𝜓𝑃⟩ → 𝑚/1#|𝜓𝑀⟩ + p/1#|𝜓𝑃⟩
|𝜓𝑀⟩ solutions |𝜓/1#⟩
𝑂(|𝜓/⟩)
Equal superposition state
|𝜓𝑃⟩
Non-solutions
Inversion about the mean reflects around the equal superposition state
MULT20015 Elements of Quantum Computing Lecture 16
Geometric Effect of Both Oracle and Inversion
|𝜓*⟩ = 𝑚4|𝜓𝑀⟩ + p4|𝜓𝑃⟩
|𝜓𝑀⟩ solutions
|𝜓* ⟩
𝑚*
|𝜓𝑃⟩
Non-solutions
𝜃
MULT20015 Elements of Quantum Computing Lecture 16
Geometric Effect of Both Oracle and Inversion
𝑂: 𝑚*|𝜓𝑀⟩ + p*|𝜓𝑃⟩ → −𝑚*|𝜓𝑀⟩ + p*|𝜓𝑃⟩
|𝜓𝑀⟩ solutions
𝜃 𝜃
𝑚*
|𝜓𝑃⟩
𝑚* 𝑂(𝜓*⟩)
Non-solutions
MULT20015 Elements of Quantum Computing Lecture 16
Geometric Effect of Both Oracle and Inversion
−𝑚*|𝜓𝑀⟩ + p*|𝜓𝑃⟩ → 𝑚#|𝜓𝑀⟩ + p#|𝜓𝑃⟩
|𝜓𝑀⟩ solutions |𝜓#⟩
2𝜃
𝜃 𝜃
Equal superposition state
|𝜓𝑃⟩
Non-solutions
𝑂(|𝜓*⟩)
Inversion about the mean reflects around the equal superposition state
MULT20015 Elements of Quantum Computing Lecture 16
Total effect of one Grover iteration
Product of two reflections is a rotation.
|𝜓𝑀⟩ solutions
pM sin✓= pN
2✓
✓
|𝜓𝑃⟩
Non-solutions
MULT20015 Elements of Quantum Computing Lecture 16
Many Grover iterations
|𝜓𝑀⟩ solutions
Product of two reflections is a rotation.
2✓
2✓
✓
|𝜓𝑃⟩
Non-solutions
pM sin✓= pN
MULT20015 Elements of Quantum Computing Lecture 16
Alice’s coffee example
• Example: Alice wants to find a coffee shop within 5 mins of walking distance.
3
4
7
2 5.7 4.5 6.2 5
0 5.8 A
5.2 6.2
71
6
6.4
• sin𝜃 =#,or𝜃=0.361367rad
• Probability after iteration 𝑗 = sin2
• Probability of soln. after iteration 0= sin2 𝜃 = sin2( 0.361367) = 0.125
• Probability of soln. after iteration 1 = sin2 3𝜃 = sin2 1.084101 = 0.781249
• Probability of soln. after iteration 2 = sin2 5𝜃 = sin2 1.80635 = 0.945312
2𝑗 + 1 𝜃
Ex. What happens after one more iteration?
MULT20015 Elements of Quantum Computing
Lecture 16
Alice’s coffee example with multiple solutions
• Example: Alice wants to find a coffee shop within 5.5 mins of walking distance.
3
4
7
2 5.7 4.5 6.2 5
0 5.8 A
5.2 6.2
71
6
6.4
• sin𝜃 =.,or𝜃=0.523598rad
• Probability after iteration 𝑗 = sin2
• Probability of soln. after iteration 0= sin2 𝜃 = sin2( 0.523598) = 0.25
• Probability of soln. after iteration 1 = sin2 3𝜃 = sin2 1.5707 = 1
2𝑗 + 1 𝜃
Ex. What happens after one more iteration?
MULT20015 Elements of Quantum Computing Lecture 16
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 Example 16.2 Probability of success
16.3 Geometric interpretation
Practice class 8
Grover’s algorithm using QUI
MULT20015 Elements of Quantum Computing Lecture 16
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