Shor's algorithm

Shor's algorithm is a quantum algorithm for factoring a number N in O((log N)³) time and O(log N) space.

Many public key cryptosystems, such as RSA, will become obsolete if Shor's algorithm is ever implemented in a practical quantum computer. A message encrypted with RSA can be deciphered by factoring the public key N, which is the product of two prime numbers. The most efficient known classical algorithm for doing this requires time O(e^N), which quickly becomes unfeasible as N is increased. By contrast, Shor's algorithm can crack RSA in polynomial time. It has also been extended to attack many other public key cryptosystems.

Shor's algorithm was demonstrated in 2001 by a group at IBM, which factored 15 into 3 and 5, using a quantum computer with 7 qubits.

Procedure

1. Pick a pseudo-random number a < N
2. Compute gcd(a, N)
3. If gcd(a, N) ≠ 1, then it is a nontrivial factor of N, so we are done.
4. Otherwise, use the period-finding subroutine (below) to find r, the period of the following function:

   f(x) = a ^x (mod N)

5. If r is odd, go back to step 1.
6. If a ^r/2 ≡ -1 (mod N), go back to step 1.
7. The factors of N are gcd(a^r/2 ± 1, N). We are done.

Period-finding subroutine:

1. Start with a pair of input and output qubit registers with log₂N qubits each, and initialize them to

   N ^-1/2 Σ_x |x> |0>

   where x runs from 0 to N - 1.
2. Construct f(x) as a quantum function and apply it to the above state, to obtain

   N ^-1/2 Σ_x |x> |f(x)>

3. Perform a measurement on the output register, obtaining some result f(x₀). The state of the input register becomes

   A^-1/2 Σ_j |x₀ + jr >

   where A is a normalization constant, and j runs from 0 to A - 1.
4. Apply the quantum fourier transform on the input register. The quantum fourier transform is defined by:

   U_QFT |x> = N^-1/2 Σ_ye^{2π i xy} |y>

5. Perform a measurement on the input register, obtaining some outcome y. With probability greater than 0.5, yr/N will lie close to an integer.
6. Turn y/N into an irreducible fraction, and extract the denominator r′, which is a candidate for r.
7. Check if f(x) = f(x + r′). If so, we are done.
8. Otherwise, obtain more candidates for r by using values near y, or multiples of r′. If any candidate works, we are done.
9. Otherwise, go back to step 1.

Explanation of the Algorithm

Pending