BQP

BQP
Bilorv · CC0 · source
Name	BQP
Type	Complexity class
Introduced	1993
Introduced by	Ethan Bernstein; Umesh Vazirani
Related	P, NP, PSPACE, BPP, QMA, EQP, AWPP

BQP

Bounded-Error Quantum Polynomial Time (BQP) is a complexity class capturing decision problems solvable by quantum computers in polynomial time with bounded error. Originating in the early 1990s, it formalizes the model of uniform polynomial-time quantum circuits and provides a framework for comparing quantum advantages against classical classes such as P, NP, BPP, and PSPACE. BQP occupies a central role in theoretical computer science and quantum information, informing work at institutions like IBM, Google, University of Waterloo, and MIT.

Definition and Formal Definition

BQP is defined as the class of languages for which there exists a polynomial-time uniform family of quantum circuits, composed from a finite universal gate set such as {Hadamard, T, CNOT}, that accepts with probability at least 2/3 on yes-instances and at most 1/3 on no-instances. The formal definition uses notions from quantum computation developed by researchers including Peter Shor, Lov Grover, Ethan Bernstein, and Umesh Vazirani. Uniformity is often specified in terms of classical polynomial-time Turing machines such as a deterministic machine in Stephen Cook's or Alan Turing's frameworks that output the description of the n-th circuit. Error bounds can be amplified by standard repetition and majority-vote techniques based on results akin to Joseph Gill's amplification lemmas and are robust against choice of universal gate set by solvers such as the Solovay–Kitaev theorem.

Computational Power and Relationships to Other Classes

BQP contains P and is contained in PSPACE under standard assumptions; the exact relations with NP and BPP are unresolved. Oracle separations established by techniques from Scott Aaronson and Andrew Yao show relative worlds where BQP differs from classes like PH (the Polynomial Hierarchy) and SZK. Complexity-theoretic reductions relate BQP to classes defined by quantum proofs such as QMA and exact quantum classes like EQP. Containments like BPP ⊆ BQP are supported by simulation results based on reversible computation formalized by Charles Bennett and coherence-preserving transforms used in implementations by John Preskill's group. Conversely, hard instances for BQP are constructed relative to oracles inspired by work at Bell Labs and proofs leveraging diagonalization methods from scholars influenced by Emil Post.

Complete Problems and Oracle Results

Unlike many classical classes, BQP lacks many natural complete problems under polynomial-time many-one reductions; however, several problems are complete for promise versions of BQP, including certain variants of the Approximate Shortest Vector Problem and simulation tasks derived from quantum Hamiltonians studied by Richard Feynman and David Deutsch. Oracle separations, such as those by Bernstein and Vazirani and later strengthened by Scott Aaronson and Alexei Kitaev, exhibit oracles A where BQP^A is not contained in or does not contain classes like PH^A or SZK^A. Reductions from problems like discrete logarithm and integer factorization, solved by Peter Shor's algorithm, place these as BQP-easy problems, while other problems from László Babai's group theory work relate to hidden subgroup frameworks that characterize families of BQP-computable tasks.

Algorithms and Examples

Key algorithms demonstrating BQP power include Shor's algorithm for integer factorization and discrete logarithm, and Grover's algorithm for unstructured search which gives a quadratic speedup over classical exhaustive search exemplified in Alan Turing-era formulations. Quantum simulation algorithms trace back to Richard Feynman's proposal for simulating quantum systems and have been developed by groups at University of Maryland and Caltech to simulate quantum chemistry and condensed-matter models such as the Hubbard model. Specialized quantum walk algorithms from researchers including Andrew Childs and Andris Ambainis provide exponential and polynomial separations for structured graph problems connected to Hamiltonian dynamics studied by Yoram Alhassid. Practical demonstrations of small BQP computations have been carried out on hardware from Google and IBM using superconducting qubits and trapped-ion platforms pioneered by groups at National Institute of Standards and Technology.

Complexity-Theoretic Properties and Open Questions

Fundamental open questions include whether BQP equals BPP or is strictly larger, and how BQP relates to NP and the Polynomial Hierarchy; these questions connect to conjectures by Leslie Valiant and structural hypotheses in complexity theory advanced by figures like Richard Karp. Structural properties such as closure under complement and amplifiability are established, while the existence of natural complete languages under many-one reductions remains unsettled. Results on query complexity and communication complexity, developed by Eyal Kushilevitz and Noam Nisan, elucidate limitations of BQP in black-box models. Research programs at Simons Foundation and NSF fund work on oracle separations, derandomization analogues, and potential relativized collapse scenarios.

Physical Realization and Fault Tolerance

Realizing BQP computations requires scalable quantum hardware with error rates below fault-tolerance thresholds derived from theories by Peter Shor and Alexei Kitaev. Fault-tolerant schemes such as surface codes, color codes, and concatenated codes are pursued by experimental groups at Microsoft, Rigetti, and IonQ using superconducting circuits, topological proposals, and trapped ions respectively. Threshold theorems ensure that, given sufficient qubit fidelity and error-correcting overhead, arbitrarily long BQP computations can be executed; this engineering challenge links to materials work at Bell Labs and cryogenic systems used by Google DeepMind collaborations. Scaling issues, qubit connectivity, and noise mitigation remain active topics at laboratories including Lawrence Berkeley National Laboratory and Los Alamos National Laboratory.

Category:Quantum computational complexity classes