MULT90063 Introduction to Quantum Computing
Quantum search – introduction to Grover’s algorithm for amplitude amplification, geometric interpretation
Lecture 10
Optimality, Succeeding with Certainty, Quantum Counting
Copyright By PowCoder代写 加微信 powcoder
Grover’s algorithm
MULT90063 Introduction to Quantum Computing
Grover’s Algorithm Lecture 9
MULT90063 Introduction to Quantum Computing
Introduction to Grover’s algorithm
• This lecture: Grover’s search algorithm – Grover’s algorithm
– Worked Example
– Geometric interpretation
References:
Reiffel, Chapter 9.1-9.2
Kaye, Chapter 8.1-8.2
Nielsen and Chuang, Chapter 6.1-6.2
MULT90063 Introduction to Quantum Computing
Reminder: Outer Product
Fortwoquantumstates | i= ab , | i= dc We can define an outer product between them:
|ih |=ab ⌦⇥c⇤ d⇤⇤ =ac⇤ ad⇤
26 0 0 0 0 37 64 0 0 1 0 75
For number basis states, this specifies a matrix with a single “1” in the location 1,2. In general:
|rowi hcolumn|
MULT90063 Introduction to Quantum Computing
Unordered Search
Grover’s algorithm performs a similar* problem to this: You are given a telephone book
And a phone number: 23675
Your task:
Find the name which goes with that number…
Part of Norfolk Island’s telephone book, with people listed by nickname (Photo: Wikicommons)
* Not all that similar, better examples later….
MULT90063 Introduction to Quantum Computing
Quantum search – Grover’s problem
Given an black box (oracle), Uf, which computes the function: f:{0,1}n à{0,1}
Find an x s.t. f(x) = 1
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
Two basic steps in Grover’s algorithm
1X Quantum database: | i = pN i |ii
(i.e. all integers 0 to N-1)
|0i |0i |0i |0i
The “oracle” Identifies a particular marked state, m
I 2 | i h | “Inversion about the mean”
Repeat these two operations O(√N) times
Inversion (I-2|0><0|)
MULT90063 Introduction to Quantum Computing
The Oracle
The task of recognizing the correct solution goes to the “oracle”.
Designed to flip the last bit if the input, i, is a solution
MULT90063 Introduction to Quantum Computing
Phase kickback for Boolean function
|yi |y f(x)i
Binary function, or “oracle”
After the function has been applied:
| i = pN ( 1)f (i) |ii ⌦
Target qubit remains the same
If the oracle function evaluates to “1” then the target qubit is flipped, and we pick up a phase (associated with the control qubit state). Otherwise, there is no phase applied. This is a simple way to write that.
| 0 i | 1 i p2
MULT90063 Introduction to Quantum Computing
Example: Oracle recognizing the state “2 = |10>”
|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
MULT90063 Introduction to Quantum Computing
The marked state
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:
I 2 |mi hm| 26 1 0 0 0 37
64 0 1 0 0 75 0 0 1 0
Here, as in future slides, we are only writing out the control qubits (in this case 2 qubits only).
As a matrix:
(in decimal ket notation)
-1inthemth position
MULT90063 Introduction to Quantum Computing
Example: Oracle recognizing the state “2 = |10>”
|0i |1i p2
In practice we can implement
the oracle without the check
qubit using a controlled-Z gate
(ex. Show the circuit right marks the state |10>, i.e. |m=2>).
Phase kickback
|00i ! |00i |01i ! |01i |10i ! |10i |11i ! |11i
MULT90063 Introduction to Quantum Computing
Two steps to Grover’s algorithm
Set up “data base”
|0i |0i |0i |0i
I 2|mihm| The oracle
I 2| ih | “Inversion about the mean”
Repeat these two operations O(√N) times
1X One iteration of Grover where | i = pN i |ii
Inversion (I-2|0><0|)
MULT90063 Introduction to Quantum Computing
Unpicking the details: “Inversion” operation
The “Inversion” part is just applying a phase to the zero state:
2 1 0 0 0 ... 3 6 0 1 0 0 ...7
|0i = B C 0 0 . . . 0 0 0 . . . 0
|0i h0| = B C ⌦ (1 0|0.i.h.00|)=B @.. A @.
C ⌦ (1 0 . . . 0) = I = B
A @ A 001...0
C @.A @ . A. . @ . A
1 0 0 0 ... 1 0 0 0 ... 100...0 10...0
6767 B01C00B... C 0100...
010...0 00...0 6767
C1 20B..I. 2|0iCh0|= 0 001...0 .
0 1 0 ... 6767
I 2|0ih0|= B 0 0
4 0 .0 0 1 ...5. 4 0 0 0 1 ...5
... ... ... ... ... ... ... ... ... ...
I 2|0ih0|=6 0 0 1 0 ... 7 6 7
4 0 0 0 1 ...5 ... ... ... ... ...
|ih |=ab ⌦⇥c⇤ d⇤⇤ How?Recallouterproductetc: | ih |= a ⌦⇥ c⇤ d⇤ ⇤= ac⇤ ad⇤
b bc⇤bd⇤ 010101
1 01=101100...0
ad⇤ bc⇤ bd⇤
10...0 10...0 BCBCBC
B0C 0 010...0
B0C BCCBCBC
Inversion (I-2|0><0|)
MULT90063 Introduction to Quantum Computing
Inversion about the mean
| i = pN i |ii Set up “data base”
|0i |0i |0i |0i
I 2 | i h |
“Inversion about the mean”...let’s see how that works.
Inversion (I-2|0><0|)
MULT90063 Introduction to Quantum Computing
Apply inversion about the mean to general state
Applying Hadamards both sides:
I 2H⌦n |0i h0| H⌦n = I 2 | i h |
1X | i = p |ii
X22222Ni3 1 ...
|i=ai|ii i
| i=Xai|ii!| 0i=(I 2| ih |)Xai|ii
General state
superposition
6NNNN7 Equal
6 N2 1 N2 N2 N2 . . . 7
0 =6 2 2 1 2 2 ...7 |i= a|ii!
... ... ... ... ...
i64N N N N 75 i N2 N2 N2 1 N2 ...
X1X1XXX ai |ii 2pN |ki pN hj| ai |ii
Xaj1A ajA
i k j Average
= (ai 2A) |ii amplitude
i instate| i
MULT90063 Introduction to Quantum Computing
Inversion about the mean
Consider a general state. The resulting amplitude from the “Inversion about the mean” step is:
X ai |ii ! X(ai 2A) |ii ii
Original amplitude
Average amplitude In practice on the QUI...
MULT90063 Introduction to Quantum Computing
Inversion about the mean
Amplitudes of the state, before and after:
ai A ai A
ai A 2A ai
When the state undergoes this transformation:
X ai |ii ! X(2A ai) |ii ii
MULT90063 Introduction to Quantum Computing
Effect of inversion about the mean
The marked state
Increased amplitude of the marked state
The mean State
Inversion about the mean
The mean State
MULT90063 Introduction to Quantum Computing
Interactive Example
https://codepen.io/samtonetto/full/BVOGmW
MULT90063 Introduction to Quantum Computing
Worked example: finding 6
“Inversion about the mean” “Inversion about the mean”
I 2| ih | I 2| ih |
|0i |0i |0i
I 2 |mi hm| The oracle
I 2 |mi hm| The oracle
Oracle = 6
Oracle = 6
MULT90063 Introduction to Quantum Computing
Worked example: finding 6
|0i |0i |0i
Oracle = 6
Oracle = 6
MULT90063 Introduction to Quantum Computing
Worked example: finding 6
|0i |0i |0i
Oracle = 6
Oracle = 6
MULT90063 Introduction to Quantum Computing
Effect of the Oracle
Apply the oracle
The marked state
MULT90063 Introduction to Quantum Computing
Worked example: finding 6
|0i |0i |0i
The mean(?)
Phase of state 6 has changed to be negative
Oracle = 6
Oracle = 6
MULT90063 Introduction to Quantum Computing
Effect of inversion about the mean
The marked state
Increased amplitude of the marked state
The mean State
Inversion about the mean
The mean State
MULT90063 Introduction to Quantum Computing
Worked example: finding 6
|0i |0i |0i
After inversion about the mean:
Oracle = 6
Oracle = 6
MULT90063 Introduction to Quantum Computing
Effect of the Oracle
Apply the oracle
The marked state
MULT90063 Introduction to Quantum Computing
Worked example: finding 6
|0i |0i |0i
After the second oracle:
Oracle = 6
Oracle = 6
MULT90063 Introduction to Quantum Computing
Effect of inversion about the mean
The mean State
Inversion about the mean
The mean State
MULT90063 Introduction to Quantum Computing
Worked example: finding 6
|0i |0i |0i
After the second oracle:
Oracle = 6
Oracle = 6
MULT90063 Introduction to Quantum Computing
Grover’s algorithm
|0i |0i |0i
95% Success!
Finally, we measure the marked state after 2 applications of the oracle, and find the marked state, 6 with 95% probability
Oracle = 6
Oracle = 6
MULT90063 Introduction to Quantum Computing
Geometric interpretation of Grover’s algorithm
|0i |0i |0i
A very useful basis:
|bi = p 1 X |ii
Solution! Non-solutions...
N 1 i2/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.
MULT90063 Introduction to Quantum Computing
Geometric Interpretation
| i=↵|ai+ |bi 1
Every state in Grover’s algorithm can be expressed as a superposition of these vectors
|bi Non-solutions
MULT90063 Introduction to Quantum Computing
Equal superposition
|0i |0i |0i
Equal superposition state:
|bi=p1 X |ii N 1 i/solutions
1X | i=pN i |ii
= pN |ai+ pN |bi
MULT90063 Introduction to Quantum Computing
Equal Superposition
Consider the equal superposition:
1 pN 1 | i= pN |ai+ pN |bi
|ai solution
Non-solutions
1 sin ✓ = pN
MULT90063 Introduction to Quantum Computing
Effect of the Oracle
|0i |0i |0i
Apply the oracle
The marked state
MULT90063 Introduction to Quantum Computing
Geometric Effect of Oracle
|ai solution
Non-solutions
MULT90063 Introduction to Quantum Computing
Geometric Effect of Oracle
↵ |ai + |bi ! ↵ |ai + |bi
|ai solution
|bi Non-solutions
MULT90063 Introduction to Quantum Computing
Effect of inversion about the mean
The mean State
Inversion about the mean
The mean State
MULT90063 Introduction to Quantum Computing
Inversion about the mean
Similar to the oracle, inversion about the mean corresponds to a reflection. Now about equal superposition.
|ai solution
|bi Non-solutions
MULT90063 Introduction to Quantum Computing
Inversion about the mean
Similar to the oracle, inversion about the mean corresponds to a reflection. Now about equal superposition.
|ai solution
| ih | i ✓
|bi Non-solutions
MULT90063 Introduction to Quantum Computing
Inversion about the mean
|ai solution
| i | ih | i
|bi Non-solutions
| ih | i ✓
MULT90063 Introduction to Quantum Computing
Inversion about the mean
| i (2| i 2| ih | i) = (| i 2| ih | i)
|ai solution
2| i 2| ih | i
|bi Non-solutions
Reflection about the mean reflects around the equal superposition state
MULT90063 Introduction to Quantum Computing
Geometric Effect of both Oracle and Inversion
Combining both effects:
|ai solution
|bi Non-solutions
MULT90063 Introduction to Quantum Computing
Geometric Effect of both Oracle and Inversion
Combining both effects:
|ai solution
|bi Non-solutions
MULT90063 Introduction to Quantum Computing
Geometric Effect of both Oracle and Inversion
Combining both effects:
|ai solution
|bi Non-solutions
MULT90063 Introduction to Quantum Computing
Total effect of one Grover iteration
Product of two reflections is a rotation.
|ai solution
|bi Non-solutions
1 sin ✓ = pN
MULT90063 Introduction to Quantum Computing
Many Grover iterations
Product of two reflections is a rotation.
|ai solution
|bi Non-solutions
1 sin ✓ = pN
MULT90063 Introduction to Quantum Computing
How many iterations required?
For small angles,
1 sin ✓ = pN
After n iterations, we rotate to have only marked solutions:
(2n + 1)✓ = ⇡2 n ⇡ ⇡4 p N
The number of steps, n, required scales as O(√N), and not with N as it would classically.
This is a “polynomial” rather than an “exponential” speedup.
MULT90063 Introduction to Quantum Computing
Multiple Solutions
There can be more than one solution to a problem.
Apply the oracle
The M=2 marked states
MULT90063 Introduction to Quantum Computing
Geometric interpretation of Grover’s algorithm
|0i |0i |0i
A very useful basis:
|ai = pM i2soXlutions |ii
|bi=p 1 |ii N M i2/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.
Solutions! Non-solutions...
MULT90063 Introduction to Quantum Computing
Geometric Interpretation
| i=↵|ai+ |bi 1
Every state in Grover’s algorithm can be expressed as a superposition of these vectors
|bi Non-solutions
MULT90063 Introduction to Quantum Computing
Equal superposition
|0i |0i |0i
Equal superposition state:
1X | i=pN i |ii
| i=pN|ai+ pN |bi
1 |ai = pM
i2solutions
|bi=p 1 X |ii N M i2/solutions
MULT90063 Introduction to Quantum Computing
Equal Superposition
Consider the equal superposition:
pM pN M | i= pN |ai+ pN |bi
|ai solutions
|bi Non-solutions
pM sin✓= pN
MULT90063 Introduction to Quantum Computing
Effect of the Oracle
|0i |0i |0i
Apply the oracle
The marked state
MULT90063 Introduction to Quantum Computing
Geometric Effect of Oracle
|ai solutions
pM sin✓= pN
Non-solutions
MULT90063 Introduction to Quantum Computing
Geometric Effect of both Oracle and Inversion
Combining both effects:
|ai solutions
pM sin✓= pN
|bi Non-solutions
MULT90063 Introduction to Quantum Computing
Geometric Effect of both Oracle and Inversion
Combining both effects:
|ai solutions
pM sin✓= pN
|bi Non-solutions
MULT90063 Introduction to Quantum Computing
Total effect of one Grover iteration
Product of two reflections is a rotation.
|ai solutions
pM sin✓= pN
|bi Non-solutions
MULT90063 Introduction to Quantum Computing
Many Grover iterations
Product of two reflections is a rotation.
|ai solutions
|bi Non-solutions
pM sin✓= pN
MULT90063 Introduction to Quantum Computing
How many iterations required?
For small angles,
pM sin✓= pN
After n iterations, we rotate to have only marked solutions:
(2n + 1)✓ = ⇡2p ⇡N
Having multiple solutions is faster than searching for a single marked solution.
MULT90063 Introduction to Quantum Computing
Grover’s Algorithm
• Unordered search, find one marked item among many
• Classically, this requires N/2 uses of the oracle
• Quantum mechanically, requires only O(√N).
|0i |0i |0i |0i
Lov Grover
Inversion (I-2|0><0|)
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com