Concept
Algorithms using quantum superposition — Shor 1994 cast a shadow on RSA security.
Understand it in one breath
"Use quantum superposition and entanglement to reach speeds impossible for classical computers." In 1994 Shor's algorithm turned integer factoring from exponential to polynomial time — a future threat to RSA. In 1996 Grover's algorithm gave √N speedup for unstructured search. Google demonstrated quantum supremacy for the first time in 2019.
At a glance
Algorithm | Problem | Classical time | Quantum time | Significance |
|---|---|---|---|---|
Deutsch (1985) / Deutsch-Jozsa (1992) | Is f constant or balanced? | O(2ⁿ⁻¹+1) | O(1) | First proof of an intrinsic quantum speedup |
Shor (1994) | Factor a large integer N | exp(O(n^(1/3))) | O(n³) | Threatens RSA and internet cryptography |
Grover (1996) | Search unsorted data | O(N) | O(√N) | Quadratic speedup for search |
HHL (2009) | Linear system Ax=b | O(N) | O(log N) | Potential acceleration for ML and simulation |
Quantum supremacy (Google 2019) | Random-circuit sampling | ~10,000 years | 200 seconds | First demonstration of quantum advantage |
Depending on the problem, quantum algorithms offer exponential speedup (Shor), quadratic speedup (Grover), or no advantage (most everyday problems) — they do not make everything faster.
Key formula
Key moments
Deutsch — a blueprint for quantum computing
David Deutsch described the universal quantum computer through a quantum analogue of a Turing machine, establishing a theoretical starting point for the field.
Shor’s algorithm — a warning for RSA
Peter Shor discovered a quantum algorithm that can factor large integers efficiently, showing how a sufficiently capable quantum computer could break RSA.
Grover — a quadratic speedup
Grover’s algorithm searches an unstructured space in roughly √N steps rather than N, effectively halving the security strength of a symmetric cryptographic key against brute force.
Google claims quantum supremacy
Google reported that its 53-qubit Sycamore processor completed a sampling task in about 200 seconds that it estimated would take a leading classical supercomputer around 10,000 years — a debated benchmark.
Modern applications
Post-quantum cryptography, drug-discovery simulation, optimization, quantum machine learning, and quantum chemistry.
Beyond MathVoyage
Loading…