Quantum phase estimation algorithm
||This article provides insufficient context for those unfamiliar with the subject. (September 2010)|
||This article needs attention from an expert on the subject. (September 2010)|
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.
The efficiency of this algorithm depends on our access to . If we only have access via an oracle function, then we need exponentially many calls (in n) to the oracle to compute (for example) . If we have complete access to , then we can use exponentiation by squaring to compute the necessary powers of efficiently.
- Alexei Kitaev (1995-11-20). "Quantum measurements and the Abelian Stabilizer Problem".
- Dieter van Melkebeek (2010-09-27). "Eigenvalue Estimation".