Quantum Computing

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.