{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,11,26]],"date-time":"2025-11-26T14:04:38Z","timestamp":1764165878288,"version":"3.46.0"},"reference-count":65,"publisher":"Association for Computing Machinery (ACM)","issue":"6","funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"crossref","award":["62332009, 12347104"],"award-info":[{"award-number":["62332009, 12347104"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Innovation Program for Quantum Science and Technology","award":["2021ZD0302901"],"award-info":[{"award-number":["2021ZD0302901"]}]},{"name":"NSFC\/RGC Joint Research Scheme","award":["12461160276"],"award-info":[{"award-number":["12461160276"]}]},{"DOI":"10.13039\/501100004608","name":"Natural Science Foundation of Jiangsu Province","doi-asserted-by":"crossref","award":["BK20243060"],"award-info":[{"award-number":["BK20243060"]}],"id":[{"id":"10.13039\/501100004608","id-type":"DOI","asserted-by":"crossref"}]},{"name":"US National Science Foundation QLCI","award":["OMA-2016245"],"award-info":[{"award-number":["OMA-2016245"]}]},{"DOI":"10.13039\/501100005090","name":"Beijing Nova Program","doi-asserted-by":"crossref","award":["20220484128 and 20240484652"],"award-info":[{"award-number":["20220484128 and 20240484652"]}],"id":[{"id":"10.13039\/501100005090","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2025,12,31]]},"abstract":"<jats:p>\n                    The class MIP* of quantum multiprover interactive proof systems with entanglement is much more powerful than its classical counterpart MIP\u00a0[\n                    <jats:xref ref-type=\"bibr\">8<\/jats:xref>\n                    ,\n                    <jats:xref ref-type=\"bibr\">31<\/jats:xref>\n                    ,\n                    <jats:xref ref-type=\"bibr\">32<\/jats:xref>\n                    ]: while MIP = NEXP, the quantum class MIP * is equal to RE, a class including the halting problem. This is because the provers in MIP * can share unbounded quantum entanglement. However, recent works\u00a0[\n                    <jats:xref ref-type=\"bibr\">53<\/jats:xref>\n                    ,\n                    <jats:xref ref-type=\"bibr\">54<\/jats:xref>\n                    ] have shown that this advantage is significantly reduced if the provers\u2019 shared state contains noise. This article attempts to exactly characterize the effect of noise on the computational power of quantum multiprover interactive proof systems. We investigate the quantum two-prover one-round interactive system MIP * [poly,\n                    <jats:italic toggle=\"yes\">O<\/jats:italic>\n                    (1)], where the verifier sends polynomially many bits to the provers and the provers send back constantly many bits. We show that noise completely destroys the computational advantage given by shared entanglement in this model. Specifically, we show that if the provers are allowed to share arbitrarily many EPR states, where each EPR state is affected by an arbitrarily small constant amount of noise, the resulting complexity class is equivalent to NEXP = MIP. This improves significantly on the previous best-known bound of NEEEXP (nondeterministic triply exponential time)\u00a0[\n                    <jats:xref ref-type=\"bibr\">53<\/jats:xref>\n                    ]. We also show that this collapse in power is due to noise, rather than the\n                    <jats:italic toggle=\"yes\">O<\/jats:italic>\n                    (1) answer size, by showing that allowing for noiseless EPR states gives the class the full power of RE = MIP * [poly, poly]. Along the way, we develop two technical tools of independent interest. First, we give a new, deterministic tester for the positivity of an exponentially large matrix, provided that it has a low-degree Fourier decomposition in terms of Pauli matrices. Secondly, we develop a new invariance principle for smooth matrix functions having bounded third-order Fr\u00e9chet derivatives or which are Lipschitz continuous.\n                  <\/jats:p>","DOI":"10.1145\/3760771","type":"journal-article","created":{"date-parts":[[2025,8,16]],"date-time":"2025-08-16T11:06:50Z","timestamp":1755342410000},"page":"1-78","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["The Computational Advantage of MIP* Vanishes in the Presence of Noise"],"prefix":"10.1145","volume":"72","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-3256-5669","authenticated-orcid":false,"given":"Yangjing","family":"Dong","sequence":"first","affiliation":[{"name":"State Key Laboratory for Novel Software Technology, New Cornerstone Science Laboratory, Nanjing University","place":["Nanjing, China"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-1934-3391","authenticated-orcid":false,"given":"Honghao","family":"Fu","sequence":"additional","affiliation":[{"name":"CSAIL, Massachusetts Institute of Technology","place":["Cambridge, United States"]},{"name":"Concordia Institute for Information Systems Engineering, Concordia University","place":["Cambridge, United States"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-3648-3844","authenticated-orcid":false,"given":"Anand","family":"Natarajan","sequence":"additional","affiliation":[{"name":"CSAIL, Massachusetts Institute of Technology","place":["Cambridge, United States"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0004-8760-5498","authenticated-orcid":false,"given":"Minglong","family":"Qin","sequence":"additional","affiliation":[{"name":"State Key Laboratory for Novel Software Technology, New Cornerstone Science Laboratory, Nanjing University","place":["Nanjing, China"]},{"name":"Centre for Quantum Technologies, National University of Singapore","place":["Nanjing, China"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0009-0001-7899-7627","authenticated-orcid":false,"given":"Haochen","family":"Xu","sequence":"additional","affiliation":[{"name":"Key Laboratory of System Software (Chinese Academy of Sciences) and State Key Laboratory of Computer Science, Institute of Software, Chinese Academy of Sciences","place":["Beijing, China"]},{"name":"Department of Computer Science and Engineering, Pennsylvania State University, State College","place":["Beijing, China"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4104-2069","authenticated-orcid":false,"given":"Penghui","family":"Yao","sequence":"additional","affiliation":[{"name":"State Key Laboratory for Novel Software Technology, New Cornerstone Science Laboratory, Nanjing University","place":["Nanjing, China"]},{"name":"Hefei National Laboratory","place":["Nanjing, China"]}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2025,11,26]]},"reference":[{"key":"e_1_3_4_2_2","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539799359385"},{"key":"e_1_3_4_3_2","doi-asserted-by":"publisher","DOI":"10.1145\/3564246.3585234"},{"key":"e_1_3_4_4_2","doi-asserted-by":"publisher","DOI":"10.1088\/1367-2630\/aafef6"},{"key":"e_1_3_4_5_2","unstructured":"Rotem Arnon-Friedman Zvika Brakerski and Thomas Vidick. 2023. Computational entanglement theory. arXiv:2310.02783. Retrieved from https:\/\/arxiv.org\/abs\/2310.02783"},{"key":"e_1_3_4_6_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2018.11"},{"key":"e_1_3_4_7_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2024.13"},{"key":"e_1_3_4_8_2","doi-asserted-by":"publisher","DOI":"10.1145\/3519935.3519965"},{"key":"e_1_3_4_9_2","doi-asserted-by":"publisher","DOI":"10.1007\/BF01200056"},{"key":"e_1_3_4_10_2","doi-asserted-by":"crossref","first-page":"1191","DOI":"10.1109\/FOCS46700.2020.00114","volume-title":"Proceedings of the 2020 IEEE 61st Annual Symposium on Foundations of Computer Science.","author":"Bakshi Ainesh","year":"2020","unstructured":"Ainesh Bakshi, Nadiia Chepurko, and Rajesh Jayaram. 2020. Testing positive semi-definiteness via random submatrices. In Proceedings of the 2020 IEEE 61st Annual Symposium on Foundations of Computer Science. IEEE, 1191\u20131202."},{"key":"e_1_3_4_11_2","first-page":"1064","volume-title":"Proceedings of the36th Conference on Learning Theory.","author":"Bao Zongbo","year":"2023","unstructured":"Zongbo Bao and Penghui Yao. 2023. On testing and learning quantum junta channels. In Proceedings of the36th Conference on Learning Theory.Gergely Neu and Lorenzo Rosasco (Eds.), Vol. 195, PMLR, 1064\u20131094. Retrieved from https:\/\/proceedings.mlr.press\/v195\/bao23b.html"},{"key":"e_1_3_4_12_2","doi-asserted-by":"publisher","DOI":"10.1063\/1.4818985"},{"key":"e_1_3_4_13_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.53.2046"},{"key":"e_1_3_4_14_2","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(93)90044-W"},{"key":"e_1_3_4_15_2","doi-asserted-by":"crossref","unstructured":"Dolev Bluvstein Simon J. Evered Alexandra A. Geim Sophie H. Li Hengyun Zhou Tom Manovitz Sepehr Ebadi Madelyn Cain Marcin Kalinowski Dominik Hangleiter and others. 2024. Logical quantum processor based on reconfigurable atom arrays. Nature 626 7997 (2024) 58\u201365.","DOI":"10.1038\/s41586-023-06927-3"},{"key":"e_1_3_4_16_2","doi-asserted-by":"publisher","DOI":"10.1038\/s41567-018-0124-x"},{"key":"e_1_3_4_17_2","doi-asserted-by":"publisher","DOI":"10.1145\/800105.803400"},{"key":"e_1_3_4_18_2","doi-asserted-by":"publisher","DOI":"10.1038\/s41467-023-41217-6"},{"key":"e_1_3_4_19_2","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977554.ch43"},{"key":"e_1_3_4_20_2","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2004.1313847"},{"key":"e_1_3_4_21_2","volume-title":"Calculus on Normed Vector Spaces","author":"Coleman Rodney","year":"1997","unstructured":"Rodney Coleman. 1997. Calculus on Normed Vector Spaces. Springer-Verlag, New York, New York, NY."},{"key":"e_1_3_4_22_2","doi-asserted-by":"publisher","DOI":"10.1145\/3406325.3451051"},{"key":"e_1_3_4_23_2","doi-asserted-by":"publisher","DOI":"10.22331\/q-2022-01-03-614"},{"key":"e_1_3_4_24_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.CCC.2018.28"},{"issue":"4","key":"e_1_3_4_25_2","first-page":"A1558\u2013A1585","article-title":"Approximating spectral sums of large-scale matrices using stochastic Chebyshev approximations","volume":"39","author":"Han Insu","year":"2017","unstructured":"Insu Han, Dmitry Malioutov, Haim Avron, and Jinwoo Shin. 2017. Approximating spectral sums of large-scale matrices using stochastic Chebyshev approximations. SIAM Journal on Scientific Computing 39, 4 (2017), A1558\u2013A1585.","journal-title":"SIAM Journal on Scientific Computing"},{"key":"e_1_3_4_26_2","doi-asserted-by":"publisher","DOI":"10.1145\/2395116.2395118"},{"key":"e_1_3_4_27_2","doi-asserted-by":"publisher","DOI":"10.1145\/502090.502098"},{"key":"e_1_3_4_28_2","doi-asserted-by":"publisher","DOI":"10.1007\/s11856-011-0181-7"},{"key":"e_1_3_4_29_2","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2009.22"},{"key":"e_1_3_4_30_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2012.11"},{"key":"e_1_3_4_31_2","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055441"},{"key":"e_1_3_4_32_2","doi-asserted-by":"crossref","unstructured":"Zhengfeng Ji Anand Natarajan Thomas Vidick John Wright and Henry Yuen. 2021. \\(\\mathrm{MIP}^*=\\mathrm{RE}\\) . Communications of the ACM 64 11 (2021) 131\u2013138.","DOI":"10.1145\/3485628"},{"key":"e_1_3_4_33_2","unstructured":"Zhengfeng Ji Anand Natarajan Thomas Vidick John Wright and Henry Yuen. 2020. Quantum soundness of the classical low individual degree test. arXiv:2009.12982. Retrieved from https:\/\/arxiv.org\/abs\/2009.12982"},{"key":"e_1_3_4_34_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.CCC.2015.567"},{"key":"e_1_3_4_35_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.CCC.2022.21"},{"key":"e_1_3_4_36_2","doi-asserted-by":"publisher","DOI":"10.1137\/090751293"},{"key":"e_1_3_4_37_2","doi-asserted-by":"publisher","DOI":"10.1137\/090772885"},{"key":"e_1_3_4_38_2","doi-asserted-by":"publisher","DOI":"10.1145\/509907.510017"},{"key":"e_1_3_4_39_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ITCS.2024.69"},{"key":"e_1_3_4_40_2","first-page":"18","volume-title":"Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms","author":"Krauthgamer Robert","year":"2003","unstructured":"Robert Krauthgamer and Ori Sasson. 2003. Property testing of data dimensionality. In Proceedings of the 14th Annual ACM-SIAM Symposium on Discrete Algorithms (Baltimore, Maryland). Society for Industrial and Applied Mathematics, USA, 18\u201327."},{"key":"e_1_3_4_41_2","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806749"},{"key":"e_1_3_4_42_2","unstructured":"Antonio Anna Mele Armando Angrisani Soumik Ghosh Sumeet Khatri Jens Eisert Daniel Stilck Fran\u00e7a and Yihui Quek. 2024. Noise-induced shallow circuits and absence of barren plateaus. arXiv:2403.13927. Retrieved from https:\/\/arxiv.org\/abs\/2403.13927"},{"key":"e_1_3_4_43_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10472-009-9169-y"},{"issue":"1","key":"e_1_3_4_44_2","article-title":"Quantum boolean functions","volume":"2010","author":"Montanaro Ashley","year":"2010","unstructured":"Ashley Montanaro and Tobias J. Osborne. 2010. Quantum boolean functions. Chicago Journal of Theoretical Computer Science 2010, 1 (2010), 1\u201345.","journal-title":"Chicago Journal of Theoretical Computer Science"},{"key":"e_1_3_4_45_2","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2005.53"},{"key":"e_1_3_4_46_2","doi-asserted-by":"publisher","DOI":"10.1145\/3618260.3649662"},{"key":"e_1_3_4_47_2","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055468"},{"key":"e_1_3_4_48_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2019.00039"},{"key":"e_1_3_4_49_2","doi-asserted-by":"publisher","DOI":"10.1145\/3564246.3585208"},{"key":"e_1_3_4_50_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS54457.2022.00016"},{"key":"e_1_3_4_51_2","volume-title":"Analysis of Boolean Functions","author":"O\u2019Donnell Ryan","year":"2013","unstructured":"Ryan O\u2019Donnell. 2013. Analysis of Boolean Functions. Cambridge University Press, Cambridge, UK."},{"key":"e_1_3_4_52_2","doi-asserted-by":"publisher","DOI":"10.1145\/3357713.3384281"},{"key":"e_1_3_4_53_2","doi-asserted-by":"publisher","DOI":"10.1145\/3460532"},{"key":"e_1_3_4_54_2","doi-asserted-by":"publisher","DOI":"10.1137\/20M134592X"},{"key":"e_1_3_4_55_2","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2023.97"},{"key":"e_1_3_4_56_2","doi-asserted-by":"crossref","first-page":"773","DOI":"10.1007\/978-3-540-70575-8_63","volume-title":"Proceedings of the International Colloquium on Automata, Languages, and Programming","author":"Regev Oded","year":"2008","unstructured":"Oded Regev and Liron Schiff. 2008. Impossibility of a quantum speed-up with a faulty oracle. In Proceedings of the International Colloquium on Automata, Languages, and Programming. Springer, 773\u2013781."},{"key":"e_1_3_4_57_2","doi-asserted-by":"publisher","DOI":"10.1038\/nature12035"},{"key":"e_1_3_4_58_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00220-024-04981-0"},{"key":"e_1_3_4_59_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.laa.2006.12.013"},{"key":"e_1_3_4_60_2","doi-asserted-by":"publisher","DOI":"10.1090\/S0025-5718-1990-0993933-0"},{"key":"e_1_3_4_61_2","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-030-32406-3","volume-title":"Multilinear operator integrals","author":"Skripka Anna","year":"2019","unstructured":"Anna Skripka and Anna Tomskova. 2019. Multilinear operator integrals. Springer."},{"key":"e_1_3_4_62_2","doi-asserted-by":"publisher","DOI":"10.1017\/fmp.2018.3"},{"key":"e_1_3_4_63_2","doi-asserted-by":"publisher","DOI":"10.1090\/jams\/929"},{"key":"e_1_3_4_64_2","article-title":"Noncommutative Bohnenblust\u2013Hille Inequality for qudit systems","author":"Slote Joseph","year":"2024","unstructured":"Joseph Slote, Alexander Volberg, and Haonan Zhang. 2024. Noncommutative Bohnenblust\u2013Hille Inequality for qudit systems. Retrieved from https:\/\/arxiv.org\/abs\/2406.08509. arxiv:2406.08509 [math.FA] https:\/\/arxiv.org\/abs\/2406.08509","journal-title":"Retrieved from https:\/\/arxiv.org\/abs\/2406.08509"},{"key":"e_1_3_4_65_2","doi-asserted-by":"publisher","DOI":"10.1561\/0400000010"},{"key":"e_1_3_4_66_2","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.84.052328"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3760771","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,11,26]],"date-time":"2025-11-26T14:00:31Z","timestamp":1764165631000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3760771"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,11,26]]},"references-count":65,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2025,12,31]]}},"alternative-id":["10.1145\/3760771"],"URL":"https:\/\/doi.org\/10.1145\/3760771","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"type":"print","value":"0004-5411"},{"type":"electronic","value":"1557-735X"}],"subject":[],"published":{"date-parts":[[2025,11,26]]},"assertion":[{"value":"2024-07-26","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-08-08","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-11-26","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}