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, named after Peter Shor.

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. Known classical algorithms cannot do this in time O((log N)^k) for any k, so they quickly become infeasible 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.

Like all quantum computer algorithms, Shor's algorithm is probabilistic: it gives the correct answer with high probability, and the probability of failure can be decreased by repeating the algorithm.

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.

Table of contents

1 Procedure
2 Explanation of the algorithm

2.1 I. Obtaining factors from period
2.2 II. Finding the period

Procedure

Pick a pseudo-random number a < N

Compute gcd(a, N). This may be done using the Euclidean algorithm.
If gcd(a, N) ≠ 1, then it is a nontrivial factor of N, so we are done.
Otherwise, use the period-finding subroutine (below) to find r, the period of the following function:
If r is odd, go back to step 1.
If a ^r/2 ≡ -1 (mod N), go back to step 1.
The factors of N are gcd(a^r/2 ± 1, N). We are done.

Period-finding subroutine:

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

where x runs from 0 to N - 1.

Construct f(x) as a quantum function and apply it to the above state, to obtain

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

where A is a normalization constant, and j runs from 0 to A - 1.

Apply the quantum Fourier transform on the input register. The quantum fourier transform is defined by:

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.

Turn y/N into an irreducible fraction, and extract the denominator r′, which is a candidate for r.

Check if f(x) = f(x + r′). If so, we are done.

Otherwise, obtain more candidates for r by using values near y, or multiples of r′. If any candidate works, we are done.

Otherwise, go back to step 1 of the subroutine.

Explanation of the algorithm

The algorithm is composed of two parts. The first part of the algorithm turns the factoring problem into the problem of finding the period of a function, and may be implemented classically. The second part finds the period using the quantum fourier transform, and is responsible for the quantum speedup.

I. Obtaining factors from period

The integers less than N and coprime with N form a finite group under multiplication modulo N, which is typically denoted (Z/NZ)^×. By the end of step 3, we have an integer a in this group. Since the group is finite, a must have a finite order r, the smallest positive integer such that

Therefore, N | (a ^r - 1). Suppose we are able to obtain r, and it is even. Then

r is the smallest positive integer such that a ^r ≡ 1, so N cannot divide (a ^{r / 2} - 1). If N also does not divide (a ^{r / 2} + 1), then N must have a nontrivial common factor with each of (a ^{r / 2} - 1) and (a ^{r / 2} + 1).

Proof: For simplicity, denote (a ^{r / 2} - 1) and (a ^{r / 2} + 1) by u and v respectively. N | uv, so kN = uv for some integer k. Suppose gcd(u, N) = 1; then mu + nN = 1 for some integers m and n (this is a property of the greatest common divisor.) Multiplying both sides by v, we find that mkN + nvN = v, so N | v. By contradiction, gcd(u, N) ≠ 1. By a similar argument, gcd(v, N) ≠ 1.

This supplies us with a factorization of N. If N is the product of two primes, this is the only possible factorization.

II. Finding the period

To be written