Physics – Quantum Physics
Scientific paper
2005-10-31
Physics
Quantum Physics
13 pages. Final version to appear in Complexity 2006; fills in some gaps in the proofs
Scientific paper
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.
No associations
LandOfFree
QMA/qpoly Is Contained In PSPACE/poly: De-Merlinizing Quantum Protocols does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with QMA/qpoly Is Contained In PSPACE/poly: De-Merlinizing Quantum Protocols, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and QMA/qpoly Is Contained In PSPACE/poly: De-Merlinizing Quantum Protocols will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-292514