Quantum complexity theory asks not whether a quantum computer can perform a calculation, but how the resources required to solve families of problems scale as the input grows—and what lower bounds prevent any quantum algorithm from doing substantially better.
Quantum algorithms are often introduced through striking examples: factoring, search, simulation and linear algebra. Complexity theory supplies the discipline needed to interpret those examples. Which problem is being solved? What is the input model? What counts as one operation or oracle query? How accurately must the answer be produced? Is the speedup proved, conjectured or only observed on selected instances?
This guide introduces BQP, QMA, query complexity and lower-bound methods without pretending that today’s open separations have already been resolved. It also connects formal complexity to the resource-heavy fault-tolerant architecture developed in Guides 25–27.
Problem family → input model → resource measure → upper bound → lower bound → complexity class → justified speedup claim.
1. Complexity studies families of inputs
Solving one 1000-bit instance quickly does not define an efficient algorithm. Complexity theory asks how runtime, memory, queries or circuit size grow with input length n.
Polynomial scaling such as n³ is considered efficient in the standard asymptotic framework. Exponential scaling such as 2ⁿ is not.
This classification ignores constants and hardware details at first. A polynomial algorithm can be impractical at useful sizes, while an exponential algorithm can be excellent for small n. Complexity gives asymptotic structure, not a stopwatch prediction.
2. Decision problems
A decision problem asks for a YES or NO answer. For example: does a graph contain a path with a specified property? Does an integer possess a factor below a bound? Is the ground energy of a Hamiltonian below a threshold?
Complexity classes are commonly defined using decision problems because acceptance probability provides a clean mathematical interface.
Function problems and sampling problems can be related to decision classes but may require their own formal definitions.
3. Promise problems
Quantum complexity often uses promise problems. Inputs are guaranteed to lie in either a YES set or a NO set, separated by a promised gap. The algorithm need not behave meaningfully outside the promise.
For example, a Local Hamiltonian promise problem may guarantee that the ground energy is either at most a or at least b, with b−a at least inverse polynomial in n.
The promise gap is part of the computational problem. Making the gap exponentially small can change the required precision and complexity dramatically.
4. Classical baseline: deterministic and randomised polynomial time
P contains decision problems solvable by deterministic polynomial-time algorithms in the standard model. BPP contains problems solvable by classical randomised polynomial-time algorithms with bounded error.
Bounded error means the algorithm can be wrong with a constant probability below one half, commonly at most 1/3, and that probability can be reduced by independent repetition and majority vote.
The constants 1/3 and 2/3 are conventions. Any fixed completeness-soundness gap bounded away from one half can be amplified efficiently.
5. BQP
BQP stands for bounded-error quantum polynomial time. A promise problem is in BQP if a uniform family of polynomial-size quantum circuits decides it with bounded error.
For YES inputs, acceptance probability is at least a constant such as 2/3. For NO inputs, it is at most 1/3. Repeating the computation and combining outcomes can make the error exponentially small with polynomial overhead.
BQP is the standard formal class for efficiently solvable decision problems on an ideal fault-tolerant quantum computer.
6. Factoring and the danger of overstating class separations
Shor’s algorithm gives a polynomial-time quantum algorithm for integer factoring and related order-finding problems.
Classically, no polynomial-time factoring algorithm is known. But it has not been proved that factoring is outside P.
Therefore Shor’s result is a dramatic algorithmic speedup relative to the best known classical algorithms, not an unconditional proof that BQP is strictly larger than P.
“No fast classical algorithm is known” and “no fast classical algorithm can exist” are different claims.
7. BQP does not mean all hard problems become easy
There is no known theorem that BQP contains all NP-complete problems. Quantum computers are not believed to turn arbitrary combinatorial search into polynomial time simply by exploring a superposition.
Grover’s algorithm gives a quadratic improvement for unstructured search, from order N oracle queries to order √N, and this improvement is optimal in the quantum query model.
Structure beyond black-box search is required for stronger speedups.
8. QMA: quantum verification with a quantum witness
QMA is the quantum analogue of NP in the verifier-and-witness sense.
For a YES instance, there exists a polynomial-size quantum witness |ψ⟩ that convinces a polynomial-time quantum verifier to accept with high probability. For a NO instance, every possible witness is accepted only with low probability.
As with BQP, the completeness and soundness probabilities can use conventional constants such as 2/3 and 1/3 and can be amplified.
9. BQP is contained in QMA
If a problem is already solvable by a BQP circuit, a QMA verifier can simply ignore the witness and run that circuit.
Therefore BQP⊆QMA.
This inclusion is straightforward. Whether the containment is strict is not known unconditionally.
10. Local Hamiltonian: the canonical QMA-complete problem
Given a Hamiltonian H expressed as a sum of local terms, and thresholds a<b separated by an inverse-polynomial promise gap, decide whether its ground-state energy is at most a or at least b.
This problem is QMA-complete for suitable locality parameters. It plays a role analogous to SAT in NP theory: every QMA verification problem can be encoded into a local-Hamiltonian instance with polynomial overhead.
The result connects quantum many-body physics directly to computational complexity.
11. Why the ground state is a witness
For a YES Local Hamiltonian instance, a low-energy state serves as the quantum witness.
The verifier estimates energy using local measurements, phase-estimation-style techniques or equivalent verification machinery, depending on the formal reduction.
If every state has energy at least b, no witness can make the verifier consistently report an energy below the NO threshold.
12. QMA-hard does not mean impossible on every instance
QMA-hardness is a worst-case asymptotic classification for a family of instances under polynomial reductions.
Specific Hamiltonians may be easy because of one-dimensionality, free-particle structure, commuting terms, symmetry, tensor-network compressibility or a known solution method.
Complexity class labels should not replace problem-specific analysis.
13. Query complexity isolates information access
In the query model, an input is accessed through an oracle. The cost is the number of oracle calls rather than the full gate count.
This abstraction is useful because it cleanly captures how much information about a black-box input is required.
But a query can be expensive to implement physically. Query complexity is one resource measure, not an end-to-end runtime by itself. [4]
14. Grover search as a query-complexity problem
Suppose an oracle marks one item among N possibilities. A classical algorithm needs order N queries in the worst case to find it with high probability.
Grover’s algorithm uses order √N quantum queries through amplitude amplification.
The BBBV lower bound shows that any quantum algorithm for unstructured search requires Ω(√N) queries. Grover is therefore asymptotically optimal in this oracle model.
15. Worked scaling comparison
Let N=10¹².
A classical unstructured search may require on the order of 10¹² oracle calls in the worst case.
Grover requires on the order of √10¹²=10⁶ oracle calls, with a constant near π/4 for the ideal one-solution setting.
This million-fold query reduction can be huge. But if one coherent quantum oracle call costs more than a million classical checks, the query advantage may not translate into wall-clock advantage.
16. Lower bounds matter as much as algorithms
An upper bound says an algorithm can solve a problem using at most a certain resource. A lower bound says no algorithm in the specified model can solve it using less than a certain resource asymptotically.
When upper and lower bounds match up to constants or logarithmic factors, the problem is essentially solved in that model.
Without a lower bound, a celebrated algorithm may still be far from optimal.
17. Polynomial method for quantum query lower bounds
After T quantum oracle queries to a Boolean input, the acceptance probability can be expressed as a real multilinear polynomial in the input bits of degree at most 2T.
If every polynomial approximating the target Boolean function within the required error must have degree at least d, then any quantum algorithm requires at least d/2 queries.
This converts an algorithmic lower-bound problem into approximation theory. [5]
18. Why the degree doubles
State amplitudes after T queries are polynomials of degree at most T in suitable oracle variables. Acceptance probabilities are squared magnitudes and therefore involve products of amplitude polynomials, giving degree at most 2T.
The polynomial method uses this algebraic footprint of a query algorithm to prove that some functions cannot be decided with too few queries.
The bound concerns black-box access. An explicit structured formula for the same function may allow a different computational route outside that oracle model.
19. Adversary methods
Adversary lower bounds compare pairs of inputs that should lead to different outputs but are difficult for a query algorithm to distinguish.
A progress measure tracks how quickly oracle calls can separate the algorithm’s states on those inputs. If each query changes the progress measure only slightly, many queries are required.
The general adversary bound is remarkably powerful and characterises bounded-error quantum query complexity up to constant factors for broad classes of problems.
20. Oracle separations
An oracle separation constructs a black-box world in which two complexity classes differ.
Such a result proves that any argument resolving the corresponding unrelativised separation must use properties not preserved by arbitrary oracles.
Oracle results are evidence about proof techniques and possible computational structure, not direct proofs that the ordinary real-world classes are separated.
21. Quantum supremacy-style sampling and decision classes
Some experimental quantum advantage proposals concern sampling from a distribution rather than deciding a language.
The complexity-theoretic evidence can involve assumptions about classical simulation, polynomial hierarchy collapse or average-case hardness rather than a direct BQP-versus-P theorem.
Decision complexity and sampling complexity should not be conflated merely because both use quantum circuits.
22. Error reduction has a resource cost
BQP’s bounded-error definition permits a constant failure probability. Real applications may require failure below 10−12 or lower.
Algorithmic repetition can reduce decision error, while quantum amplitude estimation or coherent amplification can improve some estimation tasks. Fault-tolerant coding separately suppresses hardware-induced logical error.
Do not count these as the same error. Computational soundness, numerical approximation and hardware failure belong to different layers.
23. Complexity ignores some enormous fault-tolerant constants
A circuit with polynomial T-count may still require billions of T states at the problem size of interest.
BQP classification says that the ideal logical circuit grows polynomially. It does not specify the physical qubit count, code distance, magic-state factory area, routing or cryogenic control.
Guides 25–27 supply the layer that asymptotic complexity intentionally abstracts away.
24. Fine-grained complexity
Sometimes polynomial versus exponential is too coarse. A reduction from N² to N1.5 may be transformative for large data even though both are polynomial.
Fine-grained complexity asks whether specific exponents can be improved under conjectures or lower-bound models.
Quantum query complexity is naturally fine grained because square-root and polynomial-factor speedups are meaningful even without changing a broad complexity class.
25. Space complexity
Runtime is not the only resource. Quantum algorithms use qubits, ancillas, classical memory, coherent depth and communication.
An algorithm can reduce time by storing a large quantum state or reduce qubit count by recomputing intermediate values.
Fault-tolerant hardware makes these trade-offs sharper because every additional logical qubit carries code-space overhead.
26. Communication complexity
In communication complexity, separated parties each hold part of an input and aim to compute a function while minimising communication.
Quantum communication can reduce the number of transmitted qubits for some problems, and entanglement can alter achievable protocols.
This model helps separate the cost of moving information from the cost of local computation.
27. Common misconception: BQP means exponentially faster
BQP is a class defined by polynomial quantum runtime. A problem can be in both BQP and P, or admit only a polynomial-factor quantum speedup. The class label alone does not specify the speedup magnitude relative to the best classical algorithm.
28. Common misconception: QMA is “problems quantum computers cannot solve”
QMA is a verification class. A YES instance has a short quantum witness verifiable efficiently by a quantum computer. The definition does not itself state that finding such a witness is impossible in BQP.
29. Common misconception: query lower bounds prove physical runtime lower bounds
They prove limits in an oracle-access model. Physical runtime also includes the cost of implementing a query and all between-query operations.
30. Worked synthesis problem
A database contains N=2⁶⁰ items and supports a coherent black-box membership oracle.
Step 1: Classical query scale. Unstructured search requires order 2⁶⁰ queries in the worst case.
Step 2: Quantum query scale. Grover requires order √(2⁶⁰)=2³⁰ queries.
Step 3: Lower bound. The Ω(√N) search lower bound means no quantum black-box algorithm can reduce the asymptotic query count below this scale by more than constants.
Step 4: Physical qualification. If one coherent oracle call requires a reversible circuit with 10⁹ protected T gates, the end-to-end implementation can still be impractical despite optimal query complexity.
Step 5: Correct conclusion. Grover is query-optimal for unstructured search; whether it is operationally advantageous depends on oracle construction and fault-tolerant resources.
31. Practice set
- What does asymptotic complexity measure?
- What is a promise problem?
- Define BQP informally.
- Why does Shor’s algorithm not prove P≠BQP?
- Define QMA informally.
- Why is BQP contained in QMA?
- What is the Local Hamiltonian problem?
- What does query complexity count?
- What is Grover’s query complexity for one marked item?
- What does the Grover lower bound establish?
- How does the polynomial method turn queries into an approximation problem?
- Why should ideal complexity and fault-tolerant resources be reported separately?
Answers
- How required resources scale with input size for a family of instances.
- A decision problem with a guarantee that valid inputs lie in separated YES or NO sets.
- Problems decidable by uniform polynomial-size quantum circuits with bounded error.
- Factoring is in BQP, but no proof shows factoring is outside P.
- Problems whose YES instances have polynomial-size quantum witnesses verifiable in quantum polynomial time with a bounded completeness-soundness gap.
- A QMA verifier can ignore the witness and run the BQP algorithm.
- Decide whether the ground energy of a local Hamiltonian lies below a or above b under a promised inverse-polynomial gap.
- The number of calls to an input oracle.
- Θ(√N).
- No quantum black-box search algorithm asymptotically beats √N queries.
- T queries produce an acceptance probability polynomial of degree at most 2T; approximate-degree lower bounds therefore imply query lower bounds.
- BQP abstracts away physical code, factory and routing overhead that can dominate practical runtime.
Sources and further study
[1] Ethan Bernstein and Umesh Vazirani, Quantum Complexity Theory, SIAM Journal on Computing 26 (1997). A foundational formal treatment of quantum polynomial-time computation and oracle phenomena.
[2] John Watrous, Quantum Computational Complexity. A broad survey of quantum complexity classes, amplification and complete problems.
[3] Julia Kempe, Alexei Kitaev and Oded Regev, The Complexity of the Local Hamiltonian Problem. A standard route to QMA-completeness for two-local Hamiltonians.
[4] Andris Ambainis, Understanding Quantum Algorithms via Query Complexity. A survey of query-model speedups and limitations.
[5] Robert Beals, Harry Buhrman, Richard Cleve, Michele Mosca and Ronald de Wolf, Quantum lower bounds by polynomials. The polynomial method connecting quantum query algorithms with approximation degree.
Batch 07 series navigation
- Guide 25: Fault-Tolerant Quantum Computation, Logical Qubits, Thresholds and Transversal Gates
- Guide 26: Surface Codes, Homology, Anyons, Syndromes and Topological Error Correction
- Guide 27: Magic-State Distillation, Clifford+T, T-Count and Resource States
- Guide 28: Quantum Complexity Theory, BQP, QMA, Query Complexity and Lower Bounds
- Return to the BTT Mathematics Learning Hub
Educational note: complexity-class separations contain major open problems. This guide distinguishes proven inclusions and lower bounds from widely believed but unproved claims about classical-versus-quantum computational power.