Shor's Algorithm - Beating Around the Bush

A bit of context

Before our interlude on Quantum Fourier Transform and Quantum Phase Estimation, we covered how Shor’s Algorithm addressed the problem of factorizing. Given a number $N$, we want to express it as a product of its factors. This problem is of interest to us because classically, factorizing large numbers is difficult, which is why it forms the basis of contemporary encryption standards on the internet. But quantum computers can do exponentially better than this.

But first, let’s see how one would go about factorizing a number traditionally. One can easily check whether a number $x$ is a factor of $N$ if dividing $N$ by $x$ gives a remainder of $0$. This straight away gives us two factors for $N$: $x$ and $q$ where $q$ is $\frac{N}{x}$. This was quite easy to do. Sadly, easy $N$s of this sort don’t come up in encryption standards. Instead, numbers of the sort that do come up cannot be easily factored. In fact, factorization becomes really hard when $N$ is a product of two prime numbers $p$ and $q$, that is, $N=pq$, where $p$ and $q$ are roughly equal in length. Numbers of this sort form the basis of the RSA encryption algorithm, and we’ll restrict ourselves to such numbers for the discussion henceforth.

We’ve already learned that the asymptotic time complexity of our fastest factorization algorithms of such numbers is exponential. We also know that quantum computers can eliminate these exponential terms and factorize the same numbers in polynomial ($\sim O(n^3)$) time.

But to achieve this exponential speedup, we will need to slightly modify the lens through which we see the factorization problem. So, let’s do that.