QMA ⊆ PP

Inclusion · quantum setting · MW05

Statement

$\mathbf{QMA}\subseteq \mathbf{PP}$: every language in QMA is decided by an unbounded-error probabilistic polynomial-time (PP) machine — MW05.

Sketch

Strong error reduction drives the completeness and soundness errors of a QMA verifier to $2^{-p}$ without lengthening its $m$-qubit witness. The trace of the verifier’s acceptance operator is then at least $1-2^{-p}$ on yes-instances and at most $2^{m-p}$ on no-instances, which separate once $p>m+1$; the trace is the sum over witness basis states of the circuit’s acceptance probabilities, hence a $\mathrm{GapP}$ function up to a fixed denominator, and a $\mathbf{PP}$ machine thresholds it.

Notes

• Kitaev and Watrous first stated the containment, without proof — KW00; the first written proof gives the stronger $\mathbf{QMA}\subseteq {\mathrm{A}}_0\mathrm{PP}\subseteq \mathbf{PP}$ — Vya03.