BQP ⊆ PP

BQP is contained in PP.

Statement

Migrated verbatim from bounded-error-quantum-polynomial-time § Known relationships:

• $\mathbf{BQP}\subseteq \mathbf{PP}\subseteq \mathbf{PSPACE}$: quantum computation can be simulated with unbounded-error classical randomness, and in polynomial space — Adleman, DeMarrais, and Huang (1997).

Migrated verbatim from bounded-error-quantum-polynomial-time § Known relationships:

• PostBQP $=\mathbf{PP}$ (Aaronson 2005): $\mathbf{BQP}$ augmented with postselection on measurement outcomes equals $\mathbf{PP}$. This gives an elegant proof of $\mathbf{BQP}\subseteq \mathbf{PP}$.

Migrated verbatim from probabilistic-polynomial-time § Known relationships:

• $\mathbf{BQP}\subseteq \mathbf{PP}$: quantum polynomial-time is contained in PP — TODO citation (Adleman, DeMarrais, Huang 1997). This is the key relationship placing quantum computing within classical complexity.

Notes

source: folklore: the claim carried no citation on the page it was migrated from, and none was invented.

class: unstated: no citing page says which notion of reduction is meant. Recording a class the wiki does not state would add a claim.

class: free because a containment between complexity classes is proved by any argument at all; the reduction-class axis does not discriminate here, and unstated would wrongly suggest the information is missing.

Recorded during migration and not fixed — these are claims about the source text, not changes to it:

• The page’s only attribution is prose (‘Adleman, DeMarrais, and Huang (1997)’) with no reference page and no wikilink, so this link migrates uncited.
• Duplicated at probabilistic-polynomial-time.md:20, where the same fact carries a ‘TODO citation’.
• This is a corollary of sub-edge 0 rather than an independent claim, and nothing in the record marks it as derived.
• Duplicates the inclusion already recorded at line 29 of the same page.
• Uncited.
• MISSING CITATION: an explicit ‘TODO citation (Adleman, DeMarrais, Huang 1997)’ placeholder. No reference page in content/References/ is linked; sources recorded as [] per instructions (do not invent the key).
• ‘This is the key relationship placing quantum computing within classical complexity’ is editorializing with no content to type.