Shor's Algorithm: Factoring Through Period-Finding

1. The Core Idea: Turning Factoring into Period-Finding

Peter Shor's great insight was not just in designing a quantum algorithm, but in recognizing a mathematical structure within the factoring problem that was perfectly suited for a quantum computer to exploit. He showed that you could reduce factoring to finding the period of a modular exponentiation function.

Let's break down what this means.

First, to get a feel for this idea without heavy mathematics, let's read an excerpt from a blog post by Scott Aaronson, a prominent quantum computing researcher.

As Aaronson explains, for a given number N that we want to factor, and a random guess a (where a < N and a shares no factors with N), we can look at the sequence:

$a^1(\mathrm{mod}N),a^2(\mathrm{mod}N),a^3(\mathrm{mod}N),\dots$

This sequence of remainders will eventually repeat itself in a cycle. The length of this cycle is called the period, which we'll denote as $r$. Finding this period $r$ is the key.

Let's see why this period is so important.

2. The "Magic Formula": From Period to Factors

Once you have the period $r$, a few algebraic steps can lead you to the factors of N. The logic hinges on a few properties from number theory. The following video explains this connection very clearly.

Let's summarize the logic from the video.

1. The definition of the period $r$ tells us that $a^r\equiv 1(\mathrm{mod}N)$. This is just another way of saying that $a^r$ gives a remainder of 1 when divided by N.

2. This means $a^r-1$ is a multiple of N. We can write this as $a^r-1=k\cdot N$ for some integer k.

3. If the period $r$ is even, we can use the difference of squares formula ($x^2-y^2=(x-y)(x+y)$) to rewrite the equation:

   $$(a^{r/2}-1)(a^{r/2}+1)=k\cdot N$$

4. The Breakthrough: This final equation is the magic. It tells us that the number N (whose factors we want to find) is a factor of the product $(a^{r/2}-1)(a^{r/2}+1)$.

   Unless we are unlucky (e.g., if $a^{r/2}+1$ is itself a multiple of N), this implies that the factors of N are "split" between the two terms, $(a^{r/2}-1)$ and $(a^{r/2}+1)$.

5. Finding the factors with GCD: We can then find a factor of N by calculating the Greatest Common Divisor (GCD) of one of these terms and N.

   • factor_1 = gcd(a^{r/2} - 1, N)
   • factor_2 = gcd(a^{r/2} + 1, N)

With high probability, these GCD calculations will yield the prime factors of N.

3. A Step-by-Step Example: Factoring 15

Let's make this concrete by factoring N = 15.

1. Pick a random guess. Let's pick a = 7. We check that gcd(7, 15) = 1, so it's a valid guess.

2. Find the period r of $7^k(\mathrm{mod}15)$.

   • $7^1(\mathrm{mod}15)=7$
   • $7^2(\mathrm{mod}15)=49(\mathrm{mod}15)=4$
   • $7^3(\mathrm{mod}15)=7\times 4=28(\mathrm{mod}15)=13$
   • $7^4(\mathrm{mod}15)=7\times 13=91(\mathrm{mod}15)=1$ (since $6\times 15+1=91$)
     The sequence is 7, 4, 13, 1, 7, 4, .... The sequence repeats after 4 terms, so the period is $r=4$.

3. Check the conditions.

   • Is r even? Yes, 4 is even.
   • Is $a^{r/2}+1$ a multiple of N? Let's check: $7^{4/2}+1=7^2+1=50$. gcd(50, 15) = 5, not 15, so we are not in an "unlucky" case.

4. Calculate the factors using GCD.

   • factor_1 = gcd(a^{r/2} - 1, N) = gcd(7^2 - 1, 15) = gcd(48, 15)

     • The divisors of 48 are {1, 2, 3, 4, 6, 8, 12, 16, 24, 48}.
     • The divisors of 15 are {1, 3, 5, 15}.
     • The GCD is 3. We found a factor!

   • factor_2 = gcd(a^{r/2} + 1, N) = gcd(7^2 + 1, 15) = gcd(50, 15)

     • The divisors of 50 are {1, 2, 5, 10, 25, 50}.
     • The divisors of 15 are {1, 3, 5, 15}.
     • The GCD is 5. We found the other factor!

And indeed, $3\times 5=15$. The method works.

The following video from the Qiskit team shows this exact process and how the "magic formula" is applied after finding the period.

4. The Classical and Quantum Parts of Shor's Algorithm

At this point, you might be wondering: if we can do all this, why do we need a quantum computer?

The answer lies in Step 2: Find the period $r$. For a large number N, the period r can also be very large. Calculating the sequence $a^k(\mathrm{mod}N)$ step-by-step until it repeats, as we did for N=15, is just as slow as trying to find the factors by brute force. It is a classically "hard" problem.

This is where the structure of Shor's algorithm becomes clear. It is a hybrid quantum-classical algorithm:

The Algorithm Outline:

1. (Classical) Pick a random guess a < N. Check if gcd(a, N) > 1. If so, you're done by pure luck.
2. (Quantum) If not, use a quantum computer to run a period-finding algorithm on the function $f(k)=a^k(\mathrm{mod}N)$ to find the period r. This is the only quantum step.
3. (Classical) Check if r is even and if $a^{r/2}+1\not\equiv 0(\mathrm{mod}N)$. If these checks fail, go back to Step 1 with a new guess a.
4. (Classical) If the checks pass, calculate the factors using gcd(a^{r/2} \pm 1, N).

The genius of Shor's algorithm is that it isolates the one classically hard part (period-finding) and outsources it to a quantum computer, which can solve that specific problem exponentially faster than any known classical algorithm.

Conclusion

In this lesson, you've learned the critical conceptual link that underpins Shor's algorithm. We have demystified the process, showing that it's not arbitrary magic but a clever application of number theory.

Key Takeaways:

• Shor's algorithm reduces the problem of factoring N to the problem of finding the period r of the function $f(k)=a^k(\mathrm{mod}N)$.
• Once the period r is known, and provided it is even, the factors of N can be found efficiently on a classical computer using the Greatest Common Divisor (GCD) algorithm: gcd(a^{r/2} \pm 1, N).
• The overall algorithm is a hybrid process. The quantum computer is used only for the period-finding step, which is computationally hard for classical computers. The rest of the logic is classical.

Preview of the Next Lesson:
We have now framed the exact problem that the quantum computer needs to solve: "Given the function $a^k(\mathrm{mod}N)$, find its period r." In the next lesson, we will begin to explore the core quantum component that accomplishes this: the Quantum Fourier Transform (QFT). You will learn what the QFT is and how it is used to extract the period from a quantum superposition.