| BQP | |
|---|---|
| Name | BQP |
| Introduced | 1990s |
| Related | Quantum computing, Complexity class |
| Problems | Integer factorization (believed) |
| Hardware | Quantum computer |
BQP
BQP (Bounded-Error Quantum Polynomial time) is the class of decision problems solvable by a polynomial-time quantum algorithm with bounded error probability. It formalizes the notion of efficient computation on a model of quantum computation such as the quantum circuit model or quantum Turing machine, and it is central to assessing the computational power of devices developed by organizations like IBM, Google and research laboratories such as IBM Quantum, Google Quantum AI, and IQC (Institute for Quantum Computing). BQP's significance spans foundational quantum mechanics questions and practical impacts on cryptography, economics, and equity.
BQP is typically defined using the uniform family of quantum circuits acting on qubits with gates drawn from a finite universal set (e.g., Hadamard, Toffoli, T gate). A language L is in BQP if there exists a polynomial-time uniform family of quantum circuits {C_n} such that for every input x of length n, C_n outputs the correct decision with probability at least 2/3; the constant 2/3 is arbitrary and can be amplified by standard techniques. Formal models include the quantum Turing machine introduced by David Deutsch and later formalizations by Ethan Bernstein and Umesh Vazirani. The class is robust under choice of gate set, error bounds, and reasonable encodings, analogous to robustness results for P and BPP.
BQP sits within the landscape of computational complexity theory as the quantum analogue of classical randomized polynomial time. It is contained in PSPACE under general assumptions and is suspected to strictly contain classes such as P and maybe BPP while not containing NP-complete problems unless unexpected consequences follow for NP. Early formal complexity results were developed by researchers including Bernstein and Vazirani, Peter Shor and Lov Grover. Complexity-theoretic questions about BQP connect to structural conjectures like the Polynomial Hierarchy and to hardness assumptions used in theoretical and applied cryptography.
Canonical quantum algorithms that demonstrate BQP's power include Shor's algorithm for integer prime factorization and discrete logarithms, and Grover's algorithm for unstructured search. Problems believed to lie in BQP but not in classical polynomial time include factoring and certain instances of the Hidden Subgroup Problem, which relates to groups studied in algebra and number theory. The notion of BQP-complete problems is less settled than for classical classes; natural complete problems for BQP under appropriate reductions have been proposed, such as the Local Hamiltonian problem in certain promise-problem variants and simulation tasks derived from quantum Hamiltonian complexity (work by John Preskill and researchers at Caltech and MIT). Quantum simulation of many-body Hamiltonian dynamics, inspired by Richard Feynman's original proposal of quantum simulators, provides tasks believed inherently suited to BQP.
Known inclusions and separations are central open areas. It is known that BQP is contained in AWPP and therefore in PP and PSPACE, while classical relationships such as BQP versus NP or BQP versus PH remain unresolved. Oracle results (relativized worlds) by Scott Aaronson and others provide evidence that BQP differs from BPP and from SZK in some oracles. Results connecting BQP to interactive proof systems and classes like QMA (Quantum Merlin–Arthur) illuminate verification questions: QMA is the quantum analogue of NP and contains problems like the k-local Hamiltonian as QMA-complete. Such relations have implications for understanding quantum verification, delegated quantum computing, and complexity-theoretic limits.
Implementing BQP-complete or BQP-internal computations requires scalable quantum hardware with low error rates, high-fidelity gates, and quantum error correction such as the surface code or concatenated code. Resource accounting includes qubit count, gate depth, circuit width, coherence time, and fault-tolerance overheads studied by experimental groups at D-Wave Systems, Rigetti Computing, IonQ, and national labs like Los Alamos National Laboratory and Sandia National Laboratories. Theoretical resource models relate to thermodynamic costs, control noise, and error models tied to open quantum systems and decoherence. Equity and access issues emerge because advanced quantum infrastructure concentrates at wealthy institutions and corporations, raising policy questions about shared access, workforce development, and public benefit.
BQP's ability to efficiently perform tasks like factoring threatens widely used public-key cryptosystems (e.g., RSA, Diffie–Hellman), prompting development of Post-quantum cryptography standards by agencies such as NIST. The transition implicates national security, economic fairness, and privacy—entities with early quantum advantage may gain disproportionate power. Conversely, quantum-resistant algorithms and quantum cryptographic primitives (e.g., quantum key distribution by groups like ID Quantique) offer new avenues for secure communication. Policy debates involve equitable deployment, preventing technological monopolies, and funding public research to ensure benefits accrue broadly.
Key open problems include proving separations between BQP and classical classes like BPP or NP, characterizing natural BQP-complete problems under standard reductions, and refining resource-cost models for fault-tolerant computation. Research directions span algorithm design (quantum machine learning, optimization heuristics), complexity-theoretic foundations (oracle separations, relativization, and derandomization), and experimental scaling of qubit counts and error correction. Socially engaged research emphasizes responsible innovation, inclusive workforce development, and governance frameworks to mitigate risks and distribute benefits, advocated by scholars and institutions such as ACM and IEEE working groups. Continued interdisciplinary work across physics, computer science, mathematics, and public policy is essential for realizing BQP's potential in an equitable manner.
Category:Quantum complexity theory Category:Quantum computing