| Shor's algorithm | |
|---|---|
| Name | Shor's algorithm |
| Author | Peter Shor |
| Introduced | 1994 |
| Field | Quantum computing |
| Problem | Integer factorization and discrete logarithms |
| Complexity | Polynomial-time on a Quantum computer |
| Implements | Quantum Fourier transform |
Shor's algorithm
Shor's algorithm is a quantum algorithm for integer factorization and computing discrete logarithms, discovered by Peter Shor in 1994. It showed that a quantum computer could solve certain number-theoretic problems exponentially faster than the best known classical algorithms, with profound implications for public-key cryptography and the stability of digital communication. Within Quantum Physics, Shor's algorithm is a cornerstone example of how quantum superposition and entanglement can be harnessed for algorithmic speedup.
Shor's algorithm exploits core principles of Quantum mechanics—notably superposition, interference, and entanglement—to perform a global period-finding procedure that reduces integer factorization to a problem solvable in polynomial time on a universal quantum device. Its introduction galvanized research in quantum information theory and motivated large-scale experimental programs at institutions such as IBM, Google, Rigetti Computing, and national laboratories including NIST and Los Alamos National Laboratory. The result sharpened theoretical interest in quantum complexity classes like BQP and prompted renewed emphasis on quantum error correction techniques developed by researchers such as Peter Shor (also notable for the Shor code) and Andrew Steane.
The algorithm reduces factorization of an integer N to period finding for a function f(x)=a^x mod N for a randomly chosen integer a coprime to N, connecting to classical results in number theory such as the Euler totient and the multiplicative order. The core mathematical tools include modular arithmetic, continued fractions for rational approximation, and the Quantum Fourier transform (QFT) which provides exponential information compression about periodicity. Shor's paper built on computational complexity theory results (e.g., relationships between classes like P and NP), and informed cryptanalytic study of schemes based on the presumed hardness of factoring and discrete logarithm problems in groups underlying RSA and elliptic-curve systems.
The canonical circuit comprises two main registers and three stages: state preparation, period estimation via the QFT, and classical post-processing. Initially, a uniform superposition is prepared with quantum gates described in the quantum gate model (Hadamard, controlled modular multipliers, and QFT circuits). A modular exponentiation subroutine, implementable using reversible arithmetic and controlled operations, entangles registers. Measurement of the first register collapses to an outcome whose distribution encodes the period; the continued fraction algorithm applied classically yields candidate divisors. Implementations require coherent use of controlled multiplication by a mod N and efficient decomposition of gates into a universal set such as Clifford gates plus non-Clifford rotations. Error rates and decoherence call for quantum error correction and fault-tolerant constructions like the surface code for scalable realization.
Shor's algorithm runs in expected polynomial time O((log N)^3) or variants with improved exponents, contrasting with the best classical factoring algorithms such as the general number field sieve which are sub-exponential. The quantum advantage is asymptotic and requires large-scale fault-tolerant qubit arrays; current noisy intermediate-scale quantum (NISQ) devices lack sufficient qubit counts and coherence to factor large cryptographic keys. Practical performance depends on circuit depth, gate fidelity, and overhead from error correction—estimates for breaking typical 2048-bit RSA keys often require millions of logical qubits and substantial quantum fault tolerance resources. Limitations also arise from classical post-processing success probabilities and the need for random choices of bases a with nontrivial orders.
Small instances of Shor's algorithm have been demonstrated on diverse platforms: trapped ions (e.g., experiments at University of Innsbruck), superconducting qubits (groups at Google and IBM Research), photonic systems (work by University of Bristol and Xanadu), and nuclear magnetic resonance (NMR) prototypes. Demonstrations have factored small integers like 15 and 21, or implemented core subroutines such as order-finding and modular exponentiation in constrained qubit spaces. Progress in qubit coherence, gate fidelities, cryogenic control (for superconducting circuits), and ion-trap architectures directly maps to improved practical feasibility. Industry consortia and national programs—such as the US National Quantum Initiative—prioritize scaling, interconnectivity, and error correction milestones relevant to full algorithm deployment.
Shor's algorithm threatens cryptosystems whose security depends on factoring or discrete logarithms, notably RSA, Diffie–Hellman, and many elliptic-curve schemes. This risk has driven the field of post-quantum cryptography and standardization efforts by bodies such as NIST to adopt quantum-resistant algorithms (lattice-based, code-based, multivariate). Governments and military agencies consider migration strategies, key management, and transition timelines to preserve secure communication and national infrastructure. The strategic importance has spurred public–private investment and policy initiatives balancing technological innovation with prudent defense of critical cryptographic systems.
Extensions include optimized variants of period finding, resource-reduced modular exponentiation techniques, and algorithms for the discrete logarithm problem in various groups. Related quantum algorithms demonstrating exponential speedups include Simon’s algorithm and algorithms for hidden subgroup problems in abelian and certain non-abelian groups. Research links to quantum simulation approaches, algorithmic primitives like amplitude amplification (Grover's algorithm), and hybrid classical–quantum strategies. Continued theoretical work explores fault-tolerant resource estimation, bespoke hardware co-design, and cryptanalytic uses in national research programs to ensure resilience and uphold secure communications as quantum capabilities mature.
Category:Quantum algorithms Category:Quantum computing Category:Cryptanalysis