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.

The Problem

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 e^{ i\theta}. Given an eigenvector \left| \psi \right\rangle, such that U\left| \psi \right\rangle = e^{ i \theta}\left|\psi \right\rangle, the objective is to estimate \theta. The phase estimation algorithm solves this problem.

The Algorithm

Quantum circuit representation of the phase estimation algorithm

Suppose we wish to compute the phases to an accuracy of n bits. We achieve this by subjecting our eigenvector \left| \psi \right\rangle of U to a succession of n controlled operators, followed by the inverse of the quantum Fourier transform. The controlled operators are the powers of U from U to controlled U^{2^{n-1}}.

After putting the control lines into the Hadamard state, we have

\frac{1}{\sqrt{2^{n}}} \sum_x \left| x \right\rangle \otimes \left| \psi \right\rangle.

After the controlled application of U, we have

\frac{1}{\sqrt{2^{n}}} \sum_x e^{ i x\theta} \left| x \right\rangle \otimes \left| \psi \right\rangle.

Applying the inverse of the quantum Fourier transform upon the n qubits yields

\frac{1}{2^n} \sum_y \sum_x e^{-2\pi i x\cdot y/2^n} e^{ ix\theta} \left| y \right\rangle \otimes \left| \psi \right\rangle = \frac{1}{2^n} \sum_y \frac{ e^{i 2^n \theta} - 1 }{ e^{i\left( \theta - 2\pi y/2^n \right)} - 1 } \left| y \right\rangle \otimes \left| \psi \right\rangle.

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, there will be a probability distribution clustered around the correct phase.

If \left| \psi \right\rangle 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 U^{2^n} in some time polynomial in n. 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 U as an oracle, then we need exponentially many calls to U to compute U^{2^{n}}.

See also

References