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 . We will go through each of these steps briefly, then there is an article for each of the parts that goes into more detail.
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 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: . Our sequence of numbers goes
After seven steps we are back to zero, where we started. If you keep going, the sequence just repeats itself:
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
The Quantum Fourier Transform
Select a prime number . It turns out that, if we can find the period of the function as we increment the variable , then we can find the factors of . The simplest way to do this, of course, is just to repeat calculating 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 in superposition, calculate , and now we have a superposition of all of the function results. If we can pick two different values of out of the superposition that produce the same , 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 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 , in a fashion that lets us directly read out the period !
Of course, this is still no help if either calculating 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.
The final classical step is take 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 , calculating the gcd of with the numbers and will give us two prime factors of the number .
Putting It All Together
Summarizing, let’s assume we’re trying to factor the number , which is written using bits. The algorithm consists of the following steps:
- Pick a prime number .
- Use Euclid’s algorithm to check if is a factor of ; 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 for all values of , all done modulo . 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
- Measure the register ; call the result , which should be a multiple of the period of the modular exponentiation function.
- If is even and greater than zero, calculate the numbers and ; if not, rerun the quantum portion of the algorithm to find a new .
- Use Euclid’s algorithm to calculate the gcd of each of those numbers and , and you should have two factors of !
Now, let’s go look at each of the individual techniques, before putting it all together.
© Keio University