Quantum Programming Algorithms: Deutsch- Palsberg Jan 18, 2022
Quantum Programming, by Outline Algorithms: Deutsch-Jozsa; 100 minutes; Jan 18, 2022
Hook: Our first quantum algorithm is the Deutsch-Jozsa algorithm. It solves an artificial prob- lem, but 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 begin with a simple version called Deutsch’s algorithm.
3. We will cover full details of how and why the Deutsch-Jozsa 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 a solution on a quantum computer.
Main Point 2: We will begin with a simple version called Deutsch’s algorithm. [We make the black-box computation reversible]
[We construct a circuit that puts each of two qubits in superposition]
[The reasoning about correctness uncovers the phase-kickback trick]
Transition to MP3: Now we are ready for the full solution.
Main Point 3: We will cover full details of how and why the Deutsch-Jozsa algorithm works. [We can make a black box with n inputs reversible]
[The structure is the same as in Deutsch’s algorithm]
[The reasoning about the phase-kickback trick is more complicated with n bits]
Transition to Close: So there you have it.
Review: The Deutsch-Jozsa algorithm makes a single call to the black-box function, which works
because it tries all combinations of |0⟩ and |1⟩ at the same time.
Strong finish: The Deutsch-Jozsa algorithm is the first 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: Learn how to reason about correctness by getting good at calculating with Dirac notation.
Detailed presentation
Hook: Our first quantum algorithm is the Deutsch-Jozsa algorithm. It solves an artificial prob- lem, but 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 begin with a simple version called Deutsch’s algorithm.
3. We will cover full details of how and why the Deutsch-Jozsa 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.
The Deutsch-Jozsa problem:
Input: a function f : {0, 1}n → {0, 1}.
Assumption: f is either constant or balanced.
Output: 0 if f is constant; 1 if f is balanced.
Notation: {0, 1} is the set of bits, and {0, 1}n is the set of bit strings of length n. Terminology:
Constant: f is constant if either f always outputs 0 or f always outputs 1. Balanced: f is balanced if f outputs 0 on exactly half of the inputs.
The assignment:
On a classical computer, in a classical language of your choice (such as C, Java, Python, etc), program solutions to the Deutsch-Jozsa 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]
For the case of n = 1, we have that f can be one of four functions, here called f0, f1, f2, f3:
Input f0 f1 f2 f3 00011 10101
Notice that f0 and f3 are constant, while f1 and f2 are balanced.
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.
If we want an exact solution, we need 2n−1 + 1 queries in the worst case. If we can tolerate that we get the right answer with high probability, we can randomly choose k inputs; evaluate f on each of the k inputs, and if the outputs are all the same, then output constant, and otherwise output balanced. If the function really is constant, this method is correct every time, and if the function is balanced, this method will be wrong (and answer constant) with probability 2−(k−1).
Transition to MP2: Now let us look at a solution on a quantum computer. Main Point 2: We will begin with a simple version called Deutsch’s algorithm.
[We make the black-box computation reversible]
Here we bring in the technique from the previous lecture. Specifically, if we have an operation f : {0,1}→{0,1}
then we can represent it as an invertible operation Uf :
Uf : Qubit⊗2 → Qubit⊗2
Uf |x⟩|b⟩ = |x⟩|b ⊕ f (x)⟩
We use Qubit⊗n to denote the tensor product of n vectors spaces of single qubits. We use ⊕ to denote addition (mod 2).
Let us check that for every one of the four possibilities of f, we have that Uf is a unitary function.
1000 0 1 0 0 0010
1000 0 1 0 0 0001
0100 1000 0010
0100 U= 1000 f3 0001
Notice that each of the four matrices above is a permutation matrix: every entry is 0 or 1, every column has a single 1, and every row has a single 1. Every permutation matrix is unitary.
[We construct a circuit that puts each of two qubits in superposition]
If we measure 0, we conclude that the function is constant, and otherwise it is balanced. 4
[The reasoning about correctness uncovers the phase-kickback trick]
Lemma 1. ∀a ∈ {0,1} : |0⊕a⟩−|1⊕a⟩ = (−1)a (|0⟩−|1⟩).
Proof. Let us try both possibilities for a in turn. For a = 0, we have:
left-hand side: right-hand side:
For a = 1, we have: left-hand side:
right-hand side:
|0 ⊕ a⟩ − |1 ⊕ a⟩ (−1)a (|0⟩ − |1⟩)
|0 ⊕ a⟩ − |1 ⊕ a⟩ (−1)a (|0⟩ − |1⟩)
= |0⊕0⟩−|1⊕0⟩ = = (−1)0 (|0⟩ − |1⟩) =
= |0⊕1⟩−|1⊕1⟩ = = (−1)1 (|0⟩ − |1⟩) =
|0⟩ − |1⟩ |0⟩ − |1⟩
|1⟩ − |0⟩ |1⟩ − |0⟩
Lemma 2 (Phase kickback). ∀x ∈ {0,1}n : Uf|x⟩|−⟩ = (−1)f(x)|x⟩|−⟩. Proof.
In second step, we used |−⟩ = √1 2
√1 (Uf |x⟩|0⟩ − Uf |x⟩|1⟩)
√1 (|x⟩|f (x)⟩ − |x⟩|1 ⊕ f (x)⟩) 2
|x⟩⊗ √1 (|0⊕f(x)⟩−|1⊕f(x)⟩) 2
|x⟩⊗√1 (−1)f(x) (|0⟩−|1⟩) 2
(−1)f(x) |x⟩⊗√1 (|0⟩−|1⟩) 2
(−1)f (x) |x⟩|−⟩
(|0⟩ − |1⟩). In the fourth step, we used Lemma 1.
Lemma3.∀a∈{0,1}:H √1|0⟩+√1(−1)a|1⟩ =|a⟩. 22
Proof. Let us try both possibilities for a in turn. For a = 0, we have:
(11)(11)(11)
H √ |0⟩+√ (−1)a|1⟩ = H √ |0⟩+√ (−1)0|1⟩ = H √ |0⟩+√ |1⟩ = H|+⟩
222222 = |0⟩ = |a⟩
For a = 1, we have:
(11)(11)(11)
H √ |0⟩+√ (−1)a|1⟩ = H √ |0⟩+√ (−1)1|1⟩ = H √ |0⟩−√ |1⟩ = H|−⟩
222222 = |1⟩ = |a⟩
Theorem 4. Deutsch’s algorithm is correct.
Proof. Initially, the state of the two qubits is |01⟩.
After the two uses of H, followed by the use of Uf, followed by the single use of H, the state of
the two qubits is:
(H ⊗I)◦Uf ◦(H ⊗H)(|01⟩) = (H⊗I)◦Uf (|+⟩⊗|−⟩)
⊗I)◦Uf (√1 (|0⟩+|1⟩)⊗|−⟩) 2
= (H ⊗ I) ◦ Uf (√1 (Σx∈{0,1}|x⟩) ⊗ |−⟩)
= (H ⊗ I)√1 Σx∈{0,1} (−1)f(x)|x⟩ ⊗ |−⟩ 2
= (H ⊗ I)(√1 ((−1)f(0)|0⟩ + (−1)f(1)|1⟩)) ⊗ |−⟩ 2
= (H ⊗ I )((−1)f (0) √1 (|0⟩ + (−1)f (0)⊕f (1) |1⟩)) ⊗ |−⟩ 2
= (H ⊗ I)((−1)f(0) (√1 |0⟩ + √1 (−1)f(0)⊕f(1)|1⟩)) ⊗ |−⟩ 22
= ((−1)f (0) |f (0) ⊕ f (1)⟩) ⊗ |−⟩
In the fourth step, we use Lemma 2. In the last step, we use Lemma 3. So, if we measure the first
qubit, we will get f (0) ⊕ f (1) with probability
|((−1)f(0)|2 = 12 = 1
Notice that
f(0)⊕f(1) =
The grand conclusion is that if we measure 0, we output “constant”, and if we measure 1, we output
“balanced”.
Transition to MP3: Now we are ready for the full solution.
Main Point 3: We will cover full details of how and why the Deutsch-Jozsa algorithm works.
[We can make a black box with n inputs reversible]
The above construction of permutation matrices to support reversible computing generalizes to functions f from n bits to m bits.
[The structure is the same as in Deutsch’s algorithm]
Like in the case of Deutsch’s algorithm, we use a single call to Uf .
0 f is constant
1 f is balanced
The idea is that we get n bits from the measurements. If all those bits are 0, we conclude that the function is constant, and otherwise it is balanced. Notice that we call Uf just once.
[The reasoning about the phase-kickback trick is more complicated with n bits] Lemma 5. ∀x ∈ {0, 1} : H|x⟩ = √1 Σy∈{0,1} (−1)x·y |y⟩.
Proof. The left-hand side:
Here, we use Lemma 3. The right-hand side:
H|x⟩ = √1|0⟩+√1(−1)x|1⟩ 22
= √1 ((−1)x·0 |0⟩ + (−1)x·1 |1⟩) = √1 (|0⟩ + (−1)x|1⟩) We see that the two sides are equal.
We use H⊗n to denote H ⊗H ⊗… ⊗H (n occurrences of H). If x and y are bit-strings of the same length, then x · y denotes the dot-product (mod 2) of x and y.
Lemma 6. H⊗n|x⟩ = √1 Σ n (−1)x·y |y⟩ 2n y∈{0,1}
√1 Σy∈{0,1} (−1)x·y |y⟩ 222
H|x1⟩ ⊗ … ⊗ H|xn⟩
= √2n Σy1∈{0,1} …Σyn∈{0,1} (−1)
= √2n Σy∈{0,1}n (−1) |y⟩
(1)(1) √2 Σy1∈{0,1} (−1)x1·y1 |y1⟩ ⊗ . . . ⊗ √2 Σyn∈{0,1} (−1)xn·yn |yn⟩
|y1⟩… |yn⟩
In the second step, we use Lemma 5 a total of n times. Theorem 7. The Deutsch-Jozsa algorithm is correct.
Proof. Initially, the state of the n + 1 qubits is |00 . . . 01⟩.
After the n+1 uses of H followed by the use of Uf followed by the n uses of H, the state of
the n + 1 qubits is:
(H⊗n ⊗ I) ◦ Uf ◦ H⊗n+1(|00…01⟩) ⊗n 1
= (H ⊗I)◦Uf √2n Σx∈{0,1}n |x⟩⊗|−⟩
|x⟩ ⊗ |−⟩ √2n Σx∈{0,1}n (−1) ( √2n Σy∈{0,1}n (−1)
⊗n 1 f(x) (H ⊗ I) √2n Σx∈{0,1}n (−1)
1 Σx∈{0,1}n Σy∈{0,1}n (−1)x·y⊕f (x) |y⟩ ⊗ |−⟩
|y⟩) ⊗ |−⟩
In the first step, we used Lemma 6; in the second step, we used Lemma 2; and in the third step, we used Lemma 6.
Now we measure the first n qubits. Turns out, the state |00 . . . 0−⟩ is important:
We conclude that if f is constant, a measurement of the first n qubits will give us 00…0 with probability 1.
Second, suppose f is balanced.
the amplitude of |00…0−⟩ = 0
The reason is that (−1)f(x) will be 1 half of the time and -1 half of time; they will cancel either other out. We conclude that if f is balanced, a measurement of the first n qubits will give us 00 . . . 0 with probability 0
The grand conclusion is that if we measure 00…0, we output “constant”, and if we measure anything else, we output “balanced”.
Transition to Close: So there you have it.
Review: The Deutsch-Jozsa algorithm makes a single call to the black-box function, which works
because it tries all combinations of |0⟩ and |1⟩ at the same time.
Strong finish: The Deutsch-Jozsa algorithm is the first 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: Learn how to reason about correctness by getting good at calculating with Dirac notation.
the amplitude of |00 . . . 0−⟩ Let us consider the two cases of f in turn.
First, suppose f is constant.
the amplitude of |00 . . . 0−⟩ =
Σx∈{0,1}n (−1)f (x)
if f(x) = 0 for all x
−1 iff(x)=1forallx
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com