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
Quantum phase estimation circuit
Setup
The input consists of two registers (namely, two parts): 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 of the first register can be described as
.
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 (from the first register) is .
After applying all the controlled operations with as seen in the figure, and kicking back phases to the control bits in the first register, the state of the first register can be described as
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.[2]: 157 [3]: 347 The state of the system after the measurement is .[1]: 223
For since the algorithm yields the correct result with probability . We prove this as follows: [2]: 157 [3]: 348
This result shows that we will measure the best n-bit estimate of with high probability. By increasing the amount of qubits by and ignoring those last qubits we can increase the probability to .[3]
^ abChuang, Michael A. Nielsen & Isaac L. (2001). Quantum computation and quantum information (Repr. ed.). Cambridge [u.a.]: Cambridge Univ. Press. ISBN978-0521635035.
^ abBenenti, Guiliano; Casati, Giulio; Strini, Giuliano (2004). Principles of quantum computation and information (Reprinted. ed.). New Jersey [u.a.]: World Scientific. ISBN978-9812388582.
^ abcCleve, R.; Ekert, A.; Macchiavello, C.; Mosca, M. (8 January 1998). "Quantum algorithms revisited". Proceedings of the Royal Society A: Mathematical, Physical and Engineering Sciences. 454 (1969). arXiv:quant-ph/9708016. doi:10.1098/rspa.1998.0164.
Kitaev, A. Yu. (1995). "Quantum measurements and the Abelian Stabilizer Problem". arXiv:quant-ph/9511026.