Arduous Factorization

Let’s discuss the preliminaries necessary for understanding Shor's Algorithm. We start with describing the factoring problem and its classical solution.

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 1515, into its prime factors as 15=3×515 = 3\times5 or another number, let’s say 17481748, as 1748=22×191×2311748=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 (1010010^{100}), takes O(exp1.9(logN)13(loglogN)23)O(\exp{1.9(\log N)^{\frac{1}{3}}(\log \log N)^{\frac{2}{3}}}) to factor an integer NN.

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((logN2(loglogN)(logloglogN)))O((\log {N}^{2}(\log\log N)(\log \log \log N))) or O(N3)\approx O(N^{3}), roughly cubic time complexity.

Create a free account to view this lesson.

By signing up, you agree to Educative's Terms of Service and Privacy Policy