User:Omrika/sandbox/QIP/Quantum phase estimation

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.

The problem

Let U be a unitary operator that operates on m qubits with an eigenvector $\left|\psi \right\rangle$, such that $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\pi i\theta }$of $|\psi \rangle$, which in this case is equivalent to estimating the phase $\theta$, to a finite level of precision.

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}$, the state of the first register can be described as ${\frac {1}{2^{n/2}}}(|0\rangle +|1\rangle )^{\otimes n}$.

Apply controlled unitary operations

As mentioned above, if $U$ is a unitary operator and $|\psi \rangle$ is an eigenvector of $U$ then $U\left|\psi \right\rangle =e^{2\pi i\theta }\left|\psi \right\rangle$, thus $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$ 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, the state of the first register can be described as ${\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$.

Apply inverse Quantum Fourier transform

Applying inverse Quantum Fourier transform on ${\frac {1}{2^{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$.

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 would like to approximate $\theta$'s value by rounding $2^{n}\theta \ ,\ 0\leq \theta <1$ to the nearest integer $a$.

Consider $2^{n}\theta =a+2^{n}\delta$ where $a$ is an integer and the difference is $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 ${\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

$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 $\left(\delta =0\right)$ then $Pr(a)=1$ meaning we will measure the accurate value of the phase with probability of one. The state of the system after the measurement is $|\theta \rangle \otimes |\psi \rangle$.

Otherwise, since $0\leq |\delta |\leq 2^{-(n+1)}$ the series above converges and we measure the correct approximated value of $\theta$ with some probability larger than 0.

Analysis

In case we only approximate $\theta$'s value $\left(\delta \neq 0\right)$, it is guaranteed that the algorithm will yield the correct result with a probability $Pr(a)\geq {\frac {4}{\pi ^{2}}}$.

First, recall the trigonometric identity $\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 $\delta$'s range $\left(0\leq |\delta |\leq 2^{-(n+1)}\right)$, the inequalities $\vert 2^{n}\delta \vert \leq \vert \sin(\pi 2^{n}\delta )\vert$ and $\vert \sin(\pi \delta )\vert \leq \vert \pi \delta \vert$ holds for all $\delta$.

Following the above ${\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}}}$.

See also

• Shor's algorithm
• Quantum counting algorithm

References

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