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^{ix\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 ix\cdot y/2^{n}}e^{ix\theta }\left|y\right\rangle \otimes \left|\psi \right\rangle ={\frac {1}{2^{n}}}\sum _{y}{\frac {e^{i2^{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}$ -th 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}}}}$ .

References

Alexei Kitaev (1995-11-20). "Quantum measurements and the Abelian Stabilizer Problem".
Dieter van Melkebeek (2010-09-27). "Eigenvalue Estimation" (PDF).

Quantum information science

General

Quantum communication

Quantum algorithms

Quantum complexity theory

Quantum computing models

Decoherence prevention

Physical implementations

Quantum optics	Cavity QED Circuit QED Linear optical quantum computing

Ultracold atoms	Trapped ion quantum computer Optical lattice

Spin-based	Nuclear magnetic resonance QC Kane QC Loss–DiVincenzo QC Nitrogen-vacancy center

Superconducting quantum computing	Charge qubit Flux qubit Phase qubit

This article is issued from Wikipedia - version of the 7/27/2016. The text is available under the Creative Commons Attribution/Share Alike but additional terms may apply for the media files.

Quantum phase estimation algorithm

The problem

The algorithm

See also

References