Quantum computing is often introduced through striking speedups: Shor’s algorithm factors integers in polynomial time, while Grover’s algorithm searches an unstructured database in roughly the square root of the classical number of queries. Complexity theory provides the framework needed to interpret these claims carefully. It asks not only whether a problem can be solved, but also how much computational resource is required, under which model of computation, and whether the improvement is achievable for an entire class of inputs.

Quantum complexity theory extends classical complexity theory to machines that manipulate superposition, interference and entanglement. It does not imply that every quantum computation is faster than every classical computation. Rather, it identifies classes of problems that can be solved efficiently under particular assumptions and studies the relationships among those classes.

This chapter develops the main resource measures—time, space, query, gate and sample complexity—and introduces the principal classes P, NP, BPP, BQP and QMA. It also explains reductions, completeness, lower bounds and the practical limits of quantum speedup.

Learning objectives

1. What complexity theory measures

An instance of a computational problem is encoded as a string of length n, usually over the alphabet {0, 1}. The input length n is the principal scale parameter. Complexity is studied asymptotically: a resource function is examined as n grows, rather than for one fixed input.

A complexity bound is meaningful only after specifying the computational model. Classical Turing machines, random-access machines, Boolean circuits and quantum circuits measure resources somewhat differently. For standard complexity classes, reasonable models are usually polynomially related, so the distinction does not change whether a problem is considered efficient.

1.1 Time complexity

Time complexity is the number of elementary computational steps used by an algorithm. An algorithm runs in polynomial time if there exist constants c and k such that its running time T(n) satisfies

for all sufficiently large n. Here, c > 0 and k ≥ 0 are constants independent of the input; n is input length. Polynomial time is treated as a formal notion of efficiency, although a large exponent may make an algorithm impractical.

Exponential time, such as 2^n, eventually dominates every polynomial n^k. This asymptotic distinction is central to complexity theory, but it does not by itself determine performance at realistic input sizes.

1.2 Space complexity

Space complexity measures the number of memory cells used during computation, excluding or including the input according to the stated convention. In a quantum computation, space is commonly measured by the number of qubits, together with any classical workspace required by the implementation.

A quantum algorithm using s(n) qubits has quantum space complexity s(n). This measure does not count the number of possible basis states in a superposition as separate physical memory cells. For example, n qubits represent a state in a 2^n-dimensional Hilbert space, but the physical quantum memory is still n qubits.

1.3 Query complexity

Query complexity counts accesses to an input oracle or black-box function while treating the cost of processing between queries as free. For an unknown function f, a standard quantum oracle acts as

where x is a query index, y is a target register, and ⊕ denotes addition modulo 2. Query complexity is useful because it isolates the information-acquisition bottleneck.

For unstructured search over N items, classical randomized algorithms require Θ(N) queries in the worst case, whereas Grover’s algorithm requires Θ(√N) quantum queries. The improvement is quadratic, not exponential. Query complexity may differ substantially from total gate complexity because implementing one oracle query can itself be expensive.

1.4 Gate complexity

Gate complexity is the number of elementary gates in a circuit. If an algorithm uses G(n) gates, its gate complexity is G(n). A query algorithm may use few oracle calls but many gates to prepare states, perform arithmetic, control the oracle, or measure and verify results.

A circuit with G gates acting on at most q qubits typically has execution depth at most G, although parallel hardware may reduce depth. Gate count and circuit depth therefore describe different operational constraints.

1.5 Sample complexity

Sample complexity is the number of independent observations, experimental repetitions or copies of a quantum state needed to estimate a quantity to a desired accuracy and confidence.

Suppose a measurement produces a random variable X with variance σ². Under independent sampling, the sample mean has standard deviation σ/√m after m samples. To estimate a mean with additive error ε at constant confidence, the usual scaling is

The formula assumes independent samples and finite variance. For a bounded random variable, concentration inequalities may provide explicit confidence dependence. For example, estimating a probability to additive error ε with failure probability at most δ generally requires

Quantum amplitude estimation can improve the dependence on ε in some settings, from O(1/ε²) sampling to O(1/ε) oracle uses, but this requires coherent access to the relevant state-preparation and marking procedures, and the total gate cost may be significant.

2. Classical and quantum complexity classes

Complexity classes group decision problems according to the resources and error guarantees available to an algorithm. A decision problem asks whether the correct answer is “yes” or “no.”

2.1 P: deterministic polynomial time

P is the class of decision problems solvable by a deterministic classical algorithm in polynomial time. Examples include graph connectivity, shortest paths with nonnegative edge weights, sorting-based decision problems and linear programming under standard exact or suitably encoded models.

Membership in P means that a polynomial-time algorithm exists. It does not mean that every implementation is fast, nor that the problem is easy in a practical engineering sense.

2.2 NP: efficiently verifiable solutions

NP is the class of decision problems for which a proposed solution, called a certificate or witness, can be verified by a deterministic polynomial-time algorithm. If x is a “yes” instance and w is a witness, a verifier V satisfies

in polynomial time, with an appropriate witness w. The certificate length is polynomially bounded in the input length.

The name NP refers to nondeterministic polynomial time, not “non-polynomial.” Every problem in P is in NP because a polynomial-time solver can itself provide verification. Whether P = NP remains unresolved.

2.3 BPP: bounded-error probabilistic polynomial time

BPP consists of decision problems solvable by a classical randomized polynomial-time algorithm with bounded error. For a standard constant-error definition, the algorithm accepts yes instances with probability at least 2/3 and accepts no instances with probability at most 1/3. The constants can be reduced by independent repetition and majority vote, provided the repetitions remain polynomial.

Randomness can be useful even when it does not change asymptotic worst-case power. BPP includes P, and it is widely believed that BPP is no larger than BQP, although the exact relationship between BPP and P is also not known unconditionally.

2.4 BQP: bounded-error quantum polynomial time

BQP is the class of decision problems solvable by a uniform family of polynomial-size quantum circuits with bounded error. A typical definition requires acceptance probability at least 2/3 for yes instances and at most 1/3 for no instances.

A quantum circuit begins with a standard initial state, applies a polynomial number of efficiently describable unitary gates and measurements, and produces a classical answer. The error gap can be amplified by repeating the computation and taking a majority vote, assuming independent repetitions and suitable circuit uniformity.

BQP contains P because a quantum computer can simulate classical deterministic computation. It also contains BPP in the standard circuit model because classical random bits can be generated and processed within a quantum circuit. The widely used containment chain is

These containments are established or standard under conventional definitions, but none of the major inclusions is known to be strict. In particular, it is not known whether BPP = BQP, although strong evidence suggests that quantum computers can solve some problems outside BPP.

Shor’s factoring algorithm places integer factoring in BQP, but factoring is not known to be NP-complete and is not known to lie outside classical polynomial time. Thus, “in BQP” does not automatically mean “classically impossible.”

2.5 QMA: quantumly verifiable proofs

QMA is the quantum analogue of NP in an important proof-verification sense. A polynomial-size quantum state is supplied as a witness to a polynomial-time quantum verifier. For yes instances, there exists a witness causing acceptance with probability at least 2/3. For no instances, every permitted witness causes acceptance with probability at most 1/3.

The witness is not merely a classical bit string; it may be an entangled quantum state. The verifier must therefore be designed to work despite unknown phases, measurement disturbance and possible entanglement with external systems.

The class QMA contains BQP: a BQP computation can be viewed as a verifier that ignores its witness. QMA also contains NP, since a classical certificate can be encoded in computational-basis qubits. The relationship between QMA and other classes is an active research topic. QMA-complete problems include variants of the local Hamiltonian problem, which asks whether the lowest energy of a quantum system lies below or above specified thresholds separated by an inverse-polynomial promise gap.

2.6 Related classes and caution about containment diagrams

PSPACE is the class of problems solvable using polynomial space, with no polynomial-time requirement. Since a polynomial-size quantum circuit can be simulated using polynomial classical space by storing amplitudes with sufficient precision under standard complexity-theoretic conventions, BQP is contained in PSPACE.

The class coNP contains complements of NP problems. The polynomial hierarchy extends NP and coNP through alternating forms of existential and universal computation. Classes such as MA, QCMA and PostBQP refine the study of probabilistic and quantum proof systems.

Containment diagrams are hypotheses unless the inclusion is proved. For example, the statements P ⊆ BPP and BPP ⊆ BQP are standard, while claims such as P ≠ BQP or NP ⊄ BQP remain unproved in the unrelativized setting.

3. Reductions and complete problems

Complexity theory rarely studies problems in isolation. A reduction transforms instances of one problem into instances of another while preserving the answer.

A polynomial-time many-one reduction from language A to language B, written A ≤ₘ^P B, is a polynomial-time computable function f such that

The transformation must be computable in polynomial time and must preserve yes/no membership exactly. If B has a polynomial-time algorithm, then A also has one: compute f(x), then solve B.

A problem is hard for a class C if every problem in C reduces to it using the chosen reduction. It is complete for C if it is both in C and C-hard. NP-complete problems, such as Boolean satisfiability, are therefore among the hardest problems in NP under polynomial-time reductions.

Completeness is conditional information. If one NP-complete problem were shown to be in P, then P = NP. Conversely, showing that a problem is NP-complete does not prove that it cannot be solved efficiently; it indicates that such an algorithm would have consequences for the entire class.

Quantum complexity uses analogous notions. A problem may be BQP-complete under an appropriate reduction, or QMA-complete, as with the local Hamiltonian problem. The reduction type must always be stated because different reductions preserve different amounts of structure and can lead to different completeness results.

4. Upper bounds, lower bounds and oracle evidence

An upper bound demonstrates that an algorithm exists within a resource limit. For example, Grover’s algorithm gives an O(√N) upper bound on quantum query complexity for unstructured search.

A lower bound proves that no algorithm in a specified model can do better than a stated resource. The quantum query lower bound for unstructured search is Ω(√N), so Grover’s algorithm is asymptotically optimal in that model. Here, the notation Ω(g(n)) means that the resource is at least a constant multiple of g(n) for sufficiently large n.

When upper and lower bounds match, the complexity is characterized asymptotically:

This notation means that both an upper and a lower bound proportional to g(n) hold.

Lower bounds are usually model-dependent. A proof about oracle queries does not automatically establish a lower bound on physical gate count. Likewise, a communication-complexity lower bound may not directly imply a circuit lower bound.

Oracle results are useful for separating classes relative to a black-box oracle. They can show that a proposed proof strategy cannot work in complete generality, but they do not settle the corresponding unrelativized question. This distinction is especially important when interpreting evidence about P versus BQP or NP versus BQP.

5. How quantum speedups arise—and why they are limited

Quantum algorithms exploit interference to amplify desirable computational paths and suppress undesirable ones. Superposition alone is not a speedup: measurement yields only limited classical information, and arbitrary parallel evaluation cannot simply be read out in full.

Speedup depends on exploitable structure. Shor’s algorithm uses the quantum Fourier transform to find periodicity; Grover’s algorithm uses amplitude amplification for unstructured search; quantum simulation algorithms exploit the mathematical structure of physical evolution.

Task	Classical scaling	Quantum scaling	Main qualification
Unstructured search	Θ(N) queries	Θ(√N) queries	Quadratic, optimal in query model
Mean estimation	O(1/ε²) samples	potentially O(1/ε) coherent queries	Requires coherent access and suitable implementation
Integer factoring	Best known classical methods are subexponential	polynomial-time algorithms known	Practical fault-tolerant cost is substantial
Generic data loading	Often direct access to data	may require many state-preparation gates	Input preparation can remove apparent advantage

The input model is crucial. A quantum algorithm may assume oracle access or a quantum state already prepared. If preparing that state requires reading all N classical data items, the total algorithm may lose the advertised advantage.

Noise and error correction introduce further overhead. A complexity-theoretic polynomial-time result can still be impractical if the polynomial has a large exponent, if logical gates require many physical gates, or if the algorithm needs deep fault-tolerant circuits.

6. Worked example: interpreting Grover’s complexity

Consider an unstructured database of N = 1,000,000 items containing exactly one marked item.

A classical deterministic search may require N queries in the worst case. A classical randomized search has expected query complexity approximately N/2 when the marked position is uniformly distributed, which is still Θ(N).

oracle iterations in its idealized setting. Since √1,000,000 = 1,000, this is approximately 785 iterations. The exact optimal iteration count depends on the integer rounding and success-probability target.

This example demonstrates a quadratic query reduction, from order 1,000,000 to order 1,000. It does not imply a thousand-fold total speedup: oracle implementation, state preparation, error correction, circuit depth and measurement may dominate the computation.

The lower bound Ω(√N) shows that no quantum algorithm can solve the same black-box search problem with asymptotically fewer queries. Thus Grover’s algorithm is query-optimal, but its advantage is limited by the problem’s lack of structure and by implementation costs.

7. Applied case: quantum risk estimation in a financial institution

Background

This illustrative case concerns a bank estimating the probability of a portfolio loss exceeding a threshold. The bank has a classical simulator for market scenarios and is considering quantum amplitude estimation.

Problem

A proposal claims that quantum computation will reduce the number of simulations from O(1/ε²) to O(1/ε) for error ε. Management must determine whether this is a genuine end-to-end advantage.

Analysis

The classical method independently samples scenarios and computes a loss indicator. If the required estimate has additive error ε and constant confidence, the sample count scales as O(1/ε²), assuming independent bounded observations.

A quantum method could encode scenario generation and the loss indicator into a coherent circuit, then use amplitude estimation. In an ideal oracle model, the number of coherent applications can scale as O(1/ε). However, the bank must also implement reversible random-variable generation, state preparation, payoff evaluation, error correction and output measurement. Classical historical data may be difficult to load into a quantum state without a cost proportional to the dataset size.

Approach and solution

The bank should benchmark total resources rather than query complexity alone. It should specify the data-access model, confidence level, error metric, circuit depth, number of logical qubits, fault-tolerance assumptions and classical preprocessing cost. A hybrid pilot can compare a classical quasi-Monte Carlo method, a noisy quantum prototype and a fault-tolerant resource estimate.

Outcome

The quantum approach may offer asymptotic sample-complexity improvement, but no immediate production advantage follows. The proposal is credible only if coherent data access and fault-tolerant implementation costs remain below the value of the improved precision.

Learning points

8. Practical resource analysis

Resource	Question it answers
Time	How many sequential computational steps are required?
Space	How much classical memory and how many qubits are needed?
Queries	How often must the algorithm access an unknown oracle or dataset?
Gates	How many elementary operations are executed?
Depth	How long is the critical sequential path?
Samples	How many independent repetitions or state copies are required?
Error	What accuracy and failure probability are guaranteed?

For quantum hardware, logical resources should be distinguished from physical resources. A logical qubit is an error-corrected computational unit; it may require many physical qubits. Similarly, a logical gate may require a large fault-tolerant gadget. Resource estimates should therefore state whether they count logical gates, physical gates, circuit layers or wall-clock time.

Uniformity is another requirement. A complexity claim about a circuit family assumes that the circuit for input length n can itself be generated efficiently. Merely asserting the existence of a different circuit for every n is insufficient for standard algorithmic complexity.

9. Limits, governance and professional responsibility

Complexity results can influence security, finance, medicine and public infrastructure. Claims about quantum advantage should therefore avoid misleading comparisons. A fair comparison uses the best relevant classical algorithm, equivalent accuracy, equivalent success probability and comparable input-access assumptions.

Shor’s algorithm has implications for public-key cryptography based on factoring and discrete logarithms. Organisations should plan migration to post-quantum cryptographic standards rather than assume that a practical cryptographically relevant quantum computer is either imminent or impossible. Quantum complexity theory does not predict a timetable for hardware development.

In regulated applications, reproducibility and auditability matter. Teams should document oracle definitions, data-loading procedures, precision assumptions, error budgets and confidence intervals. A theoretical asymptotic claim should not be presented as a guaranteed business outcome.

Contemporary directions

Current research examines quantum advantage in sampling, optimisation, simulation, machine learning and cryptanalysis. Important themes include fault-tolerant resource estimation, quantum error-correction overhead, fine-grained complexity, communication complexity, average-case complexity and the complexity of noisy intermediate-scale quantum computation.

Quantum supremacy or quantum advantage demonstrations typically establish performance for a carefully selected task, often a sampling problem. Such demonstrations are scientifically valuable, but they do not establish that all practical computational problems receive a speedup. Complexity theory helps separate a task-specific separation from a general claim about computational power.

Chapter Summary

Quantum complexity theory classifies problems by the resources required to solve them and by the allowed error model. Time and space describe computation and memory; query complexity isolates access to an oracle; gate complexity counts elementary operations; depth measures sequential dependence; and sample complexity counts repetitions needed for statistical accuracy.

P contains deterministic polynomial-time decision problems. NP contains problems whose solutions have polynomially verifiable classical certificates. BPP allows bounded-error randomized polynomial-time computation. BQP allows bounded-error quantum polynomial-time computation, while QMA allows a quantum witness verified by a polynomial-time quantum circuit. Standard containments include P ⊆ BPP ⊆ BQP ⊆ PSPACE, although many possible equalities or strict separations remain unresolved.

Reductions transfer algorithms and hardness between problems. A complete problem is both a member of a class and hard for that class. Upper bounds show that an algorithm exists; lower bounds show that a specified model cannot do better. Quantum speedups are model-dependent and may disappear when state preparation, oracle implementation, fault tolerance or classical post-processing is included.

A professional quantum-computing analysis must therefore report the computational model, input-access assumptions, resource type, accuracy, confidence, error-correction level and comparison baseline.

Key Terms

Complexity class: A collection of problems defined by common computational-resource and error conditions.

Time complexity: The number of computational steps used as a function of input length.

Query complexity: The number of accesses to an input oracle or black-box function.

Sample complexity: The number of observations or repetitions required for a specified estimation accuracy.

QMA: Problems having quantum witnesses verifiable by efficient quantum computation.

Reduction: An efficient transformation that converts instances of one problem into another while preserving relevant answers.

Complete problem: A problem that belongs to a class and is hard for every problem in that class.

Lower bound: A proven resource requirement that no algorithm in a stated model can beat.

Amplitude amplification: A quantum technique that increases the probability of desired outcomes.

Uniform circuit family: A circuit family that can be generated efficiently from the input length.

Fault tolerance: Techniques that preserve logical computation despite imperfect physical operations.

Review Questions

Short Answer Questions

Long Answer Questions

Analytical / Application Questions

Multiple Choice Questions with Answers

Question 1

Which class consists of decision problems solvable by bounded-error quantum polynomial-time algorithms?

Question 2

Question 3

For unstructured search over N items, Grover’s algorithm has which query complexity?

Question 4

Question 5

Question 6

Question 7

A sample mean based on independent observations typically needs what scaling to achieve additive error ε at constant confidence?

Question 8

Correct Answer: B. It must belong to the class and be hard for every problem in the class

Question 9

Why does a query lower bound not automatically give a physical gate lower bound?

Correct Answer: B. The two measures refer to different computational resources

Question 10

Correct Answer: A. It supplies a polynomial-size quantum state for an efficient verifier

Chapter 4 Quantum Complexity Theory

Quantum Complexity Theory

Introduction