Quantum phase estimation algorithm is a quantum algorithm used as a subroutine in several applications such as order finding , factoring and discrete logarithm .[ 1] : 131
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
|
ψ
⟩
{\displaystyle \left|\psi \right\rangle }
, such that
U
|
ψ
⟩
=
e
2
π
i
θ
|
ψ
⟩
,
0
≤
θ
<
1
{\displaystyle U\left|\psi \right\rangle =e^{2\pi i\theta }\left|\psi \right\rangle ,0\leq \theta <1}
.
We would like to find the eigenvalue
e
2
π
i
θ
{\displaystyle e^{2\pi i\theta }}
of
|
ψ
⟩
{\displaystyle |\psi \rangle }
, which in this case is equivalent to estimating the phase
θ
{\displaystyle \theta }
, to a finite level of precision.
Quantum phase estimation circuit
The input consists of two registers (namely, two parts): the upper
n
{\displaystyle n}
qubits comprise the first register , and the lower
m
{\displaystyle m}
qubits are the second register .
Create superposition [ edit ]
The initial state of the system is
|
0
⟩
⊗
n
|
ψ
⟩
{\displaystyle |0\rangle ^{\otimes n}|\psi \rangle }
. After applying n-bit Hadamard gate operation
H
⊗
n
{\displaystyle H^{\otimes n}}
, the state of the first register can be described as
1
2
n
/
2
(
|
0
⟩
+
|
1
⟩
)
⊗
n
{\displaystyle {\frac {1}{2^{n/2}}}(|0\rangle +|1\rangle )^{\otimes n}}
.
Apply controlled unitary operations [ edit ]
As mentioned above, if
U
{\displaystyle U}
is a unitary operator and
|
ψ
⟩
{\displaystyle |\psi \rangle }
is an eigenvector of
U
{\displaystyle U}
then
U
|
ψ
⟩
=
e
2
π
i
θ
|
ψ
⟩
{\displaystyle U\left|\psi \right\rangle =e^{2\pi i\theta }\left|\psi \right\rangle }
, thus
U
2
j
|
ψ
⟩
=
U
⋯
U
⏟
2
j
|
ψ
⟩
=
e
2
π
i
2
j
θ
|
ψ
⟩
{\displaystyle U^{2^{j}}\left|\psi \right\rangle =\underbrace {U\cdots U} _{2^{j}}|\psi \rangle =e^{2\pi i2^{j}\theta }\left|\psi \right\rangle }
.
C
−
U
{\displaystyle C-U}
is a controlled-U gate which applies the unitary operator
U
{\displaystyle U}
on the second register only if its corresponding control bit (from the first register) is
|
1
⟩
{\displaystyle |1\rangle }
.
After applying all the
n
{\displaystyle n}
controlled operations
C
−
U
2
j
{\displaystyle C-U^{2^{j}}}
with
0
≤
j
≤
n
−
1
{\displaystyle 0\leq j\leq 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
⟩
{\displaystyle {\frac {1}{2^{n/2}}}\underbrace {(|0\rangle +e^{2\pi i2^{n-1}\theta }|1\rangle )} _{1^{st}\ qubit}\otimes \cdots \otimes \underbrace {(|0\rangle +e^{2\pi i2^{1}\theta }|1\rangle )} _{n-1^{th}\ qubit}\otimes \underbrace {(|0\rangle +e^{2\pi i2^{0}\theta }|1\rangle )} _{n^{th}\ qubit}={\frac {1}{2^{n/2}}}\sum _{k=0}^{2^{n}-1}e^{2\pi i\theta k}|k\rangle }
.
Applying inverse Quantum Fourier transform on
1
2
n
/
2
∑
k
=
0
2
n
−
1
e
2
π
i
θ
k
|
k
⟩
{\displaystyle {\frac {1}{2^{n/2}}}\sum _{k=0}^{2^{n}-1}e^{2\pi i\theta k}|k\rangle }
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
⟩
{\displaystyle {\frac {1}{2^{n}}}\sum _{x=0}^{2^{n}-1}\sum _{k=0}^{2^{n}-1}e^{2\pi i\theta k}e^{\frac {-2\pi ikx}{2^{n}}}|x\rangle }
.
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
⟩
⊗
|
ψ
⟩
{\displaystyle {\frac {1}{2^{n}}}\sum _{x=0}^{2^{n}-1}\sum _{k=0}^{2^{n}-1}e^{-{\frac {2\pi ik}{2^{n}}}\left(x-2^{n}\theta \right)}|x\rangle \otimes |\psi \rangle }
.
Phase approximation representation [ edit ]
We would like to approximate
θ
{\displaystyle \theta }
's value by rounding
2
n
θ
,
0
≤
θ
<
1
{\displaystyle 2^{n}\theta \ ,\ 0\leq \theta <1}
to the nearest integer
a
{\displaystyle a}
.
Consider
2
n
θ
=
a
+
2
n
δ
{\displaystyle 2^{n}\theta =a+2^{n}\delta }
where
a
{\displaystyle a}
is an integer and the difference is
2
n
δ
,
0
≤
|
2
n
δ
|
≤
2
−
1
{\displaystyle 2^{n}\delta \ ,\ 0\leq |2^{n}\delta |\leq 2^{-1}}
.
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
⟩
⊗
|
ψ
⟩
{\displaystyle {\frac {1}{2^{n}}}\sum _{x=0}^{2^{n}-1}\sum _{k=0}^{2^{n}-1}e^{{\frac {-2\pi ik}{2^{n}}}\left(x-a\right)}e^{2\pi i\delta k}|x\rangle \otimes |\psi \rangle }
.
Performing a measurement in the computational basis on the first register yields
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
{\displaystyle Pr(a)={\Bigg \vert }\langle a|\underbrace {{\frac {1}{2^{n}}}\sum _{x=0}^{2^{n}-1}\sum _{k=0}^{2^{n}-1}e^{{\frac {-2\pi ik}{2^{n}}}\left(x-a\right)}e^{2\pi i\delta k}|x\rangle } _{State\ of\ the\ first\ register}{\Bigg \vert }^{2}={\frac {1}{2^{2n}}}{\Bigg \vert }\sum _{k=0}^{2^{n}-1}e^{2\pi i\delta k}{\Bigg \vert }^{2}={\begin{cases}\displaystyle 1&{\text{if }}\delta =0\\\displaystyle {\frac {1}{2^{2n}}}{\Bigg \vert }{\frac {1-{e^{2\pi i2^{n}\delta }}}{1-{e^{2\pi i\delta }}}}{\Bigg \vert }^{2}&{\text{if }}\delta \neq 0\end{cases}}}
.
If the approximation is precise
(
δ
=
0
)
{\displaystyle \left(\delta =0\right)}
then
P
r
(
a
)
=
1
{\displaystyle Pr(a)=1}
meaning we will measure the accurate value of the phase with probability of one.[ 2] : 157 [ 3] : 347
The state of the system after the measurement is
|
θ
⟩
⊗
|
ψ
⟩
{\displaystyle |\theta \rangle \otimes |\psi \rangle }
. [ 1] : 223
Otherwise, since
0
≤
|
δ
|
≤
2
−
(
n
+
1
)
{\displaystyle 0\leq |\delta |\leq 2^{-(n+1)}}
the series above converges and we measure the correct approximated value of
θ
{\displaystyle \theta }
with some probability larger than 0.
In case we only approximate
θ
{\displaystyle \theta }
's value
(
δ
≠
0
)
{\displaystyle \left(\delta \neq 0\right)}
, it is guaranteed that the algorithm will yield the correct result with a probability
P
r
(
a
)
≥
4
π
2
{\displaystyle Pr(a)\geq {\frac {4}{\pi ^{2}}}}
.
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
)
|
{\displaystyle \vert 1-e^{2ix}\vert =\vert e^{ix}\vert \vert e^{-ix}-e^{ix}\vert \underbrace {=} _{\vert e^{ix}\vert =1}2\vert \sin(x)\vert }
.
Second, within
δ
{\displaystyle \delta }
's range
(
0
≤
|
δ
|
≤
2
−
(
n
+
1
)
)
{\displaystyle \left(0\leq |\delta |\leq 2^{-(n+1)}\right)}
, the inequalities
|
2
n
δ
|
≤
|
sin
(
π
2
n
δ
)
|
{\displaystyle \vert 2^{n}\delta \vert \leq \vert \sin(\pi 2^{n}\delta )\vert }
and
|
sin
(
π
δ
)
|
≤
|
π
δ
|
{\displaystyle \vert \sin(\pi \delta )\vert \leq \vert \pi \delta \vert }
holds for all
δ
{\displaystyle \delta }
.
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
δ
|
=
1
2
2
n
|
e
π
i
2
n
δ
|
|
e
π
i
δ
|
2
|
sin
(
π
2
n
δ
)
|
2
|
sin
(
π
δ
)
|
≥
1
2
2
n
|
2
⋅
2
n
δ
π
δ
|
2
=
4
π
2
{\displaystyle {\frac {1}{2^{2n}}}{\Bigg \vert }{\frac {1-{e^{2\pi i2^{n}\delta }}}{1-{e^{2\pi i\delta }}}}{\Bigg \vert }^{2}={\frac {1}{2^{2n}}}{\Bigg \vert }{\frac {e^{\pi i2^{n}\delta }}{e^{\pi i\delta }}}\cdot {\frac {e^{-\pi i2^{n}\delta }-e^{\pi i2^{n}\delta }}{e^{-\pi i\delta }-e^{\pi i\delta }}}{\Bigg \vert }={\frac {1}{2^{2n}}}{\frac {\vert e^{\pi i2^{n}\delta }\vert }{\vert e^{\pi i\delta }\vert }}{\frac {2\vert \sin \left(\pi 2^{n}\delta \right)\vert }{2\vert \sin \left(\pi \delta \right)\vert }}\geq {\frac {1}{2^{2n}}}{\Bigg \vert }{\frac {2\cdot 2^{n}\delta }{\pi \delta }}{\Bigg \vert }^{2}={\frac {4}{\pi ^{2}}}}
.
[ 2] : 157 [ 3] : 348
^ a b Chuang, Michael A. Nielsen & Isaac L. (2001). Quantum computation and quantum information (Repr. ed.). Cambridge [u.a.]: Cambridge Univ. Press. ISBN 978-0521635035 .
^ a b Benenti, Guiliano; Strini, Giulio Casati, Giuliano (2004). Principles of quantum computation and information (Reprinted. ed.). New Jersey [u.a.]: World Scientific. ISBN 978-9812388582 . {{cite book }}
: CS1 maint: multiple names: authors list (link )
^ a b Cleve, R.; Ekert, A.; Macchiavello, C.; Mosca, M. (8 January 1998). "Quantum algorithms revisited". Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences . 454 (1969). doi :10.1098/rspa.1998.0164 .
Kitaev, A. Yu. (1995). "Quantum measurements and the Abelian Stabilizer Problem". arXiv :quant-ph/9511026 .