Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR05-129 | 30th October 2005 00:00

QMA/qpoly Is Contained In PSPACE/poly: De-Merlinizing Quantum Protocols


Authors: Scott Aaronson
Publication: 8th November 2005 21:59
Downloads: 2761


This paper introduces a new technique for removing existential quantifiers
over quantum states. Using this technique, we show that there is no way
to pack an exponential number of bits into a polynomial-size quantum
state, in such a way that the value of any one of those bits can later be
proven with the help of a polynomial-size quantum witness. We also show
that any problem in QMA with polynomial-size quantum advice, is also in
PSPACE with polynomial-size classical advice. This builds on our earlier
result that BQP/qpoly is contained in PP/poly, and offers an intriguing
counterpoint to the recent discovery of Raz that QIP/qpoly = ALL.
Finally, we show that QCMA/qpoly is contained in PP/poly and that
QMA/rpoly = QMA/poly.

ISSN 1433-8092 | Imprint