# Diagonalization in oracle separation between QMA and PP Reposting from cstheorystackexchange for more visibility:

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?

As one of the answers suggested, a way to approach an oracle separation between $$\cal{QMA}$$ and $$\cal{PP}$$ is to consider a language $$L$$, for any language $$A$$, such that $$L = \{1^{n} : |A \cap \{0, 1\}^{n}| > \frac{1}{2} 2^{n} \}.$$

Clearly, $$L \in \cal{PP}^{A}$$, and it is reasonable to think that $$L \notin \cal{QMA}^{A}$$ and we can use diagonalization to show it. However, for me, the analysis of the latter is getting complicated as I do not how to mathematically model the prover’s action: the prover can send any quantum state and can potentially send a quantum state unrelated to the previous one when the oracle is changed during diagonalization. I am looking for any reference or any explicit proof of this non-containment. Posted on Categories proxies