Jump to content

User:Omrika/sandbox/QIP/Quantum phase estimation

From Wikipedia, the free encyclopedia

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 , the state of the first register can be described as .

Apply controlled unitary operations

[edit]

As mentioned above, if is a unitary operator and is an eigenvector of then , 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, the state of the first register can be described as .

Applying inverse Quantum Fourier transform on yields .

The state of both registers together is .

Phase approximation representation

[edit]

We would like to approximate 's value by rounding to the nearest integer .

Consider where is an integer and the difference is .

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

.


If the approximation is precise then meaning we will measure the accurate value of the phase with probability of one.[2]: 157 [3]: 347  The state of the system after the measurement is . [1]: 223 

Otherwise, since the series above converges and we measure the correct approximated value of with some probability larger than 0.

Analysis

[edit]

In case we only approximate 's value , it is guaranteed that the algorithm will yield the correct result with a probability .

First, recall the trigonometric identity .

Second, within 's range , the inequalities and holds for all .

Following the above . [2]: 157 [3] : 348 

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; Strini, Giulio Casati, Giuliano (2004). Principles of quantum computation and information (Reprinted. ed.). New Jersey [u.a.]: World Scientific. ISBN 978-9812388582.{{cite book}}: CS1 maint: multiple names: authors list (link)
  3. ^ a b 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/9511026.