QMA/qpoly Is Contained In PSPACE/poly: De-Merlinizing Quantum Protocols
| dc.creator | Aaronson, Scott | |
| dc.date | 2005-10-31 | |
| dc.date | 2006-04-02 | |
| dc.date.accessioned | 2026-07-07T06:48:49Z | |
| dc.date.available | 2026-07-07T06:48:49Z | |
| dc.description | 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. | |
| dc.description | 13 pages. Final version to appear in Complexity 2006; fills in some gaps in the proofs | |
| dc.identifier | https://arxiv.org/abs/quant-ph/0510230 | |
| dc.identifier | http://arxiv.org/abs/quant-ph/0510230 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/104158 | |
| dc.subject | Quantum Physics | |
| dc.subject | Computational Complexity | |
| dc.title | QMA/qpoly Is Contained In PSPACE/poly: De-Merlinizing Quantum Protocols | |
| dc.type | text |