Quantum Programming Algorithms: Bernstein- Palsberg Jan 20, 2022
Quantum Programming, by Outline Algorithms: Bernstein-Vazirani; 100 minutes; Jan 20, 2022
Hook: Our second quantum algorithm is the Bernstein-Vazirani 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 cover full details of how and why the algorithm works. 3. We will show an additional algorithm that uses similar ideas.
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 cover full details of how and why the algorithm works. [We will mix classical and quantum computing]
[The structure of the quantum part is the same as in Deutsch-Josza]
[We can use some of the lemmas about Deutsch-Josza]
Transition to MP3: Now let us apply our knowledge to a different case.
Main Point 3: We will show an additional algorithm that uses similar ideas. [The problem is a special case of Grover’s problem]
[The solution uses a different circuit]
[The reasoning uses some of the same lemmas that we proved earlier]
Transition to Close: So there you have it.
Review: The Bernstein-Vazirani algorithm combines classical and quantum computing.
Strong finish: The Bernstein-Vazirani algorithm is the second indication that a quantum com- puter 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 second quantum algorithm is the Bernstein-Vazirani 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 cover full details of how and why the algorithm works. 3. We will show an additional algorithm that uses similar ideas.
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.
The Bernstein-Vazirani problem:
Input: a function f : {0, 1}n → {0, 1}.
Assumption: f(x)=(a·x)⊕b.
Output: a,b.
Notation: {0, 1}n is the set of bit strings of length n, a is an unknown bit string of length n, · is dot product mod 2, ⊕ is addition mod 2, and b is an unknown single bit.
The assignment:
On a classical computer, in a classical language of your choice (such as C, Java, Python, etc), program solutions to the Bernstein-Vazirani 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.
Notice that if a = 00…0, then f is constant. Additionally, if a ̸= 00…0, then f is balanced. So, solving Bernstein-Vazirani is a lot like solving Deutsch-Josza.
[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 several calls to f: a total of n + 1 calls to f are needed. The reason is that we need to call f(00…0) = b, and then we need to do n calls to determine a, one call for each bit of a.
Transition to MP2: Now let us look at how to solve the problem.
Main Point 2: We will cover full details of how and why the algorithm works.
[We will mix classical and quantum computing]
First do a classical call f (00 . . . 0) = b. Then use a quantum circuit to determine a.
[The structure of the quantum part is the same as in Deutsch-Josza]
[We can use some of the lemmas about Deutsch-Josza]
After the second round of uses of H, we know that the state of the first n qubits is:
1 Σx∈{0,1}n Σy∈{0,1}n (−1)(x·y)⊕f (x) |y⟩ 2n
= 1 Σx∈{0,1}n Σy∈{0,1}n (−1)(x·y)⊕((a·x)⊕b) |y⟩ 2n
= 1 (−1)b Σx∈{0,1}n Σy∈{0,1}n (−1)(a⊕y)·x |y⟩ 2n
= (−1)b |a⟩
In the third step, we rely on this calculation:
The amplitude of |a⟩
= 1 (−1)b Σx∈{0,1}n (−1)(a⊕a)·x
= 1 (−1)b Σx∈{0,1}n 1
So, when we measure the first n qubits, we will observe |a⟩ with probability |(−1)b|2 = 12 = 1.
Transition to MP3: Now let us apply our knowledge to a different case. Main Point 3: We will show an additional algorithm that uses similar ideas.
[The problem is a special case of Grover’s problem]
Suppose we are given f : {0, 1}2 → {0, 1} and we are promised that f returns 1 for a single input and that f returns 0 otherwise. Our goal is to determine which input makes f return 1. In classical computing, we have to make three calls of f to solve the problem.
Grover’s problem generalizes this situation to a function f of n bits. [The solution uses a different circuit]
Above, the diagram uses Bf instead of Uf . The box with the “?” denotes the following matrix:
−1 1 1 1 1 1 −1 1 1 21 1 −1 1
[The reasoning uses some of the same lemmas that we proved earlier]
Let us give names to four particular superpositions:
12 (−|00⟩ + |01⟩ + |10⟩ + |11⟩) 12 (|00⟩ − |01⟩ + |10⟩ + |11⟩)
12 (|00⟩ + |01⟩ − |10⟩ + |11⟩)
12 (|00⟩ + |01⟩ + |10⟩ − |11⟩)
Lemma1.∀c,d∈{0,1}: U(φcd)=|cd⟩.
Proof. The proof has four cases. We will show one of the cases; the others are similar.
−1 1 1 1 −1 4 1
U(φ ) = 11 −1 1 1( 11) = 10 = 0 = |00⟩
00 211−1121400 111−1 1 0 0
Theorem 2. The algorithm works.
Proof. The initial state of the three qubits is |001⟩.
After using the three H, followed by the use of Uf, followed by the use of U, the state of the
three qubits
(U ⊗I)◦Uf ◦(H ⊗H ⊗H) |001⟩
(U⊗I)◦Uf |++−⟩
(U ⊗ I) ◦ U 1(|00−⟩ + |01−⟩ + |10−⟩ + |11−⟩)
(U ⊗ I ) 12 ((−1)f (00) |00−⟩ + (−1)f (01) |01−⟩ + (−1)f (10) |10−⟩ + (−1)f (11) |11−⟩)
(U ⊗ I ) 12 (((−1)f (00) |00⟩ + (−1)f (01) |01⟩ + (−1)f (10) |10⟩ + (−1)f (11) |11⟩) ⊗ |−⟩) |cd⟩|−⟩ where f (cd) = 1
In the third step, we used the phase-kickback lemma. In the fifth step, we used Lemma 1. Now we measure the first two qubits; with probability |1|2 = 1, we get cd where f(cd) = 1.
Transition to Close: So there you have it.
Review: The Bernstein-Vazirani algorithm combines classical and quantum computing.
Strong finish: The Bernstein-Vazirani algorithm is the second indication that a quantum com- puter 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