BQP: quantum in the complexity zoo

You have seen a quantum computer factor numbers and search faster. The honest next question is a complexity-theory question: exactly which problems does it make easy, and how big is that set compared to the problems we already solve on a laptop? There is a name for that set, and drawing it on the map is the whole job of this lesson.

Play with the map first

Below is the believed landscape of complexity classes and five familiar problems. Drag each problem into the region where researchers believe it lives. Watch where factoring lands relative to sorting and to Boolean SAT. The surprise is that factoring, the poster child of quantum speedup, sits nowhere near the NP-complete problems.

The classes, from the one you already know

Start from P, the problems your laptop solves efficiently: sorting, shortest paths, multiplying numbers. Allowing a fair coin and a small chance of error barely widens this to BPP, bounded-error probabilistic polynomial time. Now give the machine qubits, gates, and one measurement, and keep the same rules - polynomial size, bounded error - and you get BQP, bounded-error quantum polynomial time. That is the class this whole subject has been circling.

BQP has the same shape as BPP, with one word changed. A problem is in BQP when a polynomial-size quantum circuit outputs the right answer with probability at least $\frac{2}{3}$. The two-thirds is not special; run the circuit a few times and take the majority vote and the error shrinks as fast as you like, exactly as it does for a classical randomized algorithm.^[2]

How the classes nest

Anything a classical machine can do, a quantum one can do too - it can just ignore the extra machinery. And a quantum circuit can be simulated, slowly, by writing down and summing amplitudes, which a classical machine can do in polynomial space. Those two facts pin BQP between P and PSPACE:

Every containment there is proven. What is not proven is whether any of them are strict - nobody has shown BQP is actually bigger than P, because that would settle P versus PSPACE along the way, an open problem for half a century.^[2] The evidence we do have is a single problem believed to separate them: factoring is in BQP, via Shor's algorithm, and is not known to be in P despite centuries of effort.^[3]

This is why the earlier drag placed factoring in a lonely spot. It is in BQP and in NP, but not in P and not NP-complete: it is one of the few problems that quantum genuinely rescues from classical intractability, precisely because it is not one of the truly hard ones.^[1]

# "believed" because separations here are conjectured, not proven.
believed_class = {
    "sorting":           "P",     # polynomial time, classical
    "scan a list of n":  "P",     # O(n) linear scan
    "factoring":         "BQP",   # Shor: quantum polynomial time
    "boolean SAT":       "NP-complete, believed outside BQP",
    "graph isomorphism": "NP, no known quantum speedup",
}

# Proven:    P subset of BPP subset of BQP subset of PSPACE
# Conjecture: NP-complete problems lie OUTSIDE BQP

Check yourself