Quantum phase estimation algorithm is a quantum algorithm used as a subroutine in several applications such as order finding, factoring and discrete logarithm.
This algorithm makes it possible to estimate the phase that a unitary transformation adds to one of its eigenvectors.
Let U be a unitary operator that operates on m qubits with an eigenvector | ψ ⟩ , such that U | ψ ⟩ = e 2 π i θ | ψ ⟩ , 0 ≤ θ < 1 .
We would like to find the eigenvalue e 2 π i θ of | ψ ⟩ , which in this case is equivalent to estimating the phase θ , to a finite level of precision.
The input consists of two registers (namely, two parts): the upper n qubits comprise the first register, and the lower m qubits are the second register.
The initial state of the system is | 0 ⟩ ⊗ n | ψ ⟩ . After applying n-bit Hadamard gate operation H ⊗ n on the first register, the state of the first register can be described as 1 2 n / 2 ( | 0 ⟩ + | 1 ⟩ ) ⊗ n .
U is a unitary operator and | ψ ⟩ is an eigenvector of U such that U | ψ ⟩ = e 2 π i θ | ψ ⟩ , thus U 2 j | ψ ⟩ = U ⋯ U ⏟ 2 j | ψ ⟩ = e 2 π i 2 j θ | ψ ⟩ .
C − U is a controlled-U gate which applies the unitary operator U on the second register only if its corresponding control bit (from the first register) is | 1 ⟩ .
After applying all the n controlled operations C − U 2 j with 0 ≤ j ≤ n − 1 , as seen in the figure, the state of the first register can be described as 1 2 n / 2 ( | 0 ⟩ + e 2 π i 2 n − 1 θ | 1 ⟩ ) ⏟ 1 s t q u b i t ⊗ ⋯ ⊗ ( | 0 ⟩ + e 2 π i 2 1 θ | 1 ⟩ ) ⏟ n − 1 t h q u b i t ⊗ ( | 0 ⟩ + e 2 π i 2 0 θ | 1 ⟩ ) ⏟ n t h q u b i t = 1 2 n / 2 ∑ k = 0 2 n − 1 e 2 π i θ k | k ⟩ .
Applying inverse Quantum Fourier transform on 1 2 n / 2 ∑ k = 0 2 n − 1 e 2 π i θ k | k ⟩ yields 1 2 n ∑ x = 0 2 n − 1 ∑ k = 0 2 n − 1 e 2 π i θ k e − 2 π i k x 2 n | x ⟩ = 1 2 n ∑ x = 0 2 n − 1 ∑ k = 0 2 n − 1 e − 2 π i k 2 n ( x − 2 n θ ) | x ⟩ .
The state of both registers together is 1 2 n ∑ x = 0 2 n − 1 ∑ k = 0 2 n − 1 e − 2 π i k 2 n ( x − 2 n θ ) | x ⟩ ⊗ | ψ ⟩ .
We can approximate the value of θ ( 0 ≤ θ < 1 ) by rounding 2 n θ to the nearest integer a . This means that 2 n θ = a + 2 n δ , where a is the nearest integer to 2 n θ , and the difference 2 n δ satisfies 0 ≤ | 2 n δ | ≤ 1 2 .
We can now write the state of the first and second register in the following way: 1 2 n ∑ x = 0 2 n − 1 ∑ k = 0 2 n − 1 e − 2 π i k 2 n ( x − a ) e 2 π i δ k | x ⟩ ⊗ | ψ ⟩ .
Performing a measurement in the computational basis on the first register yields the result | a ⟩ with probability
P r ( a ) = | ⟨ a | 1 2 n ∑ x = 0 2 n − 1 ∑ k = 0 2 n − 1 e − 2 π i k 2 n ( x − a ) e 2 π i δ k | x ⟩ ⏟ S t a t e o f t h e f i r s t r e g i s t e r | 2 = 1 2 2 n | ∑ k = 0 2 n − 1 e 2 π i δ k | 2 = { 1 if δ = 0 1 2 2 n | 1 − e 2 π i 2 n δ 1 − e 2 π i δ | 2 if δ ≠ 0 .
If the approximation is precise ( δ = 0 , thus a = 2 n θ ), then P r ( a ) = 1 . In this case, we always measure the accurate value of the phase. The state of the system after the measurement is | 2 n θ ⟩ ⊗ | ψ ⟩ .
Otherwise, since 0 ≤ | δ | ≤ 2 − ( n + 1 ) , the series above converges and we measure the correct approximated value of θ (namely, we measure | a ⟩ ) with some probability larger than 0, as analyzed below.
We discuss here only the case δ ≠ 0 . We prove that in this case, the algorithm yields the correct result ( a ) with a probability P r ( a ) ≥ 4 π 2 ≈ 0.405 .
First, recall the trigonometric identity | 1 − e 2 i x | = | e i x | | e − i x − e i x | = ⏟ | e i x | = 1 2 | sin ( x ) | .
Second, within δ 's range ( 0 ≤ | δ | ≤ 2 − ( n + 1 ) ), the inequalities | 2 ⋅ 2 n δ | ≤ | sin ( π 2 n δ ) | and | sin ( π δ ) | ≤ | π δ | hold for all δ .
Following the above 1 2 2 n | 1 − e 2 π i 2 n δ 1 − e 2 π i δ | 2 = 1 2 2 n | e π i 2 n δ e π i δ ⋅ e − π i 2 n δ − e π i 2 n δ e − π i δ − e π i δ | 2 = 1 2 2 n | e π i 2 n δ | 2 | e π i δ | 2 2 | sin ( π 2 n δ ) | 2 2 | sin ( π δ ) | 2 ≥ 1 2 2 n | 2 ⋅ 2 n δ π δ | 2 = 4 π 2 .
This result shows that we will measure the best n-bit estimate of θ with high probability. Provided a large number of qubits n , this probability will become closer to 1.
