Arduous Factorization

Shor’s Algorithm was proposed by the American mathematician Peter Shor in 1994, and it promises prime factorization of numbers in polynomial time. This might seem like an easy problem, at first. After all, we learned the procedure for representing a number as a product of its prime factors in secondary school. Following the same process, we know that we can break down a number, let’s say $15$, into its prime factors as $15 = 3\times5$ or another number, let’s say $1748$, as $1748=2^{2}\times19^{1}\times23^{1}$.

It turns out that this problem is not that easy to do with larger numbers. In fact, the time complexity of our fastest and most efficient classical algorithms for prime factorization is exponential. Specifically, the general number field sieve algorithm, which is the fastest known algorithm for factoring numbers larger than a googol ($10^{100}$), takes $O(\exp{1.9(\log N)^{\frac{1}{3}}(\log \log N)^{\frac{2}{3}}})$ to factor an integer $N$.

As Peter Shor discovered in 1994, quantum computers can solve this problem much faster. In fact, Shor’s Algorithm provides an exponential speedup over its classical counterpart. Specifically, it gets rid of the exponential term and has an overall asymptotic time complexity of order $O((\log {N}^{2}(\log\log N)(\log \log \log N)))$ or $\approx O(N^{3})$, roughly cubic time complexity.

This is a significant advantage, considering that polynomial-time factorization of numbers with multiple hundreds of bits can break popular encryption algorithms like the RSA Algorithm. These algorithms are based on the idea that factorizing large numbers is an arduous task for computers, so we can use this property to formulate the public-private encryption key procedure to provide security over the internet.

However, while it is true that our quantum volumeA metric that gives the maximum size of square quantum circuits that can be successfully implemented using existing hardware is nowhere near the thousands of qubits required for breaking encryption standards, Shor’s Algorithm cannot be brushed under the carpet.

So, let’s start building up the preliminary concepts that we will need to understand Shor’s Algorithm. In the next lesson, we’ll start with the quantum analog of Fourier Transform.