| quantum complexity theory | |
|---|---|
| Name | Quantum complexity theory |
| Field | Theoretical computer science |
| Related | Quantum computing, Quantum information theory |
| Notable institutions | IBM, Google Quantum AI, Microsoft Research, Perimeter Institute for Theoretical Physics, QuTech |
| Notable people | Peter Shor, Lov Grover, John Preskill, Scott Aaronson |
quantum complexity theory
Quantum complexity theory studies the resources required to solve computational problems when computation is governed by the laws of quantum mechanics and implemented on quantum devices. It formalizes how notions such as time, space, randomness, and entanglement affect algorithmic efficiency, and connects foundational aspects of Quantum Physics with the mathematical framework of Computational complexity theory and Quantum computing.
Quantum complexity theory sits at the intersection of theoretical computer science and experimental quantum mechanics. It abstracts physical processes into models such as the quantum circuit model and Hamiltonian complexity, allowing rigorous statements about what can be computed under constraints imposed by coherence times, locality of interactions, or energy. Results in the field often rely on physical concepts like entanglement, decoherence, and the no-cloning theorem and inform feasibility assessments for devices developed by organizations such as IBM, Google Quantum AI, and academic groups at MIT, Caltech, and the Perimeter Institute for Theoretical Physics.
Central formal models include the quantum circuit model (circuits of quantum gates acting on qubits), the quantum Turing machine introduced by David Deutsch and variants like the quantum query model used to count oracle calls. Continuous-time models such as adiabatic quantum computation and models based on many-body physics lead to Hamiltonian complexity, which connects to paradigms like stoquastic Hamiltonian problems and the Quantum Adiabatic Theorem. Other models include measurement-based schemes such as one-way quantum computer and quantum cellular automata. Model comparisons underpin reductions between physical implementations and complexity-theoretic classes.
Quantum complexity theory defines classes that mirror classical ones: BQP (bounded-error quantum polynomial time) is the quantum analogue of BPP and captures decision problems solvable efficiently on a quantum computer. Classes such as QMA (quantum Merlin–Arthur) generalize NP with quantum proofs; QCMA is a variant with classical witnesses. Higher-level classes include QIP (quantum interactive proofs) and classes for space-bounded quantum computation like BQSPACE. Relationships among classes—e.g., containment results BPP ⊆ BQP ⊆ PP and separations conjectured between BQP and NP—are central research topics. Complexity of local Hamiltonians yields QMA-completeness results analogous to NP-completeness for classical constraint satisfaction.
Quantum complexity theory studies algorithmic speedups and lower bounds. Landmark algorithms include Shor's algorithm for integer factorization and discrete logarithms, and Grover's algorithm for unstructured search, establishing separations between BQP and classical classes under plausible assumptions. Query complexity and adversary methods provide lower bounds for black-box problems. Results on simulation hardness, such as the conjectured classical intractability of sampling from boson sampling devices and complexity evidence from quantum supremacy experiments by Google and others, tie algorithmic complexity to experimental demonstrations. Complexity-theoretic hardness underpins cryptographic schemes resistant to quantum attacks and informs post-quantum cryptography work led by groups like the NIST process.
Quantum complexity also treats communication resources: quantum communication complexity measures qubit or entanglement cost in distributed tasks, with seminal results by Harry Buhrman, Richard Cleve, and collaborators on entanglement-assisted protocols. Interactive proof systems such as QIP and multi-prover variants like MIP^* examine the power of entangled provers; recent breakthroughs include the result MIP^* = RE with deep implications for operator algebras and the Connes embedding problem. Relationships between quantum interactive proofs and classical proof systems illuminate verification of quantum computations, as in the development of delegated quantum computation and protocols relying on blind quantum computing.
Resource measures in quantum complexity quantify not only time and space but also qubit count, entanglement entropy, and gate fidelity. The theory informs thresholds for fault-tolerant quantum computation and design of quantum error correction codes such as the surface code, stabilizer codes, and concatenated codes. Fault-tolerance theorems relate noise models to overheads required for scalable quantum computation; practical thresholds have been studied by researchers including John Preskill and groups at Microsoft Research and IBM. Complexity considerations also address thermodynamic and energy costs, connecting to research on reversible computing and the Landauer's principle in quantum settings.
Major open problems include pinning down separations between quantum and classical complexity classes (e.g., whether BQP lies outside PH), characterizing the full power of quantum proofs and interactive protocols, and refining hardness assumptions underpinning quantum advantage claims. Other directions involve connecting Hamiltonian complexity to condensed matter physics (e.g., classification of ground states), developing resource theories for entanglement and coherence with complexity implications, and establishing concrete complexity-theoretic guarantees for near-term devices (NISQ era) pursued by Rigetti Computing, IonQ, and academic testbeds. Progress often requires collaboration among theorists such as Scott Aaronson and experimentalists across institutions including Caltech, University of Oxford, and QuTech.
Category:Quantum information theory Category:Computational complexity theory