Given a unitary operator U, the algorithm estimates 'θ' in the equation:
U Ψ⟩ = exp(2πiθ) Ψ⟩
In the above Ψ⟩ is an eigenvector of the unitary operator U and exp(2πiθ) is the corresponding eigenvalue. Since U is unitary, its eigenvalues have unit norm and can be written as exp(2πiθ). The quantum phase estimation is often reused as a subroutine in many other quantum algorithms and offers an exponential speedup over classical methods.
The algorithm uses phase kickback to write the phase of U to the top n qubits. The more qubits are used in the top n register, the better the final result approximates the phase corresponding to the eigenvalue of the operator U. In our example, n = 7 and θ = 1/3. The initial state is prepared by applying a layer of Hadamard gates on the top n qubits to create a superposition of all states and the X gate on the work qubit such that the work qubit is in state 1⟩ which is an eigenstate of U in this case. The operator U itself is applied to the second register of qubits which can contain any number of qubits but it was chosen to be one for this example. The phase is extracted in the Fourier basis, hence an inverse Fourier transform must be applied at the end. After this, we can measure the top n qubits and extract an approximation of the correct result with high probability, as:
θ = x / (2^n)
Here, x is the decimal number corresponding to the binary representation of the most probable measured state. Measurements are expected to be made in the standard zbasis. The value of θ calculated using the equation above is 0.3359375, very close to the exact value of 1/3.
