5Phase estimation algorithm
III Quantum Computation
5 Phase estimation algorithm
We now describe a quantum algorithm that estimates the eigenvalues of a unitary
operator. Suppose we are given a unitary operator
U
and an eigenstate
v
ϕ
i
.
Then we can write
U V
ϕ
i = e
2πiϕ
v
ϕ
i
with 0 ≤ ϕ < 1. Our objective is to estimate ϕ to n binary bits of precision:
ϕ ≈ 0.i
1
i
2
i
3
···i
n
=
i
1
2
+
i
2
2
2
+ ··· +
i
n
2
n
.
We will need the controlled U
k
gate c  U
k
for integers k, defined by
c  U
k
0iξi = 0iξi
c  U
k
1iξi = 1iU
k
ξi,
where 0i, 1i are 1qubit states, and ξi is a general ddimensional register.
Note that we have
U
k
v
ϕ
i = e
2πikϕ
v
ϕ
i,
and we have
c  U
k
= (c  U)
k
,
Note that if we are given
U
as a formula or a circuit description, then we can
readily implement c
 U
by adding control to each gate. However, if
U
is a
quantum blackbox, then we need further information. For example, it suffices to
have an eigenstate
αi
with known eigenvalue
e
iα
. However, we will not bother
ourselves with that, and just assume that we can indeed implement it.
In fact, we will use a “generalized” controlled U given by
xiξi 7→ xiU
x
ξi,
where xi has n qubits. We will make this from c  U
k
= (c  U)
k
as follows: for
x = x
n−1
···x
1
x
0
= x
0
+ 2
1
x
1
+ 2
2
x
2
+ ··· + 2
n−1
x
n−1
,
we write c  U
k
i
for the controlled U
k
controlled by i. Then we just construct
U
2
0
0
U
2
1
1
···U
2
n−1
n−1
.
Now if input ξi = v
ϕ
i, then we get
e
2πiϕx
xiv
ϕ
i.
To do phase estimation, we superpose the above over all
x
= 0
,
1
,
2
, ··· ,
2
n−1
and use ξi = v
ϕ
i. So we construct our starting state by
si = H ⊗ ··· ⊗ H 0 ···0i =
1
√
2
n
X
all x
xi.
Now if we apply the generalized control U, we obtain
1
√
2
n
X
x
e
2πiϕx
xi
!
 {z }
Ai
v
ψ
i.
Finally, we apply the inverse Fourier transform
QFT
−1
2
n
to
Ai
and measure to
see y
0
, y
1
, ··· , y
n−1
on lines 0, 1, ··· , n − 1. Then we simply output
0.y
0
y
1
···y
n−1
=
y
0
2
+
y
1
4
+ ··· +
y
n−1
2
n
=
y
0
y
1
···y
n−1
2
n
.
as the estimate of ϕ.
Why does this work? Suppose
ϕ
actually only had
n
binary digits. Then we
have
ϕ = 0.z
0
z
1
······z
n−1
=
z
2
n
,
where z ∈ Z
2
n
. Then we have
Ai =
1
√
2
n
X
x
2
2πixz/2
n
xi,
which is the Fourier transform of
zi
. So the inverse Fourier transform of
Ai
is
exactly Zi and we get ϕ exactly with certainty.
If ϕ has more than n bits, say
ϕ = 0.z
0
z
1
···z
n−1
z
n
z
n+1
··· ,
then we have
Theorem.
If the measurements in the above algorithm give
y
0
, y
1
, ··· , y
n
and
we output
θ = 0.y
0
y
1
···y
n−1
,
then
(i) The probability that θ is ϕ to n digits is at least
4
π
2
.
(ii) The probability that θ − ϕ ≥ ε is at most O(1/(2
n
ε)).
The proofs are rather boring and easy algebra.
So for any fixed desired accuracy
ε
, the probability to fail to get
ϕ
to this
accuracy falls exponentially with n.
Note that if c
 U
2
k
is implemented as (c
 U
)
2
k
, then the algorithm would
need
1 + 2 + 4 + ··· + 2
n−1
= 2
n−1
many c
 U
gates. But for some special
U
’s, this c
 U
2
k
can be implemented in
polynomial time in k.
For example, in Kitaev’s factoring algorithm, for
hcf
(
a, N
) = 1, we will use
the function
U : mi 7→ am mod Ni.
Then we have
U
2
k
mi =
a
2
k
m
E
,
which we can implement by repeated squaring.
Now what if we didn’t have an eigenstate to being with? If instead of
v
ϕ
i
,
we used a general input state ξi, then we can write
ξi =
X
j
c
j
v
ϕ
j
,
where
U
v
ϕ
j
= e
2πiϕ
j
v
ϕ
j
.
Then in the phase estimation algorithm, just before the final measurement, we
have managed to get ourselves
0 ···0iξi →
X
j
c
j
ϕ
j
i
v
ϕ
j
.
Then when we measure, we get one of the
ϕ
j
’s (or an approximation of it) with
probability
c
j

2
. Note that this is not some average of them. Of course, we
don’t know which one we got, but we still get some meaningful answer.
Quantum counting
An application of this is the quantum counting problem. Given
f
:
B
n
→ B
with k good x’s, we want to estimate the number k.
Recall the Grove iteration operator
Q
G
is rotation through 2
θ
in a 2
dimensional plane spanned by
ψ
0
i =
1
√
2
n
X
x
xi
and its good projection, and θ is given by
sin θ ≈ θ =
r
k
N
.
Now the eigenvalues of this rotation in the plane are
e
2iθ
, e
−2iθ
.
So either eigenvalue will suffice to get k.
We will equivalently write
e
i2θ
= e
2πiϕ
with
0 ≤ ϕ < 1.
Then ±2θ is equivalent to ϕ or 1 − ϕ, where ϕ is small.
Now we don’t have an eigenstate, but we can start with any state in the
plane,
ψ
0
i
. We then do phase estimation with it. We will then get either
ϕ
or
1
− ϕ
with some probabilities, but we don’t mind which one we get, since we
can obtain one from the other, and we can tell them apart because ϕ is small.