Quantum phase estimation algorithm

The quantum phase estimation algorithm is a quantum algorithm that estimates the phase belonging to an eigenvalue of a given unitary operator. The eigenvalues of a unitary operator always have unit modulus, so each is characterized by its phase, and the algorithm can equally be described as recovering the phase or the eigenvalue itself. It was introduced by Alexei Kitaev in 1995. The algorithm works on two registers of qubits: one holds an eigenvector of the operator as a quantum state, and the other gathers the phase information. It assumes oracular access to the operator, so its efficiency is measured by how many times the operator must be applied, not by the cost of building it. It returns, with high probability, an approximation of the phase within a chosen additive error, using a number of qubits that grows with the logarithm of the inverse error and a number of controlled operations that grows with the inverse error. Phase estimation is used as a subroutine in other quantum algorithms, including Shor's algorithm, the quantum algorithm for linear systems of equations and the quantum counting algorithm.