| Shor's algorithm | |
|---|---|
| Name | Shor's algorithm |
| Inventor | Peter Shor |
| Introduced | 1994 |
| Field | Quantum computing |
| Related | Quantum Fourier transform; Integer factorization |
Shor's algorithm
Shor's algorithm is a quantum algorithm for integer factorization and discrete logarithms that runs in polynomial time on a quantum computer, dramatically outperforming the best known classical algorithms. It is widely regarded as a foundational result in Quantum computing and Quantum physics because it demonstrates how quantum mechanics can give exponential speedups for problems with deep practical and societal consequences, notably modern public-key cryptography.
Shor's algorithm was published by Peter Shor in 1994 and leverages key principles of quantum mechanics — superposition, interference, and entanglement — to solve integer factorization by reducing it to period finding. The algorithm combines modular arithmetic from number theory with the Quantum Fourier transform (QFT) to extract periodicity from quantum states, showing a concrete quantum advantage over classical techniques such as the general number field sieve and pollard's rho algorithm. Its existence catalyzed intensive research programs in quantum information science, influencing work at institutions like IBM, Google Quantum AI, Rigetti Computing, and academic groups at MIT, University of California, Berkeley, and University of Waterloo's Institute for Quantum Computing. The result also stimulated policy and funding initiatives for quantum technologies at agencies such as the National Science Foundation and national laboratories including Los Alamos National Laboratory.
The algorithm reduces factoring an integer N to finding the order r of a randomly chosen integer a modulo N, relying on modular exponentiation and properties of the multiplicative group (Z/NZ)*. Core mathematical elements include modular arithmetic, Euler's phi function, and the reduction that if a^r ≡ 1 (mod N) with r even, then gcd(a^{r/2} ± 1, N) yields nontrivial factors. The quantum subroutine prepares a superposition of computational basis states, applies modular exponentiation to produce an entangled state, and then performs the QFT to obtain frequency information from which r can be deduced with high probability. Classical post-processing involves the greatest common divisor (gcd) computation and continued fractions for extracting r from phase estimates. The original presentation appears in Shor's paper "Polynomial-Time Algorithms for Prime Factorization and Discrete Logarithms", which also influenced follow-up analyses by researchers in cryptography and computational number theory.
Implementation requires circuits for modular multiplication, modular exponentiation, and the QFT. Practical circuits use arithmetic building blocks such as Toffoli gates, controlled-U operations, and Hadamard gates, often synthesized into fault-tolerant gate sets like Clifford+T. Resource estimates account for qubit count, gate depth, and T-gate complexity; proposals vary from implementations using a few dozen logical qubits for toy instances to thousands or millions for cryptographically relevant key sizes. Experimental demonstrations have been performed on platforms including NMR quantum computers, ion trap systems (e.g., groups led by David Wineland), superconducting qubit devices (work by John Martinis and teams), and photonic quantum computing experiments. Quantum compiling, circuit optimization, and techniques such as phase estimation and amplitude amplification are important to reduce resource overheads.
Shor's algorithm runs in expected polynomial time, typically cited as O((log N)^3) or similar depending on implementation details, whereas the best classical factoring methods like the general number field sieve run in sub-exponential time. This constitutes an exponential separation in asymptotic complexity for factoring and discrete logarithms under standard complexity-theoretic assumptions. Complexity-theory implications link to classes such as BQP (bounded-error quantum polynomial time) and contrast with classical classes like NP and P. While theoretical speedup is clear, practical performance depends on error rates, qubit connectivity, and resource scaling; hybrid classical-quantum approaches and algorithmic improvements continue to be subjects of research.
Shor's algorithm threatens the security of widely deployed public-key systems, notably RSA, elliptic curve cryptography (ECC), and other schemes relying on the hardness of integer factorization or discrete logarithms. This prompted the field of post-quantum cryptography and standards efforts at organizations such as the National Institute of Standards and Technology (NIST) to develop quantum-resistant algorithms. The societal implications include risks to confidentiality, authentication, and critical infrastructure; governments and corporations now face decisions about cryptographic agility, migration plans, and long-term archival secrecy. Justice- and equity-focused analyses highlight that unequal access to quantum decryption capabilities could exacerbate geopolitical power imbalances and threaten privacy for vulnerable populations, motivating open standards, transparency, and capacity-building in under-resourced communities.
Realizing Shor's algorithm at scale requires robust quantum error correction (QEC) to mitigate decoherence and operational noise. Fault-tolerant architectures use codes such as the surface code and concatenated codes, incurring large overheads in physical qubits per logical qubit and in gate operations. Scalability also depends on fabrication, control electronics, cryogenics for superconducting systems, and photon loss control for optical platforms. Ongoing research addresses resource reduction via algorithmic optimizations, tailored QEC, and co-design between hardware and software. Equity-minded policy recommends international collaboration, open-access benchmarking, and diversion of resources to ensure benefits of quantum computing—including economic opportunities and scientific advances—are broadly shared rather than concentrated.
Category:Quantum algorithms Category:Cryptanalysis