|
| related topics |
| {algorithm, log, probability} |
| {alice, bob, state} |
| {let, theorem, proof} |
| {key, protocol, security} |
| {error, code, errors} |
|
QMA/qpoly Is Contained In PSPACE/poly: De-Merlinizing Quantum Protocols
Scott Aaronson
abstract: 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.
- oai_identifier:
- oai:arXiv.org:quant-ph/0510230
- categories:
- quant-ph cs.CC
- comments:
- 13 pages. Final version to appear in Complexity 2006; fills in some
gaps in the proofs
- arxiv_id:
- quant-ph/0510230
- created:
- 2005-10-30
- updated:
- 2006-04-01
Full article ▸
|
|
| related documents |
| 9904079v3 |
| 0408119v1 |
| 9910033v4 |
| 0703231v2 |
| 0603135v1 |
| 0510185v1 |
| 0504083v2 |
| 0408150v2 |
| 0612089v3 |
| 0607148v3 |
| 0206023v2 |
| 0511272v1 |
| 0610235v2 |
| 0609220v1 |
| 0609166v1 |
| 0609160v1 |
| 0702007v2 |
| 0610105v1 |
| 0606077v1 |
| 0610214v3 |
| 0612052v2 |
| 0608156v1 |
| 0702155v3 |
| 0609125v1 |
| 0601126v1 |
|