| BQP | |
|---|---|
| Name | BQP |
| Type | Probabilistic quantum complexity class |
| Introduced | 1990s |
| Introduced by | Ethan Bernstein and Umesh Vazirani; David Deutsch (early ideas) |
| Related | P, NP, BPP, QMA, QMA, Quantum computing |
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 bounded error probability. It formalizes the notion of efficient quantum computation within the framework of computational complexity theory and quantum computing, and it is central to understanding which tasks gain provable speedups from quantum algorithms and quantum information processing.
BQP is defined as the set of languages L for which there exists a polynomial-time uniform family of quantum circuits {C_n} acting on n input qubits and polynomially many ancilla qubits such that, for every input x of length n, the circuit C_n outputs the correct bit with probability at least 2/3 if x ∈ L and at most 1/3 if x ∉ L. The constants 2/3 and 1/3 are arbitrary thresholds that can be amplified by repetition; this amplification property parallels the completeness and soundness amplification used in probabilistic complexity theory. Formal treatments of BQP rely on the model of quantum circuits developed by David Deutsch and later refined by Peter Shor and others, and on mathematical frameworks such as unitary operators, Hilbert space, and the quantum Turing machine model introduced by Bernstein and Vazirani.
BQP occupies a central position among quantum complexity classes. It generalizes classical randomized polynomial time BPP and is contained in probabilistic exponential classes under reasonable assumptions. Known inclusions include BPP ⊆ BQP (every efficient classical randomized algorithm can be simulated by a quantum computer) and BQP ⊆ PSPACE (by simulation using exponential-space classical algorithms). BQP is believed to be incomparable with NP and strictly larger than P under standard conjectures, though these separations remain unproven. Related classes include QMA (Quantum Merlin–Arthur), which generalizes NP in the quantum setting, and QIP (Quantum Interactive Polynomial time), tied to interactive proof systems such as those studied by Lance Fortnow and collaborators.
Several problems are canonical for illustrating BQP's power. The most famous is the integer factorization problem as solved by Shor's algorithm, which implies that the decision version of factoring lies in BQP and motivated interest from cryptography and national security institutions such as NSA and research labs like IBM and Google. Other representative problems include discrete logarithms (also via Shor-type algorithms), certain instances of the Hidden Subgroup Problem (including for abelian groups), and simulation of local quantum systems, following the formalization by Seth Lloyd. The search problem solved by Grover's algorithm demonstrates a quadratic speedup for unstructured search and corresponds to BQP algorithms that outperform classical exhaustive search. Unlike NP-complete languages, no natural NP-complete problem is known to lie in BQP; the question of BQP-complete problems is subtle and often focuses on promise problems and problems such as approximating the value of the Jones polynomial at specific roots of unity, shown to be BQP-hard or BQP-complete under certain encodings.
BQP is tied to the circuit model of quantum gates and to the quantum Turing machine formalism. Universal gate sets such as the Clifford+T set permit efficient approximation of arbitrary unitaries, underpinning Solovay–Kitaev-type results used in constructing family {C_n}. Key algorithms demonstrating BQP's capabilities include Shor's algorithm for factoring and discrete logarithms, Grover's algorithm for search, phase estimation subroutines central to many quantum algorithms, and algorithms for simulating Hamiltonian dynamics (e.g., Trotter–Suzuki decomposition and more modern Hamiltonian simulation techniques). Implementations and experiments at institutions like MIT, Caltech, Harvard University, Google AI Quantum, and IBM Quantum probe practical aspects of BQP through noisy intermediate-scale quantum (NISQ) devices and error-corrected logical qubits based on quantum error correction codes.
BQP is conjectured to strictly contain P and to be incomparable with NP under prevailing beliefs in theoretical computer science. Unlike NP-completeness, which focuses on worst-case hardness for nondeterministic verification, BQP concerns efficient quantum verification and bounded-error acceptance. Classical complexity theory results, such as oracles constructed by Bennett and Gill and later by Bernstein and Vazirani and Scott Aaronson, show relativized worlds where BQP differs from BPP and from NP, illustrating subtle separations. These oracle results shape conservative views arguing that quantum speedups respect structural stability: BQP provides advantages without necessarily undermining the broad framework of classical complexity classes.
BQP has profound practical implications. Algorithms in BQP threaten widely used public-key schemes like RSA and Diffie–Hellman by placing factoring and discrete log inside an efficiently solvable quantum class; this has driven development of post-quantum cryptography standards at agencies such as NIST. Conversely, BQP also enables novel applications in chemistry and materials science via quantum simulation, potentially transforming industry sectors through more accurate modeling of molecular Hamiltonians and catalyzing investment from corporations like Microsoft and Intel. Policy and national cohesion concerns have stimulated governmental funding for quantum initiatives, exemplified by national programs in the United States, European Union, and China.
Major open problems include proving separations between BQP and classical classes like P and NP, characterizing complete problems for BQP in the standard decision framework, and understanding the role of quantum resources (entanglement, coherence) that enable BQP speedups. Research efforts span improving fault-tolerant architectures, developing quantum algorithms for practical tasks (machine learning, optimization), and formalizing reductions among quantum classes. Leading researchers and institutions—Scott Aaronson, Umesh Vazirani, Ethan Bernstein, Peter Shor, John Preskill, alongside laboratories at IBM, Google, Microsoft Research, and major universities—continue to explore the theoretical and engineering frontier that will determine how BQP shapes technology and society.
Category:Quantum complexity theory