{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,23]],"date-time":"2026-07-23T10:15:23Z","timestamp":1784801723335,"version":"3.55.0"},"reference-count":72,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2013,2,1]],"date-time":"2013-02-01T00:00:00Z","timestamp":1359676800000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"IARPA MUSIQC"},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["0916400, 0829937, 0803478"],"award-info":[{"award-number":["0916400, 0829937, 0803478"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000266","name":"Engineering and Physical Sciences Research Council","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000185","name":"Defense Advanced Research Projects Agency","doi-asserted-by":"publisher","award":["FA9550-09-1-044"],"award-info":[{"award-number":["FA9550-09-1-044"]}],"id":[{"id":"10.13039\/100000185","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100004965","name":"Sixth Framework Programme","doi-asserted-by":"publisher","id":[{"id":"10.13039\/501100004965","id-type":"DOI","asserted-by":"publisher"}]},{"name":"QCS"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2013,2]]},"abstract":"<jats:p>\n            We give a test that can distinguish efficiently between product states of\n            <jats:italic>n<\/jats:italic>\n            quantum systems and states that are far from product. If applied to a state |\n            <jats:italic>\u03c8<\/jats:italic>\n            \u232a whose maximum overlap with a product state is 1 \u2212\n            <jats:italic>\u03b5<\/jats:italic>\n            , the test passes with probability 1 \u2212\n            <jats:italic>\u0398<\/jats:italic>\n            (\n            <jats:italic>\u03b5<\/jats:italic>\n            ), regardless of\n            <jats:italic>n<\/jats:italic>\n            or the local dimensions of the individual systems. The test uses two copies of |\n            <jats:italic>\u03c8<\/jats:italic>\n            \u232a. We prove correctness of this test as a special case of a more general result regarding stability of maximum output purity of the depolarizing channel.\n          <\/jats:p>\n          <jats:p>\n            A key application of the test is to quantum Merlin-Arthur games with multiple Merlins, where we obtain several structural results that had been previously conjectured, including the fact that efficient soundness amplification is possible and that two Merlins can simulate many Merlins: QMA(\n            <jats:italic>k<\/jats:italic>\n            ) = QMA(2) for\n            <jats:italic>k<\/jats:italic>\n            \u2265 2. Building on a previous result of Aaronson et al., this implies that there is an efficient quantum algorithm to verify 3-SAT with constant soundness, given two unentangled proofs of\n            <jats:italic>\u00d5<\/jats:italic>\n            (\u221a\n            <jats:italic>n<\/jats:italic>\n            ) qubits. We also show how QMA(2) with log-sized proofs is equivalent to a large number of problems, some related to quantum information (such as testing separability of mixed states) as well as problems without any apparent connection to quantum mechanics (such as computing injective tensor norms of 3-index tensors). As a consequence, we obtain many hardness-of-approximation results, as well as potential algorithmic applications of methods for approximating QMA(2) acceptance probabilities.\n          <\/jats:p>\n          <jats:p>Finally, our test can also be used to construct an efficient test for determining whether a unitary operator is a tensor product, which is a generalization of classical linearity testing.<\/jats:p>","DOI":"10.1145\/2432622.2432625","type":"journal-article","created":{"date-parts":[[2013,3,5]],"date-time":"2013-03-05T20:28:36Z","timestamp":1362515316000},"page":"1-43","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":69,"title":["Testing Product States, Quantum Merlin-Arthur Games and Tensor Optimization"],"prefix":"10.1145","volume":"60","author":[{"given":"Aram W.","family":"Harrow","sequence":"first","affiliation":[{"name":"University of Bristol and University of Washington"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Ashley","family":"Montanaro","sequence":"additional","affiliation":[{"name":"University of Bristol and University of Cambridge"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2013,2]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1098\/rspa.2007.0113"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2009.v005a001"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/1536414.1536472"},{"key":"e_1_2_1_4_1","doi-asserted-by":"crossref","unstructured":"Aja-Fern\u00e1ndez S. Garc\u00eda R. Tao D. and Li X. 2009. Tensors in Image Processing and Computer Vision. Advances in Pattern Recognition. Springer.   Aja-Fern\u00e1ndez S. Garc\u00eda R. Tao D. and Li X. 2009. Tensors in Image Processing and Computer Vision . Advances in Pattern Recognition. Springer.","DOI":"10.1007\/978-1-84882-299-3"},{"key":"e_1_2_1_5_1","first-page":"305","article-title":"On some additivity problems in quantum information theory","volume":"36","author":"Amosov G. G.","year":"2000","journal-title":"Prob. Inform. Transmiss."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11128-007-0061-6"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213977.2214006"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539796302452"},{"key":"e_1_2_1_10_1","doi-asserted-by":"crossref","unstructured":"Beigi S. 2010. NP vs QMA_log(2). Quant. Inf. Comput. 10 1&2 0141--0151. arXiv:0810.5109.   Beigi S. 2010. NP vs QMA_log(2). Quant. Inf. Comput. 10 1&2 0141--0151. arXiv:0810.5109.","DOI":"10.26421\/QIC10.1-2-10"},{"key":"e_1_2_1_11_1","unstructured":"Beigi S. and Shor P. 2007. On the complexity of computing zero-error and Holevo capacity of quantum channels. arXiv:0709.2090.  Beigi S. and Shor P. 2007. On the complexity of computing zero-error and Holevo capacity of quantum channels. arXiv:0709.2090."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICQNM.2009.21"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(93)90044-W"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00220-011-1302-1"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993683"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-03685-9_31"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.87.167902"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539704442416"},{"key":"e_1_2_1_20_1","doi-asserted-by":"crossref","unstructured":"Chailloux A. and Sattath O. 2011. The complexity of the separable Hamiltonian problem. arXiv:1111.5247.  Chailloux A. and Sattath O. 2011. The complexity of the separable Hamiltonian problem. arXiv:1111.5247.","DOI":"10.1109\/CCC.2012.42"},{"key":"e_1_2_1_21_1","unstructured":"Chen J. and Drucker A. 2010. Short multi-prover quantum proofs for SAT without entangled measurements. arXiv:1011.0716.  Chen J. and Drucker A. 2010. Short multi-prover quantum proofs for SAT without entangled measurements. arXiv:1011.0716."},{"key":"e_1_2_1_22_1","unstructured":"Chiesa A. and Forbes M. 2011. Improved soundness for QMA with multiple provers. arXiv:1108.2098.  Chiesa A. and Forbes M. 2011. Improved soundness for QMA with multiple provers. arXiv:1108.2098."},{"key":"e_1_2_1_23_1","first-page":"441","article-title":"Remarks on symmetries of trilinear forms","volume":"94","author":"Cobos F.","year":"2000","journal-title":"Rev. R. Acad. Cienc. Exact. Fis. Nat. (Esp)"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00220-008-0625-z"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1060590.1060701"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00220-006-0034-0"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.57.830"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.70.062317"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1088\/0305-4470\/39\/45\/001"},{"key":"e_1_2_1_30_1","first-page":"97","article-title":"The art of uninformed decisions: A primer to property testing","volume":"75","author":"Fischer E.","year":"2001","journal-title":"Bull. Europ. Assoc. Theoret Comput. Sci."},{"key":"e_1_2_1_31_1","doi-asserted-by":"crossref","unstructured":"Gharibian S. 2010. Strong NP-hardness of the quantum separability problem. Quant. Inf. Comput. 10 3&4 343--360. arXiv:0810.4507.   Gharibian S. 2010. Strong NP-hardness of the quantum separability problem. Quant. Inf. Comput. 10 3&4 343--360. arXiv:0810.4507.","DOI":"10.26421\/QIC10.3-4-11"},{"key":"e_1_2_1_32_1","doi-asserted-by":"crossref","unstructured":"Gharibian S. Sikora J. and Upadhyay S. 2013. QMA variants with polynomially many provers. Quant. Inf. Comput. 13 1&2 0135--0137. arXiv:1108.0617.   Gharibian S. Sikora J. and Upadhyay S. 2013. QMA variants with polynomially many provers. Quant. Inf. Comput. 13 1&2 0135--0137. arXiv:1108.0617.","DOI":"10.26421\/QIC13.1-2-8"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1007\/s000390050065"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00039-001-0332-9"},{"key":"e_1_2_1_35_1","doi-asserted-by":"crossref","unstructured":"Gr\u00f6tschel M. Lov\u00e1sz L. and Schrijver A. 1993. Geometric Algorithms and Combinatorial Optimization. Springer-Verlag.  Gr\u00f6tschel M. Lov\u00e1sz L. and Schrijver A. 1993. Geometric Algorithms and Combinatorial Optimization . Springer-Verlag.","DOI":"10.1007\/978-3-642-78240-4"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1088\/1751-8113\/43\/42\/425304"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.physrep.2009.02.004"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1145\/780542.780545"},{"key":"e_1_2_1_39_1","unstructured":"Harrow A. W. 2013. Permutations are nearly orthogonal. In preparation.  Harrow A. W. 2013. Permutations are nearly orthogonal. In preparation."},{"key":"e_1_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1038\/nphys1224"},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00220-008-0624-0"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1063\/1.1498491"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0375-9601(96)00706-2"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1103\/RevModPhys.81.865"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2000.1727"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.5555\/2011725.2011730"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2009.22"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2010.10"},{"key":"e_1_2_1_49_1","volume-title":"Proceedings of the 14th International Symposium on Algorithms and Computation (ISAAC\u201903)","author":"Kobayashi H."},{"key":"e_1_2_1_50_1","doi-asserted-by":"crossref","unstructured":"Le Gall F. Nakagawa S. and Nishimura H. 2012. On QMA protocols with two short quantum proofs. Quant. Inf. Comput. 12 7&8 589--600. arXiv:1108.4306.   Le Gall F. Nakagawa S. and Nishimura H. 2012. On QMA protocols with two short quantum proofs. Quant. Inf. Comput. 12 7&8 589--600. arXiv:1108.4306.","DOI":"10.26421\/QIC12.7-8-4"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.98.110503"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.80.052314"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-005-0194-x"},{"key":"e_1_2_1_55_1","volume-title":"conference.","author":"Matsumoto K.","year":"2005"},{"key":"e_1_2_1_56_1","unstructured":"McKague M. 2011. On the power of quantum computation over real Hilbert spaces. arXiv:1109.0795.  McKague M. 2011. On the power of quantum computation over real Hilbert spaces. arXiv:1109.0795."},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.95.260502"},{"key":"e_1_2_1_58_1","unstructured":"Montanaro A. and Osborne T. 2010. Quantum Boolean functions. Chic. J. Theoret. Comput. Sci. 2010. arXiv:0810.2435.  Montanaro A. and Osborne T. 2010. Quantum Boolean functions. Chic. J. Theoret. Comput. Sci. 2010 . arXiv:0810.2435."},{"key":"e_1_2_1_59_1","unstructured":"Nielsen M. A. and Chuang I. L. 2000. Quantum Computation and Quantum Information. Cambridge University Press Cambridge UK.   Nielsen M. A. and Chuang I. L. 2000. Quantum Computation and Quantum Information . Cambridge University Press Cambridge UK."},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1109\/18.796386"},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.77.1413"},{"key":"e_1_2_1_62_1","unstructured":"Renner R. 2005. Security of quantum key distribution. Ph.D. dissertion ETH Zurich. quant-ph\/0512258.  Renner R. 2005. Security of quantum key distribution. Ph.D. dissertion ETH Zurich. quant-ph\/0512258."},{"key":"e_1_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-31594-7_67"},{"key":"e_1_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0375-9601(00)00401-1"},{"key":"e_1_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.75.052318"},{"key":"e_1_2_1_66_1","volume-title":"Unpublished NSF Workshop Report.","author":"van Loan C.","year":"2009"},{"key":"e_1_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.86.5803"},{"key":"e_1_2_1_68_1","doi-asserted-by":"crossref","unstructured":"Walborn S. Ribeiro P. Davidovich L. Mintert F. and Buchleitner A. 2006. Experimental determination of entanglement with a single measurement. Nature 440 7087 1022--1024.  Walborn S. Ribeiro P. Davidovich L. Mintert F. and Buchleitner A. 2006. Experimental determination of entanglement with a single measurement. Nature 440 7087 1022--1024.","DOI":"10.1038\/nature04627"},{"key":"e_1_2_1_69_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.84.052328"},{"key":"e_1_2_1_70_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.68.042307"},{"key":"e_1_2_1_71_1","doi-asserted-by":"publisher","DOI":"10.1063\/1.1498491"},{"key":"e_1_2_1_72_1","doi-asserted-by":"publisher","DOI":"10.1109\/18.796385"},{"key":"e_1_2_1_73_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.95.190501"},{"key":"e_1_2_1_74_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.101.140501"},{"key":"e_1_2_1_75_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.71.4287"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2432622.2432625","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2432622.2432625","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T08:18:20Z","timestamp":1750234700000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2432622.2432625"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2013,2]]},"references-count":72,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2013,2]]}},"alternative-id":["10.1145\/2432622.2432625"],"URL":"https:\/\/doi.org\/10.1145\/2432622.2432625","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2013,2]]},"assertion":[{"value":"2012-03-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2012-11-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2013-02-01","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}