Shor's Algorithm, named after mathematician Peter Shor, is a quantum algorithm designed to efficiently factorize large composite numbers. It's one of the most famous and impactful algorithms in quantum computing, as it provides an exponential speedup over the best-known classical algorithms for factoring. The ability to factor large numbers has significant implications for cryptography, particularly RSA encryption.
Shor's Algorithm can factor a composite number \( N \) in polynomial time, specifically O((log N)3), compared to the exponential time required by classical algorithms. This efficiency has made Shor's Algorithm a symbol of the potential power of quantum computing and has spurred interest in post-quantum cryptography, which seeks cryptographic methods resistant to quantum attacks.
Shor's Algorithm is more than just a method for factoring numbers; it's a foundational result that has shaped the field of quantum computing. It has inspired further research into quantum algorithms, complexity theory, and the development of quantum-resistant cryptographic protocols.
Shor's Algorithm represents a landmark achievement in quantum computing, showcasing the potential of quantum algorithms to solve problems previously considered intractable. Its discovery has had a profound impact on both the theoretical and practical aspects of quantum computing and cryptography.
For an introduction to the algorithm by Peter Shor himself, Physics World has a 2:09 video titled “What is Shor’s factoring algorithm?” on YouTube. Then for more information, the Quantiki article “Shor's factoring algorithm” provides the mathematics wrapped in plain English. And for a deep dive, you can download “Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms on a Quantum Computer,” the original preprint of the algorithm.
Shor's factoring algorithm finds one of two unknown variables that are crucial for efficiently factoring an integer. With two unknowns in one equation, finding both values quickly becomes classically intractable as the target integer gets larger. There are classical algorithms to find one of those values, but they become increasingly inefficient as the target integer gets larger. With Shor's quantum algorithm finding that value efficiently, it then becomes considerably easier to find the other value.
Specifically, an unknown integer g when multiplied by itself p times and modulo divided by the integer N we want to factor equals one, or gp%N=1. We start off knowing the number N we want to factor. Shor’s Algorithm estimates p, the period of N, so we only need to guess g. Using the smallest practical number N, which is N=15, Shor’s Algorithm returns period p=4. We can see that with g4%15=1 we can guess g=2, which results in 24%15=1, or 16%15=1, being true. Guessing g gets harder as N grows larger, but not as hard as guessing both g and p. Together, we can use guess g, period p, and number N to find the factors of N.
The core of Shor's Algorithm is the Quantum Fourier Transform (QFT), a quantum analog of the classical Fourier Transform. The QFT allows the algorithm to find the period of a specific mathematical function related to the number being factored. Once the period is found, the prime factors can be efficiently extracted using classical methods.
The entire quantum component of the algorithm is Quantum Phase Estimation (QPE), which incorporates the QFT. QPE uses modular exponentiation and the inverse of the QFT to estimate the phase of a quantum state. The classical information retrieved from measuring the circuit is then used by classical algorithms such as continued fraction factoring to efficiently determine the factors of the target integer.
The problem of factoring a large composite number into its prime factors is classically hard, meaning that the time required to solve it grows rapidly with the size of the input. RSA encryption, widely used in secure data transmission, relies on the difficulty of factoring large numbers. Shor's Algorithm, by efficiently solving this problem, poses a potential threat to RSA and similar encryption schemes. Shor's algorithm complexity is exponentially more efficient than known classical algorithms, such as Quadratic Sieve or General Number Field Sieve.
Shor's factoring algorithm also highlights the computational power of QPE and QFT, which have applications beyond integer factorization. One of the most talked about potential applications of quantum computing, for example, is quantum chemistry. QPE can compute the ground state energies of molecules with the same exponential efficiency advantage as it bestows upon integer factorization.
While Shor's Algorithm is theoretically efficient, its practical implementation on current quantum computers is challenging. It requires a significant number of qubits and error-corrected operations. Efforts to implement Shor's Algorithm have led to valuable insights into quantum error correction, algorithm optimization, and hardware development.
In fact, the size of the quantum circuit resulted in the discovery of one of the earliest Quantum Error Correction (QEC) codes, also by Peter Shor, known as Shor’s Code. To avoid confusion, “Shor’s Algorithm” refers to the factoring algorithm, and “Shor’s Code” refers to the quantum error correction code (QECC) that would make it possible to implement Shor’s Algorithm on fault-tolerant quantum computers (FTQC). FTQC will use newer, more sophisticated codes, but many of these potential codes are the children and grandchildren of Shor’s Code.
.svg){kind=small}
