QMA/qpoly Is Contained In PSPACE/poly: De-Merlinizing Quantum Protocols
QMA/qpoly Is Contained In PSPACE/poly: De-Merlinizing Quantum Protocols
复制标题
QMA/qpoly 包含在 PSPACE/poly 中：去梅林化量子协议
DOI：
--
复制
发表时间：
2005
期刊：
影响因子：
--
通讯作者：
S. Aaronson
中科院分区：
文献类型：
--
作者：
S. Aaronson
本文介绍了一种消除量子态上存在量词的新技术。使用这种技术，我们证明了不可能将指数数量的比特打包成多项式大小的量子态，这样一来，这些比特中的任何一个的值都可以在以后通过多项式大小的量子见证来证明。我们还证明了在具有多项式大小的量子建议的QMA中的任何问题，在具有多项式大小的经典建议的PSPACE中也是如此。这建立在我们早先的结果基础上，即bqp/qpoly包含在PP/poly中，并与最近发现的Raz的qip/qpoly=all提供了一个有趣的对立面。最后，我们证明了PP/Poly中含有qCMA/qpoly，且qMA/rpoly=qMA/poly。
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.