In May 1981, Richard Feynman gave the keynote at the First Conference on the Physics of Computation at MIT and posed a question that has organized the field since: can a classical computer simulate the behavior of a quantum-mechanical system? Feynman's answer was structural: no, not efficiently — the state space of n quantum particles grows as 2ⁿ dimensions, and any classical simulation must use exponential resources. The corollary he suggested has become the field: a computer that is itself quantum-mechanical might do it. Four years later, David Deutsch at Oxford published the formal quantum Turing machine model. In 1994, Peter Shor at Bell Labs published an algorithm that factors integers in polynomial time, breaking RSA — and quantum computing went from theoretical curiosity to strategic-funding priority overnight.
A classical bit is in one of two states: 0 or 1. A qubit is in a superposition: |ψ⟩ = α|0⟩ + β|1⟩, with complex amplitudes whose squared magnitudes sum to 1. Measurement collapses the superposition probabilistically and destroys the amplitude information. n qubits in coherent superposition form a 2ⁿ-dimensional state space — a thousand qubits exist in a state space larger than the number of atoms in the observable universe. Entanglement is the non-classical correlation between qubits whose state cannot be described as a product of individual qubit states. Quantum gates are unitary transformations of the state space; a small set (Hadamard, CNOT, T, Pauli X/Y/Z) is universal. Quantum algorithms exploit two features unavailable classically: quantum parallelism (computing on superposed inputs simultaneously) and quantum interference (designing computations so wrong answers cancel and right answers reinforce). Shor's algorithm factors integers in O((log N)³) by reducing factoring to period-finding via the quantum Fourier transform. Grover's algorithm (1996) gives a quadratic speedup for unstructured search. Quantum simulation algorithms — Hamiltonian simulation, VQE, QAOA — are the second major application class, addressing Feynman's original question about chemistry and materials science. The engineering challenge is decoherence — qubits interact with their environment and lose superposition on timescales of microseconds to milliseconds. Quantum error correction protects logical information by encoding it across many physical qubits; the surface code is the dominant approach, encoding one logical qubit in roughly a thousand physical qubits at present error rates. A fault-tolerant machine capable of running Shor on RSA-2048 requires roughly 4,000 logical qubits and therefore millions of physical qubits. Hardware platforms competing toward that target — superconducting circuits (Google Willow 2024, IBM Heron), trapped ions, photonic systems, neutral atoms, topological qubits — have not yet settled on a winning architecture.
Post-quantum cryptography is the largest immediate operational consequence. Because Shor's algorithm threatens RSA, elliptic-curve cryptography, and Diffie-Hellman — essentially every public-key system in current use — the cryptographic community has spent fifteen years developing alternatives. NIST announced the first final post-quantum standards in August 2024: CRYSTALS-Kyber (now ML-KEM), CRYSTALS-Dilithium, SPHINCS+, and Falcon. US federal agencies have until 2035 to complete migration. The harvest-now, decrypt-later threat — adversaries collecting encrypted traffic today to decrypt later — has made migration a near-term priority. Google Chrome, Cloudflare, and Apple iMessage deployed hybrid post-quantum key exchange in 2023-24. On the advantage side, the most-watched commercial applications are molecular simulation, materials science, and combinatorial optimization. Quantum advantage — a useful task performed faster than the best classical alternative — has not yet been clearly demonstrated for any commercial application.