Quantum Complexity Theory

Throughout this site, you've seen claims like "Shor's Algorithm offers an exponential speedup" or "no proven quantum advantage exists for this problem." Complexity theory is the mathematical framework that makes these claims precise — it's how computer scientists rigorously classify which problems are easy, which are hard, and which quantum computers can plausibly help with at all.

A quick refresher: P and NP

Classical complexity theory organizes problems into classes based on how the resources needed to solve them scale with input size. The two most famous classes are:

• P (Polynomial time): Problems solvable efficiently by a classical computer — the required time grows as a polynomial function of input size (like n² or n³), not explosively.
• NP (Nondeterministic Polynomial time): Problems where a proposed solution can be efficiently verified, even if finding that solution might be hard. Whether every NP problem can also be solved efficiently (whether P = NP) is one of the most famous open problems in mathematics.

Introducing BQP

BQP (Bounded-error Quantum Polynomial time) is the complexity class capturing problems a quantum computer can solve efficiently, with a high probability of correctness. It's the quantum analog of P, and it's the class that actually defines what "quantum speedup" rigorously means.

The key relationships, as currently understood (and proven, unlike the open P vs NP question):

• P is contained within BQP — anything a classical computer can do efficiently, a quantum computer can too (just run the classical algorithm).
• BQP is contained within PSPACE — quantum computers, despite their power, can't solve arbitrarily hard problems; they're still bounded by fundamental limits on memory and time.
• Whether BQP equals P (meaning quantum computers offer no fundamental advantage at all) is not proven false, but is considered extremely unlikely given algorithms like Shor's.

Where does Shor's Algorithm fit?

Integer factoring (the problem Shor's Algorithm solves) is believed to be in BQP but not known to be in P — meaning quantum computers can solve it efficiently, while no efficient classical algorithm is known. This is the precise, technical version of the looser claim "quantum computers are faster than classical ones at factoring."

Crucially, factoring is not believed to be NP-complete (the hardest class of NP problems) — so Shor's Algorithm does not prove that quantum computers can efficiently solve all NP problems, including notoriously hard ones like the traveling salesman problem. This is one of the most important and frequently misunderstood points in popular discussion of quantum computing.

Why complexity theory predicts no "quantum magic bullet"

A common misconception, also addressed in our Myths page, is that quantum computers can "solve any hard problem instantly." Complexity theory explains precisely why this is false: BQP is believed to be a relatively narrow class, offering speedups for problems with specific mathematical structure (like periodicity, which Shor's Algorithm exploits) — not a general tool for defeating computational hardness wherever it appears.

This is also why algorithms like Grover's Algorithm only offer a quadratic speedup for unstructured search, rather than an exponential one — complexity theory proves this quadratic bound is actually optimal for the general unstructured search problem, not just a current limitation of our algorithms.

NP-hard problems and quantum optimization

Many real-world optimization problems discussed throughout this site's Industries coverage — like the traveling salesman problem — are NP-hard. Complexity theory strongly suggests that even quantum computers won't solve these problems in polynomial time for the general case (since this would imply NP is contained in BQP, a much stronger and more surprising claim than anything proven so far).

This is precisely why algorithms like QAOA aim for good approximate solutions rather than provably optimal ones — the complexity-theoretic ceiling on these problems applies to quantum computers too, not just classical ones.

Why this matters for evaluating quantum computing claims

Complexity theory gives a rigorous way to separate well-grounded claims from hype. A trustworthy quantum computing claim should point to a specific problem with known complexity-theoretic status, and a specific quantum algorithm with a proven (not just hoped-for) performance guarantee. Claims that quantum computers will soon solve "all hard problems" or provide unlimited speedup for arbitrary tasks are, almost without exception, inconsistent with what complexity theory tells us is even possible.

Frequently Asked Questions

Has anyone proven that quantum computers are more powerful than classical ones?

Not in an absolute mathematical sense — proving BQP ≠ P would resolve a major open problem, similar in difficulty to P vs NP. What we have instead are specific algorithms like Shor's that offer provable speedups for specific problems, under the (extremely well-supported but not absolutely proven) assumption that no equally fast classical algorithm exists for those same problems.

Does this mean quantum computing claims could all be wrong?

No — the speedups for problems like factoring and unstructured search are about as well-established as anything in theoretical computer science, even without an absolute proof of BQP ≠ P. The uncertainty here is similar in spirit to other deep open problems in mathematics, not a sign that the field's foundations are shaky.