Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > AUTHORS > ANDRÉ DEUTZ:
All reports by Author André Deutz:

TR19-131 | 11th September 2019
Lieuwe Vinkhuijzen, André Deutz

A Simple Proof of Vyalyi's Theorem and some Generalizations

In 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 ... more >>>




ISSN 1433-8092 | Imprint