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.
I hope somebody can supply useful literature references.
-
$\begingroup$ Great, I understand the intuition! But how do I show mathematically that the presence of a prover doesn’t help much? I tinkered around with the states, but didn’t get anywhere. $\endgroup$ – AngryLion May 21 '20 at 16:03