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 1-qubit states, and |ξi is a general d-dimensional 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 black-box, 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
|xi|v
ϕ
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.