Shor’s algorithm is an amazing accomplishment, isn’t it? But it’s a complex algorithm involving a number of concepts that are probably new to you and it’s a combination of both quantum and classical subroutines. So, let’s take a look back at the overall structure, then we’ll talk about the performance implications of the algorithm. First, we start with the number N that you’d like to factor. Next, pick a random number a less than N. Before going any farther, it’s worth checking the greatest common denominator of a and N. Almost certainly, the gcd will be 1.

If you get very lucky and it’s greater than 1, you have found the factor of N and you are already done, so there is no need to actually use the quantum computer. Most likely though, we move onto the next step, which is to use the quantum computer to find the period of the function, f (x) = a^x mod N. We are going to need high accuracy. But quantum systems are very fragile and noisy, which means using a lot of extra qubits to correct the errors.

This doesn’t sound like a big deal in a world where we buy gigabit memories and terabyte discs for our laptops, but in fact, building even a few qubits is very hard, so it’s actually a serious concern. We will discuss error correction and hardware later in the course. First, we need to optimize the program for the quantum computer to suit our particular numbers a and N, which means recompiling the program. Then, we would use the broad superposition state for the variable x so that we calculate the modular exponentiation in superposition. Applying the quantum Fourier transform to that state should give us the period when we measure the result.

Finally, we take that period r that we found and calculate the gcds – gcd of a^r/2 +1 and N and gcd of a^r/2 - 1 and N. That should give us two prime number factors of our number N. Sometimes, the algorithm fails and we have to re-run it, but we shouldn’t have to do that very many times. So that’s the algorithm.