Overview
Direct Answer
Shor's Algorithm is a polynomial-time quantum algorithm for factorising large composite integers, published by Peter Shor in 1994. It achieves exponential speedup over classical algorithms such as the general number field sieve, reducing the computational complexity from sub-exponential to polynomial time.
How It Works
The algorithm leverages quantum superposition and entanglement to identify the period of a modular exponential function. It uses the quantum Fourier transform to extract periodicity information from a superposed state, then applies classical post-processing to derive factors from the discovered period. The period-finding subroutine—the quantum core—runs in polynomial time, whereas classical period-finding requires exponential evaluation.
Why It Matters
The algorithm poses a theoretical threat to RSA and elliptic-curve cryptography, which underpin financial transactions, secure communications, and digital signatures across enterprises. This cryptographic vulnerability has driven urgent investment in post-quantum cryptography standards and quantum-resistant key exchange protocols by organisations including NIST and industry security leaders.
Common Applications
Potential applications include breaking RSA encryption used in legacy banking infrastructure and compromising TLS certificates in transit. Academic research focuses on factorising benchmarks; no practical large-scale cryptanalytic deployment exists due to quantum hardware immaturity.
Key Considerations
Implementation requires fault-tolerant quantum computers with thousands of logical qubits; current quantum processors lack the stability and scale necessary for cryptographically relevant integer sizes. The algorithm's theoretical power remains unrealised in practice, making near-term impact unlikely despite long-term strategic risk.
Cross-References(1)
More in Quantum Computing
Quantum Circuit
FundamentalsA sequence of quantum gates applied to qubits to perform a quantum computation.
Quantum Operating System
FundamentalsSystem software designed to manage quantum computing resources, schedule operations, and handle error correction.
Qiskit
FundamentalsIBM's open-source quantum computing framework for creating and running quantum programs.
Quantum Sensing
ApplicationsUsing quantum mechanical effects to achieve measurement sensitivities beyond what classical sensors can achieve.
Quantum Approximate Optimisation Algorithm
Hardware & ImplementationA hybrid algorithm designed to solve combinatorial optimisation problems on near-term quantum hardware.
Hybrid Quantum-Classical Computing
FundamentalsComputing architectures that combine quantum processors with classical computers to leverage the strengths of both.
Topological Qubit
Hardware & ImplementationA qubit design that encodes information in the topological properties of matter, offering inherent error protection.
Quantum Register
FundamentalsA collection of qubits that together store quantum information for processing in a quantum circuit.