| Shor's algorithm | |
|---|---|
| Name | Shor's algorithm |
| Developer | Peter Shor |
| Introduced | 1994 |
| Field | Quantum computing |
| Purpose | Integer factorization and discrete logarithms |
| Complexity | Polynomial time on a Quantum computer |
Shor's algorithm
Shor's algorithm is a quantum algorithm for integer factorization and related problems, discovered by Peter Shor in 1994. It showed that a sufficiently large quantum computer could factor large integers in polynomial time, threatening widely used public-key cryptosystems and motivating research in quantum information and post-quantum cryptography. The algorithm combines classical number theory with quantum subroutines such as the quantum Fourier transform.
Shor's algorithm occupies a central role in Quantum physics because it provides a concrete demonstration that quantum mechanical principles—superposition and entanglement—can lead to asymptotic speedups for computational tasks believed hard for classical machines. The result spurred experimental efforts at institutions such as IBM, Google, Rigetti Computing, University of Oxford, and laboratories like Institute for Quantum Computing and National Institute of Standards and Technology (NIST). The algorithm also catalysed the formal development of quantum complexity theory and benchmarks for noisy intermediate-scale quantum (NISQ) devices.
Shor's algorithm reduces integer factorization to the problem of order finding. Given an odd composite integer N and an integer a with 1 < a < N and gcd(a,N)=1, the algorithm seeks the smallest positive integer r such that a^r ≡ 1 (mod N); r is the order of a modulo N. From a nontrivial period r one can often extract a nontrivial factor of N via gcd(a^{r/2} ± 1, N). The underlying number-theoretic concepts draw on work by Euclid (gcd), properties of modular arithmetic, and classical algorithms such as the Euclidean algorithm and fast modular exponentiation.
At a high level, Shor's algorithm interleaves classical and quantum computation. Classically one selects random a coprime to N and performs trivial tests (e.g., trial division). The quantum part constructs a superposition over input exponents and evaluates the modular exponentiation function f(x)=a^x mod N. Key quantum circuit components include registers of qubits, modular exponentiation circuits built from quantum arithmetic primitives, and the quantum Fourier transform (QFT). The algorithm requires coherent control of entangling gates (e.g., CNOT gate, controlled modular multiplication), reversible arithmetic similar to arithmetic in Toffoli gate based circuits, and measurement to collapse the period information into a classical value that is post-processed by continued fraction expansion to recover r.
The QFT is the quantum analogue of the discrete Fourier transform and is central to period finding in Shor's algorithm. Applied to the superposed input register, the QFT concentrates amplitude on basis states corresponding to integer multiples of the reciprocal of the period r, allowing measurement outcomes that with high probability yield information from which r can be determined. The QFT on n qubits can be implemented using O(n^2) elementary gates (or O(n log n) with approximations) and uses controlled phase rotations; its efficient realization contrasts with the classical discrete Fourier transform's cost when performed in quantum amplitude space.
Shor's algorithm runs in time polynomial in log N using a quantum computer: roughly O((log N)^3) to O((log N)^2 log log N log log log N) depending on arithmetic optimizations and gate models. This contrasts sharply with the best-known classical factoring algorithms such as the general number field sieve (GNFS), which run in sub-exponential time exp((c+o(1))(log N)^{1/3}(log log N)^{2/3}). As a consequence, Shor's algorithm renders problems like factoring and discrete logarithms in complexity classes believed easier under quantum computation (e.g., factoring ∈ BQP) while remaining outside current classical algorithmic reach for large N. Practical performance depends on qubit count, gate fidelity, and error correction overhead.
Implementing Shor's algorithm at scale faces major experimental challenges: large numbers of high-fidelity qubits, low error rates, scalable quantum error correction (e.g., surface code), and efficient reversible modular arithmetic circuits. Early small-scale demonstrations implemented proof-of-principle factoring of small numbers (e.g., factoring 15) on platforms including nuclear magnetic resonance, ion trap quantum computers, and superconducting qubit processors. Scaling to cryptographically relevant sizes (thousands of logical qubits) requires fault-tolerant architectures, long coherence times, and substantial engineering advances; organizations such as Microsoft Quantum, D-Wave Systems (annealing approach), and academic groups continue research toward these milestones.
The primary application of Shor's algorithm is breaking public-key cryptosystems whose security rests on integer factorization or discrete logarithms, notably RSA, Diffie–Hellman key exchange, and elliptic-curve cryptography (ECC). The prospect of large-scale quantum attacks accelerated the field of post-quantum cryptography and standardization efforts led by NIST to identify quantum-resistant algorithms (e.g., lattice-based schemes like CRYSTALS-Kyber and CRYSTALS-Dilithium). Beyond cryptanalysis, Shor-like period-finding techniques inform quantum algorithms for problems in algebraic number theory and chemistry, and drive development of quantum hardware, error correction theory, and cryptographic policy considerations for governments and industries.
Category:Quantum algorithms Category:Computational number theory