Quantum Complexity: BQP and Beyond

BQP (Bounded-error Quantum Polynomial time) is the class of decision problems solvable by a quantum circuit whose size grows only polynomially with the input size, with the correct answer returned at least two-thirds of the time — an arbitrary but standard threshold, since repeating the computation a few times and taking a majority vote pushes the success probability arbitrarily close to 1. It is the direct quantum analogue of BPP, the classical class of problems efficiently solvable by a randomized algorithm.

Shor's factoring algorithm is exactly a demonstration that one specific, believed-to-be-hard problem sits inside BQP. That's strong evidence — though not a proof, since factoring has never been proven classically hard — that BQP is strictly larger than P, the class of problems an ordinary computer solves efficiently.

BQP is known to sit inside PSPACE, the class of problems solvable with a polynomial amount of memory regardless of running time: a quantum computation can always be simulated classically using memory that scales reasonably even though the simulation itself may take exponentially longer. Whether BQP sits inside NP, or contains all of NP, remains a genuinely open question — Grover's algorithm searches an NP-flavored space quadratically faster, but a quadratic speedup falls well short of showing NP ⊆ BQP.

This is precisely the distinction separating Shor's algorithm from Grover's in complexity-theoretic terms. Grover's √N speedup is proven optimal for unstructured search in the oracle model — no algorithm using only oracle queries can do better, full stop — while Shor's exponential speedup exploits deep algebraic structure (the periodicity of modular exponentiation) that has no counterpart in Grover's fully unstructured setting.

Aaronson's work relating BQP to the polynomial hierarchy is part of a broader research program locating BQP within the full landscape of classical complexity classes, not just P and PSPACE but the polynomial hierarchy — a tower of classes built by alternating quantifiers over NP. Settling these relationships precisely would resolve some of the deepest open questions in theoretical computer science generally, not only in quantum computing.

This framing matters directly when reading a paper: whenever a new quantum algorithm claims a 'speedup,' the meaningful question is always speedup relative to which class of classical algorithms, and whether that speedup is proven or merely conjectured. A claimed advantage measured against a needlessly weak classical baseline is one of the most common ways a quantum advantage claim gets walked back on closer inspection — exactly the kind of thing the credibility checklist from the previous topic is built to catch.

In short: BQP is quantum computing's answer to 'what's efficiently computable,' Shor's algorithm is the leading evidence that it's a genuinely bigger class than classical efficient computation, and Grover's algorithm is proof that not every quantum advantage is that dramatic — most problems, if they get a quantum speedup at all, get something far more modest than exponential.