Complexity classes group computational problems by resources such as time, memory, randomness, and proof verification. They describe families of problems, not brands of hardware or a promise about every input.
Quantum computing adds new classes and new relationships, but it does not erase computational difficulty.
P and BPP
P contains decision problems solvable by a deterministic classical algorithm in polynomial time. Polynomial time means runtime grows as a polynomial in input size, such as n, n², or n³, rather than an exponential such as 2ⁿ.
BPP contains problems solved by a randomized classical algorithm in polynomial time with a bounded probability of error. Repeated runs reduce error probability. Most practical randomized algorithms sit in this broad model.
P is contained in BPP because deterministic computation is a special case of randomized computation.
NP means efficiently verifiable
NP contains decision problems where a proposed solution receives verification in polynomial time. A verifier checks a certificate, such as a valid route, a satisfying assignment, or a schedule.
NP does not mean "not polynomial." The name comes from nondeterministic polynomial time. P sits inside NP because a solver also supplies a verifier.
Whether P equals NP remains open. A quantum computer does not currently provide a proof of P = NP or P ≠ NP.
NP-complete and NP-hard
An NP-complete problem has two properties:
- A proposed solution is verifiable in polynomial time.
- Every problem in NP reduces to it through a polynomial-time transformation.
SAT, 3-SAT, and many scheduling and graph problems have NP-complete forms.
NP-hard problems are at least as hard as every problem in NP under the chosen reduction. An NP-hard problem does not need to belong to NP. Optimization versions often sit in this category because a solution might be difficult to verify or because the problem asks for the best value rather than a yes-or-no answer.
QAOA and quantum annealing address selected optimization instances. They do not establish efficient solutions for all NP-complete or NP-hard problems.
BQP
BQP means bounded-error quantum polynomial time. A problem belongs to BQP when a uniform family of quantum circuits solves it with bounded error using polynomial resources.
BQP includes P. A quantum computer runs classical reversible computation, so every efficient deterministic classical algorithm has a quantum implementation.
BQP also contains problems with known quantum speedups. Shor's algorithm places integer factoring and discrete logarithms inside BQP under standard assumptions. Those problems are not known to lie in P, and their relationship to NP-complete problems differs from popular headlines.
Grover's algorithm gives a quadratic query improvement for unstructured search. A quadratic improvement does not turn exponential search into polynomial search. Searching N possibilities changes from roughly N checks to roughly √N oracle calls, still large when N grows exponentially.
Does BQP contain NP?
The relationship between BQP and NP is unresolved. No known result places every NP problem inside BQP. No known result proves a quantum computer cannot solve every NP problem efficiently.
The careful statement is narrower: current quantum algorithms offer major speedups for selected algebraic and simulation problems, plus limited improvements for search. They do not provide a general method for NP-complete optimization.
A quantum heuristic might produce good answers for a useful instance. Complexity theory asks a different question about worst-case scaling over a problem family.
QMA
QMA is a quantum analogue of NP verification. A prover supplies a quantum state as a witness. A quantum verifier checks the witness with bounded error.
The local Hamiltonian problem is a central QMA-complete example. Given local quantum interactions, the task asks whether the ground-state energy sits below or above separated thresholds. The problem connects complexity theory with quantum many-body physics.
QMA does not mean every QMA problem needs a quantum computer in practice. It describes verification power under a formal model. Hardware noise, witness preparation, and resource limits still matter.
Complexity versus practical performance
Complexity classes describe asymptotic behavior. Business decisions also depend on constants, input sizes, data loading, hardware cost, error rates, memory, and implementation time.
A polynomial quantum algorithm might lose to a classical method on every input size reachable this decade. A heuristic with no worst-case advantage might still help one workload. A POC needs measured baselines rather than class labels alone.
Use quantum benchmarking for hardware claims, quantum resource estimation for future workloads, and quantum versus classical computing for a broader introduction.