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.