Quantum Interactive Proofs with Short Messages

by Salman Beigi, Peter Shor, and John Watrous

Theory of Computing, Volume 7(7), pp. 101-117, 2011

Bibliography with links to cited articles

[1]   Sanjeev Arora and Boaz Barak: Complexity Theory: A Modern Approach. Cambridge University Press, 2009.

[2]   László Babai: Trading group theory for randomness. In Proc. 17th STOC, pp. 421–429. ACM Press, 1985. [doi:10.1145/22145.22192]

[3]   László Babai and Shlomo Moran: Arthur-Merlin games: A randomized proof system, and a hierarchy of complexity classes. J. Comput. System Sci., 36(2):254–276, 1988. [doi:10.1016/0022-0000(88)90028-1]

[4]   Man-Duen Choi: Completely positive linear maps on complex matrices. Linear Algebra Appl., 10(3):285–290, 1975. [doi:10.1016/0024-3795(75)90075-0]

[5]   Matthias Christandl, Robert König, Graeme Mitchison, and Renato Renner: One-and-a-half quantum de Finetti theorems. Comm. Math. Phys., 273(2):473–498, 2007. [doi:10.1007/s00220-007-0189-3]

[6]   Christopher A. Fuchs and Jeroen van de Graaf: Cryptographic distinguishability measures for quantum-mechanical states. IEEE Trans. Inform. Theory, 45(4):1216–1227, 1999. [doi:10.1109/18.761271]

[7]   Oded Goldreich: Computational Complexity – A Conceptual Perspective. Cambridge University Press, 2008.

[8]   Oded Goldreich, Silvio Micali, and Avi Wigderson: Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systems. J. ACM, 38(1):691–729, 1991. [doi:10.1145/116825.116852]

[9]   Shafi Goldwasser, Silvio Micali, and Charles Rackoff: The knowledge complexity of interactive proof systems. In Proc. 17th STOC, pp. 291–304. ACM Press, 1985. [doi:10.1145/22145.22178]

[10]   Shafi Goldwasser, Silvio Micali, and Charles Rackoff: The knowledge complexity of interactive proof systems. SIAM J. Comput., 18(1):186–208, 1989. [doi:10.1137/0218012]

[11]   Shafi Goldwasser and Michael Sipser: Private coins versus public coins in interactive proof systems. In S. Micali, editor, Randomness and Computation, volume 5 of Advances in Computing Research, pp. 73–90. JAI Press, 1989.

[12]   Martin Grötschel, László Lovász, and Alexander Schrijver: Geometric Algorithms and Combinatorial Optimization. Springer–Verlag, second corrected edition, 1993.

[13]   Gus Gutoski and John Watrous: Toward a general theory of quantum games. In Proc. 39th STOC, pp. 565–574. ACM Press, 2007. [doi:10.1145/1250790.1250873]

[14]   Rahul Jain, Zhengfeng Ji, Sarvagya Upadhyay, and John Watrous: QIP = PSPACE. In Proc. 42nd STOC, pp. 573–581. ACM Press, 2010. [doi:10.1145/1806689.1806768]

[15]   A. Jamiołkowski: Linear transformations which preserve trace and positive semidefiniteness of operators. Rep. Math. Phys., 3(4):275–278, 1972. [doi:10.1016/0034-4877(72)90011-0]

[16]   A. Yu. Kitaev, A. H. Shen, and M. N. Vyalyi: Classical and Quantum Computation. Volume 47 of Graduate Studies in Mathematics. American Mathematical Society, 2002.

[17]   Alexei Kitaev and John Watrous: Parallelization, amplification, and exponential time simulation of quantum interactive proof system. In Proc. 32nd STOC, pp. 608–617. ACM Press, 2000. [doi:10.1145/335305.335387]

[18]   Robert König and Renato Renner: A de Finetti representation for finite symmetric quantum states. J. Math. Phys., 46:122108, 2005. [doi:10.1063/1.2146188]

[19]   Carsten Lund, Lance Fortnow, Howard Karloff, and Noam Nisan: Algebraic methods for interactive proof systems. J. ACM, 39(4):859–868, 1992. [doi:10.1145/146585.146605]

[20]   Chris Marriott and John Watrous: Quantum Arthur-Merlin games. Comput. Complexity, 14(2):122–152, 2005. [doi:10.1007/s00037-005-0194-x]

[21]   Michael A. Nielsen and Isaac L. Chuang: Quantum Computation and Quantum Information. Cambridge University Press, 2000.

[22]   Adi Shamir: IP = PSPACE. J. ACM, 39(4):869–877, 1992. [doi:10.1145/146585.146609]

[23]   John Watrous: Limits on the power of quantum statistical zero-knowledge. In Proc. 43rd FOCS, pp. 459–468. IEEE Comp. Soc. Press, 2002. [doi:10.1109/SFCS.2002.1181970]

[24]   John Watrous: PSPACE has constant-round quantum interactive proof systems. Theoret. Comput. Sci., 292(3):575–588, 2003. Preliminary version in Proc. 40th FOCS, 1999, pp. 112–119. [doi:10.1016/S0304-3975(01)00375-9]