Bounded-Error Quantum Polynomial-Time

The class of decision problems solvable by a uniform family of polynomial-size quantum circuits with two-sided bounded error:

1. If the answer is “yes,” the circuit accepts with probability at least 2/3.
2. If the answer is “no,” the circuit accepts with probability at most 1/3.

BQP is the quantum analogue of BPP and is the standard model for efficient quantum computation.

See the complexity zoo entry here.

Notable problems

• Integer factorization and discrete logarithm are in $\mathbf{BQP}$ via Shor’s algorithm — TODO citation (Shor 1994). This directly breaks RSA and elliptic-curve Diffie-Hellman.
• Unstructured search: Grover’s algorithm provides a quadratic quantum speedup for unstructured search — TODO citation (Grover 1996). This does not place unstructured search in $\mathbf{BQP}$ itself, but implies that any problem with a classical $O(N)$ exhaustive-search algorithm can be solved quantumly in $O(\sqrt{N})$ queries.

Known relationships

• $\mathbf{P}\subseteq \mathbf{BPP}\subseteq \mathbf{BQP}$: classical probabilistic computation is a special case of quantum computation.
• $\mathbf{BQP}\subseteq \mathbf{PP}\subseteq \mathbf{PSPACE}$: quantum computation can be simulated with unbounded-error classical randomness, and in polynomial space — TODO citation (Adleman, DeMarrais, Huang 1997).
• $\mathbf{BQP}$ vs $\mathbf{NP}$: the two classes are believed incomparable. Simon’s problem is in $\mathbf{BQP}$ but not in $\mathbf{NP}$ relative to a random oracle; conversely, NP-complete problems are not believed to be in $\mathbf{BQP}$ — TODO citation.
• PostBQP $=\mathbf{PP}$ (Aaronson 2005 — TODO citation): $\mathbf{BQP}$ augmented with postselection on measurement outcomes equals $\mathbf{PP}$. This gives an elegant proof of $\mathbf{BQP}\subseteq \mathbf{PP}$.

Relevance to cryptography

BQP defines the power of a quantum adversary. All post-quantum cryptographic schemes — lattice-based, hash-based, code-based, isogeny-based — are designed to resist $\mathbf{BQP}$ adversaries. Shor’s algorithm shows that the number-theoretic hardness assumptions underlying RSA, Diffie-Hellman, DSA, and ECDSA are all broken by $\mathbf{BQP}$ machines.

Grover’s algorithm gives a generic quadratic speedup on unstructured search, implying that symmetric-key schemes and hash functions need security parameters roughly twice as large (e.g., AES-256 instead of AES-128) to maintain $\lambda$-bit post-quantum security.