In theoretical computer science, computational power is measured not by clock speeds or transistor counts, but by asymptotic complexity classes. The Strong Church-Turing Thesis posited that any physically realizable computing model can be simulated by a probabilistic Turing machine with at most polynomial overhead ($text{BPP}$). In 1993, Umesh Vazirani and Ethan Bernstein formalized the computational model of quantum circuits, introducing the complexity class BQP (Bounded-Error Quantum Polynomial-Time). BQP mathematically delineates the exact boundary of what a quantum computer can decide efficiently in polynomial time, fundamentally challenging the classical Church-Turing thesis and establishing the theoretical limits of quantum advantage.
1. The Formal Definition of BQP
A language $L subseteq {0, 1}^*$ belongs to the complexity class BQP if there exists a polynomial-time classical Turing machine that, given input $x$ of length $n = |x|$, outputs the classical description of a quantum circuit $C_n$ satisfying:
- Uniformity: The circuit $C_n$ is synthesized in time $text{poly}(n)$ by a deterministic Turing machine.
- Polynomial Gate Complexity: The total number of discrete gates in $C_n$ drawn from a universal set $mathcal{G} = {H, S, text{CNOT}, T}$ is bounded by a polynomial:
$$text{size}(C_n) le p(n) quad text{for some polynomial } p$$ - Bounded Probability of Error: Measuring the first qubit in the computational basis yields the correct decision with high probability:
$$text{If } x in L, quad P(C_n text{ accepts } x) ge frac{2}{3}$$
$$text{If } x notin L, quad P(C_n text{ accepts } x) le frac{1}{3}$$
By standard Chernoff bound probability amplification, repeating the circuit $mathcal{O}(k)$ times and taking the majority vote exponentially reduces the error rate to $2^{-k}$ without altering the polynomial class boundary.
2. BQP in the Classical Complexity Zoo
The positioning of BQP relative to classical classes is one of the most profound investigations in mathematics:
$$text{P} subseteq text{BPP} subseteq text{BQP} subseteq text{PP} subseteq text{PSPACE}$$
Why $text{BPP} subseteq text{BQP}$
Any classical probabilistic computation can be simulated reversibly using Toffoli gates. Introducing randomness is trivial: measuring a Hadamard state $H|0rangle = frac{1}{sqrt{2}}(|0rangle + |1rangle)$ generates a truly uniform random bit. Hence, quantum computers can efficiently simulate all classical randomized algorithms.
Why $text{BQP} subseteq text{PSPACE}$
The final amplitude of a quantum circuit acting on $n$ qubits is a sum of matrix product paths: $langle x | U_m dots U_1 | 0^{otimes n} rangle = sum_{j_1, dots, j_{m-1}} U_{m, x, j_{m-1}} dots U_{1, j_1, 0}$. Because each individual path can be evaluated sequentially and summed using depth-first search in polynomial memory space without storing the full $2^n$ state vector, BQP is strictly contained within $text{PSPACE}$.
3. The Grand Frontier: BQP versus NP
A prevalent popular misconception is that quantum computers can magically solve all $text{NP}$ problems (or $text{NP-complete}$ problems like Traveling Salesperson or 3-SAT) in polynomial time by evaluating all $2^n$ combinations simultaneously. In theoretical computer science, this is widely believed to be false.
The Oracle Query Lower Bound (BBBV Theorem, 1997)
Charles Bennett, Ethan Bernstein, Gilles Brassard, and Umesh Vazirani proved that for an unstructured search space of $N = 2^n$ items, any quantum algorithm requires at least:
$$Omegaleft(sqrt{N}right) quad text{oracle queries}$$
Because Grover’s algorithm achieves $mathcal{O}(sqrt{N})$, Grover search is asymptotically optimal. A speedup from $2^n$ to $2^{n/2}$ is polynomial (quadratic) in nature, but still exponential in $n$. Thus, quantum brute-force cannot reduce $text{NP-complete}$ problems to polynomial time.
Conjectured Relationship
The consensus amongst complexity theorists is that BQP and NP are incomparable:
- Problems like Integer Factoring and Discrete Logarithm reside in $text{BQP} setminus text{BPP}$, but are in $text{NP} cap text{co-NP}$ and not believed to be NP-complete.
- Problems like 3-SAT reside in $text{NP} setminus text{BQP}$.
- Problems in $text{BQP}$ with oracle separations (such as Aaronson’s Forrelation problem) are proven to reside outside the entire Polynomial Hierarchy (PH)!
