Quantum Programming Algorithms: Palsberg Jan 27, 2022
Quantum Programming, by Outline Algorithms: Grover; 100 minutes; Jan 27, 2022
Hook: Our next quantum algorithm is Grover’s algorithm. It solves a natural problem and does so faster on a quantum computer than we can ever do on a classical computer.
Copyright By PowCoder代写 加微信 powcoder
Purpose: Persuade you that you can understand this algorithm.
1. We will make sure that everybody understands the problem.
2. We will show how Grover’s algorithm iterates the application of a unitary matrix. 3. We will cover full details of why Grover’s algorithm works.
Transition to Body: Now let us talk about the problem that this algorithm solves.
Main Point 1: We will make sure that everybody understands the problem.
[Most of you have done the homework on solving the problem on a classical computer] [We can represent the black-box function in multiple ways]
[We can program the solution in any classical language]
Transition to MP2: Now let us look at how to solve the problem.
Main Point 2: We will show how Grover’s algorithm iterates the application of a unitary matrix. [First we need two particular unitary operations]
[Second we compose them in a particular way]
[Finally we iterate the use of the resulting matrix]
Transition to MP3: Now let us get into correctness.
Main Point 3: We will cover full details of why Grover’s algorithm works.
[We can define a subspace with two dimensions]
[Each iteration performs a rotation on the subspace]
[After some iterations, a measurement gives what we are looking for, with high probability]
Transition to Close: So there you have it.
Review: Grover’s algorithm iterates to set up for a measurement that will give a good outcome
with high probability.
Strong finish: Grover’s algorithm is a powerful indication that a quantum computer can be faster than a classical computer. We will see more examples of that in this course.
Call to action: Look for other natural problems that may be solvable on quantum computers.
Detailed presentation
Hook: Our next quantum algorithm is Grover’s algorithm. It solves a natural problem and does so faster on a quantum computer than we can ever do on a classical computer.
Purpose: Persuade you that you can understand this algorithm.
1. We will make sure that everybody understands the problem.
2. We will show how Grover’s algorithm iterates the application of a unitary matrix. 3. We will cover full details of why Grover’s algorithm works.
Transition to Body: Now let us talk about the problem that this algorithm solves. Main Point 1: We will make sure that everybody understands the problem.
[Most of you have done the homework on solving the problem on a classical computer] Here is the homework problem.
Grover’s problem:
Input: a function f : {0, 1}n → {0, 1}.
Output: 1 if there exists x ∈ {0, 1}n such that f (x) = 1, and 0 otherwise. Notation: {0, 1}n is the set of bit strings of length n.
The assignment:
On a classical computer, in a classical language of your choice (such as C, Java, Python, etc), program a solution to Grover’s problem. Treat the input function f as black box that you can call but cannot inspect in any way at all. Each solution will be code that includes one or more calls of f.
[We can represent the black-box function in multiple ways]
How do we keep the black-box function at an arms length such that we cannot get tempted to inspect it? In C we can use a function pointer. In Java we can use a lambda expression. In Python we can use an anonymous function. Other languages have similar constructs that will enable us to call the function, while giving us no way to inspect it.
[We can program the solution in any classical language]
You wrote the solutions to the homework in several languages. We need to make many calls to f: in the worst case, we need to try f on every bit string of length n. This means 2n calls to f.
Transition to MP2: Now let us look at how to solve the problem.
Main Point 2: We will show how Grover’s algorithm iterates the application of a unitary matrix.
[First we need two particular unitary operations]
Each of those operations map n qubits (plus helper qubits) to n qubits (plus helper qubits). If we
ignore the helper qubits, those operations behave as follows. We use x to range over {0,1}n. Zf |x⟩ = (−1)f (x) |x⟩
{−|x⟩ ifx=0n Z0|x⟩ = |x⟩ ifx̸=0n
[Second we compose them in a particular way] Define
G = −H⊗nZ0H⊗nZf [Finally we iterate the use of the resulting matrix]
Let X be a collection of n qubits that initially is |0n⟩. Grover’s algorithm is: 1. Apply H⊗n to X.
2. Repeat { apply G to X } O(√2n) times.
3. Measure X and output the result.
Let us try Grover’s algorithm on an example. Suppose n = 2. Let f : {0,1}2 → {0,1} be definedby: f(00)=0andf(01)=0andf(10)=0andf(11)=1.
Now we initialize two qubits to |00⟩. Now let us execute the algorithm. How many times should we iterate in Step 2? Turns out that the correct number of iterations is 1, as we will see later.
Here is a property of H⊗2 that will be useful later:
H⊗2 (|00⟩+|01⟩+|10⟩−|11⟩) = 12 ((|00⟩+|01⟩+|10⟩+|11⟩)+(|00⟩−|01⟩+|10⟩−|11⟩)+
(|00⟩ + |01⟩ − |10⟩ − |11⟩) − (|00⟩ − |01⟩ − |10⟩ + |11⟩)) = |00⟩ + |01⟩ + |10⟩ − |11⟩
Now we calculate Grover’s algorithm for the example:
G H⊗2 |00⟩
= G 21 (|00⟩+|01⟩+|10⟩+|11⟩)
= −H⊗2 = −H⊗2 = −H⊗2 = −H ⊗2 = −H ⊗2
Z H⊗2 Z 1 (|00⟩+|01⟩+|10⟩+|11⟩) 0f2
Z0 H⊗2 1 (|00⟩+|01⟩+|10⟩−|11⟩) 2
Z 1 (|00⟩+|01⟩+|10⟩−|11⟩) 02
1 (−|00⟩ + |01⟩ + |10⟩ − |11⟩) 2
12 (−2|00⟩ + (|00⟩ + |01⟩ + |10⟩ − |11⟩))
= −21 (−2 (12 (|00⟩ + |01⟩ + |10⟩ + |11⟩)) + (|00⟩ + |01⟩ + |10⟩ − |11⟩))
= −21(−2|11⟩)
In the fourth and seventh step, we used the above property of H⊗2. In conclusion, when we measure
we get 11 with probability 1. Thus, we found 11 after a single use of f. 4
Transition to MP3: Now let us get into correctness.
Main Point 3: We will cover full details of why Grover’s algorithm works.
[We can define a subspace with two dimensions] Define two sets of bit strings as follows:
A = {x∈{0,1}n |f(x)=1} B = {x∈{0,1}n |f(x)=0}
We can think of A as the Awesome bit strings and B as the Bad bit strings. For convenience, define
N = 2n a = |A| b = |B|
Notice that N = a+b.
Let us focus on the main case of (a ̸= 0∧b ̸= 0). Define
|A⟩ = √1 Σx∈A |x⟩ a
|B⟩ = √1 Σx∈B |x⟩ b
Lemma 1. |A⟩ and |B⟩ are orthogonal unit vectors.
[Each iteration performs a rotation on the subspace]
( 2a) 2√ab G|A⟩ = 1−N |A⟩− N |B⟩
2√ab ( 2b) G|B⟩= N|A⟩−1−N|B⟩
Proof. The proof has three main parts.
In the first part of the proof, define |h⟩ to be the state of X after Step 1 of the algorithm.
|h⟩ = H |0⟩ = √NΣx∈{0,1}n |x⟩ = N|A⟩+ N|B⟩
Notice that in the third step, the renormalization is correct:
(√ )2 (√ )2 a+b=a+b=a+b=1
In the second part of the proof, notice that we can write Z0 = I − 2|0n⟩⟨0n|
This is because Z0 is the matrix that looks almost entirely like the identity matrix but has a −1 (instead +1) in the top-left corner. The above way of writing Z0 enables us to calculate:
H⊗n Z0 H⊗n = H⊗n (I − 2|0n⟩⟨0n|) H⊗n = I − 2|h⟩⟨h|
HereweusedthatH† =H andthatif|ψ⟩=U|φ⟩,then⟨ψ|=⟨φ|U†.
In the third part of the proof, we consider the two equations stated in the lemma. We begin
with the equation for G|A⟩.
−H⊗n Z0 H⊗n Zf |A⟩ = (I − 2|h⟩⟨h|) |A⟩
= (I − 2|h⟩⟨h|) (−Zf ) |A⟩
= |A⟩ − 2⟨h|A⟩ |h⟩
=|A⟩−2a a|A⟩+b|B⟩ NNN
( 2a) 2√ab
= 1−N |A⟩− N |B⟩
In the third step, we use that we apply Zf to |A⟩, so for each vector in the sum for A, we have f(x) = 1, hence (−1)f(x) = −1.
We continue with the equation for G|B⟩.
G|B⟩ = −H⊗n Z0 H⊗n Zf |B⟩ = −(I − 2|h⟩⟨h|) Zf |B⟩
= −(I − 2|h⟩⟨h|) |B⟩
= −|B⟩ + 2⟨h|B⟩ |h⟩
=−|B⟩+2b a|A⟩+b|B⟩ NNN
2√ab ( 2b)
= N |A⟩− 1−N |B⟩
In the third step, we use that we apply Zf to |B⟩, so for each vector in the sum for B, we have f(x) = 0, hence (−1)f(x) = 1.
Lemma 2 shows that G maps the subspace spanned by A and B to itself. Indeed, if we put |B⟩ in the first row and first column, and we put |A⟩ in the second row and second column, we see that we can represent G by the matrix:
(√) −(1−2b) −2 ab
Define θ ∈ (0, π2 ) to be the angle that satisfies:
sinθ= Na and cosθ= Nb 6
2 ab 1−2a NN
Lemma 3. G causes a rotation by an angle 2θ in the space spanned by A and B. Proof. The following matrix causes a rotation of θ:
(cos θ − sin θ) Rθ = sinθ cosθ
Notice that
( )√√2(√)( √) cosθ −sinθ2 b − a b−a −2 ab −(1−2b) −2 ab
=√N√N=√N N = √N N sinθcosθ ab 2abb−a 2ab1−2a
In the second-to-last step we used b−a = −(a−b) = −((a−b+2b)−2b) = −((a+b)−2b) = −(N −2b) and b−a = (b−a+2a)−2a = (a+b)−2a = N −2a.
We conclude that M does two applications of Rθ so M causes a rotation that is twice the angle of the rotation caused by Rθ.
We can illustrate the effect of G as follows:
[After some iterations, a measurement gives what we are looking for, with high probability] After Step 1 of the algorithm, the qubits are in the state
|h⟩ = the state of the qubits is:
We are going for
Na |A⟩ = cosθ |B⟩ + sinθ |A⟩ cos((2k + 1)θ) |B⟩ + sin((2k + 1)θ) |A⟩
sin((2k+1)θ) ≈ 1 ⇐⇒ (2k+1)θ ≈ π2
⇐⇒ 2k+1≈ π 2θ
⇐⇒ k ≈ π − 1 4θ 2
We want to rotate until we are as close to |A⟩ as we can get. If we do k iterations in Step 2, then
Let us focus on the case of a = 1, that is, we are looking for a unique bit string. Then √√
−1 1 1 1 θ = sin N ≈ N = √N
k≈π−1≈ π−1=π√N−1 4θ 2 4√1 2 4 2
In the calculation of θ, in the second step (the one with ≈), we use that when y is close to 0, we have sin(y) ≈ y. Eventually, we will have to round k to the nearest integer.
In the example above, we have N = 22 = 4 so
k ≈ π√N−1 = π√4−1 = π−1 ≈ 1
This justifies why we iterated the use of G a single time in the example.
We can check that we have good a good estimate of k by calculating the probability that we
will measure and get a bit string x such that f(x) = 1:
| sin((2k + 1)θ) |2
≈ | sin((2(4 N−2)+1) √N )|2
= |sin(((2 N−1)+1) √N )|2
= |sin(2 N √N )|2
= |sin(π2)|2 = |1|2
We can repeat the algorithm and evaluate f on the output each time; this will find the unique x such that f(x) = 1 with high probability.
If a > 1, we can use the same algorithm as for a = 1, and if it is unsuccessful, then we can try larger and larger values of k. This turns out to be an effective strategy.
If a = 0, then we can use the same algorithm as for a > 1, and if after a while, nothing has been found, we can be confident in concluding that a = 0.
Transition to Close: So there you have it.
Review: Grover’s algorithm iterates to set up for a measurement that will give a good outcome
with high probability.
Strong finish: Grover’s algorithm is a powerful indication that a quantum computer can be faster than a classical computer. We will see more examples of that in this course.
Call to action: Look for other natural problems that may be solvable on quantum computers.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com