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.

| cite | improve this answer | |
  • $\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 at 16:03

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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