ECCC-Report TR19-131https://eccc.weizmann.ac.il/report/2019/131Comments and Revisions published for TR19-131en-usMon, 30 Sep 2019 17:57:20 +0300-
Paper TR19-131
| A Simple Proof of Vyalyi's Theorem and some Generalizations |
Lieuwe Vinkhuijzen,
AndrĂ© Deutz
https://eccc.weizmann.ac.il/report/2019/131In quantum computational complexity theory, the class QMA models the set of problems efficiently verifiable by a quantum computer the same way that NP models this for classical computation. Vyalyi proved that if $\text{QMA}=\text{PP}$ then $\text{PH}\subseteq \text{QMA}$. In this note, we give a simple, self-contained proof of the theorem, using only the closure properties of the complexity classes in the theorem statement. We then extend the theorem in two directions: (i) we strengthen the consequent, proving that if $\text{QMA}=\text{PP}$ then $\text{QMA}=\text{PH}^{\text{PP}}$, and (ii) we weaken the hypothesis, proving that if $\text{QMA}=\text{coQMA}$ then $\text{PH}\subseteq \text{QMA}$. Lastly, we show that all the above results hold, without loss of generality, for the class QAM instead of QMA. We also formulate a ``Quantum Toda's Conjecture''.Mon, 30 Sep 2019 17:57:20 +0300https://eccc.weizmann.ac.il/report/2019/131