Quantum phase estimation algorithm

From Wikipedia, the free encyclopedia
Jump to: navigation, search

Quantum phase estimation algorithm is a quantum algorithm used as a subroutine in several applications such as order finding, factoring and discrete logarithm.[1]:131

This algorithm makes it possible to estimate the phase that a unitary transformation adds to one of its eigenvectors.

The problem[edit]

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.

The algorithm[edit]

Quantum phase estimation circuit

Setup[edit]

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[edit]

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[edit]

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

where denotes the binary representation of .

Apply inverse Quantum Fourier transform[edit]

Applying inverse Quantum Fourier transform on

yields

The state of both registers together is

Phase approximation representation[edit]

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[edit]

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]

See also[edit]

References[edit]

  1. ^ a b Chuang, Michael A. Nielsen & Isaac L. (2001). Quantum computation and quantum information (Repr. ed.). Cambridge [u.a.]: Cambridge Univ. Press. ISBN 978-0521635035. 
  2. ^ a b Benenti, Guiliano; Casati, Giulio; Strini, Giuliano (2004). Principles of quantum computation and information (Reprinted. ed.). New Jersey [u.a.]: World Scientific. ISBN 978-9812388582. 
  3. ^ a b c Cleve, 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). doi:10.1098/rspa.1998.0164. 
  • Kitaev, A. Yu. (1995). "Quantum measurements and the Abelian Stabilizer Problem". arXiv:quant-ph/9511026Freely accessible.