| Quantum supremacy | |
|---|---|
| Name | Quantum supremacy |
| Field | Quantum physics |
| Introduced | 2010s |
| Notable examples | Sycamore, Zuchongzhi, BosonSampling |
| Related | Quantum computing, Quantum annealing, NISQ |
Quantum supremacy
Quantum supremacy is the milestone at which a quantum computer performs a computational task that is infeasible for any known classical algorithm running on existing supercomputer hardware. It matters in quantum physics and computer science because it marks a practical demonstration that quantum mechanics can enable qualitatively new computational capabilities, challenging assumptions about complexity and informing the development of quantum hardware, algorithms, and cryptography.
The term "quantum supremacy" was popularized by John Preskill in 2012 to denote a point where quantum devices outperform classical computers for a specific task. Early theoretical proposals such as Shor's algorithm (1994) and Grover's algorithm (1996) suggested asymptotic advantages, but they required fault-tolerant machines. In the 2010s, research shifted toward near-term demonstrations on NISQ devices, including proposals like BosonSampling (Aaronson and Arkhipov) and random circuit sampling that aimed at achieving supremacy with dozens to hundreds of qubits. Industrial efforts from companies and institutions such as Google (Quantum AI), IBM, Intel, Rigetti, D‑Wave and national laboratories (e.g., Oak Ridge National Laboratory, NIST) accelerated experimental attempts.
Quantum supremacy is framed within computational complexity theory by comparing the resources required by quantum models (e.g., the quantum circuit model, boson sampling model) to classical models such as the Turing machine and classical randomized algorithms. Hardness arguments often rely on conjectures like the non-collapse of the polynomial hierarchy and complexity assumptions specific to sampling problems. Notable theoretical constructs include BosonSampling, IQP circuits (Instantaneous Quantum Polynomial-time), and random quantum circuit sampling; researchers such as Scott Aaronson and Alex Arkhipov formalized complexity-theoretic evidence that these tasks are hard for classical computers. The literature connects to topics like #P-hardness, approximate simulation, and anticoncentration properties, and employs techniques from computational complexity theory and statistical mechanics.
Major experimental milestones include demonstrations by Google with the Sycamore processor (2019), which reported random circuit sampling results claimed to surpass classical supercomputers, and subsequent work by teams using Chinese processors such as Zuchongzhi developed by researchers at the USTC. Other platforms include superconducting qubits (transmon qubit architectures), trapped ions (e.g., systems from IonQ and academic groups), photonic quantum processors implementing BosonSampling (e.g., experiments by groups at University of Bristol), and quantum annealers sold by D‑Wave for optimization-style tasks. Demonstrations vary by qubit type, gate fidelity, connectivity, and error rates; key enabling technologies include cryogenic control electronics, microwave control, high-fidelity two-qubit gates, and error mitigation techniques.
Verifying supremacy experiments requires benchmarks and statistical tests. For sampling tasks, metrics such as linear cross-entropy benchmarking (XEB), fidelity estimation, and heavy-output generation tests are used to compare experimental output distributions against ideal quantum predictions. Classical simulation approaches (tensor network contraction, stabilizer methods, and hybrid quantum-classical algorithms) serve as baselines; improvements in classical algorithms have sometimes narrowed claimed quantum advantages. Independent verification approaches include cross-validation with alternative classical simulators, extrapolation via noise models, and interactive protocols where a classical verifier checks specific properties of quantum states (related to concepts from quantum verification and blind quantum computing). Standards bodies and academic benchmarks are evolving to address reproducibility and adversarial classical simulation.
Quantum supremacy experiments typically address specialized tasks—e.g., random circuit sampling or boson sampling—that do not immediately translate to broadly useful applications. However, they have practical implications: demonstrating control at scale informs pathways toward fault-tolerant quantum computing and impacts fields such as quantum chemistry (via algorithms like VQE), materials science, and optimization. They also affect post-quantum cryptography planning, as advancements in quantum hardware motivate the transition to quantum-resistant cryptographic standards. Industrial and governmental investment decisions in quantum hardware, workforce development, and standards have been influenced by supremacy milestones.
Critics note that supremacy demonstrations often target contrived problems chosen to be hard for classical simulators but not necessarily useful; this has prompted discussion about terminology and emphasis on "quantum advantage" for practical speedups. Challenges include error rates, qubit coherence times, cross-talk, scaling control electronics, and thermal management. Rapid advances in classical algorithms and specialized hardware (e.g., GPUs, tensor contraction optimizations) have repeatedly shifted the boundary between classical and quantum feasibility. Ethical and policy critiques address hype, resource allocation, and the need for rigorous verification standards.
Quantum supremacy is a milestone distinct from broad economic or scientific utility, often contrasted with "quantum advantage," which denotes a demonstrable improvement on a problem of practical importance. Future directions emphasize achieving fault-tolerant quantum computing via quantum error correction (e.g., surface code), scaling qubit counts while improving coherence and gate fidelity, and demonstrating advantage on useful tasks (quantum simulation, chemistry, optimization). Continued interplay among theorists (complexity theorists), experimentalists (in institutions like Caltech, MIT, Harvard University) and industry players (Google, IBM, Microsoft's quantum efforts) will shape timelines and benchmarks for when quantum devices move from supremacy demonstrations to widespread practical impact. Category:Quantum computing