QMA/qpoly Is Contained In PSPACE/poly: De-Merlinizing Quantum Protocols
<|reference_start|>QMA/qpoly Is Contained In PSPACE/poly: De-Merlinizing Quantum Protocols: 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.<|reference_end|>
@article{aaronson2005qma/qpoly,
    title={QMA/qpoly Is Contained In PSPACE/poly: De-Merlinizing Quantum Protocols},
    author={Scott Aaronson},
    journal={arXiv preprint arXiv:quant-ph/0510230},
    year={2005},
    archivePrefix={arXiv},
    eprint={quant-ph/0510230},
    primaryClass={quant-ph cs.CC}
}