Hirotada Kobayashi
ABSTRACT
This paper presents stronger methods of achieving perfect completeness in quantum interactive proofs. First, it is proved that any problem in QMA has a two-message quantum interactive proof system of perfect completeness with constant soundness error, where the verifier has only to send a constant number of halves of EPR pairs. This in particular implies that the class QMA is necessarily included by the class QIP1(2)} of problems having two-message quantum interactive proofs of perfect completeness, which gives the first nontrivial upper bound for QMA in terms of quantum interactive proofs. It is also proved that any problem having an $m$-message quantum interactive proof system necessarily has an ${(m+1)}$-message quantum interactive proof system of perfect completeness. This improves the previous result due to Kitaev and Watrous, where the resulting system of perfect completeness requires ${m+2}$ messages if not using the parallelization result.
- Dorit Aharonov, Itai Arad, Zeph Landau, and Umesh Vazirani. The detectability lemma and quantum gap amplification {extended abstract}. In Proceedings of the 41st Annual ACM Symposium on Theory of Computing, pages 417--426, 2009. Google Scholar
Digital Library
- Dorit Aharonov, Itai Arad, Zeph Landau, and Umesh Vazirani. The 1D area law and the complexity of quantum states: A combinatorial approach. In 52nd Annual IEEE Symposium on Foundations of Computer Science, pages 324--333, 2011. Google ScholarDigital Library
- Scott Aaronson. On perfect completeness for QMA. Quantum Information and Computation, 9(1--2):0081--0089, 2009. Google ScholarDigital Library
- Dorit Aharonov and Lior Eldar. On the complexity of commuting local hamiltonians, and tight conditions for topological order in such systems. In 52nd Annual IEEE Symposium on Foundations of Computer Science, pages 334--343, 2011. Google ScholarDigital Library
- Dorit Aharonov. A simple proof that Toffoli and Hadamard are quantum universal. arXiv.org e-Print archive,arXiv:quant-ph/0301040, 2003.Google Scholar
- Dorit Aharonov, Alexei Kitaev, and Noam Nisan. Quantum circuits with mixed states. In Proceedings of the Thirtieth Annual ACM Symposium on Theory of Computing, pages 20--30, 1998. Google ScholarDigital Library
- Sanjeev Arora, Carsten Lund, Rajeev Motwani, Madhu Sudan, and Mario Szegedy. Proof verification and the hardness of approximation problems. Journal of the ACM, 45(3):501--555, 1998. Google ScholarDigital Library
- Sanjeev Arora and Shmuel Safra. Probabilistic checking of proofs: A new characterization of NP. Journal of the ACM, 45(1):70--122, 1998. Google ScholarDigital Library
- László Babai. Trading group theory for randomness. In Proceedings of the Seventeenth Annual ACM Symposium on Theory of Computing, pages 421--429, 1985. Google ScholarDigital Library
- Sergey Bravyi. Efficient algorithm for a quantum analogue of 2-SAT. arXiv.org e-Print archive,arXiv:quant-ph/0602108, 2006.Google Scholar
- Salman Beigi, Peter Shor, and John Watrous. Quantum interactive proofs with short messages. Theory of Computing, 7:101--117 (Article 7), 2011.Google ScholarCross Ref
- Man-Duen Choi. Completely positive linear maps on complex matrices. Linear Algebra and its Applications, 10(3):285--290, 1975.Google ScholarCross Ref
- Matthias Christandl, Robert König, Graeme Mitchison, and Renato Renner. One-and-a-half quantum de Finetti theorems. Communications in Mathematical Physics, 273(2):473--498, 2007.Google ScholarCross Ref
- Shimon Even, Alan L. Selman, and Yacov Yacobi. The complexity of promise problems with applications to public-key cryptography. Information and Control, 61(2):159--173, 1984. Google ScholarDigital Library
- Lov K. Grover. A fast quantum mechanical algorithm for database search. In Proceedings of the Twenty-Eighth Annual ACM Symposium on the Theory of Computing, pages 212--219, 1996. Google ScholarDigital Library
- Sevag Gharibian, Jamie Sikora, and Sarvagya Upadhyay. QMA variants with polynomially many provers. arXiv.org e-Print archive,arXiv:1108.0617 {quant-ph}, 2011.Google Scholar
- Gustav Gutoski. Quantum Strategies and Local Operations. PhD thesis, David R. Cheriton School of Computer Science, University of Waterloo, 2009. arXiv:1003.0038 {quant-ph}.Google Scholar
- Oded Goldreich and David Zuckerman. Another proof that BPP ⊆ ¶H (and more). In Oded Goldreich, editor, Studies in Complexity and Cryptography, Miscellanea on the Interplay between Randomness and Computation, volume 6650 of Lecture Notes in Computer Science, pages 40--53. Springer-Verlag, 2011. Electronic Colloquium on Computational Complexity, Report TR97-045, 1997. Google ScholarDigital Library
- Andrzej Jamiołkowski. Linear transformations which preserve trace and positive semidefiniteness of operators. Reports on Mathematical Physics, 3(4):275--278, 1972.Google ScholarCross Ref
- Rahul Jain, Zhengfeng Ji, Sarvagya Upadhyay, and John Watrous. QIP = SPACE. Journal of the ACM, 58(6):Article 30, 2011.Google ScholarDigital Library
- Stephen P. Jordan, Hirotada Kobayashi, Daniel Nagaj, and Harumichi Nishimura. Achieving perfect completeness in classical-witness quantum Merlin-Arthur proof systems. Quantum Information and Computation, 12(5--6):0461--0471, 2012. Google ScholarDigital Library
- AlexeirelaxYu. Kitaev. Quantum NP. Talk at the 2nd Workshop on Algorithms in Quantum Information Processing, DePaul University, Chicago, January 1999.Google Scholar
- Julia Kempe, Hirotada Kobayashi, Keiji Matsumoto, and Thomas Vidick. Using entanglement in quantum multi-prover interactive proofs. Computational Complexity, 18(2):273--307, 2009.Google ScholarCross Ref
- Emanuel Knill. Quantum randomness and nondeterminism. Technical Report LAUR-96--2186, Los Alamos National Laboratory, 1996. arXiv.org e-Print archive,arXiv:quant-ph/9610012.Google Scholar
- Robert König and Renato Renner. A de Finetti representation for finite symmetric quantum states. Journal of Mathematical Physics, 46(12):122108, 2005.Google ScholarCross Ref
- AlexeirelaxYu. Kitaev, Alexander H. Shen, and Mikhail N. Vyalyi. Classical and Quantum Computation, volume 47 of Graduate Studies in Mathematics. American Mathematical Society, 2002. Google ScholarDigital Library
- Greg Kuperberg. How hard is it to approximate the Jones polynomial? arXiv.org e-print archive,arXiv:0908.0512 {quant-ph}, 2009.Google Scholar
- Alexei Kitaev and John Watrous. Parallelization, amplification, and exponential time simulation of quantum interactive proof systems. In Proceedings of the Thirty-Second Annual ACM Symposium on Theory of Computing, pages 608--617, 2000. Google ScholarDigital Library
- Chris Marriott and John Watrous. Quantum Arthur-Merlin games. Computational Complexity, 14(2):122--152, 2005. Google ScholarDigital Library
- Michael A. Nielsen and Isaac L. Chuang. Quantum Computation and Quantum Information. Cambridge University Press, 2000. Google ScholarDigital Library
- Ashwin Nayak and Peter Shor. Bit-commitment-based quantum coin flipping. Physical Review A, 67(1):012304, 2003.Google ScholarCross Ref
- Daniel Nagaj, Pawel Wocjan, and Yong Zhang. Fast amplification of QMA. Quantum Information and Computation, 9(11--12):1053--1068, 2009. Google ScholarDigital Library
- Yaoyun Shi. Both Toffoli and Controlled-NOT need little help to do universal quantum computing. Quantum Information and Computation, 3(1):084--092, 2002. Google ScholarDigital Library
- Peter W. Shor. Fault-tolerant quantum computation. In 37th Annual Symposium on Foundations of Computer Science, pages 56--65, 1996. Google ScholarDigital Library
- Robert W. Spekkens and Terry Rudolph. Degrees of concealment and bindingness in quantum bit commitment protocols. Physical Review A, 65(1):012310, 2002.Google ScholarCross Ref
- Mikhail N. Vyalyi. QMA=P implies that P contains H. Electronic Colloquium on Computational Complexity, Report TR03-021, 2003.Google Scholar
- John Watrous. Succinct quantum proofs for properties of finite groups. In 41st Annual Symposium on Foundations of Computer Science, pages 537--546, 2000. Google ScholarDigital Library
- John Watrous. SPACE has constant-round quantum interactive proof systems. Theoretical Computer Science, 292(3):575--588, 2003. Google ScholarDigital Library
- John Watrous. Quantum computational complexity. In Robert A. Meyers, editor, Encyclopedia of Complexity and Systems Science, pages 7174--7201. Springer-Verlag, 2009.Google ScholarCross Ref
- John Watrous. Zero-knowledge against quantum attacks. SIAM Journal on Computing, 39(1):25--58, 2009. Google ScholarDigital Library
- Stathis Zachos and Martin Fürer. Probabilistic quantifiers vs. distrustful adversaries. In Foundations of Software Technology and Theoretical Computer Science, Seventh Conference, volume 287 of Lecture Notes in Computer Science, pages 443--455, 1987. Google ScholarDigital Library
Index Terms
- Stronger methods of making quantum interactive proofs perfectly complete
Recommendations
Stronger Methods of Making Quantum Interactive Proofs Perfectly Complete
This paper presents stronger methods of achieving perfect completeness in quantum interactive proofs. It is proved that any problem in QMA has a two-message quantum interactive proof system with perfect completeness and constant soundness error, where the ...
Quantum interactive proofs with weak error bounds
ITCS '12: Proceedings of the 3rd Innovations in Theoretical Computer Science ConferenceThis paper proves that the computational power of quantum interactive proof systems, with a double-exponentially small gap in acceptance probability between the completeness and soundness cases, is precisely characterized by EXP, the class of problems ...
Quantum multi-prover interactive proof systems with limited prior entanglement
This paper gives the first formal treatment of a quantum analogue of multi-prover interactive proof systems. It is proved that the class of languages having quantum multi-prover interactive proof systems is necessarily contained in NEXP, under the ...
Comments