Quantum Programming Algorithms: Phase Estimation
Mar 8, 2022
Quantum Programming, by Outline Algorithms: Phase Estimation; 100 minutes; Mar 8, 2022
Copyright By PowCoder代写 加微信 powcoder
Hook: Shor’s algorithm factors integers in polynomial time with high probability. At the core of Shor’s algorithm is a subroutine for Phase Estimation. This subroutine uses the Quantum Fourier Transform, which can be executed efficiently on a quantum computer. How does this work?
Purpose: Persuade you that you can understand details of Phase Estimation.
1. Phase Estimation is about finding the eigenvalue of an eigenvector. 2. Phase Estimation uses the Quantum Fourier Transform.
3. The Quantum Fourier Transform can be implemented efficiently.
Transition to Body: Now let us recall how Phase Estimation plays a role in Shor’s algorithm.
Main Point 1: Phase Estimation is about finding the eigenvalue of an eigenvector. [The problem statement talks about finding the exponent of an eigenvalue] [Shor’s algorithm uses Phase Estimation as the only quantum subroutine] [The idea of Phase Estimation is iteration plus post-processing]
Transition to MP2: Now let us sketch the idea of Phase Estimation.
Main Point 2: Phase Estimation uses the Quantum Fourier Transform.
[The post-processing is done by the Quantum Fourier Transform]
[The post-processing works perfectly for eigenvalues of a particular form] [The post-processing works well for any eigenvalue]
Transition to MP3: Now let us us build a circuit for the Quantum Fourier Transform.
Main Point 3: The Quantum Fourier Transform can be implemented efficiently.
[The quantum version is exponentially faster than the classical version]
[The quantum circuit can be defined recursively]
[The quantum circuit uses a number of gates that is quadratic in the number of qubits]
Transition to Close: So there you have it.
Review: At the core of Shor’s algorithm is a subroutine for Phase Estimation, which, in turn,
uses the Quantum Fourier Transform.
Strong finish: When people talk about how quantum computing can get an exponential speed-up compared to classical computing, a key part of the picture is the Quantum Fourier Transform.
Call to action: Find other quantum algorithms that use the Quantum Fourier Transform.
Detailed Presentation
Hook: Shor’s algorithm factors integers in polynomial time with high probability. At the core of Shor’s algorithm is a subroutine for Phase Estimation. This subroutine uses the Quantum Fourier Transform, which can be executed efficiently on a quantum computer. How does this work?
Purpose: Persuade you that you can understand details of Phase Estimation.
1. Phase Estimation is about finding the eigenvalue of an eigenvector. 2. Phase Estimation uses the Quantum Fourier Transform.
3. The Quantum Fourier Transform can be implemented efficiently.
Transition to Body: Now let us recall how Phase Estimation plays a role in Shor’s algorithm. Main Point 1: Phase Estimation is about finding the eigenvalue of an eigenvector.
[The problem statement talks about finding the exponent of an eigenvalue]
Algorithm: Input: Output:
Phase Estimation.
A unitary operation U and an eigenvector |ψ⟩ of U, that is, U|ψ⟩ = e2πiθ|ψ⟩. θ.
[Shor’s algorithm uses Phase Estimation as the only quantum subroutine]
At the core of Shor’s algorithm is a subroutine for finding the order of an element in a group, which relies on Phase Estimation. We have this hierarchy of subroutines:
Integer Factorization
Shor’s Algorithm
Order Finding
1) Phase Estimation and 2) Continued Fractions Quantum Fourier Transform
which calls which calls which calls where (1) calls
Here, the quantum part of the algorithm lies in Phase Estimation and its use of the Quantum Fourier Transform.
[The idea of Phase Estimation is iteration plus post-processing]
Assume we have a circuit for the unitary operation U on n qubits. Suppose also that we have an integer m.
Define the following iterative unitary operation on m + n qubits: Λm(U) |k⟩ |φ⟩ = |k⟩ (Uk |φ⟩)
where k ∈ {0,…,2m−1}, written in binary. Intuitively, Λm(U) uses the first m qubits to determine how many times to apply U to the remaining n qubits.
Let |ψ⟩ be an eigenvector of U with eigenvalue e2πiθ and let us calculate: 2m −1
Λm(U) (H⊗m ⊗ I⊗n) |0m⟩ |ψ⟩
= Λm(U) 1 ∑ |k⟩|ψ⟩
= 1 ∑|k⟩(Uk|ψ⟩)
= 1 ∑|k⟩(e2πiθ)k|ψ⟩
= 1 ∑|k⟩e2πikθ|ψ⟩
The idea is to post-process the first m qubits and then measure them, with the goal of getting θ.
2πikθ (k=0 )
Transition to MP2: Now let us sketch the idea of Phase Estimation. Main Point 2: Phase Estimation uses the Quantum Fourier Transform.
[The post-processing is done by the Quantum Fourier Transform] Define
ω = e2πi/2m
ω |k⟩ † 1 ∑ −kj
QFT2m |j⟩ = 2m/2 QFT2m |k⟩ = 2m/2
Here QFT2m is the famous Discrete Fourier Transform, which we write as this matrix:
1 ω QFT2m = 1 1 ω2
ω2 ··· ω2m−1 ω4 ··· ω2(2m−1)
2m/2 . 1
ω2(2m−1) · · · 2m if j = l
. ω(2m−1)2
ω = 0 ifj̸=l
WeproveLemma1asfollows. Inthecaseofj=l,weusethatωk(j−l) =ω0 =1,sothesum has 2m elements, each of which is 1, for a total of 2m. In the case of j ̸= l, we first rearrange the exponents and then use the formula for a geometric series:
2m−1 2m−1 m ∑ k(j−l) ∑ (j−l) k 1−ω(j−l)2
ω = (ω)=1−ωj−l k=0 k=0
We see that
ω(j−l)2m = (ω2m )j−l = ((e2πi/2m )2m )j−l = (e2πi)j−l = ((eπi)2)j−l
= ((−1)2)j−l
In the first step, we rearrange the exponents; in the second step, we use the definition of ω; in the third step, we cancel out two exponents; in the fourth step, we rearrange the exponents; in the fifth step, we use Euler’s identity; and in the sixth step, we use (−1)2 = 1. So 1 − ω(j−l)2m = 1 − 1 = 0, which means that the sum stated in the lemma equals 0. This completes the proof of Lemma 1.
We can check that QFT2m QFT2m = I:
( 2m−1 ) † 1∑jk
QFT2m QFT2m |j⟩
= QFT2m 2m/2
( 2m−1 ) 1 ∑ −kl
= 2m/2 ω 2m/2 ω |l⟩ k=0 ( l=0)
2m −1 2m −1
1 ∑ jk ∑ −kl
=2m ω ω|l⟩ k=0( l=0 )
2m −1 2m −1
1 ∑ ∑ k(j−l)
=2m ω|l⟩ l=0 k=0
= 12m|j⟩ 2m
In the first step, we use the definition of QFT2m; in the second step, we use the definition of
QFT2m; in the third step, we use the distributive law; in the fourth step, we rearrange the sums and use a product law for exponents; in the fifth step, we use Lemma 1; and in the sixth step, we cancel out two constants.
Now we can define
PhaseEstimationm U |ψ⟩ = (QFT2m ⊗ I ) Λm(U) (H ⊗ I ) |0 ⟩ |ψ⟩
†⊗n ⊗m⊗nm which uses the inverse of the Quantum Fourier transform to post-process.
[The post-processing works perfectly for eigenvalues of a particular form] Let us do a calculation of PhaseEstimationm U |ψ⟩ in the case where θ = j/2m.
PhaseEstimationm U |ψ⟩ =
†⊗n ⊗m⊗nm (QFT2m ⊗ I ) Λm(U) (H ⊗ I ) |0 ⟩ |ψ⟩
† ⊗n 1 ∑ 2πikθ = (QFT2m ⊗I ) 2m/2 e
|k⟩ |ψ⟩ (k=0 )
† ⊗n 1 ∑ 2πik(j/2m)
= (QFT2m ⊗I ) 2m/2 e |k⟩ |ψ⟩ ( k=0 )
† ⊗n 1 ∑ kj
= (QFT2m ⊗I ) 2m/2
Now we can measure the first m qubits, get j with probability 1, and use θ = j/2m to get θ.
[The post-processing works well for any eigenvalue]
Let us return to the general case, which we pick up after the second step in the above calculation:
PhaseEstimationm U |ψ⟩
(2m−1 ) † ⊗n 1 ∑ 2πikθ
=(QFT2m⊗I)2m/2 e |k⟩|ψ⟩ (k=0 )
† ⊗n 1 ∑ k2mθ
= (QFT2m ⊗I ) 2m/2 ω |k⟩ |ψ⟩
k=0 2m −1 2m −1
1 ∑ k2mθ 1 ∑ −kj
= 2m/2 ω 2m/2 ω |j⟩ |ψ⟩
k=0 j=0
2m −1 2m −1 1∑∑k(2mθ−j)
=2m ω|j⟩|ψ⟩ k=0 j=0
2m−1 ( 2m−1 ) ∑ 1 ∑ k(2mθ−j)
From the above we see that the probability pj of measuring the first m qubits and getting j is:
= 2m ω j=0 k=0
2 m − 1 2 2 m − 1 2 1 ∑ k(2mθ−j) 1 ∑ (2mθ−j)k
pj=2m ω =22m (ω ) k=0 k=0
Likeaboveweseethatforθ=j/2m,wehavepj =1. Forθ̸=j/2m,weusetheformulafora geometric series and get:
(2mθ−j) 2m 2 (2mθ−j) 2m 2 (2mθ−j) 2m 2 p = 1 1−(ω ) = 1 (ω ) −1 = 1 |(ω ) −1|
j 22m 1−ω(2mθ−j) 22m ω(2mθ−j) −1 22m |ω(2mθ−j) −1|2
The best cases of θ are θ = j/2m. Now let us consider some good cases of θ, namely those are
within ε of the best cases:
θ= j+ε(mod1)
Here we still hope to measure j, which will give us an approximation of θ that is within ε of θ.
Notice that |ε| ≤ 1 means that the first m bits of θ will be good. In other words, we get θ with 2m+1
m bits of precision.
Notice that 2mθ − j = 2mε. From this and the above equation for pj we get:
|(ω(2mθ−j))2m − 1|2 |ω(2mθ−j) − 1|2
1 |(ω2mε)2m − 1|2 1 |(ω22mε) − 1|2 = 22m |ω2mε − 1|2 = 22m |(ω2mε) − 1|2
|(e2πi2mε) − 1| = |(e2πi2m|ε|) − 1| 7
a = |(ω22mε) − 1| =
b = |(ω2mε) − 1| = |(e2πiε) − 1| = |(e2πi|ε|) − 1|
In each case, the idea of the second step is to think of (e2πi2m|ε|) and (e2πi|ε|) and 1 as complex numbers on the unit circle in the complex plane. This means that each of a and b expresses the distance between two points on the unit circle.
Now we can write pj as follows:
Let us go for a lower bound on pj by finding a lower bound on a and an upper bound on b.
For the lower bound on a, consider this picture:
The angle from the x-axis to the point (e2πi2m|ε|) is 2π2m|ε|. Thus, the minor arc length from 1 to (e2πi2m|ε|) is 2π2m|ε|. Recall that
2π2m|ε| ≤ 2π2m 1 = π 2m+1
1 a2 22m b2
We have the the ratio between the minor arc length and the chord length is at most π2 , that is: 2π2m|ε| ≤ π
From this we get
For the upper bound on b, consider this picture:
The angle from the x-axis to the point (e2πi|ε|) is 2π|ε|. Thus, the minor arc length from 1 to (e2πi|ε|) is 2π|ε|. Recall that
|ε| ≤ 2π|ε| ≤ 2π 1
We have the the ratio between the chord length and the minor arc length is at least 1, that is:
From this we get
Now we can use the two bounds on a and b to get a bound on pj:
1 a2 1 (4|ε|2m)2 4 pj=22mb2≥22m(2π|ε|)2 =π2>0.4
This means that the probability of getting a θ with m correct significant bits is at least 0.4.
Now let us consider some bad cases of θ, namely those are further away than ε from the best
α ≤ |ε| < 1 2m 2
θ= j+ε(mod1) 2m
Here α is a positive number that we can choose later. We still hope to measure j, but it will give us an approximation of θ that is further away than ε from the best cases. Notice that α ≤ |ε|
This time we will use that a ≤ 2 and, by reasoning similar to how we derived a bound on a
means that at least one the first m bits of θ will be bad. above, we get b ≥ 4|ε|. Now we calculate
1a2 122 122 1 pj = 22mb2 ≤ 22m(4|ε|)2 ≤ 22m(4α)2 = 4α2
For example, for α = 1, we have pj ≤ 14 . For a worse approximation, which means a larger value of
α, pj is upper-bounded by a smaller probability. 9
Transition to MP3: Now let us us build a circuit for the Quantum Fourier Transform. Main Point 3: The Quantum Fourier Transform can be implemented efficiently.
[The quantum version is exponentially faster than the classical version]
A milestone in Fourier analysis was the 1965 paper by Cooley and Tukey, which presented the Fast Fourier Transform (FFT) algorithm. The FFT algorithm computes the Discrete Fourier Transform in O(n log n) time. The FFT algorithm has become a cornerstone of many disciplines within Electrical Engineering and Computer Science. The FFT paper has been cited 15,640 times, according to Google Scholar.
The FFT paper is amazing and the O(nlogn) run time is blazingly fast, yet the quantum Fourier transform is exponentially faster. The quantum Fourier transform is due to Shor (1994).
[The quantum circuit can be defined recursively]
For convenience, we will define QF T
reverse order. Thus the goal is to define QFT2m that satisfies:
For any positive integer N, define:
w2m |k0 k1 ··· km−1⟩
QFT2m |jm−1 ··· j0⟩ = √2m We will give a recursive definition.
, which is like QFT but outputs the measurement in 2m 2m
First the base case of m = 1:
ωN = e2πi/N QF T 2 | j ⟩ = H | j ⟩
Now for any m ≥ 1: here is the circuit QFT2m+1 :
Now let us show that the definition satisfies the stated property. We proceed by induction on m.
Inthebasecaseofm=1,wehave2m =2andω2 =e2πi/2 =−1(byEuler’sidentity)sothe property reads:
QFT2 |j0⟩ = √ wj0k |k0⟩
= √1 ((−1)(j0 0) |0⟩ + (−1)(j0 1) |1⟩) 2
= √1 (|0⟩ + (−1)j0 |1⟩) 2
In the induction step, suppose that the property holds for some m ≥ 0. Define:
j′ = jm jm−1 ··· j1 = ⌊j/2⌋
k′ =km−1km−2···k0 =k−km2m
Now we can write:
|j⟩ = |j′⟩ |j0⟩ and the induction hypothesis can be written
Now we calculate
QFT2m+1 |jm jm−1 ··· j0⟩ =
H(j0) C(j0,j1,ω4) ...C(j0,jm−1,ω2m) C(j0,jm,ω2m+1) QFT2m |j′⟩ |j0⟩
12m−1′′ ′∑jk′′′
QFT2m |j ⟩ |j0⟩ = √2m
w2m |k0 k1 ··· km−1⟩ |j0⟩
= H(j0)C(j0,j1,ω4) ...C(j0,jm−1,ω2m)C(j0,jm,ω2m+1)
√2m = H(j)√
w2m |k0 k1 ··· km−1⟩ |j0⟩
2m −1 1∑j′k′′′ ′
∑ j ′ k ′ j 0 k ′ j 0 k ′
j 0 k m′ − 1 2 2m+1 2 4
wm w 0 wm1 ···w | k 0′ k 1′ · · · k m′ − 1 ⟩ | j 0 ⟩
k′=0 2m −1
1 ∑ jk′ ′ ′ ′
= H(j0) √2m w2m+1 |k0 k1 · · · km−1⟩ |j0⟩
w2m+1 |k0 k1 · · · km−1⟩ ((−1) m 0 |km⟩) w2m+1 |k0 k1 ··· km⟩
k′=0 2m−1 1
1∑∑jk′′′′ kj
k′=0 km=0 2m+1 −1
In the fourth step, we use
j ′ k ′ j 0 k ′ j 0 k ′ j 0 k m′ − 1 j k ′ wmw0wm1···w =w
22m+12 4 2m+1 which we won’t prove here. In the fifth step, we use
In the sixth step, we use
In the first substep, we use that j is even or odd depending only on whether j0 is even or odd. In
the second substep, we use Euler’s identity. In the third substep, we use the definition of ω2m+1. [The quantum circuit uses a number of gates that is quadratic in the number of qubits]
Let g(m) be the number of gates in the circuit QFT2m+1 . We have g(1) = 1
g(m+1) = g(m)+(m+1) The solution to those equations is:
Thus we need O(m2) gates to compute the quantum Fourier transform on m qubits, that is a vector of size 2m. This is exponentially better than the classical Fast Fourier Transform, which needs O(2m log(2m)) = O(2m) time.
Transition to Close: So there you have it.
Review: At the core of Shor’s algorithm is a subroutine for Phase Estimation, which, in turn,
uses the Quantum Fourier Transform.
Strong finish: When people talk about how quantum computing can get an exponential speed-up compared to classical computing, a key part of the picture is the Quantum Fourier Transform.
Call to action: Find other quantum algorithms that use the Quantum Fourier Transform.
((−1)kmj0 |km⟩) = √2 (((−1)0 j0 |0⟩) + ((−1)1 j0 |1⟩)) = H(j0) |j0⟩
kmj0 kmj πi kmj j(2mkm) = (−1) = (e ) = ω2m+1
j = 2m(m+1) = O(m)
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com