Quantum phase estimation algorithm

In quantum information theory, suppose we have a register of qubits, and some unitary operator U acting upon it. We know that the spectrum of a unitary operator consists of phases $e^{i\theta }$ . Suppose we wish to compute the phases to an accuracy of n bits.

Let's also assume we can compute $U^{2^{j}}$ in some time polynomial in j. There are unitary operators for which this is the case, and there are those for which this isn't the case. Note that applying U sequentially takes exponentially long in j. The algorithm only applies to the former case.

Just as we have controlled NOT operators, we can have controlled $U^{2^{j}}$ gates. We have a control qubit, and the register of qubits $\left|\psi \right\rangle$ .

\left[\alpha \left|0\right\rangle +\beta \left|1\right\rangle \right]\otimes \left|\psi \right\rangle \to \alpha \left|0\right\rangle \otimes \left|\psi \right\rangle +\beta \left|1\right\rangle \otimes U^{2^{j}}\left|\psi \right\rangle

If $\left|\psi \right\rangle$ is an eigenstate of U, we can perform a succession of controlled operators with respect to n different control qubits varying from controlled $U$ to controlled $U^{2^{n-1}}$ .

Now perform a quantum Fourier transform upon the n qubits. If the phase is exactly a $2^{n}$ root of unity, the quantum Fourier transform will single out that phase in binary expansion. If not, we have a probability distribution clustered around the correct phase.

If $\left|\psi \right\rangle$ is really a superposition of eigenstates, we simply have a weighted probability distribution over the individual eigenstates, with the weight given by the Born probabilities.

See also