Quantum phase estimation algorithm
In quantum computing, the quantum phase estimation algorithm is a quantum algorithm that finds many applications as a subroutine in other algorithms. The quantum phase estimation algorithm allows one to estimate the eigenphase of an eigenvector of a unitary gate, given access to a quantum state proportional to the eigenvector and a procedure to implement the unitary conditionally.
Let U be a unitary operator that operates on m qubits. Then all of the eigenvalues of U have absolute value 1. Thus the spectrum of a unitary operator consists of phases . Given an eigenvector , such that , the objective is to estimate . The phase estimation algorithm solves this problem.
Suppose we wish to compute the phases to an accuracy of n bits. We achieve this by subjecting our eigenvector of to a succession of n controlled operators, followed by the inverse of the quantum Fourier transform. The controlled operators are the powers of from to controlled .
After putting the control lines into the Hadamard state, we have
After the controlled application of , we have
Applying the inverse of the quantum Fourier transform upon the n qubits yields
If the phase is exactly a root of unity, the quantum Fourier transform will single out that phase in binary expansion. If not, there will be a probability distribution clustered around the correct phase.
If is really a superposition of eigenstates, there is a weighted probability distribution over the individual eigenstates, with the weight given by the Born probabilities. This is because eigenstates corresponding to different eigenvalues are orthogonal.
Note that this algorithm is only efficient if we can compute in some time polynomial in . There are unitary operators for which this is the case, and there are those for which this isn't. If we only have access to as an oracle, then we need exponentially many calls to to compute .
- Alexei Kitaev (1995-11-20). "Quantum measurements and the Abelian Stabilizer Problem".
- Dieter van Melkebeek (2010-09-27). "Eigenvalue Estimation" (PDF).