BQP ⊆ PP

Inclusion · quantum setting · ADH97

Statement

BQP $\subseteq$ PP: every language decided with bounded error by a polynomial-time quantum machine with algebraic transition amplitudes is decided by an unbounded-error probabilistic polynomial-time machine — ADH97.

Sketch

With rational amplitudes, the acceptance probability of a polynomial-time quantum machine is a sum, over pairs of computation paths ending in the same accepting configuration, of products of amplitudes; after clearing a common denominator it is the difference of two $\#P$ functions, and comparing it with $1/2$ is a $\mathbf{PP}$ predicate. ADH97 extend the argument to algebraic amplitudes.

Notes

• Alternative proof via $\mathbf{BQP}\subseteq \mathbf{PostBQP}=\mathbf{PP}$ — Aar05.
• Strengthened to $\mathbf{BQP}\subseteq \mathbf{AWPP}\subseteq \mathbf{PP}$, and ${\mathbf{PP}}^{\mathbf{BQP}}=\mathbf{PP}$ — FR99.