21st Annual IEEE Conference on Computational Complexity (CCC'06)
QMA/qpoly \subseteq PSPACE/poly: De-Merlinizing Quantum Protocols
Prague, Czech Republic
July 16-July 20
ISBN: 0-7695-2596-2
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 polynomialsize quantum advice, is also in PSPACE with polynomialsize classical advice. This builds on our earlier result that BQP/qpoly \subseteq PP/poly, and offers an intriguing counterpoint to the recent discovery of Raz that QIP/qpoly = ALL. Finally, we show that QCMA/qpoly \subseteq PP/poly and that QMA/rpoly = QMA/poly.