QMA/qpoly Is Contained In PSPACE/poly: De-Merlinizing Quantum Protocols
作者： Scott Aaronson
DOI:
关键词:
摘要: 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 polynomial-size state, in such the value any one those can later be proven with help witness. We also problem QMA advice, PSPACE classical advice. builds on our earlier result BQP/qpoly contained PP/poly, and offers intriguing counterpoint recent discovery Raz QIP/qpoly = ALL. Finally, QCMA/qpoly PP/poly QMA/rpoly QMA/poly.
arxiv.org
harvard.edu
128.84.21.199参考文章(14)
R. Raz, Quantum information and the PCP theorem foundations of computer science. pp. 459- 468 ,(2005) , 10.1109/SFCS.2005.62
Hirotada Kobayashi, Keiji Matsumoto, Tomoyuki Yamakami, Quantum Merlin-Arthur Proof Systems: Are Multiple Merlins More Helpful to Arthur? international symposium on algorithms and computation. pp. 189- 198 ,(2003) , 10.1007/978-3-540-24587-2_21
Isaac L. Chuang, Michael A. Nielsen, Quantum Computation and Quantum Information ,(2000)
Alexei Kitaev, John Watrous, Parallelization, amplification, and exponential time simulation of quantum interactive proof systems symposium on the theory of computing. pp. 608- 617 ,(2000) , 10.1145/335305.335387
Richard E. Ladner, Polynomial space counting problems SIAM Journal on Computing. ,vol. 18, pp. 1087- 1097 ,(1989) , 10.1137/0218073
John Watrous, Space-Bounded Quantum Complexity Journal of Computer and System Sciences. ,vol. 59, pp. 281- 326 ,(1999) , 10.1006/JCSS.1999.1655
Ilan Newman, Private vs. common random bits in communication complexity Information Processing Letters. ,vol. 39, pp. 67- 71 ,(1991) , 10.1016/0020-0190(91)90157-D
Chris Marriott, John Watrous, Quantum Arthur---Merlin games Computational Complexity. ,vol. 14, pp. 122- 152 ,(2005) , 10.1007/S00037-005-0194-X
Scott Aaronson, Quantum Computing, Postselection, and Probabilistic Polynomial-Time Proceedings of The Royal Society A: Mathematical, Physical and Engineering Sciences. ,vol. 461, pp. 3473- 3482 ,(2005) , 10.1098/RSPA.2005.1546
Michael Sipser, Shafi Goldwasser, Private Coins versus Public Coins in Interactive Proof Systems. Adv. Comput. Res.. ,vol. 5, pp. 73- 90 ,(1989)