# Structure of Shor's algorithm

Let’s talk about the structure of Peter Shor’s algorithm for factoring large numbers.

As we saw, a “quantum” algorithm is really a hybrid
quantum-classical algorithm. It begins with some classical
processing, then uses the quantum computer to execute a particular
part of the algorithm (a subroutine or function) and measures the
result. It then takes those results and does some more classical
post-processing. The quantum computer essentially serves as a
*coprocessor* to the classical computer.

In the case of Shor’s algorithm, the quantum subroutine is known as
the *period finding routine*, which uses an important technique known
as the *quantum Fourier transform*, or QFT, to create interference
that gives us the period. We then use a classical technique known as
*Euclid’s algorithm* to find the prime factors of the number \(N\).
We will go through each of these steps briefly, then there is an
article for each of the parts that goes into more detail.

^{Fig.1. Block structure of Shor’s algorithm}

## Modulo Arithmetic

Recall that *modulo* arithmetic means that any time our result gets to
be greater than or equal to the modulus, we subtract the modulus until
we’re back between zero and that number minus one.

Doing arithmetic modulo ten is just like keeping track of only the last digit of any addition or multiplication operation, so for example \(9 \times 9 \bmod 10\) is just 1, rather than 81.

Consider a function where you add four every step, and do the whole
thing *modulo* seven. If you start with zero, your sequence goes 0,
4, then it *should* go 8, but since 8 is greater than 7, we subtract 7
and we’re back to 1. Then the next step would be 5. Modulo seven,
then, is just like doing math in base seven and keeping only the last
digit.

## The Period of a Function

A lot of mathematical functions are *periodic*. That is, if you start
by evaluating the function in some place and move forward, eventually
you’ll come back to where you started. In fact, the entire sequence
of values repeats itself. The time it takes for that repetition to
occur is called the *period*.

We’ve already talked a lot about waves, so you might suspect that the period of a function is like the period of a wave. In fact, it’s exactly like that!

Rather than a continuous function like a sine wave, let’s look at what happens just with discrete steps, like modulo arithmetic. Go back to the function of adding four modulo seven, which we can write like this: \(x_{i+1} = x_i + 4 \bmod 7\). Our sequence of numbers goes

\[0, 4, 1, 5, 2, 6, 3, 0\]After seven steps we are back to zero, where we started. If you keep going, the sequence just repeats itself:

\[0, 4, 1, 5, 2, 6, 3, 0, 4, 1, 5, 2, 6, 3, 0, 4, 1, 5, 2, 6, 3, ...\]Every 0 is seven steps apart, and even 4 is seven steps apart in that
sequence. We say that the *period* of our function is seven, and we
can say that

\(f(x + 7) = f(x)\).

## The Quantum Fourier Transform

Select a prime number \(a < N\). It turns out that, if we can find
the period \(r\) of the function \(f(x) = a^x \bmod N\) as we
increment the variable \(x\), then we can find the factors of \(N\).
The simplest way to do this, of course, is just to repeat calculating
\(f(x)\) until we find two identical results; the number of steps in
between will be the period. While it’s theoretically possible, it’s
impractical, because the period grows roughly exponentially as the
length of the number grows. For large numbers, that period could be
*enormous*, so big that we could calculate for the lifetime of the
universe and never find the period. It’s less efficient than the
number field sieve we already have. We need a different approach.

A common classical technique for finding the frequency of a signal,
which we can easily invert to find the period, is the *Fourier
transform*. If we could take the Fourier transform of a sequence of
these results, we might find the period. Doing so classically,
unfortunately, would require data from a sequence of results like the
one we just described. Still obviously impractical.

With a quantum computer, though, the finding of the period of a function suddenly becomes practical. We take all of the possible values of \(x\) in superposition, calculate \(f(x)\), and now we have a superposition of all of the function results. If we can pick two different values of \(x\) out of the superposition that produce the same \(f(x)\), then we can find the period.

Unfortunately, we can’t do that directly. As we have seen, any time you measure a superposition, you get one of the possible values randomly, depending on the quantum probability amplitudes. Finding only one value for \(x\) doesn’t help us at all. Instead, though, we can apply the quantum form of the Fourier transform (the QFT), and it will create interference among all of values of \(x\), in a fashion that lets us directly read out the period \(r\)!

Of course, this is still no help if either calculating \(f(x)\) or
doing the QFT is computationally expensive. The modular
exponentiation and the QFT both turn out to have a cost that is
*polynomial* in the length of the number in bits, a profound reduction
compared to the exponential effort necessary to find the period
classically.

This is the core of Shor’s algorithm, and one of the most exciting technical results in any field in the last several decades, in our opinion.

## Euclid’s Algorithm

The final classical step is take \(r\) and use it to find the factors. This is done on a classical computer, using Euclid’s algorithm for finding the greatest common denominator (gcd) of two numbers. Euclid’s algorithm is polynomial in the size of the numbers, and indeed is fairly fast on a classical computer, so there is no need to be concerned about the difficulty of this step.

Assuming we have correctly found the period \(r\), calculating the gcd of \(N\) with the numbers \(a^{(r/2)}+1\) and \(a^{(r/2)}-1\) will give us two prime factors of the number \(N\).

### Putting It All Together

Summarizing, let’s assume we’re trying to factor the number \(N\), which is written using \(n\) bits. The algorithm consists of the following steps:

- Pick a prime number \(a < N\).
- Use Euclid’s algorithm to check if \(a\) is a factor of \(N\); if so, you’re done.
- Otherwise, prepare your quantum computer and a program for it to
execute
*quantum period finding*. - The first important quantum step is to calculate the superposition of \(a^x\) for all values of \(x\), all done modulo \(N\). \(|x\rangle\) and the remainder both appear in our quantum register.
- Measure the remainder. (Technically, this is unnecessary, but it simplifies the explanation, so we will assume we use it.)
- Take the quantum Fourier transform (QFT) of \(|x\rangle.\)
- Measure the register \(|x\rangle\); call the result \(r\), which should be a multiple of the period of the modular exponentiation function.
- If \(r\) is even and greater than zero, calculate the numbers \(a^{(r/2)}+1\) and \(a^{(r/2)}-1\); if not, rerun the quantum portion of the algorithm to find a new \(r\).
- Use Euclid’s algorithm to calculate the gcd of each of those numbers and \(N\), and you should have two factors of \(N\)!

Now, let’s go look at each of the individual techniques, before putting it all together.

© Keio University