MULT90063 Introduction to Quantum Computing
Introduction to Grover’s algorithm for amplitude amplification, geometric interpretation
Lecture 10
Amplitude Amplification, Succeeding with Certainty, Quantum Counting
Copyright By PowCoder代写 加微信 powcoder
Grover’s algorithm
MULT90063 Introduction to Quantum Computing
Amplitude Amplification
MULT90063 Introduction to Quantum Computing Lecture 10
MULT90063 Introduction to Quantum Computing
Amplitude Amplification
• This lecture: Amplitude amplificaiton – Amplitude Amplification
– Succeeding with certainty
– Quantum Counting
References:
Rieffel, Chapter 9.1-9.2
Kaye, Chapter 8.1-8.2
Nielsen and Chuang, Chapter 6.1-6.2
MULT90063 Introduction to Quantum Computing
Grover’s Algorithm (1996)
• 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
Inversion (I-2|0><0|)
MULT90063 Introduction to Quantum Computing
Some notation
|0i |0i |0i |0i
SG =I 2|mihm|
S0 =I 2|0ih0|
Inversion (I-2|0><0|)
MULT90063 Introduction to Quantum Computing
Some notation
|0i |0i |0i |0i
n is the number of input qubits. N is the total dimension (N=2n). M is the number of solutions.
Inversion (I-2|0><0|)
MULT90063 Introduction to Quantum Computing
Oracles for NP-problems
The phone book isn’t a great example: Adding in all the names would take O(N) time.
In general though, many problems (specifically those in the class NP) can have easily checkable solutions even if it is hard to solve the problem originally. Examples:
• Factoring
• Travelling Salesman with route less than
distance d
• Hamiltonian cycle
Straightforward application of Grover’s algorithm provides a polynomial improvement over random guessing... and potentially a better (but still polynomial speedup) known as amplitude amplication.
Part of Norfolk Island’s telephone book, with people listed by nickname (Photo: Wikicommons)
MULT90063 Introduction to Quantum Computing
Oracle for a hash function
A hash function whose output is hard to predict based on the input.
“Uncompute” the hash function – ensures the input register remains unchanged.
The oracle recognises the ‘correct’ solution, but does not know in advance which input leads to the correct solution
MULT90063 Introduction to Quantum Computing
Amplitude amplification
What happens if we replace the Hadamard gates with some other U? Perhaps, for example, we can create a U which gives the correct outcome with probability greater than 1/N. Can we get any advantage?
Inversion about the mean Apply general U instead of H
MULT90063 Introduction to Quantum Computing
New inversion step
Apply general U instead of H
| i = U |0i Then we can break this up as:
| i = g0 | gi + b0 | bi
Good: In the subspace spanned by all solutions
Bad: Not in the subspace spanned by all solutions
MULT90063 Introduction to Quantum Computing
Maths of the Geometric Interpretation
US0U†| i=U(I 2|0ih0|)U†| i =| i 2h0|U†| iU|0i
=| i 2h |U|0i⇤U|0i where | i = U |0i
| i = g0 | gi + b0 | bi Q | ig = US0U†SG | gi
= US0U† | gi
= | g i 2 g 0⇤ U | 0 i
=| i 2gg| i 2gb| i = | g i 2 g 0g | g i 2 g 0b | b i
g000g000b pp
=(1(1 2t2)t|)| ii 22 t(t1(1 t)t|)| ii gg bb
MULT90063 Introduction to Quantum Computing
Maths of Amplitude Amplification
S i m i l a r l y, Q | b i = ( 1 2 t ) | b i + 2 p t ( 1 t ) | g i Andfrompreviousslide: Q| gi=(1 2t)| gi 2pt(1 t)| bi
Q recursive step:
pp (1 2t) 2 t(1 t)
Compare to a rotation matrix:
2 t(1 t) (1 2t)
sin ✓ = pt = g0
R(2✓) = cos2✓ sin 2✓
sin2✓ cos 2✓
MULT90063 Introduction to Quantum Computing
Grover vs Amplitude Amplification
Amplification
Angle of rotation: p Angle of rotation: p
M sin✓= t=g0
If you can construct a U with a higher probability of success than random guessing 1/N, then amplitude amplificaton can help.
MULT90063 Introduction to Quantum Computing
How to achieve 100% Success
The optimal, 100% probability of measuring marked can be missed.
Can we modify the algorithm to obtain 100% probability of success?
|ai solutions
|bi Non-solutions
pM sin✓= pN
MULT90063 Introduction to Quantum Computing
Grover with 100% success
Using amplitude amplification
This step gives 100% probability of finding the marked state
Idea: reduce the size of each step (intentionally) so that a whole number of steps is required.
|bi Non-solutions
|ai solutions
MULT90063 Introduction to Quantum Computing
Reducing the angle
We want to reduce the angle of rotation in Grover’s algorithm/amplitude amplification so that we require a whole number of steps to achieve 100% probability of success.
Trick: Introduce a new qubit.
MULT90063 Introduction to Quantum Computing
How much reduction?
Previously:
U |0i = g0 | gi + b0 | bi With new qubit:
V ⌦U|0i=V |0i⌦(g0| gi+b0| bi) If we arrange so that:
V |0i = s1 g0 |0i + g0 |1i
e.g. Y-rotation by an angle: cos ↵ = g0 2g
MULT90063 Introduction to Quantum Computing
New rotation angle
V ⌦U|0i=sV |0i⌦(g0| gi+b0| bi) ✓g0 ◆2 g0
V |0i = 1 g0 |0i + g0 |1i
Our new “good” states, but now have a preceding “1” on the extra qubit we added
V ⌦U|0i=g |1i| g i+...
We can choose the initial amplitude to be anything value less than the original
Chooseg0’s.t. i= ⇡ 1 isawholenumber 4✓0 2
MULT90063 Introduction to Quantum Computing
100% success
The ith step gives 100% probability of finding the marked state
Using amplitude amplification
sin✓0 =g0 i=⇡ 1
|bi Non-solutions
|ai solutions
MULT90063 Introduction to Quantum Computing
Example: Three qubit Grover
|0i |0i |0i
|0i |0i |0i |0i
Extra qubit!
Inversion (I-2|0><0|)
Inversion (I-2|0><0|)
MULT90063 Introduction to Quantum Computing
Example: Searching for 5 (101)
Added an extra qubit
Extra rotations (e.g. around Y) to ensure that we obtain the answer with certainty
Oracle selects for “1” on the
Oracle selects for “101” in main register
Inversion: similar to Grover’s algorithm
MULT90063 Introduction to Quantum Computing
Example: Searching for 5 (101)
MULT90063 Introduction to Quantum Computing
Example: Searching for 5 (101)
MULT90063 Introduction to Quantum Computing
Example: Searching for 5 (101)
MULT90063 Introduction to Quantum Computing
Example: Searching for 5 (101)
MULT90063 Introduction to Quantum Computing
Example: Searching for 5 (101)
MULT90063 Introduction to Quantum Computing
Example: Searching for 5 (101)
MULT90063 Introduction to Quantum Computing
Amplitude Amplification
Given an black box (oracle), Uf, which computes the function f:{0,1}n à{0,1} Find an x s.t. f(x) = 1
• Unordered search, generalisation of Grover’s algorithm
• Classically, this requires N/2 uses of the oracle
• Quantum mechanically, requires only O(√N).
|0i |0i |0i |0i
Inversion (I-2|0><0|)
MULT90063 Introduction to Quantum Computing
Amplitude Amplification is optimal
Proof in your textbooks.
Grover’s algorithm is optimal in terms of the number of applications of the oracle. For many oracle problems the required number of uses of the oracle scales like:
This means that for a broad range of problems the best speedup we can achieve using a quantum computer is not exponential, but polynomial (which can be quite significant).
For problems with identifiable structure, we might hope for more speedup.
More on this next week.
MULT90063 Introduction to Quantum Computing
Quantum Counting
Will show you this algorithm now, but will leave some of the details until after next week’s lectures/lab.
Given an black box (oracle), Uf, which computes the function f:{0,1}n à{0,1} How many x s.t. f(x) = 1?
MULT90063 Introduction to Quantum Computing
Equivalent question
What angle rotation does Q make?
Oracle, M solutions
MULT90063 Introduction to Quantum Computing
Plotting amplitude as function of step number
After k steps:
✓k = (2k + 1)✓
pM sin✓= pN
Number of solutions is reflected in the period/frequency
Incorrect solutions would follow cosine, rather than sin
Amplitude at step ‘k’ is:
gk = sin(2k + 1)✓
MULT90063 Introduction to Quantum Computing
Finding the period of a periodic function
| i=pN x |xi⌦Q |0i
Control register, x
x steps of Grover’s algorithm
Quantum Fourier Transform (next week)
MULT90063 Introduction to Quantum Computing
Finding the period of a periodic function
| i=pN |xi⌦Q |0i
|xi⌦(sin(2x+1)✓| gi+cos(2x+1)✓| bi)
If we measure the second register
MULT90063 Introduction to Quantum Computing
After measurement of the second register
| i = X sin(2x + 1)✓ |xi ⌦ | gi (not normalized) x
Next step: Use Quantum Fourier Transformation to find the period
MULT90063 Introduction to Quantum Computing
After the Fourier transformation
Dimension: N’ Dimension: N
After Fourier transforming a periodic function, we get a good approximation to theta. If we
measure value “j”:
pM ✓ = N0 sin✓ = pN
Which we can solve to obtain the number of solutions, M
MULT90063 Introduction to Quantum Computing
Phase Estimation and HSP Problems
The Hadamard and Fourier transform part is a known as phase estimation, and extremely useful for period functions (and eigenvalues which are periodic).
As we will see in the next lecture, this pattern is often repeated.
MULT90063 Introduction to Quantum Computing
Introduction to Grover’s algorithm for amplitude amplification, geometric interpretation
Lecture 10
Amplitude Amplification, Succeeding with Certainty, Quantum Counting
Grover’s algorithm
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com