| BQP | |
|---|---|
| Name | BQP |
| Introduced | 1990s |
| Type | Probabilistic quantum |
| Problem | Decision problems |
| Best known complete | Period finding (under certain reductions) |
| Related | P, NP, BPP, QMA |
BQP
BQP (Bounded-Error Quantum Polynomial time) is the class of decision problems solvable by a uniform family of quantum circuits in polynomial time with error probability bounded below 1/3. It formalizes the notion of efficient quantum computation and is central to theoretical Quantum Physics study of computational power enabled by quantum mechanics. BQP matters because it captures tasks for which quantum algorithms such as Shor's algorithm and Grover's algorithm offer asymptotic or practical advantages over classical algorithms.
BQP is defined using the circuit model of quantum computation: a problem L is in BQP if there exists a polynomial-time classical algorithm that outputs a description of a polynomial-size family of quantum circuits (or quantum Turing machines) such that for every input x the circuit accepts with probability ≥ 2/3 when x∈L and ≤ 1/3 when x∉L. The constants 2/3 and 1/3 are arbitrary error bounds that can be amplified by repetition or by techniques analogous to majority voting. Formalizations of BQP rely on the theory of quantum gate sets, with universality results by David Deutsch, Ethan Bernstein, and Umesh Vazirani showing equivalence between uniform quantum circuits and quantum Turing machines. The definition presumes access to quantum amplitude manipulation consistent with the postulates of quantum mechanics and unitary evolution.
The quantum computational model underlying BQP uses qubits, unitary gates (e.g., Hadamard gate, CNOT gate, phase gates), and projective measurement. Universal gate sets such as the Solovay–Kitaev theorem-compatible sets permit efficient approximation of arbitrary unitaries. Prominent algorithms that motivate BQP include Shor's algorithm for integer factorization and discrete logarithms, and Grover's algorithm for unstructured search, each demonstrating different resource scalings: exponential speedup for period-finding problems and quadratic speedup for search. Quantum phase estimation and the quantum Fourier transform are subroutines central to many BQP algorithms. Complexity-theoretic formalism also studies quantum space-bounded computation (BQL) and interactive variants like QIP to situate BQP among other quantum classes.
BQP is believed to strictly contain classical probabilistic polynomial time BPP, though this is not proven. Known inclusions place BQP within classes defined with respect to classical oracles: BQP ⊆ PP by a counting argument, and BQP is contained in AWPP under specific technical conditions. Relationships to deterministic classes P and nondeterministic classes NP remain unresolved; problems in NP (e.g., SAT) are not known to be in BQP, and BQP is not known to contain NP-complete problems unless widely believed complexity-theoretic separations fail. Oracle results by researchers such as Scott Aaronson and Constantin Zalka exhibit relativized worlds where BQP is incomparable with NP or where BQP ⊄ PH (the polynomial hierarchy), informing conjectures about nonrelativizing techniques.
Unlike NP, BQP lacks natural complete problems under polynomial-time many-one reductions widely accepted as appropriate; nevertheless, several problems are BQP-complete under restricted reductions or promise-problem formulations. Examples include the period-finding and certain instances of estimating eigenvalues or amplitudes (quantum amplitude estimation) and the problem of approximating the Jones polynomial at specific roots of unity (links via topological quantum computation). Oracle separations exhibit that relative to some oracles, BQP is not contained in PH, as shown in work by Scott Aaronson and Alex Arkhipov among others. Such oracle and promise-problem results help delineate the boundaries of BQP in the absence of unconditional separations.
Realizing BQP in physical devices requires scalable quantum computing hardware capable of implementing arbitrary poly-size circuits with low error. Platforms pursued in experimental quantum information science include superconducting qubits (IBM Quantum, Google Quantum AI), trapped ions (e.g., IonQ, Honeywell Quantum Solutions), photonic systems (e.g., Xanadu), and topological proposals motivated by Kitaev's anyon models. Achieving fault-tolerant BQP computation depends on quantum error correction codes such as the surface code and concatenated CSS codes, and thresholds quantified by the threshold theorem that specify permissible physical error rates. Practical demonstration of BQP-scale advantage requires control of decoherence, gate fidelity, and error-suppression techniques alongside scalable architectures.
BQP has deep implications for foundational and applied aspects of quantum information theory and cryptography. Quantum algorithms in BQP inform our understanding of entanglement, interference, and computational resource trade-offs in physical theories; conversely, hardness conjectures about BQP guide cryptanalytic assessments of cryptosystems such as those based on integer factorization and discrete logarithms, prompting development of post-quantum cryptography standards by organizations like NIST. Results about BQP also intersect with quantum simulation tasks advocated by Richard Feynman and formal models for simulating many-body quantum systems, where BQP captures efficient simulation capabilities under certain encodings. The study of BQP therefore bridges theoretical computer science and experimental quantum physics, shaping priorities for both algorithm design and quantum hardware engineering.
Category:Quantum complexity theory Category:Quantum computing