In quantum computing, the quantum phase estimation algorithm is a quantum algorithm to estimate the phase corresponding to an eigenvalue of a given unitary operator. Because the eigenvalues of a unitary operator always have unit modulus, they are characterized by their phase, and therefore the algorithm can be equivalently described as retrieving either the phase or the eigenvalue itself. 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, the quantum algorithm for linear systems of equations, and the quantum counting algorithm.

The algorithm operates on two sets of qubits, referred to in this context as registers. The two registers contain ${\displaystyle n}$ and ${\displaystyle m}$ qubits, respectively. Let ${\displaystyle U}$ be a unitary operator acting on the ${\displaystyle m}$-qubit register. The eigenvalues of a unitary operator have unit modulus, and are therefore characterized by their phase. Thus if ${\displaystyle |\psi \rangle }$ is an eigenvector of ${\displaystyle U}$, then ${\displaystyle U|\psi \rangle =e^{2\pi i\theta }\left|\psi \right\rangle }$ for some ${\displaystyle \theta \in \mathbb {R} }$. Due to the periodicity of the complex exponential, we can always assume ${\displaystyle 0\leq \theta <1}$.

The goal is producing a good approximation for ${\displaystyle \theta }$ with a small number of gates and a high probability of success. The quantum phase estimation algorithm achieves this assuming oracular access to ${\displaystyle U}$, and having ${\displaystyle |\psi \rangle }$ available as a quantum state. This means that when discussing the efficiency of the algorithm we only worry about the number of times ${\displaystyle U}$ needs to be used, but not about the cost of implementing ${\displaystyle U}$ itself.

More precisely, the algorithm returns with high probability an approximation for ${\displaystyle \theta }$, within additive error ${\displaystyle \varepsilon }$, using ${\displaystyle n=O(\log(1/\varepsilon ))}$ qubits in the first register, and ${\displaystyle O(1/\varepsilon )}$ controlled-U operations. Furthermore, we can improve the success probability to ${\displaystyle 1-\Delta }$ for any ${\displaystyle \Delta >0}$ by using a total of ${\displaystyle O(\log(1/\Delta )/\varepsilon )}$ uses of controlled-U, and this is optimal.

The initial state of the system is:

where ${\displaystyle |\psi \rangle }$ is the ${\displaystyle m}$-qubit state that evolves through ${\displaystyle U}$. We first apply the n-qubit Hadamard gate operation ${\displaystyle H^{\otimes n}}$ on the first register, which produces the state:$${\displaystyle |\Psi _{1}\rangle =(H^{\otimes n}\otimes I_{m})|\Psi _{0}\rangle ={\frac {1}{2^{\frac {n}{2}}}}(|0\rangle +|1\rangle )^{\otimes n}|\psi \rangle ={\frac {1}{2^{n/2}}}\sum _{j=0}^{2^{n}-1}|j\rangle |\psi \rangle .}$$Note that here we are switching between binary and ${\displaystyle n}$-ary representation for the ${\displaystyle n}$-qubit register: the ket ${\displaystyle |j\rangle }$ on the right-hand side is shorthand for the ${\displaystyle n}$-qubit state ${\displaystyle |j\rangle \equiv \bigotimes _{\ell =0}^{n-1}|j_{\ell }\rangle }$, where ${\displaystyle j=\sum _{\ell =0}^{n-1}j_{\ell }2^{\ell }}$ is the binary decomposition of ${\displaystyle j}$.

This state ${\displaystyle |\Psi _{1}\rangle }$ is then evolved through the controlled-unitary evolution ${\displaystyle U_{C}}$ whose action can be written as$${\displaystyle U_{C}(|k\rangle \otimes |\psi \rangle )=|k\rangle \otimes (U^{k}|\psi \rangle ),}$$ for all ${\displaystyle k=0,...,2^{n}-1}$. This evolution can also be written concisely as$${\displaystyle U_{C}=\sum _{k=0}^{2^{n}-1}|k\rangle \!\langle k|\otimes U^{k},}$$ which highlights its controlled nature: it applies ${\displaystyle U^{k}}$ to the second register conditionally to the first register being ${\displaystyle |k\rangle }$. Remembering the eigenvalue condition holding for ${\displaystyle |\psi \rangle }$, applying ${\displaystyle U_{C}}$ to ${\displaystyle |\Psi _{1}\rangle }$ thus gives$${\displaystyle |\Psi _{2}\rangle \equiv U_{C}|\Psi _{1}\rangle =\left({\frac {1}{2^{n/2}}}\sum _{k=0}^{2^{n}-1}e^{2\pi i\theta k}|k\rangle \right)\otimes |\psi \rangle ,}$$ where we used ${\displaystyle U^{k}|\psi \rangle =e^{2\pi ik\theta }|\psi \rangle }$.