MULT20015 Elements of Quantum Computing Lecture 17
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 17
Week 9
Lecture 17
17.1 Grover’s algorithm with Unknown number of solutions 17.2 Quantum counting
17.3 Quantum counting example
Lecture 18 Quadratic Unconstrained Binary Optimization (QUBO)
18.1 Optimization Problems
18.2 Number Partitioning
18.3 Graph Partitioning
18.4 Traveling Salesman Problem
Practice class 9
Quantum counting and QUBO
MULT20015 Elements of Quantum Computing Lecture 17
Recap: Grover’s Algorithm
• Unordered search, find one 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 17
HH HH HH HH
Apply Oracle,
flip the sign of solution
Iteration i
Conditional Phase shift:
0→0 𝑥 →−𝑥 for 𝑥 > 0
|0i H |0i H |0i H |0i H
Recap: Grover’s algorithm
……
Iter 1
Iter n
Mean
Mean
Maps every amplitude Mean−𝛿 to Mean+𝛿
Mean
01234567
Inversion about the mean increases the amplitude of solution vector.
01234567 01234567
Intuition:
Flipping the sign of the amplitude of solution vector reduces the mean.
Amplitude
Amplitude
Amplitude
MULT20015 Elements of Quantum Computing
Lecture 17
|0i H |0i H |0i H |0i H
1 *+!
Recap: 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⟩ =
𝑁 . |𝑥⟩ #()
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 17
|0i H |0i H |0i H |0i H
Recap: Number of Grover iterations
…
Probability 𝑡 = 𝑚2,-! =𝑠𝑖𝑛2
where 𝑗 is the number of iterations and sin 𝜃
Iteration 1
Iteration 2
Iteration k-1
2𝑗 + 1 𝜃 ,
Iteration k
…
• Inversion about the mean transforms:
– 𝑗th iteration: −𝑚,|𝜓𝑀⟩ + p,|𝜓𝑃⟩ → (2𝐴, 𝑀 + 𝑚,)|𝜓𝑀⟩ + (2𝐴,
= 𝑚,-!|𝜓𝑀⟩ + p.-!|𝜓𝑃⟩
• Solution to the recurrence equations: –𝑚,-!=sin 2𝑗+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 17
How many iterations required?
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 17
Recap: Geometric interpretation
Consider the equal superposition:
𝜓0 = “|𝜓𝑀⟩+ *+”|𝜓𝑃⟩ **
|𝜓𝑀⟩ solutions
pM pN
|𝜓𝑃⟩
Non-solutions
1
✓
pN M pN
pM sin✓= pN
MULT20015 Elements of Quantum Computing Lecture 17
Recap: Geometric interpretation
|𝜓𝑀⟩ solutions
Product of two reflections is a rotation.
2✓
2✓
✓
|𝜓𝑃⟩
Non-solutions
pM sin✓= pN
MULT20015 Elements of Quantum Computing Lecture 17
17.1 Unknown number of solutions
MULT20015 Lecture 17
MULT20015 Elements of Quantum Computing Lecture 17
Grover’s algorithm – Unknown number of solutions
•
•
1. 2.
The optimal number of Grover iterations depends on the number of solutions 𝑀 relative to the size of search space 𝑁.
• In general, 𝑀 is unknown!
Two approaches to account for unknown number of solutions:
Execute Grover’s algorithm with number of iterations 𝑖 selected randomly between 1 and /0 𝑁
Count the number of solutions using Quantum counting
Note: One of the assumptions of Grover’s algorithm was 𝑀 < N.
• Since 𝑀 is unknown, it could be that the problem has many solutions.
• To account for this, we can double the search space to 2𝑁 by one extra “dummy”
qubit.
MULT20015 Elements of Quantum Computing Lecture 17
Alice’s coffee example
• Example: Alice wants to find a coffee shop that has nice cakes. We cannot see inside the oracle
Shop 2
3 ? 2???5
0?A ??
71
4
?
6
• 𝑋= 0,1,...,7
– 𝑋 is not ordered
• 𝑓(𝑥) = M1, if solugon 0, otherwise
– In general, the function 𝑓 does not need to know about the search space.
• We don’t know how many solutions are there.
• The function 𝑓 is a blackbox (similar to Deutsch-Jozsa and Simon’s algorithms).
MULT20015 Elements of Quantum Computing Lecture 17
17.2 Quantum counting
MULT20015 Lecture 17
MULT20015 Elements of Quantum Computing Lecture 17
Grover iteration as Matrix operation
• We can write the state after 𝑗 iterations of Grover as: 𝐺, 𝜓) =cos( 2𝑗+1 𝜃) 𝜓𝑃 +sin((2𝑗+1)𝜃)|𝜓𝑀⟩
• In the basis|𝜓𝑀⟩, |𝜓𝑃⟩ Grover’s iteration can be written as:
𝐺 = cos2𝜃 −sin2𝜃 where, sin𝜃 = "
|𝜓𝑀⟩ solutions
sin2𝜃 cos2𝜃
*
−sin2𝜃 has cos2𝜃
• Matrix G = cos2𝜃 sin2𝜃
two eigenvalues 𝑒123 and 𝑒+123
We can measure 𝜃 by Quantum phase estimation.
2✓
2✓
✓
|𝜓0⟩
|𝜓𝑃⟩
Non-solutions
MULT20015 Elements of Quantum Computing Lecture 17
Quantum Phase Estimation Circuit
𝑈 𝜓 = 𝑒1/23|𝜓⟩
Eigenstate
Controlled operation, U
Measure an estimate of 24𝜃
Inverse Quantum Fourier Transform
(1) Prepare equal superposition, x in the upper register, and eigenstate 𝜓 . (2) Apply Ux to lower register
(3) Apply (inverse) Quantum Fourier Transform to the upper register
(4) Measure to obtain an estimate equal to 25𝜃.
MULT20015 Elements of Quantum Computing Lecture 17
𝑈 𝜓 = 𝑒±123|𝜓⟩
Quantum Counting Circuit
|0i H measurement |0i H
Measure an estimateof
2 4 𝜽𝝅
Inverse Quantum Fourier Transform
𝑛 qubits for
|0i
H
Input for Grover’s
|0i H |0i H
H H
𝐺'!"#
𝐺'!"$
...
|0i |0i
Controlled Grover’s operation
(1) Prepare equal superposition, x in the upper register, and eigenstate 𝜓 . (2) Apply Gx to lower register
(3) Apply (inverse) Quantum Fourier Transform to the upper register
(4) Measure to obtain an estimate equal to 1!3. /
𝐺'%
𝑄𝐹𝑇 †
...
MULT20015 Elements of Quantum Computing Lecture 17
17.2 Quantum counting example
MULT20015 Lecture 17
MULT20015 Elements of Quantum Computing Lecture 17
Alice’s coffee example
• Example: Alice wants to find a coffee shop that has nice cakes. We cannot see inside the oracle
Shop 2
3 ? 2???5
0?A ??
71
4
?
6
• 𝑋= 0,1,...,7
– 𝑋 is not ordered
• 𝑓(𝑥) = M1, if solugon 0, otherwise
– In general, the function 𝑓 does not need to know about the search space.
• We don’t know how many solutions are there.
• The function 𝑓 is a blackbox (similar to Deutsch-Jozsa and Simon’s algorithms).
MULT20015 Elements of Quantum Computing Lecture 17
Quantum counting example
• (The figures are from Qiskit) New version for QUI will have this feature.
Measured output = 5 (101 in decimal).
MULT20015 Elements of Quantum Computing Lecture 17
Quantum counting example
• Calculating angle 𝜃 by using the measured value: – 1!3 = 5, alternatively,
/
– 𝜃 = 5𝜋/29 (we used 3 bits for counting)
– 𝜃 = 1.963495
• The value of 𝜃 can respond to either of the eigenvalues! (that is, number of
solutions or number of non-solutions).
• Weknowthatsin𝜃= "* orco𝑠𝜃= "*
– 𝑀 = 8 ∗ sin1(1.963495) or 𝑀 = 8 ∗ cos1(1.963495) – 𝑀=6.828or𝑀=1.172
• Since our assumption was 𝑀 << 𝑁, therefore 𝑀 = 1.172 ~1
• There is only one coffee shop that serves cake!
MULT20015 Elements of Quantum Computing Lecture 17
Quantum counting example
• Let us increase the number of counting bits to 8
Measured output = 157 (10011101 in decimal).
MULT20015 Elements of Quantum Computing Lecture 17
Quantum counting example
• Calculating 𝜃 by using the measured value: – 1!3 = 157, alternatively,
/
– 𝜃 = 157𝜋/2: (we used 8 bits for counting)
– 𝜃 = 1.926679
• The value of 𝜃 can respond to either of the eigenvalues! (that is, number of solutions or
number of non-solutions).
• Weknowthatsin𝜃= "* orco𝑠𝜃= "*
– 𝑀 = 8 ∗ sin1(1.926679) or 𝑀 = 8 ∗ cos1(1.926679) – 𝑀=7.028or𝑀=0.972
• Since our assumption was 𝑀 << 𝑁, therefore 𝑀 = 0.972 ~1
• There is only one coffee shop that serves cake!
We get a lower error now!
MULT20015 Elements of Quantum Computing
Lecture 17
Grover’s with unknown solutions: Example
Step 1: Estimate the number of solutions 𝑀 by quantum counting
𝑀=1
Step 2: Number of Grover iterations sin𝜃 = "* = !:, or 𝜃 = 0.361367. 2𝑘+1 𝜃=𝜋/2,or𝑘=2
MULT20015 Elements of Quantum Computing
Lecture 17
Quantum counting example: multiple solutions
• Using 8 counting bits
Measured output = 85 (01010101 in decimal).
MULT20015 Elements of Quantum Computing Lecture 17
Quantum counting example
• Calculating 𝜃 by using the measured value: – 1!3 = 85, alternatively,
/
– 𝜃 = 85𝜋/2: (we used 8 bits for counting)
– 𝜃 = 1.0431
• The value of 𝜃 can respond to either of the eigenvalues! (that is, number of
solutions or number of non-solutions).
• Weknowthatsin𝜃= "* orco𝑠𝜃= "*
– 𝑀 = 8 ∗ sin1(1.0431) or 𝑀 = 8 ∗ cos1(1.0431) – 𝑀 = 5.97159 or 𝑀 = 2.02841
• Since our assumption was 𝑀 << 𝑁, therefore 𝑀 = 2.02841 ~ 2
MULT20015 Elements of Quantum Computing
Lecture 17
Grover’s with unknown solutions: Example
Step 1: Estimate the number of solutions 𝑀 by quantum counting
𝑀=2
Step 2: Number of Grover iterations sin𝜃 = "* = 1:, or 𝜃 = 0.52359. 2𝑘+1 𝜃=𝜋/2,or𝑘=1
MULT20015 Elements of Quantum Computing
Lecture 17
Grover’s algorithm and Quantum counting
• Grover’s algorithm solves a blackbox problem with only 𝑁 calls to an oracle.
• Provides a quadratic speedup over classical methods
– If there is no structure that classical algorithms can exploit!
• Grover’s algorithm is optimal amongst other Quantum computing techniques
– This is the best we can hope for!
• Grover’s algorithm is sometimes referred as a database search algorithm
– This is misleading as databases often have structure
• Quantum counting has applications beyond computing the optimal number of
Grover iterations.
– Useful for NP problems where one is interested in existence of solutions.
• Phase estimation and amplitude amplification relevant for option pricing – Pricing options by simulating possible price trajectories
MULT20015 Elements of Quantum Computing
Lecture 17
Quantum counting example: No solution
Measured output = 4 (100 in decimal).
MULT20015 Elements of Quantum Computing Lecture 17
Quantum counting example
• Calculating angle 𝜃 by using the measured value: – 1!3 = 4, alternatively,
/
– 𝜃 = 4𝜋/29 (we used 3 bits for counting)
– 𝜃 = 1.57079
• The value of 𝜃 can respond to either of the eigenvalues! (that is, number of
solutions or number of non-solutions).
• Weknowthatsin𝜃= "* orco𝑠𝜃= "*
– 𝑀 = 8 ∗ sin1(1.57079) or 𝑀 = 8 ∗ cos1(1.57079) – 𝑀 = 8 or 𝑀 = 0
• Since our assumption was 𝑀 << 𝑁, therefore 𝑀 = 0
• There is no solution!
MULT20015 Elements of Quantum Computing Lecture 17
Week 9
Lecture 17
17.1 Grover’s algorithm with Unknown number of solutions 17.2 Quantum counting
17.3 Quantum counting example
Lecture 18 Quadratic Unconstrained Binary Optimization (QUBO)
18.1 Optimization Problems
18.2 Number Partitioning
18.3 Graph Partitioning
18.4 Traveling Salesman Problem
Practice class 9
Quantum counting and QUBO
MULT20015 Elements of Quantum Computing Lecture 17
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