Promise Problem : It is a pair $$\mathcal{A}=\{\mathcal{A}_{\text{yes}},\mathcal{A}_{\text{no}}\}$$ where $\mathcal{A}_{\text{yes}}$ and $\mathcal{A}_{\text{no}}$ are disjoint sets of inputs (yes inputs and no inputs). Strings not contained in $\mathcal{A}_{\text{yes}} \cup \mathcal{A}_{\text{no}}$ are "don't care" inputs.

$\mathsf{PP}:$ The class of promise problems solvable in polynomial time on a probabilistic Turing machine with bounded error (correct on every input with probability at least $\frac{2}{3}$).

$\mathsf{BQP}:$ The class of promise problems $\mathcal{A} = (\mathcal{A}_{\text{yes}}, \mathcal{A}_{\text{no}})$ for which there exists a polynomial time-uniform family

$$\mathrm{Q} = \{\mathrm{Q}_n: n\in \Bbb N\}$$

of quantum circuits such that, for all input strings $x$, we have:

$$x\in\mathcal{A}_{\text{yes}} \implies \text{Pr}[\mathrm{Q}(x)=1]\geq \frac{2}{3}$$

$$x\in\mathcal{A}_{\text{no}} \implies \text{Pr}[\mathrm{Q}(x)=0]\geq \frac{2}{3}$$

Source: John Watrous - Quantum Complexity Theory (Part 1) - CSSQI 2012

Watrous says that an intuitive approach for proving the containment $\mathsf{BQP}\subseteq \mathsf{PP}$ is along the lines of: unbounded error probabilistic computations can simulate interference in quantum computations (e.g. run two probabilistic processes, and condition them on obtaining the same outputs).

Not sure what they mean by "simulate interference" and how it is relevant to the proof. This so-called intuitive proof doesn't seem clear to me. Could someone clarify the proof-sketch and give me an actual example of a promise problem (with a quantum algorithm) which lies in $\mathsf{BQP}$, and the corresponding equivalent classical algorithm involving two or more parallel probabilistic processes, such that the classical algorithm can be easily proven to lie in $\mathsf{PP}$? I'm finding it a bit hard to imagine without a solid example. Relevant reading material suggestions are also welcome.

Related: Query regarding BQP belonging to PP


1 Answer 1


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.

  • $\begingroup$ Thanks, I'm going through the answer. If possible, could you summarize Scott Aaronson's definition here? It's also not very clear to me how you're "counting the number of paths which their product is $1$ and the number of paths which their product is $-1$". The product of a sequence of $\operatorname{CCNOT}$ and $\operatorname{H}$'s would be just another unitary matrix rather than a number like $1$ or $-1$, isn't it? Could you draw out a diagrammatic representation of the tree structure (for a specific example)? $\endgroup$ Commented Jan 16, 2019 at 15:26
  • $\begingroup$ @Blue Sorry for the mistake, it should be a DAG instead of a tree. I also add some comments on Aaronson's definition of PostBQP, but the important part here is that we can define BQP by some specific universal gate set, namely Hadamard and Toffoli, and such gate set is easy to relate to counting arguments. $\endgroup$
    – Yupan Liu
    Commented Jan 16, 2019 at 17:04
  • $\begingroup$ The answer somewhat makes sense to me now. But which paper discusses this DAG thing? I couldn't find it in Kuperberg's paper. $\endgroup$ Commented Jan 19, 2019 at 9:19
  • $\begingroup$ @Blue I don't think people will write such details in their paper... I added more explanation, and now it coincides with the intuition of the proof for BQP⊆PP mentioned in the Marriott-Watrous (page 6). $\endgroup$
    – Yupan Liu
    Commented Jan 23, 2019 at 11:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.