In quantum computing, 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(\log(1/\varepsilon)) qubits (without counting the ones used to encode the eigenvector state) and O(1/\varepsilon) controlled-U operations.
The algorithm was initially introduced by Alexei Kitaev in 1995.
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
500px|thumb|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 becomes:
\frac{1}{2^{\frac{n}{2}}}(|0\rangle + |1\rangle)^{\otimes n}|\psi\rangle.
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 i 2^{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.
Assuming for the sake of clarity that the controlled gates are applied sequentially, after applying  C-U^{2^{0}} to the n^{th}   qubit of the first register and the second register, the state becomes
\frac{1}{2^{\frac{1}{2}}}  \underbrace{ \left (|0\rangle|\psi \rangle + |1\rangle e^{2\pi i 2^{0} \theta}|\psi\rangle \right )}_ {n^{th} \ qubit \ and \ second \ register}  \otimes  \frac{1}{2^{\frac{n-1}{2}}}  \underbrace{ \left (|0\rangle + |1\rangle \right )^{\otimes^{n-1}}} _{qubits \ 1^{st} \ to \ n-1^{th}} = \frac{1}{2^{\frac{1}{2}}} \left (|0\rangle|\psi \rangle + e^{2\pi i 2^{0} \theta} |1\rangle |\psi\rangle \right ) \otimes  \frac{1}{2^{\frac{n-1}{2}}} \left (|0\rangle + |1\rangle \right )^{\otimes^{n-1}}
= \frac{1}{2^{\frac{1}{2}}} \left (|0\rangle + e^{2\pi i 2^{0} \theta} |1\rangle \right ) |\psi\rangle \otimes \frac{1}{2^{\frac{n-1}{2}}} \left (|0\rangle + |1\rangle \right )^{\otimes^{n-1}} = \frac{1}{2^{\frac{n}{2}}}  \underbrace{ \left (|0\rangle + e^{2\pi i 2^{0} \theta} |1\rangle \right )} _{n^{th} \ qubit} \otimes \left (|0\rangle + |1\rangle \right )^{\otimes^{n-1}} |\psi\rangle ,
where we use:
|0\rangle |\psi\rangle + |1\rangle \otimes e^{2\pi i 2^{j} \theta} |\psi\rangle  =(|0\rangle + e^{2\pi i 2^{j} \theta} |1\rangle) |\psi\rangle, \ \forall j .
After applying all the remaining n-1 controlled operations C-U^{2^{j}} with 1 \leq j \leq n-1, as seen in the figure, the state of the first register can be described as
\frac{1}{2^{\frac{n}{2}}} \underbrace{ \left (|0\rangle + e^{2\pi i 2^{n-1} \theta}|1\rangle \right )}_{1^{st} \ qubit} \otimes \cdots \otimes \underbrace{\left (|0\rangle + e^{2\pi i 2^1 \theta}|1\rangle \right )}_{n-1^{th} \ qubit} \otimes\underbrace{\left (|0\rangle + e^{2\pi i 2^{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, i.e. it's the k^{th}  computational basis, and the state of the second register is left physically unchanged at |\psi \rangle  .
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^{\frac{n}{2}}}\sum_{k=0}^{2^n - 1} e^{2\pi i \theta k} \frac{1}{2^{\frac{n}{2}}}\sum_{x=0}^{2^n - 1} e^{\frac{-2\pi i kx}{2^n}}|x\rangle = \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 i kx}{2^n}}|x\rangle = \frac{1}{2^{n}}\sum_{x=0}^{2^n - 1} \sum_{k=0}^{2^n - 1}e^{-\frac{2\pi i k}{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 i k}{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 i k}{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 i k}{2^n}(x-a)} e^{2 \pi i \delta k} \right       | x }_{\text{State of the first register}}      \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 i 2^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{align}  \Pr(a) &=  \frac{1}{2^{2n}} \left | \frac{1- {e^{2 \pi i 2^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\cdot2^n \delta | \leqslant | \sin(\pi 2^n\delta) |  \text{ for }  |\delta| \leqslant \frac{1}{2^{n+1}} \\ [6pt] &\geqslant \frac {4}{\pi^2}  \end{align}
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
Parity measurement
References
