Quantum phase estimation algorithm


The Quantum phase estimation algorithm, is a quantum algorithm to estimate the phase of an eigenvector of a unitary operator. More precisely, given a unitary matrix and a quantum state such that, the algorithm estimates the value of with high probability within additive error, using qubits and controlled-U operations.
Phase estimation is frequently used as a subroutine in other quantum algorithms, such as Shor's algorithm and the quantum algorithm for linear systems of equations.

The problem

Let U be a unitary operator that operates on m qubits with an eigenvector such that.
We would like to find the eigenvalue of, which in this case is equivalent to estimating the phase, to a finite level of precision. We can write the eigenvalue in the form because U is a unitary operator over a complex vector space, so its eigenvalues must be complex numbers with absolute value 1.

The algorithm

Setup

The input consists of two registers : the upper qubits comprise the first register, and the lower qubits are the second register.

Create superposition

The initial state of the system is:
After applying n-bit Hadamard gate operation on the first register, the state becomes:

Apply controlled unitary operations

Let be a unitary operator with eigenvector such that thus
is a controlled-U gate which applies the unitary operator on the second register only if its corresponding control bit is.
Assuming for the sake of clarity that the controlled gates are applied sequentially, after applying to the qubit of the first register and the second register, the state becomes
where we use:
After applying all the remaining controlled operations with as seen in the figure, the state of the first register can be described as
where denotes the binary representation of, i.e. it's the computational basis, and the state of the second register is left physically unchanged at.

Apply inverse [Quantum Fourier transform]

Applying inverse Quantum Fourier transform on
yields
The state of both registers together is

Phase approximation representation

We can approximate the value of by rounding to the nearest integer. This means that where is the nearest integer to and the difference satisfies.
We can now write the state of the first and second register in the following way:

Measurement

Performing a measurement in the computational basis on the first register yields the result with probability
For the approximation is precise, thus and In this case, we always measure the accurate value of the phase. The state of the system after the measurement is.
For since the algorithm yields the correct result with probability. We prove this as follows:
This result shows that we will measure the best n-bit estimate of with high probability. By increasing the number of qubits by and ignoring those last qubits we can increase the probability to.