Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > EXP:
Reports tagged with EXP:
TR15-173 | 29th October 2015
Martin Schwarz

An exponential time upper bound for Quantum Merlin-Arthur games with unentangled provers

We prove a deterministic exponential time upper bound for Quantum Merlin-Arthur games with k unentangled provers. This is the first non-trivial upper bound of QMA(k) better than NEXP and can be considered an exponential improvement, unless EXP=NEXP. The key ideas of our proof are to use perturbation theory to reduce ... more >>>




ISSN 1433-8092 | Imprint