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 Approximate Optimisation Algorithm
Hardware & ImplementationA hybrid algorithm designed to solve combinatorial optimisation problems on near-term quantum hardware.
Quantum Advantage
Hardware & ImplementationThe practical ability of a quantum computer to solve real-world problems faster or better than classical computers.
Bloch Sphere
FundamentalsA geometrical representation of the state space of a single qubit as a point on the surface of a sphere.
Fault-Tolerant Quantum Computing
FundamentalsQuantum computing systems that can continue to operate correctly even in the presence of errors.
Quantum Teleportation
FundamentalsThe transfer of quantum states between qubits using entanglement and classical communication.
Quantum Simulation
ApplicationsUsing quantum computers to model and simulate quantum systems that are intractable for classical computers.
Quantum Entanglement
FundamentalsA phenomenon where two or more qubits become correlated such that the quantum state of one instantly influences the other regardless of distance.
Quantum Sensing
ApplicationsUsing quantum mechanical effects to achieve measurement sensitivities beyond what classical sensors can achieve.