Quantum Complexity Theory

Quantum complexity theory is the rigorous framework for asking: what can quantum computers solve that classical computers cannot, and what are the fundamental limits on quantum speedup? The answers are surprisingly subtle. Quantum computers are not simply faster classical computers; they are a different computational model that excels at specific problem structures.

BQP: the central complexity class

BQP (Bounded-error Quantum Polynomial time) is the class of problems solvable by a quantum computer in polynomial time with success probability at least $2/3$. The choice of $2/3$ is conventional; running the algorithm a constant number of times and taking the majority vote can boost success probability to $1 - \delta$ for any $\delta > 0$, so the exact threshold does not matter as long as it exceeds $1/2$.

More formally, a language $L$ is in BQP if there exists a polynomial-time uniform family of quantum circuits $\{C_n\}$ such that:

• If $x \in L$, the circuit accepts with probability $\geq 2/3$.
• If $x \notin L$, the circuit accepts with probability $\leq 1/3$.

Where BQP sits in the complexity landscape

The known containments are:

$\mathbf{P} \subseteq \mathbf{BPP} \subseteq \mathbf{BQP} \subseteq \mathbf{PP} \subseteq \mathbf{PSPACE}$

P (deterministic polynomial time) is contained in BQP because any classical circuit can be simulated by a quantum circuit with only polynomial overhead. PSPACE contains BQP because a quantum computation with polynomially many qubits can be simulated in polynomial space (by computing amplitudes one at a time).

The relationship between BQP and NP is genuinely unknown and believed to be that neither contains the other. This is important: quantum computers are not expected to solve NP-complete problems in polynomial time.

         PSPACE
        /       \
      BQP        NP
     /    \    /    \
   BPP     ??       NP-complete
     \    /
      P

The overlap between BQP and NP exists (both contain P), but BQP contains problems not known to be in NP (quantum simulation) and NP likely contains problems not in BQP (NP-complete problems).

Problems in BQP but not believed in P

These are the crown jewels of quantum computing: problems where quantum speedup is proven or strongly expected:

Integer factoring (Shor’s algorithm): no classical polynomial-time algorithm is known. Shor’s algorithm runs in $O((\log N)^3)$ quantum operations.

Discrete logarithm: same structure as factoring; Shor’s algorithm handles both.

Quantum simulation: simulating the time evolution of a quantum system with $n$ particles. Classical algorithms require exponential resources; quantum simulation is efficient by design.

Pell’s equation and unit group computation: proven to be in BQP; no efficient classical algorithm known.

BQP-complete problems

A problem is BQP-complete if it is in BQP and every other BQP problem reduces to it in polynomial time. Approximating the Jones polynomial of a braid at a fifth root of unity is BQP-complete, as is the problem of approximating output probabilities of universal quantum circuits.

QMA: quantum NP

QMA (Quantum Merlin-Arthur) is the quantum analogue of NP. A problem is in QMA if a quantum proof (witness state) can be verified efficiently by a quantum computer. The canonical QMA-complete problem is:

Local Hamiltonian problem: given a Hamiltonian $H = \sum_i H_i$ where each $H_i$ acts on at most $k$ qubits, is the ground state energy below $a$ or above $b$ (with $b - a \geq 1/\text{poly}(n)$)?

This captures the hardness of finding ground states of quantum systems, the central problem in quantum chemistry and materials science. NP $\subseteq$ QMA (an NP witness can be verified on a classical computer, which is a special case of a quantum computer), but QMA is believed to be strictly harder than NP.

Why quantum computers probably do not solve NP-hard problems

Grover’s algorithm gives a quadratic speedup on unstructured search ($O(\sqrt{N})$ vs $O(N)$), provably optimal for quantum computers. Quadratic speedup does not convert exponential classical hardness into polynomial quantum time.

QAOA provides approximation guarantees for combinatorial problems, not exact polynomial-time solutions.

Oracle separations show that relative to a random oracle, BQP $\not\supseteq$ NP, ruling out certain proof techniques. Establishing unconditional separation (BQP $\neq$ BPP) remains open. Shor’s speedup is not an oracle result; it exploits concrete number-theoretic structure, which is why it cannot be automatically extended to other hard problems.

See also

• Shor’s Algorithm
• Grover’s Algorithm
• Quantum Speedup
• Quantum Advantage