Quantum phase estimation algorithm is a quantum algorithm used as a subroutine in several applications such as order finding, factoring and discrete logarithm.
This algorithm makes it possible to estimate the phase that a unitary transformation adds to one of its eigenvectors.
Let U be a unitary operator that operates on m qubits with an eigenvector
|
ψ
⟩
, such that
U
|
ψ
⟩
=
e
2
π
i
θ
|
ψ
⟩
,
0
≤
θ
<
1
.
We would like to find the eigenvalue
e
2
π
i
θ
of
|
ψ
⟩
, which in this case is equivalent to estimating the phase
θ
, to a finite level of precision.
The input consists of two registers (namely, two parts): the upper
n
qubits comprise the first register, and the lower
m
qubits are the second register.
The initial state of the system is
|
0
⟩
⊗
n
|
ψ
⟩
. After applying n-bit Hadamard gate operation
H
⊗
n
on the first register, the state of the first register can be described as
1
2
n
/
2
(
|
0
⟩
+
|
1
⟩
)
⊗
n
.
U
is a unitary operator and
|
ψ
⟩
is an eigenvector of
U
such that
U
|
ψ
⟩
=
e
2
π
i
θ
|
ψ
⟩
, thus
U
2
j
|
ψ
⟩
=
U
⋯
U
⏟
2
j
|
ψ
⟩
=
e
2
π
i
2
j
θ
|
ψ
⟩
.
C
−
U
is a controlled-U gate which applies the unitary operator
U
on the second register only if its corresponding control bit (from the first register) is
|
1
⟩
.
After applying all the
n
controlled operations
C
−
U
2
j
with
0
≤
j
≤
n
−
1
, as seen in the figure, the state of the first register can be described as
1
2
n
/
2
(
|
0
⟩
+
e
2
π
i
2
n
−
1
θ
|
1
⟩
)
⏟
1
s
t
q
u
b
i
t
⊗
⋯
⊗
(
|
0
⟩
+
e
2
π
i
2
1
θ
|
1
⟩
)
⏟
n
−
1
t
h
q
u
b
i
t
⊗
(
|
0
⟩
+
e
2
π
i
2
0
θ
|
1
⟩
)
⏟
n
t
h
q
u
b
i
t
=
1
2
n
/
2
∑
k
=
0
2
n
−
1
e
2
π
i
θ
k
|
k
⟩
.
Applying inverse Quantum Fourier transform on
1
2
n
/
2
∑
k
=
0
2
n
−
1
e
2
π
i
θ
k
|
k
⟩
yields
1
2
n
∑
x
=
0
2
n
−
1
∑
k
=
0
2
n
−
1
e
2
π
i
θ
k
e
−
2
π
i
k
x
2
n
|
x
⟩
=
1
2
n
∑
x
=
0
2
n
−
1
∑
k
=
0
2
n
−
1
e
−
2
π
i
k
2
n
(
x
−
2
n
θ
)
|
x
⟩
.
The state of both registers together is
1
2
n
∑
x
=
0
2
n
−
1
∑
k
=
0
2
n
−
1
e
−
2
π
i
k
2
n
(
x
−
2
n
θ
)
|
x
⟩
⊗
|
ψ
⟩
.
We can approximate the value of
θ
(
0
≤
θ
<
1
) by rounding
2
n
θ
to the nearest integer
a
. This means that
2
n
θ
=
a
+
2
n
δ
, where
a
is the nearest integer to
2
n
θ
, and the difference
2
n
δ
satisfies
0
≤
|
2
n
δ
|
≤
1
2
.
We can now write the state of the first and second register in the following way:
1
2
n
∑
x
=
0
2
n
−
1
∑
k
=
0
2
n
−
1
e
−
2
π
i
k
2
n
(
x
−
a
)
e
2
π
i
δ
k
|
x
⟩
⊗
|
ψ
⟩
.
Performing a measurement in the computational basis on the first register yields the result
|
a
⟩
with probability
P
r
(
a
)
=
|
⟨
a
|
1
2
n
∑
x
=
0
2
n
−
1
∑
k
=
0
2
n
−
1
e
−
2
π
i
k
2
n
(
x
−
a
)
e
2
π
i
δ
k
|
x
⟩
⏟
S
t
a
t
e
o
f
t
h
e
f
i
r
s
t
r
e
g
i
s
t
e
r
|
2
=
1
2
2
n
|
∑
k
=
0
2
n
−
1
e
2
π
i
δ
k
|
2
=
{
1
if
δ
=
0
1
2
2
n
|
1
−
e
2
π
i
2
n
δ
1
−
e
2
π
i
δ
|
2
if
δ
≠
0
.
If the approximation is precise (
δ
=
0
, thus
a
=
2
n
θ
), then
P
r
(
a
)
=
1
. In this case, we always measure the accurate value of the phase. The state of the system after the measurement is
|
2
n
θ
⟩
⊗
|
ψ
⟩
.
Otherwise, since
0
≤
|
δ
|
≤
2
−
(
n
+
1
)
, the series above converges and we measure the correct approximated value of
θ
(namely, we measure
|
a
⟩
) with some probability larger than 0, as analyzed below.
We discuss here only the case
δ
≠
0
. We prove that in this case, the algorithm yields the correct result (
a
) with a probability
P
r
(
a
)
≥
4
π
2
≈
0.405
.
First, recall the trigonometric identity
|
1
−
e
2
i
x
|
=
|
e
i
x
|
|
e
−
i
x
−
e
i
x
|
=
⏟
|
e
i
x
|
=
1
2
|
sin
(
x
)
|
.
Second, within
δ
's range (
0
≤
|
δ
|
≤
2
−
(
n
+
1
)
), the inequalities
|
2
⋅
2
n
δ
|
≤
|
sin
(
π
2
n
δ
)
|
and
|
sin
(
π
δ
)
|
≤
|
π
δ
|
hold for all
δ
.
Following the above
1
2
2
n
|
1
−
e
2
π
i
2
n
δ
1
−
e
2
π
i
δ
|
2
=
1
2
2
n
|
e
π
i
2
n
δ
e
π
i
δ
⋅
e
−
π
i
2
n
δ
−
e
π
i
2
n
δ
e
−
π
i
δ
−
e
π
i
δ
|
2
=
1
2
2
n
|
e
π
i
2
n
δ
|
2
|
e
π
i
δ
|
2
2
|
sin
(
π
2
n
δ
)
|
2
2
|
sin
(
π
δ
)
|
2
≥
1
2
2
n
|
2
⋅
2
n
δ
π
δ
|
2
=
4
π
2
.
This result shows that we will measure the best n-bit estimate of
θ
with high probability. Provided a large number of qubits
n
, this probability will become closer to 1.