Since $\mathsf{BQP}$ can be defined on different universal gate sets due to the Solovay-Kitaev theorem, we can choose Hadamard gate $\operatorname{H}$ and Toffoli gate $\operatorname{CCNOT}$ as a gate set, like Scott Aaronson's definition of $\mathsf{PostBQP}$ mentioned in the following:
Here ‘uniform’ means that there exists a classical algorithm that outputs a description of $C_n$ in time
polynomial in $n$. Note that, by a result of Shi, we can assume without loss of generality that Cn is
composed only of Hadamard and Toffoli gates. (This is true even for a postselected quantum circuit since by
the Solovay-Kitaev Theorem, we can achieve the needed accuracy in amplitudes at the cost of a polynomial
increase in circuit size.)
But the definition of $\mathsf{PostBQP}$ for different universal gate sets is a little delicate, we also need the matrix element of any gate cannot be too small, namely the theorem 2.10 in Kuperberg's paper.
Note that matrix elements of these gates is either $0$ or $\pm 1$ up to some normalization (the number of Hadamard gates in such sequence), namely $$\operatorname{H}=\frac{1}{\sqrt{2}}\begin{pmatrix} 1&-1\\-1&1\\\end{pmatrix}, \operatorname{CCNOT} = \begin{pmatrix}
1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\
0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0\\
0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0\\
0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0\\
0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0\\
0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0\\
0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0\\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1\\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0\\
\end{pmatrix}.$$
Hence, the outcome of a polynomially long gate sequence of $\operatorname{H}$ and $\operatorname{CCNOT}$ can be simulated by counting the number of paths which their product is $1$ and the number of paths which their product is $-1$. It can be thought as the following DAG.
- Starting from a $n$-bit string $00\cdots0$ with an associated value $1$, i.e. $(00\cdots0,1)$.
- Generating vertices in the next level of the DAG by applying a Hadamard gate (out-degree $2$) or a Toffoli gate (out-degree $1$), also let the associated value be the correspondent matrix element in the gate. For instance, leaves of $(00,1)$ by applying a Hadamard gate on the first qubit are $(00,1)$ and $(10,-1)$.
- The "depth" of such DAG is the length of the gate sequence.
- And we only care about leaves associated with string $0\cdots$ (the first qubit is $0$).
Let such polynomially long gate sequence denoted by $A_x$ where $x$ is an input of some $\mathsf{BQP}$ problem. Notice that the following in the defintion of $\mathsf{BQP}$, $$\|\Pi_1 A_x|0^n \rangle\|_2^2 = \langle 0^n| A_x^{\dagger} \Pi_1 A_x | 0^n \rangle,$$ where $\Pi_1 = |0\rangle\langle 0|\otimes I_{n-1}$, we can simply do the above construction for $A_x^{\dagger} \Pi_1 A_x$, and at the end of day, we only care above the leave associated with string $0\cdots 0$.
Then the probability of getting some leaf is $\dfrac{a-b}{2^{k}}$ where $k$ is the number of Hadamard gates, $a$ is the number of paths which the product of all associated values on such path is $1$, and $b$ is the number of paths which the product of all associated values on such path is $-1$.
Such a counting task can be calculated by $\mathsf{PP}$ machine, namely using the GapP function mentioned in Marriott-Watrous (page 6), also the proof the theorem 3.1 in Fortnow-Rogers. Also, Watrous explained a similar proof for $\mathsf{BQP}\subseteq\mathsf{PP}$ in his lecture notes.
Furthermore, the above proof of $\mathsf{BQP}\subseteq\mathsf{PP}$ can be automatically extended to show that $\mathsf{PostBQP}\subseteq\mathsf{PP}$. The reason is mentioned in Greg Kuperberg's clarification on $\mathsf{PostBQP}$, namely the matrix element of the gate in the $\mathsf{PostBQP}$ quantum circuit need an exponential accuracy (instead of a polynomial accuracy in the $\mathsf{BQP}$ case). Since the Solovay-Kitaev theorem gives an approximation algorithm in time $\text{poly}(n,\log(1/\epsilon))$ for a single $n$-qubit gate, such quantum gate with exponentially accuracy still can be generated by polynomial long quantum gates on the given universal set (such as $\operatorname{H}$ and $\operatorname{CCNOT}$). Therefore, any $\mathsf{PostBQP}$ quantum circuit can be described as a polynomial long gate sequence on $\operatorname{H}$ and $\operatorname{CCNOT}$, and we can use the same argument which we mentioned above.
