<p>Yes, diagonalization arguments can still be used. For the oracle separation <span class="math-container">$\mathcal{QMA}^\mathcal{O}\subsetneq \mathcal{PP}^\mathcal{O}$</span>, design an oracle <span class="math-container">$\mathcal{O}$</span> such that the following language separates the classes:</p>

<p><span class="math-container">$$L = \{1^n\ |\ \left| \mathcal{O}\cap\{0,1\}^n\right|&gt;\tfrac{1}{2}2^n \}$$</span></p>

<p>This language is clearly in <span class="math-container">$\mathcal{PP}^\mathcal{O}$</span> for any choice of oracle <span class="math-container">$\mathcal{O}$</span>. However, it is not always in <span class="math-container">$\mathcal{QMA}^{\mathcal{O}}$</span>, "because" it is difficult for a quantum machine to estimate whether a state <span class="math-container">$a|0\rangle |\phi\rangle+b|1\rangle |\psi\rangle$</span> has <span class="math-container">$|a|&gt;|b|$</span> when the difference <span class="math-container">$|a|-|b|=\mathcal{O}(2^{-n})$</span> 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.</p>

<p>I hope somebody can supply useful literature references.</p>

CC BY-SA 4.0
2020-05-21T16:03:01.387Z
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.
AngryLion
CC BY-SA 4.0
2020-05-21T12:11:22.733Z
2020-05-21T12:11:22.733Z
Lieuwe Vinkhuijzen
<p>Diagonalization is a very common technique to find oracle separations. For example, it can be used to separate <span class="math-container">$\cal{P}$</span> and <span class="math-container">$\cal{NP}$</span>, with the essential idea being that of constructing an oracle in stages and diagonalizing any <span class="math-container">$\cal{P}$</span> machine against that oracle. Similarly, diagonalization arguments can also be used to diagonalize a <span class="math-container">$\cal{BQP}$</span> machine against an oracle like the Grover oracle, and achieve a separation between <span class="math-container">$\cal{BQP}$</span> and <span class="math-container">$\cal{QMA}$</span>. I was wondering whether I can use diagonalization (against <span class="math-container">$\cal{QMA}$</span> machines) to separate classes like <span class="math-container">$\cal{QMA}$</span> and <span class="math-container">$\cal{PP}$</span>, or <span class="math-container">$\cal{QMA}$</span> and <span class="math-container">$\cal{AWPP}$</span>. Is there any literature on these types of separations? A subtlety that I note is that for the diagonalization argument against <span class="math-container">$\cal{BQP}$</span> 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? </p>

<cc.complexity-theory><reference-request><complexity-classes><quantum-computing>
Diagonalization arguments for QMA type proof systems
AngryLion
# Diagonalization arguments for QMA type proof systems

(Asked by: username_0 on 2020-05-21)

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?

**Tags:** cc.complexity-theory, reference-request, complexity-classes, quantum-computing


---

## 1 answers

### Answer by username_1 on 2020-05-21. Score: 3

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.

> **Comments:**
> **username_0**: 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.  

---

