# Diagonalization arguments for QMA type proof systems

Diagonalization is a very common technique to find oracle separations. For example, it can be used to separate $$\cal{P}$$ and $$\cal{NP}$$, with the essential idea being that of constructing an oracle in stages and diagonalizing any $$\cal{P}$$ machine against that oracle. Similarly, diagonalization arguments can also be used to diagonalize a $$\cal{BQP}$$ machine against an oracle like the Grover oracle, and achieve a separation between $$\cal{BQP}$$ and $$\cal{QMA}$$. I was wondering whether I can use diagonalization (against $$\cal{QMA}$$ machines) to separate classes like $$\cal{QMA}$$ and $$\cal{PP}$$, or $$\cal{QMA}$$ and $$\cal{AWPP}$$. Is there any literature on these types of separations? A subtlety that I note is that for the diagonalization argument against $$\cal{BQP}$$ machines, the essential idea is that the quantum machine cannot "search for a needle in a haystack", meaning that if there are an exponential number of query states to keep track of, a quantum machine is almost blind to the change in any one of them. However, if you have a prover as well as a quantum machine, the prover can just "give you the needle"; meaning, the prover can just send you the right state to query. Can diagonalization still work in these settings?

Yes, diagonalization arguments can still be used. For the oracle separation $$\mathcal{QMA}^\mathcal{O}\subsetneq \mathcal{PP}^\mathcal{O}$$, design an oracle $$\mathcal{O}$$ such that the following language separates the classes:
$$L = \{1^n\ |\ \left| \mathcal{O}\cap\{0,1\}^n\right|>\tfrac{1}{2}2^n \}$$
This language is clearly in $$\mathcal{PP}^\mathcal{O}$$ for any choice of oracle $$\mathcal{O}$$. However, it is not always in $$\mathcal{QMA}^{\mathcal{O}}$$, "because" it is difficult for a quantum machine to estimate whether a state $$a|0\rangle |\phi\rangle+b|1\rangle |\psi\rangle$$ has $$|a|>|b|$$ when the difference $$|a|-|b|=\mathcal{O}(2^{-n})$$ is exponentially small. This is true even in the presence of a prover, because even if the prover supplies the correct answer, it is not possible to verify whether the answer is correct. In your terminology: There is no needle to give; rather, the task is to count the number of needles, and then a single needle doesn't help much.