Shor’s algorithm, introduced by Peter Shor in 1994, is a foundational quantum algorithm designed to factor large integers efficiently. This problem—factoring composite numbers into their prime components—is widely regarded as computationally hard for classical algorithms when the integers involved are sufficiently large. Shor’s contribution remains one of the most prominent demonstrations of how quantum computation can surpass classical methods in solving certain mathematically significant problems. The ability to factor integers into prime numbers has profound implications in the field of cryptography, especially since it breaks wide-used public-key encryption systems like RSA. Factoring also makes for a great test case when talking about “quantum advantage.” It belongs to a group of problems—NP problems—that are (believed) hard to solve, but easy to check. Given two primes, it is easy to check they multiply to a given number. But going the other direction? That’s the hard part.
How does Shor’s algorithm work?
Shor’s algorithm consists of three main parts.
- A classical reduction of the factoring problem to the problem of finding the period rr of a function f(x)=ax mod Nfx=ax mod N where NN is the number to be factored.
- A quantum algorithm which is the quantum phase estimation. It includes a famous subroutine called Quantum Fourier Transform (QFT).
- An efficient classical post-processing step that allows to extract the period rr from the measurement outcomes of the quantum phase estimation. This last step relies on the continued fractions algorithm.
Frequently asked questions
Why is Shor’s algorithm important?
Shor’s algorithm is the first quantum algorithm that solves a real-world problem exponentially faster than the best-known classical algorithm. Its discovery motivated a lot of interest in quantum computing.
Can current quantum computers run Shor’s algorithm for meaningful numbers?
Alas not yet. Though experimental demonstration of Shor’s algorithm running on a quantum device have been carried out for factoring the number 15 for instance, today’s quantum devices are not large enough and noise-free enough to run large-scale factoring. Running Shor’s algorithm require a large-scale error corrected computer.