PP was proved greater than QMA in by Kitaev and Watrous 2000 - Parallelization, Amplification, and Exponential Time Simulation of Quantum Interactive Proof Systems.

Later Aaronson proved that PostBQP was equal to PP in his PHD 2004.

It has been stated that the knowledge that PostBQP = PP makes proving PP is greater than or equal to QMA a lot easier.

Is there a short explanation of this. Or if not could someone provide a reference detailing this fact?


3 Answers 3


I think the reason PostBQP contained in PP makes it easier to show QMA in PP is that it's easy to show QMA in PostBQP. (Note that we don't really need PostBQP contains PP, we only need the reverse containment, which is easier to show.)

QMA can be shown to be in PostBQP in exactly the same way that one would show MA is in PostBPP (also known as BPPpath). First use error amplification to reduce the error of the MA machine to something more than exponentially small in the size of the witness. Now if you use a random witness, in the yes case there will be some probability of it being accepted (although exponentially small), whereas in the no case the probability of acceptance will be even lower. In the quantum case, we choose the maximally mixed state as the witness and use strong error amplification for QMA. (Both of these ideas are explained in John Watrous' survey on quantum complexity theory.)

Now we need to use the power of post-selection to distinguish these two cases. This is not too hard, but it might sound complicated when I explain it. If you have a machine that accepts yes instances with probability $1/2^k$ (say) and no instances with probability $1/2^{k+4}$. Let our machine with the power of post-selection do the following: With probability $1/2^{k+2}$ just set the post-selection bit (let's call this the PSB) to 1 and the output bit to 0 and end the computation. Otherwise just run the previous machine and set the PSB and the answer bit equal to the output of the computation.

Now in the yes case, with probability $1/2^{k+2}$ the machine with have the PSB equal to 1 and answer bit equal to 0, and with probability at least $1/2^k$ it will have the PSB equal to 1 and answer bit equal to 1. So conditioned on the PSB being 1, there's a much higher chance that it accepts than rejects. Similarly, in the no case, conditioned on the PSB being set to 1 there will be a higher chance of rejecting than accepting.

You might have to tweak the constants a bit to make this idea work exactly, but I think it contains all the ideas needed to make the proof go through.


The shortest proof for me is this: By definition of $PostBQP$, $PP=PostBQP$ implies that quantum circuits with deterministic projections onto a measurement outcome can be simulated in $PP$. Following Schuch et al., a projection onto the ground state $|\psi_0\rangle$ of a $k$-local poly-gapped Hamiltonian $H$ can be achieved by imaginary time evolution of a random state $|\chi\rangle$, i.e. by applying $|\psi_0\rangle \approx \exp[-\beta H]|\chi\rangle$ which suppresses high energy levels exponentially fast. The imaginary time evolution can in turn be approximated using the Trotter decomposition, which only requires operations $\exp[-\beta/NH_i]$ acting on finitely many spins. Since those operations are linear, they can be implemented using postselection, and we see that postselection can be used to cool into the ground state. Phase estimation can then be applied to determine the groundstate energy of the $k$-local Hamiltonian, which is the prototypical $QMA$-complete problem. Thus, $QMA \subseteq PostBQP = PP$.

  • $\begingroup$ Nice answer! One confusion on my part: For the phase estimation part, the circuit takes in as input an eigenstate (or some superposition of eigenstates) and outputs the corresponding phase (or a superposition of phases). How do we know that the input state vector has a non-zero projection onto the eigenspace corresponding to low eigenvalues? If the input state vector is a superposition of eigenstates with high eigenvalues, the PostBQP circuit might never find the low energy states - unless you're doing some kind of sampling? $\endgroup$
    – Henry Yuen
    Jun 30, 2011 at 17:03
  • $\begingroup$ Indeed, this is a problem. Following Schuch et al., I've changed my argument now to explicitly implement a cooling process. $\endgroup$ Jun 30, 2011 at 18:22
  • $\begingroup$ I don't think we know of QMA-complete instances where the spectral gap is a constant (or even $\Omega(1/\mathrm{poly})$), do we? It seems necessary that the spectral gap be bounded below in order for the cooling process to converge. Or is the idea that it's okay to cool to some low-lying subspace in order to decide the answer? There could still be cases where all eigenstates from the ground state to the one with eigenvalue b (where b is the cutoff energy beyond which we reject) have exponentially small energy separation.. $\endgroup$
    – Abhinav
    Nov 7, 2019 at 16:43

I assume by "greater or equal to" you mean "contains". Well, one facile answer to this question is that PostBQP is inherently a quantum complexity class, whereas PP is defined in terms of classical nondeterministic Turing Machines. If one were to try to show that QMA (another quantum complexity class) is contained in PP, it SEEMS that it would be easier to show that QMA is contained in PostBQP, simply because the models of computation that define each class "line up" - you don't have to spend extra effort "translating" from quantum polynomial time to classical nondeterministic polynomial time.


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.