Complexity Class Glossary

Complexity classes organize computational problems by asymptotic resources and acceptance rules. They do not compare particular processors or predict a crossover size. This glossary records the standard classes used in quantum information; Quantum Complexity Classes develops their relationships and examples.

Decision classes and witnesses

The input is a finite classical string of length n. Polynomial means polynomial in n, not in the numerical value represented by that string. Quantum circuit families are uniformly generated by an efficient classical procedure over a fixed suitable gate set. Bounded-error acceptance uses, for example, probability at least $2/3$ on yes inputs and at most $1/3$ on no inputs; the particular constants can be amplified.

Class	Resource and acceptance rule	Essential distinction
P	Deterministic polynomial time	No random or quantum acceptance error.
BPP	Randomized polynomial time with bounded two-sided error	Random bits do not provide a witness chosen to make the input acceptable.
NP	Polynomial-size classical witness verified deterministically in polynomial time	Yes instances have at least one accepting witness; no instances have none.
BQP	Quantum polynomial time with bounded two-sided error	Efficient computation without an untrusted witness or free postselection.
QCMA	Polynomial-size classical witness checked by a bounded-error quantum verifier	Soundness must hold for every classical witness on a no instance.
QMA	Polynomial-size quantum witness checked by a bounded-error quantum verifier	Soundness must hold for every witness state, including malicious choices.
PP	Randomized polynomial time; acceptance probability exceeds $1/2$ exactly on yes instances	No inverse-polynomial gap from one half is promised.
PSPACE	Deterministic polynomial working space	Runtime need not be polynomial.

The witness classes are frequently used for promise problems. A promise separates allowed inputs into disjoint yes and no sets; behavior outside their union is unconstrained. When a theorem is stated for languages, a promise-problem extension must not be assumed without checking its formulation.

Interactive proofs and postselection

IP permits a probabilistic polynomial-time classical verifier to exchange polynomially many bits with one computationally unbounded prover over polynomially many rounds. QIP permits the corresponding quantum verifier and quantum messages. These are proof systems, not models of an unaided efficient computer. Their established characterizations include

$$\mathrm{IP}=\mathrm{QIP}=\mathrm{PSPACE}.$$

Shamir established the IP equality; Jain, Ji, Upadhyay, and Watrous established the QIP equality. The single-prover qualification matters: multiprover and shared-entanglement models are different classes.

PostBQP augments uniform polynomial-size quantum circuits with conditioning on a designated measurement event and demands bounded error in the conditional output. Use the standard discrete gate formulation, or explicitly require an event probability at least $2^{-\operatorname{poly}(n)}$. With Hadamard and Toffoli circuits, a nonzero event probability already has such a lower bound. Aaronson proved

$$\mathrm{PostBQP}=\mathrm{PP}.$$

The event can be very rare. Physically rerunning a circuit until it occurs costs approximately the reciprocal success probability on average, which can be exponential. A laboratory’s decision to discard failed shots does not make PostBQP available at unit cost.

Established containments

Useful language-class containments are

$$\begin{aligned} \mathrm P&\subseteq\mathrm{BPP}\subseteq\mathrm{BQP},\\ \mathrm{BQP}&\subseteq\mathrm{PP}\subseteq\mathrm{PSPACE}. \end{aligned}$$ $$\begin{aligned} \mathrm{NP}&\subseteq\mathrm{QCMA}\subseteq\mathrm{QMA},\\ \mathrm{QMA}&\subseteq\mathrm{PP},\\ \mathrm{BQP}&\subseteq\mathrm{QCMA}. \end{aligned}$$

These standard containments are surveyed by Watrous. An inclusion symbol here does not assert strictness. These inclusions do not provide a polynomial-time quantum algorithm for NP-complete problems or prove that classical computers cannot efficiently simulate BQP. An oracle separation establishes a limitation in that oracle model; it is not automatically an unrelativized separation. See Query Complexity and Lower Bounds and Limitations.

The local Hamiltonian promise problem

A representative QMA-complete family asks whether the least eigenvalue of

$$H=\sum_{j=1}^{m}H_j$$

is at most a or at least b. Here m is polynomial in n, each term acts on at most a fixed k qubits, coefficients have polynomial descriptions, term norms are bounded, and $b-a\geq1/\operatorname{poly}(n)$. The promise excludes intermediate energies. General 5-local Hamiltonian is a standard QMA-complete formulation; additional geometry or interaction restrictions require their own theorem.

A low-energy state is a quantum witness. Its verification can estimate local energies to the required gap without reconstructing all amplitudes. This does not show that the verifier can efficiently prepare such a state: verifying a supplied witness and finding it are different tasks.

As a size check, an integer N written in binary has $n=\lceil\log_2(N+1)\rceil$ bits. An algorithm taking O(N) steps can therefore be exponential in its input length. Resource claims should state which size variable appears in the polynomial.

References

• Aaronson, Scott, “Quantum computing, postselection, and probabilistic polynomial-time,” Proceedings of the Royal Society A 461, 3473–3482 (2005), doi:10.1098/rspa.2005.1546 — PostBQP equals PP.
• Jain, Rahul, Zhengfeng Ji, Sarvagya Upadhyay, and John Watrous, “QIP = PSPACE,” Journal of the ACM 58(6), article 30 (2011), arXiv:0907.4737 — quantum interactive-proof characterization.
• Kitaev, Alexei Yu., Alexander H. Shen, and Mikhail N. Vyalyi, Classical and Quantum Computation, Graduate Studies in Mathematics 47, American Mathematical Society, 2002, doi:10.1090/gsm/047 — computational models and the local Hamiltonian problem.
• Shamir, Adi, “IP = PSPACE,” Journal of the ACM 39(4), 869–877 (1992), doi:10.1145/146585.146609 — classical interactive-proof characterization.
• Watrous, John, “Quantum computational complexity,” in Encyclopedia of Complexity and Systems Science, Springer, pp. 7174–7201 (2009), arXiv:0804.3401 — uniform computation, witness classes, promises, and standard containments.