Overview of Shor's Algorithm

Shor's algorithm hinges on a result from number theory: the function $\mathcal{F}(a) = x^{a} \bmod n$ is a periodic function when $x$ is an integer coprime to $n$. In the context of Shor's algorithm $n$ will be the number we wish to factor. When two numbers are coprime it means that their greatest common divisor is 1.

Calculating this function for an exponential number of $a$'s would take exponential time on a classical computer. Shor's algorithm utilizes quantum parallelism to perform the exponential number of operations in one step.

Since $\mathcal{F}(a)$ is a periodic function, it has some period $r$. We know that $x^{0} \bmod n = 1$ (since $x^{0} = 1$), and therefore $x^{r} \bmod n = 1$, and $x^{2r} \bmod n = 1$, and so on.

Given this information and through the following algebraic manipulation:

$$x^{r} \equiv 1 \bmod n$$

$$(x^{r/2})^{2} = x^{r} \equiv 1 \bmod n$$

$$(x^{r/2})^{2} - 1 \equiv 0 \bmod n$$

and if $r$ is an even number

$$(x^{r/2} - 1)(x^{r/2} + 1) \equiv 0 \bmod n$$

We can see that the product $(x^{r/2} - 1)(x^{r/2} + 1)$ is an integer multiple of $n$, the number to be factored. So long as $\left\vert x^{r/2}\right\vert$ is not $1$, then at least one of $(x^{r/2} - 1)$, $(x^{r/2} + 1)$ must have a nontrivial factor in common with $n$. So by computing $\gcd(x^{r/2} - 1, n)$, and $\gcd(x^{r/2} + 1, n)$, we will obtain a factor of $n$, where $\gcd$ is the greatest common denominator function.

Shor's algorithm tries to find $r$, the period of $x^{a} \bmod n$, where $n$ is the number to be factored by Shor's algorithm, and $x$ is an integer coprime to $n$. To do this Shor's algorithm creates a quantum memory register with two parts. In the first part the algorithm places a superposition of the integers which are to be $a$'s in the $x^{a} \bmod n$ function. We will choose our $a$'s to be the integers 0 through $q - 1$, where $q$ is the power of two such that $n^{2} \leq q < 2n^{2}$. Then the algorithm calculates $x^{a} \bmod n$, where $a$ is the superposition of the states, and places the result in the second part of the quantum memory register.

Remember, the number $n$ is represented by a $\lceil \log n \rceil$ bit string. We must calculate $x^{a} \bmod n$ an exponential number of times, with respect to the length of the encoded input to the algorithm (although it is a polynomial number of times with respect to the value of $n$).

Next the algorithm measures the state of the second register, the one that contains the superposition of all possible outcomes for $x^{a} \bmod n$. Measuring this register has the effect of collapsing the state into some observed value, say $k$. It also has the side effect of projecting the first part of the quantum register into a state consistent with the value measured in the second part. So: measurement of the second part results in exactly one value, and causes the other partition to collapse into a superposition of the base states consistent with the value observed in the second part.

After this measurement the second part of the register contains the value $k$, and the first part of the register contains a superposition of the base states whose evaluation in $x^{a} \bmod n$ produce $k$. We know $x^{a} \bmod n$ is a periodic function, therefore the first part of the register will contain the values $c$, $c+r$, $c+2r\ldots$, where $c$ is the lowest integer such that $x^{c} \bmod n = k$.

The next step is to perform a discrete Fourier transform on the contents of first part of the register. The application of the discrete Fourier transformation has the effect of peaking the probability amplitudes of the first part of the register at integer multiples of the quantity $q / r$.

Measuring the first part of the quantum register will yield an integer multiple of the inverse of the period with high probability. Once this number is retrieved from the quantum memory register, a classical computer can do analysis of this number, make a guess as to the actual value of $r$, and from that compute the possible factors of $n$. This post processing is covered in more detail below. (Shor)