Quantum phase estimation algorithm

The Quantum phase estimation algorithm (also referred to as quantum eigenvalue estimation algorithm), is a quantum algorithm to estimate the phase (or eigenvalue) of an eigenvector of a unitary operator. More precisely, given a unitary matrix $U$ and a quantum state $|\psi \rangle$ such that $U|\psi \rangle =e^{2\pi i\theta }|\psi \rangle$, the algorithm estimates the value of $\theta$ with high probability within additive error $\varepsilon$, using $O(1/\varepsilon )$ controlled-U operations.

Phase estimation is frequently used as a subroutine in other quantum algorithms, such as Shor's algorithm and the quantum algorithm for linear systems of equations.

The problem

Let U be a unitary operator that operates on m qubits with an eigenvector $|\psi \rangle ,$ such that $U|\psi \rangle =e^{2\pi i\theta }\left|\psi \right\rangle ,0\leq \theta <1$.

We would like to find the eigenvalue $e^{2\pi i\theta }$of $|\psi \rangle$, which in this case is equivalent to estimating the phase $\theta$, to a finite level of precision. We can write the eigenvalue in the form $e^{2\pi i\theta }$ because U is a unitary operator over a complex vector space, so its eigenvalues must be complex numbers with absolute value 1.

The algorithm

Quantum phase estimation circuit

Setup

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.

Create superposition

The initial state of the system is $|0\rangle ^{\otimes n}|\psi \rangle$. After applying n-bit Hadamard gate operation $H^{\otimes n}$ on the first register, the state of the first register can be described as

${\frac {1}{2^{\frac {n}{2}}}}(|0\rangle +|1\rangle )^{\otimes n}$.

Apply controlled unitary operations

Let $U$ be a unitary operator with eigenvector $|\psi \rangle$ such that $U|\psi \rangle =e^{2\pi i\theta }|\psi \rangle ,$ thus

$U^{2^{j}}|\psi \rangle =U^{2^{j}-1}U|\psi \rangle =U^{2^{j}-1}e^{2\pi i\theta }|\psi \rangle =\cdots =e^{2\pi i2^{j}\theta }|\psi \rangle$.

$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\rangle$.

After applying all the $n$ controlled operations $C-U^{2^{j}}$ with $0\leq j\leq n-1,$ as seen in the figure, and using $|0\rangle \otimes |\psi \rangle +|1\rangle \otimes e^{2\pi i\theta }|\psi \rangle =(|0\rangle +e^{2\pi i\theta }|1\rangle )\otimes |\psi \rangle$, the state of the first register can be described as

${\frac {1}{2^{\frac {n}{2}}}}\underbrace {\left(|0\rangle +e^{2\pi i2^{n-1}\theta }|1\rangle \right)} _{1^{st}\ qubit}\otimes \cdots \otimes \underbrace {\left(|0\rangle +e^{2\pi i2^{1}\theta }|1\rangle \right)} _{n-1^{th}\ qubit}\otimes \underbrace {\left(|0\rangle +e^{2\pi i2^{0}\theta }|1\rangle \right)} _{n^{th}\ qubit}={\frac {1}{2^{\frac {n}{2}}}}\sum _{k=0}^{2^{n}-1}e^{2\pi i\theta k}|k\rangle ,$

where $|k\rangle$ denotes the binary representation of $k$.

Apply inverse Quantum Fourier transform

Applying inverse Quantum Fourier transform on

${\frac {1}{2^{\frac {n}{2}}}}\sum _{k=0}^{2^{n}-1}e^{2\pi i\theta k}|k\rangle$

yields

${\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 ={\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 .$

The state of both registers together is

${\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

We can approximate the value of $\theta \in [0,1]$ by rounding $2^{n}\theta$ to the nearest integer. This means that $2^{n}\theta =a+2^{n}\delta ,$ where $a$ is the nearest integer to $2^{n}\theta ,$ and the difference $2^{n}\delta$ satisfies $0\leqslant |2^{n}\delta |\leqslant {\tfrac {1}{2}}$.

We can now write the state of the first and second register in the following way:

${\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 .$

Measurement

Performing a measurement in the computational basis on the first register yields the result $|a\rangle$ with probability

$\Pr(a)=\left|\left\langle a\underbrace {\left|{\frac {1}{2^{n}}}\sum _{x=0}^{2^{n}-1}\sum _{k=0}^{2^{n}-1}e^{{\frac {-2\pi ik}{2^{n}}}(x-a)}e^{2\pi i\delta k}\right|} _{\text{State of the first register}}x\right\rangle \right|^{2}={\frac {1}{2^{2n}}}\left|\sum _{k=0}^{2^{n}-1}e^{2\pi i\delta k}\right|^{2}={\begin{cases}1&\delta =0\\&\\{\frac {1}{2^{2n}}}\left|{\frac {1-{e^{2\pi i2^{n}\delta }}}{1-{e^{2\pi i\delta }}}}\right|^{2}&\delta \neq 0\end{cases}}$

For $\delta =0$ the approximation is precise, thus $a=2^{n}\theta$ and $\Pr(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}\theta \rangle \otimes |\psi \rangle$.

For $\delta \neq 0$ since $|\delta |\leqslant {\tfrac {1}{2^{n+1}}}$ the algorithm yields the correct result with probability $\Pr(a)\geqslant {\frac {4}{\pi ^{2}}}\approx 0.405$. We prove this as follows:

${\begin{aligned}\Pr(a)&={\frac {1}{2^{2n}}}\left|{\frac {1-{e^{2\pi i2^{n}\delta }}}{1-{e^{2\pi i\delta }}}}\right|^{2}&&{\text{for }}\delta \neq 0\\[6pt]&={\frac {1}{2^{2n}}}\left|{\frac {2\sin \left(\pi 2^{n}\delta \right)}{2\sin(\pi \delta )}}\right|^{2}&&\left|1-e^{2ix}\right|^{2}=4\left|\sin(x)\right|^{2}\\[6pt]&={\frac {1}{2^{2n}}}{\frac {\left|\sin \left(\pi 2^{n}\delta \right)\right|^{2}}{|\sin(\pi \delta )|^{2}}}\\[6pt]&\geqslant {\frac {1}{2^{2n}}}{\frac {\left|\sin \left(\pi 2^{n}\delta \right)\right|^{2}}{|\pi \delta |^{2}}}&&|\sin(\pi \delta )|\leqslant |\pi \delta |{\text{ for }}|\delta |\leqslant {\frac {1}{2^{n+1}}}\\[6pt]&\geqslant {\frac {1}{2^{2n}}}{\frac {|2\cdot 2^{n}\delta |^{2}}{|\pi \delta |^{2}}}&&|2\cdot 2^{n}\delta |\leqslant |\sin(\pi 2^{n}\delta )|{\text{ for }}|\delta |\leqslant {\frac {1}{2^{n+1}}}\\[6pt]&={\frac {4}{\pi ^{2}}}\end{aligned}}$

This result shows that we will measure the best n-bit estimate of $\theta$ with high probability. By increasing the number of qubits by $O(\log(1/\epsilon ))$ and ignoring those last qubits we can increase the probability to $1-\epsilon$.

See also

• Shor's algorithm
• Quantum counting algorithm

References

• Kitaev, A. Yu. (1995). "Quantum measurements and the Abelian Stabilizer Problem". arXiv:quant-ph/9511026.