Quantum Complexity Theory Explained: What Quantum Computers Can (and Can't) Solve

Quantum complexity theory is the branch of computer science that studies which problems quantum computers can solve efficiently, and how that set compares with what classical computers can do. Its central object is BQP, the class of problems a quantum computer can solve in polynomial time with a small, bounded chance of error. It is the field that separates real quantum speedups from hype.

Here is what the field has established so far, with each claim labelled by how certain it is:

Proven: A quantum computer can efficiently solve every problem a classical computer can efficiently solve.
Proven: A quantum computer cannot compute anything a classical computer cannot also compute, given enough time. Quantum computing changes speed, not computability.
Proven: Factoring large numbers can be done in polynomial time on a quantum computer (Shor’s algorithm).
Unknown: Whether quantum computers are strictly more powerful than classical computers for any problem. Nobody has proven this unconditionally.
Unknown: How BQP relates to NP, the class that contains most famous “hard” problems.
Believed, not proven: Quantum computers cannot solve NP-complete problems in polynomial time.
Proven: Grover’s search speedup is quadratic, not exponential, and it is optimal for unstructured search in the black-box model.
Established fact about experiments: “Quantum supremacy” experiments show hard-to-simulate behaviour. They do not prove a useful speedup or a complexity-class separation.

The bottom line: quantum computers are believed to be dramatically faster on a narrow set of structured problems. They are not believed to be a general shortcut for hard problems. The rest of this page explains why, one claim at a time.

What Problems Can Quantum Computers Solve Faster Than Classical Computers?

The honest answer comes in tiers. A few problems have large known quantum speedups, some get only a modest boost, most have no known speedup at all, and some are impossible for every computer.

The table below sorts the main problem types by the best quantum speedup currently known. The last column matters most because it says whether each claim is proven, believed, or unknown.

Problem type	Best known quantum speedup	Status
Factoring and discrete logarithms	Superpolynomial (often loosely called exponential) over the best known classical algorithm	Quantum polynomial-time algorithm: proven. No fast classical algorithm exists: believed, not proven
Unstructured search	Quadratic: roughly √N steps instead of N	Quadratic is the best possible in the black-box model: proven
Simulating quantum systems (chemistry, materials)	Exponential over the best known classical methods, for many physical systems	Efficient quantum simulation: proven for broad classes of systems. Classical hardness: believed
General NP-complete problems	Only quadratic, Grover-style speedups on brute-force search	Efficient quantum solution: unknown, widely believed impossible
Uncomputable problems (e.g., the halting problem)	None	Impossible for any computer: proven

The pattern is clear. Large quantum speedups depend on hidden mathematical structure, and most hard problems don’t seem to have the right kind.

What Are P, NP, NP-Complete, and BPP in Complexity Theory?

A complexity class is a group of problems that need similar amounts of computing resources. Before BQP makes sense, you need four classical classes. If you’ve met P vs NP before, skim this section.

What Is P in Computational Complexity? Problems Solvable in Polynomial Time

P covers problems a classical computer can solve in polynomial time, where the number of steps grows like n, n², or n³ as the input size n grows. Computer scientists treat this as the dividing line for “efficient.”

Example: Sorting a list, or finding the shortest route between two points on a map.
Why polynomial matters: Doubling the input multiplies the work by a fixed amount. With exponential time (2ⁿ steps), adding a single input item doubles the work.

What Is NP in Computational Complexity? Problems With Efficiently Verifiable Solutions

NP covers problems where a proposed answer can be checked in polynomial time, even if finding that answer seems hard. A completed sudoku is quick to verify but can be very slow to fill in.

Proven: Every problem in P is also in NP. If you can solve a problem quickly, you can check an answer quickly.
Unknown: Whether P equals NP. This is one of the central open problems in computer science.
Widely believed, but not proven: P ≠ NP.

What Are NP-Complete Problems? Examples and Why They Matter for Quantum Computing

NP-complete problems are the hardest problems in NP. Every NP problem can be reduced (translated efficiently) into any one of them, so solving one NP-complete problem quickly would solve all NP problems quickly.

Examples: Boolean satisfiability (SAT), the travelling salesman problem (decision version), and graph colouring.
Why they matter here: Any claim that quantum computers “solve NP-complete problems” is a claim about all of NP at once.

What Is BPP? Randomised Classical Computing With Bounded Error

BPP covers problems a classical computer can solve in polynomial time using randomness, with the answer correct at least two-thirds of the time. Repeating the algorithm a few times makes the error rate negligible.

Example: Randomised primality tests such as Miller–Rabin were a classic BPP-style tool for decades.
Proven: Every problem in P is in BPP.
Widely believed, but not proven: BPP equals P, which would mean randomness gives no fundamental speedup.
Why it matters: BQP is the quantum version of BPP, not of P. Both allow a small, controllable error.

📐 For the mathematically curious
P ⊆ BPP (proven). BPP = P is conjectured but open.

What Is BQP? The Quantum Complexity Class for Efficient Quantum Computing

BQP is the central class in quantum complexity. It describes what a quantum computer can do efficiently, and the key questions are how it compares with P, BPP and NP.

What Does BQP Mean? Bounded-Error Quantum Polynomial Time Explained

BQP stands for bounded-error quantum polynomial time. A problem is in BQP if a quantum algorithm can solve it in polynomial time and give the right answer with probability at least two-thirds.

Bounded error is not a weakness. It is the same standard we already accept for classical randomised algorithms in BPP.
Origin: The class was formalised in Bernstein and Vazirani’s “Quantum Complexity Theory” (SIAM Journal on Computing, 1997), the field’s foundational paper.

What Is Proven About BQP and Its Relationship With P, BPP, PP, and PSPACE?

Several relationships between BQP and classical classes are mathematically proven. Together they set a floor and a ceiling on quantum power.

It is proven that quantum computers can efficiently solve every problem in P and BPP. A quantum computer can do anything a classical one can, at least as fast up to polynomial factors.
It is proven that BQP sits inside PP, a much larger classical class defined by majority-vote probabilistic computation.
It is proven that BQP sits inside PSPACE, the class of problems solvable with a polynomial amount of memory and unlimited time.
It is proven that factoring is in BQP, via Shor’s algorithm.

The PSPACE result deserves its own sentence: everything a quantum computer can compute, a classical computer can also compute, given enough time. Quantum computing does not make uncomputable problems computable.

📐 For the mathematically curious
P ⊆ BPP ⊆ BQP ⊆ PP ⊆ PSPACE (all proven).
BQP ⊆ PSPACE is due to Bernstein and Vazirani (1997). BQP ⊆ PP is due to Adleman, DeMarrais and Huang (1997).

What Is Still Unknown About BQP and Its Relationship With P and NP?

This is where the popular story and the mathematics part ways. The most important questions about BQP are still open, and saying so plainly is what makes the rest of this page trustworthy.

It is not known whether BQP equals P or BPP. No one has proven, unconditionally, that any problem is solvable efficiently by a quantum computer but not by a classical one.
Why it is so hard: Proving BQP is larger than P would automatically prove that P is smaller than PSPACE. That is itself a long-standing open problem.
It is not known how BQP relates to NP in either direction. Neither is proven to contain the other.
It is widely believed, but not proven, that BQP is strictly larger than P, mainly because no fast classical factoring algorithm has been found.

For the mathematically curious

Can Quantum Computers Solve NP-Complete Problems Efficiently? What We Know and What Remains Unknown

Not as far as anyone knows, and essentially no one in the field expects them to. It is unproven either way. It is widely believed, but not proven, that quantum computers cannot solve NP-complete problems in polynomial time.

Three lines of evidence support that belief. None of them is a proof.

1. Grover’s speedup is quadratic, and provably optimal for unstructured search.
Grover’s algorithm searches N possibilities in roughly the square root of N steps. Bennett, Bernstein, Brassard and Vazirani proved that no quantum algorithm can do better on unstructured search in the black-box model.

That leaves exponential problems exponential. Brute-forcing 100 yes/no variables means about 2¹⁰⁰ options. Grover cuts that to about 2⁵⁰, which is still over a quadrillion steps, and the cost keeps doubling with every two extra variables.

Caveat: The optimality proof covers black-box search. It does not rule out a quantum algorithm that exploits the specific structure of an NP-complete problem. That is why it counts as evidence, not proof.

2. Shor’s algorithm does not apply.
Shor’s speedup exploits a special structure, periodicity, that factoring happens to have. Factoring is in NP, but it is not known to be NP-complete, and it is widely believed not to be.

So Shor’s result, however striking, says nothing about NP-complete problems.

3. Heuristics are not proofs.
Quantum optimisation methods such as quantum annealing and QAOA are sometimes presented as NP-complete solvers. They are heuristics, and there is no proof that they solve NP-complete problems in polynomial time.

The current position: the standard reference view, reflected in Wikipedia’s quantum complexity theory entry and the academic literature, is that NP is suspected not to be contained in BQP. “Suspected” is the correct word. No one has shown it.

What Problems Are Quantum Computers Expected to Solve Faster Than Classical Computers?

Quantum computers are not believed to be weak, only narrow. Their expected advantages come from problems with the kind of mathematical structure quantum algorithms can exploit.

Factoring and discrete logarithms: Shor’s algorithm gives a superpolynomial speedup over the best known classical methods. This is why post-quantum cryptography exists.
Unstructured search and its relatives: Grover-style algorithms give a quadratic speedup. That is useful at the margin but not transformative for exponential problems.
Simulating quantum systems: Modelling molecules and materials was the original motivation for quantum computing. It has the clearest theoretical case, because nature itself is quantum mechanical.

What Did Quantum Supremacy Experiments Actually Prove About Quantum Computing?

Quantum supremacy (or “quantum advantage”) experiments are real scientific milestones. They answer a different question from the one this page is about.

In 2019, Google reported in Nature that its Sycamore processor sampled from random quantum circuits faster than it estimated classical supercomputers could. Other groups ran similar sampling experiments afterwards.

What these experiments show: A quantum device can perform a specific task that classical computers find hard to simulate.
What they do not show: That BQP is larger than P. An experiment on a fixed-size device cannot prove anything about how the problem scales.
What they do not show: A useful speedup. Random-circuit sampling was chosen because it is hard classically, not because anyone needs the answer.
Contested claims: Several supremacy claims were later narrowed by improved classical simulation methods, including tensor-network techniques.

Even the claimed classical hardness of these sampling tasks rests on complexity conjectures. Supremacy results are meaningful evidence. They are not proofs.

Why Does Quantum Complexity Theory Matter?

Quantum complexity theory is the most reliable filter for judging quantum-computing claims. You don’t need to prove theorems to use it; you just need to know which claims line up with the known theory.

If someone claims…	What the theory says	Sensible reaction
A quantum shortcut for general optimisation, scheduling or logistics	These are typically NP-hard; no efficient quantum algorithm is known	Be sceptical
Quantum computers will break RSA encryption	Shor’s algorithm factors in polynomial time (proven), given large, error-corrected hardware	Take it seriously
Quantum computers will transform chemistry and materials simulation	The strongest theoretical case for quantum advantage	Pay attention
Quantum computers are “exponentially faster” at everything	No known speedup for most problems	Treat as hype

The usable takeaway: the more a quantum claim depends on hidden structure, the more plausible it is. The more it promises a general shortcut, the less plausible it is.

Complexity theory is where quantum computing stops being physics and becomes computer science, and it is the part that tells you which quantum claims to take seriously. If you’d like to study it alongside quantum algorithms and hardware rather than in isolation, explore the

Certification in Applied Quantum Computing and AI with IIT Delhi

through InterviewBit Varsity: a 6.5-month programme, delivered live online with recorded sessions.

Frequently Asked Questions

1. What is quantum complexity theory used for?

Quantum complexity theory helps determine which computational problems quantum computers can solve efficiently and how their capabilities compare with classical computers. It provides a mathematical framework for identifying proven quantum speedups, possible advantages, and problems where no quantum advantage is currently known.

2. What is the difference between quantum complexity theory and classical complexity theory?

Classical complexity theory studies the resources needed to solve problems using conventional computers, while quantum complexity theory studies those resources when quantum computation is allowed. Classes such as P, NP, and BPP describe classical computation, while BQP describes efficient bounded-error quantum computation.

3. Why is BQP important in quantum computing?

BQP is the central complexity class for efficient quantum computation. It contains problems that a quantum computer can solve in polynomial time with a bounded probability of error, making it useful for studying where quantum algorithms may provide computational advantages.

4. What problems are considered hard for quantum computers?

Many problems remain difficult even for quantum computers, particularly problems for which no efficient quantum algorithm is known. This includes most NP-complete problems, although whether quantum computers can efficiently solve NP-complete problems remains an open question.

5. Does a quantum computer always provide a speedup over a classical computer?

No. Quantum computers do not automatically make every computation faster. The known advantages depend on the structure of the problem: Shor’s algorithm provides a major speedup for factoring, while Grover’s algorithm provides a quadratic speedup for unstructured search. For many problems, no quantum speedup is known.

6. Why can’t quantum computers solve every difficult computational problem faster?

Quantum algorithms can exploit specific mathematical structures, but there is no known general-purpose quantum method that efficiently solves every difficult problem. Complexity theory studies these limitations and helps distinguish problems with known quantum speedups from those where an advantage remains unknown.

7. What is the difference between BQP, P, NP, and PSPACE?

P contains problems efficiently solvable by classical deterministic algorithms, NP contains problems whose proposed solutions can be efficiently verified, BQP contains problems efficiently solvable by quantum computers with bounded error, and PSPACE contains problems solvable using polynomial memory. Several relationships between these classes are proven, while others remain open.

8. Can quantum computing solve the travelling salesman problem faster?

Quantum algorithms can provide speedups for certain approaches to search and optimisation, but there is currently no proven polynomial-time quantum algorithm for the general NP-complete version of the travelling salesman problem. Quantum optimisation methods may offer practical or heuristic advantages, but these do not establish a general efficient solution.

9. What role does Grover’s algorithm play in quantum complexity theory?

Grover’s algorithm demonstrates that quantum computers can search an unstructured space in roughly the square root of the number of possibilities rather than checking every possibility individually. Its quadratic speedup is also known to be optimal for black-box unstructured search, making it an important example of both quantum power and quantum limitations.

10. What should I study to understand quantum complexity theory?

A useful foundation includes algorithms and data structures, computational complexity, discrete mathematics, probability, and linear algebra. After learning classical complexity classes such as P and NP, you can study quantum computation and BQP before moving into quantum algorithms and advanced complexity results.