[SCI] Quantum Computing Theory
Quantum Computing Theory studies the computational power of systems governed by quantum mechanics — qubits, quantum gates, algorithms — and the fundamental question of whether quantum computers can efficiently solve problems intractable for classical machines.
Overview
Feynman (1982) proposed quantum computers to simulate quantum systems. Deutsch (1985) defined the quantum circuit model. Shor's algorithm (1994) factors integers exponentially faster than any known classical algorithm, threatening RSA cryptography. Grover's algorithm (1996) gives a quadratic speedup for search. The quantum threshold theorem shows fault-tolerant quantum computation is possible with error rates below ~1% per gate. Quantum error correction codes (Shor 1995, Steane 1996, surface code) are the current frontier.
Key Figures & Recognition
- Peter Shor (1959–): Shor's algorithm. Turing Award 1998, Nevanlinna Prize.
- Lov Grover (1961–): Grover search algorithm.
- John Preskill (1953–): Coined "quantum supremacy," quantum error correction.
Seminal Papers
- Shor, P. "Algorithms for Quantum Computation: Discrete Logarithms and Factoring." FOCS (1994)
- Grover, L. "A fast quantum mechanical algorithm for database search." STOC (1996)
- Preskill, J. "Quantum Computing in the NISQ Era and Beyond." Quantum 2 (2018)
What This Enables
- [TECH] Quantum Computing Hardware — Theoretical requirements — fault tolerance thresholds, qubit connectivity, gate fidelity targets — guide hardware roadmaps.
Discovery Character
Surprise level: High — Shor's algorithm (1994) — showing that a quantum computer could factor integers exponentially faster than any known classical algorithm, threatening all public-key cryptography — was a genuine shock. Nobody had expected quantum computing to have such a direct and devastating implication for information security.
Mode: Systematic-theoretical. Shor was a mathematician at Bell Labs solving a specific algorithmic question; he did not set out to threaten cryptography. Grover's search algorithm (1996) followed similarly from systematic algorithmic analysis. The field is notable for tight interplay between quantum physics, information theory, and complexity theory — all systematic, no serendipity, but producing results more surprising than any of the inputs suggested.