Shor's Algorithm - Beating Around the Bush

This lesson is the converging point of the preliminary lessons on QFT and QPE. We finally address Shor's Algorithm and see how it enables polynomial-time factorization of large numbers.

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 NN, 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 xx is a factor of NN if dividing NN by xx gives a remainder of 00. This straight away gives us two factors for NN: xx and qq where qq is Nx\frac{N}{x}. This was quite easy to do. Sadly, easy NNs 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 NN is a product of two prime numbers pp and qq, that is, N=pqN=pq, where pp and qq 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 (O(n3)\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.

Get hands-on with 1200+ tech skills courses.