estimation
One version of Shor’s algorithm is based on phase estimation. This appli-
cation of the quantum Fourier transform is used to estimate the eigenvalue of
a unitary operator, which is a phase:
ˆ
U|ui = e
iθ
|ui; θ = 2πφ (8.63)
where φ is a fraction.
As a preliminary to this algorithm, let’s look at a toy version. Suppose you
are given U and an eigenstate |ui. We have seen that the circuit of Figure 7.14
simulates a measurement of U.
|0i
H
•
H
|ui
U
|ui
Here,
1
√
2
|0i + |1i
⊗ |ui →
1
√
2
|0i + e
2πiφ
|1i
⊗ |ui. (8.64)
If φ were a single bit, then you can see that the output is 0 if φ = 0.0 and 1
if φ = 0.1. This circuit thus gives us the value in one run. But in general φ
will be several bits long. A measurement of the upper register in the H basis
will yield a 0 or 1 with probabilities cos
2
πφ and sin
2
πφ. A statistically large
number of measurements will allow us to recover φ from the counts. But this
is an inefficient method.
Note that the H transform on the upper register is the one-bit Fourier
transform. In order to estimate φ to more bits of accuracy, we must have
a qubit for each significant figure of φ and then perform an inverse Fourier
transform, as shown in the circuit of Figure 8.13.
|0i
H
. . .
•
QF T
−1
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
t qubits |0i
H
•
. . .
|0i
H
•
. . .
|ui /
n
U
U
2
. . .
U
2
t−1
|ui
FIGURE 8.13: Circuit for phase estimation.
Imagine φ upto t bits as
φ = 0.φ
1
φ
2
···φ
t
=
φ
0
2
t
, φ
0
= φ
t
φ
t−1
···φ
1
. (8.65)
Quantum Algorithms 167
Then we start with t working qubits in the input register, and use them to
control gates of the form U
2
k
. After the control gates, the output on the k
th
line is
1
√
2
(|0i + |1i) −→
1
√
2
|0i + e
2πi2
k
φ
|1i
(8.66)
=
1
√
2
|0i + e
2πi(0.φ
1
φ
2
···φ
k
)
|1i
. (8.67)
You can see that just before the QFT gate, the state of the upper register is
1
√
2
t
|0i + e
2πiφ
|1i
⊗
|0i + e
4πiφ
|1i
⊗ . . . ⊗
|0i + e
2πi.2
t
φ
|1i
(8.68)
=
1
√
2
t
2
t
−1
X
k=0
e
2πiφk
|ki (8.69)
This is just the QFT mod 2
t
of φ
0
and an inverse Fourier transform will give
you φ
0
exact to t significant figures.
Leave a Reply