{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,17]],"date-time":"2026-06-17T02:10:52Z","timestamp":1781662252120,"version":"3.54.5"},"reference-count":61,"publisher":"Association for Computing Machinery (ACM)","issue":"6","license":[{"start":{"date-parts":[[2011,12,1]],"date-time":"2011-12-01T00:00:00Z","timestamp":1322697600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["6.07E+15"],"award-info":[{"award-number":["6.07E+15"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2011,12]]},"abstract":"<jats:p>This work considers the quantum interactive proof system model of computation, which is the (classical) interactive proof system model\u2019s natural quantum computational analogue. An exact characterization of the expressive power of quantum interactive proof systems is obtained: the collection of computational problems having quantum interactive proof systems consists precisely of those problems solvable by deterministic Turing machines that use at most a polynomial amount of space (or, more succinctly, QIP = PSPACE). This characterization is proved through the use of a parallelized form of the matrix multiplicative weights update method, applied to a class of semidefinite programs that captures the computational power of quantum interactive proof systems. One striking implication of this characterization is that quantum computing provides no increase in computational power whatsoever over classical computing in the context of interactive proof systems, for it is well known that the collection of computational problems having classical interactive proof systems coincides with those problems solvable by polynomial-space computations.<\/jats:p>","DOI":"10.1145\/2049697.2049704","type":"journal-article","created":{"date-parts":[[2011,12,13]],"date-time":"2011-12-13T15:45:47Z","timestamp":1323791147000},"page":"1-27","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":36,"title":["QIP = PSPACE"],"prefix":"10.1145","volume":"58","author":[{"given":"Rahul","family":"Jain","sequence":"first","affiliation":[{"name":"National University of Singapore"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Zhengfeng","family":"Ji","sequence":"additional","affiliation":[{"name":"Perimeter Institute for Theoretical Physics and Institute of Software, Chinese Academy of Sciences"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Sarvagya","family":"Upadhyay","sequence":"additional","affiliation":[{"name":"University of Waterloo"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"John","family":"Watrous","sequence":"additional","affiliation":[{"name":"University of Waterloo"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2011,12]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511804090"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2005.35"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250790.1250823"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/22145.22192"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(88)90028-1"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01200056"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/12130.12165"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/62212.62223"},{"key":"e_1_2_1_9_1","volume-title":"Proceedings of the IEEE International Conference on Computers, Systems, and Signal Processing. IEEE Computer Society Press","author":"Bennett C.","unstructured":"Bennett , C. and Brassard , G . 1984. Quantum cryptography: Public key distribution and coin tossing . In Proceedings of the IEEE International Conference on Computers, Systems, and Signal Processing. IEEE Computer Society Press , Los Alamitos, CA, 175--179. Bennett, C. and Brassard, G. 1984. Quantum cryptography: Public key distribution and coin tossing. In Proceedings of the IEEE International Conference on Computers, Systems, and Signal Processing. IEEE Computer Society Press, Los Alamitos, CA, 175--179."},{"key":"e_1_2_1_10_1","volume-title":"Matrix Analysis","author":"Bhatia R.","unstructured":"Bhatia , R. 1997. Matrix Analysis . Springer , New York . Bhatia, R. 1997. Matrix Analysis. Springer, New York."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539790182482"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1137\/0206054"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(83)80060-6"},{"key":"e_1_2_1_14_1","volume-title":"Approximation by Algebraic Numbers","author":"Bugeaud Y.","unstructured":"Bugeaud , Y. 2004. Approximation by Algebraic Numbers . Cambridge Tracts in Mathematics, vol. 160 . Cambridge University Press , Cambridge, UK. Bugeaud, Y. 2004. Approximation by Algebraic Numbers. Cambridge Tracts in Mathematics, vol. 160. Cambridge University Press, Cambridge, UK."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/276698.276713"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.2307\/2371045"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/800157.805047"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1137\/0205040"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1098\/rspa.1985.0070"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(79)90152-2"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0019-9958(84)80056-X"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/258533.258644"},{"key":"e_1_2_1_23_1","unstructured":"Feldman P. 1986. The optimum prover lies in PSPACE. Manuscript. Feldman P. 1986. The optimum prover lies in PSPACE. Manuscript."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02650179"},{"key":"e_1_2_1_25_1","volume-title":"Micali Ed. Advances in Computing Research","volume":"5","author":"Furer M.","unstructured":"Furer , M. , Goldreich , O. , Mansour , Y. , Sipser , M. , and Zachos , S . 1989. On completeness and soundness in interactive proof systems. In Randomness and Computation, S . Micali Ed. Advances in Computing Research , vol. 5 . JAI Press, 429--442. Furer, M., Goldreich, O., Mansour, Y., Sipser, M., and Zachos, S. 1989. On completeness and soundness in interactive proof systems. In Randomness and Computation, S. Micali Ed. Advances in Computing Research, vol. 5. JAI Press, 429--442."},{"key":"e_1_2_1_26_1","unstructured":"Goldreich O. 2005. On promise problems (a survey in memory of Shimon Even {1935--2004}). In Electronic Colloquium on Computational Complexity Rep. TR05-018. Goldreich O. 2005. On promise problems (a survey in memory of Shimon Even {1935--2004}). In Electronic Colloquium on Computational Complexity Rep. TR05-018."},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/116825.116852"},{"key":"e_1_2_1_28_1","volume-title":"Micali Ed. Advances in Computing Research","volume":"5","author":"Goldwasser S.","unstructured":"Goldwasser , S. and Sipser , M . 1989. Private coins versus public coins in interactive proof systems. In Randomness and Computation, S . Micali Ed. Advances in Computing Research , vol. 5 . JAI Press, 73--90. Goldwasser, S. and Sipser, M. 1989. Private coins versus public coins in interactive proof systems. In Randomness and Computation, S. Micali Ed. Advances in Computing Research, vol. 5. JAI Press, 73--90."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/22145.22178"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1137\/0218012"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/1250790.1250873"},{"key":"e_1_2_1_32_1","unstructured":"Gutoski G. and Wu X. 2010. Short quantum games characterize PSPACE. arXiv.org e-Print 1011.2787. Gutoski G. and Wu X. 2010. Short quantum games characterize PSPACE. arXiv.org e-Print 1011.2787."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-70583-3_48"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1103\/RevModPhys.81.865"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2009.26"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.25"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.5555\/1747597.1748069"},{"key":"e_1_2_1_39_1","volume-title":"Complexity of Computer Computations","author":"Karp R.","unstructured":"Karp , R. 1972. Reducibility among combinatorial problems . In Complexity of Computer Computations , R. Miller and J. Thatcher Eds. Plenum Press , New York , 85--103. Karp, R. 1972. Reducibility among combinatorial problems. In Complexity of Computer Computations, R. Miller and J. Thatcher Eds. Plenum Press, New York, 85--103."},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-009-0275-3"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/335305.335387"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.5555\/1802614.1802624"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(03)00035-7"},{"key":"e_1_2_1_44_1","first-page":"265","article-title":"Universal sequential search problems (English translation)","volume":"9","author":"Levin L.","year":"1973","unstructured":"Levin , L. 1973 . Universal sequential search problems (English translation) . Probl. Inf. Trans. 9 , 3, 265 -- 266 . Levin, L. 1973. Universal sequential search problems (English translation). Probl. Inf. Trans. 9, 3, 265--266.","journal-title":"Probl. Inf. Trans."},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/146585.146605"},{"key":"e_1_2_1_46_1","volume-title":"Lectures on Diophantine Approximations. Cushing Malloy","author":"Mahler K.","unstructured":"Mahler , K. 1961. Lectures on Diophantine Approximations. Cushing Malloy , Ann Arbor, MI . Mahler, K. 1961. Lectures on Diophantine Approximations. Cushing Malloy, Ann Arbor, MI."},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-005-0194-x"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(92)90132-F"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1137\/S00361445024180"},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(05)80061-3"},{"key":"e_1_2_1_51_1","unstructured":"Nielsen M. and Chuang I. 2000. Quantum Computation and Quantum Information. Cambridge University Press Cambridge UK. Nielsen M. and Chuang I. 2000. Quantum Computation and Quantum Information . Cambridge University Press Cambridge UK."},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/301250.301343"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(91)90194-M"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1145\/146585.146609"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795293172"},{"key":"e_1_2_1_56_1","volume-title":"Introduction to the Theory of Computation","author":"Sipser M.","unstructured":"Sipser , M. 1997. Introduction to the Theory of Computation . PWS Publishing Company , Boston, MA . Sipser, M. 1997. Introduction to the Theory of Computation. PWS Publishing Company, Boston, MA."},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1147\/rd.481.0071"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1112\/plms\/s2-42.1.230"},{"key":"e_1_2_1_59_1","volume-title":"Synthesis of Parallel Algorithms","author":"von zur Gathen J.","unstructured":"von zur Gathen , J. 1993. Parallel linear algebra . In Synthesis of Parallel Algorithms . J. Reif Ed. Morgan Kaufmann Publishers, Inc. , San Francisco, CA , Chap. 13, 573--618. von zur Gathen, J. 1993. Parallel linear algebra. In Synthesis of Parallel Algorithms. J. Reif Ed. Morgan Kaufmann Publishers, Inc., San Francisco, CA, Chap. 13, 573--618."},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1007\/11776420_38"},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.5555\/795665.796478"},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1137\/060670997"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2049697.2049704","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2049697.2049704","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T20:26:41Z","timestamp":1750278401000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2049697.2049704"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,12]]},"references-count":61,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2011,12]]}},"alternative-id":["10.1145\/2049697.2049704"],"URL":"https:\/\/doi.org\/10.1145\/2049697.2049704","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,12]]},"assertion":[{"value":"2011-03-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2011-09-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2011-12-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}