{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,31]],"date-time":"2026-03-31T17:25:03Z","timestamp":1774977903081,"version":"3.50.1"},"reference-count":89,"publisher":"Association for Computing Machinery (ACM)","issue":"1","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["SIGACT News"],"published-print":{"date-parts":[[2026,3,31]]},"abstract":"<jats:p>The complexity class QMA(2), featuring two unentangled quantum provers, occupies a central yet poorly understood position in quantum complexity theory. While superficially a modest extension of QMA, unentanglement fundamentally changes both the algorithmic and complexitytheoretic landscape, connecting QMA(2) to deep questions in separability testing, polynomial optimization, and hardness of approximation. Over the past two decades, QMA(2) has inspired a rich body of work spanning restricted verification models, semidefinite and Sum-of-Squares hierarchies, and surprising links to classical problems such as the Unique Games Conjecture. This survey provides an overview of these developments, emphasizing structural insights, algorithmic techniques, and known barriers, while highlighting how progress on QMA(2) continues to illuminate the interplay between quantum information, convex optimization, and classical complexity theory.<\/jats:p>","DOI":"10.1145\/3802807.3802814","type":"journal-article","created":{"date-parts":[[2026,3,31]],"date-time":"2026-03-31T16:40:36Z","timestamp":1774975236000},"page":"64-99","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["The QMA(2) UniverseComplexity, Entanglement, and Optimization"],"prefix":"10.1145","volume":"57","author":[{"given":"Fernando Granha","family":"Jeronimo","sequence":"first","affiliation":[{"name":"University of Illinois Urbana-Champaign, Champaign, IL, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pei","family":"Wu","sequence":"additional","affiliation":[{"name":"Penn State University, University Park, PA, USA"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Itai","family":"Leigh","sequence":"additional","affiliation":[{"name":"AI, Tel-Aviv University, Tel-Aviv, Israel"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2026,3,31]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2008.5"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/2775105"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2014.13"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-981-96-1218-5_3"},{"key":"e_1_2_1_5_1","volume-title":"Quantum np - a survey","author":"Aharonov Dorit","year":"2002","unstructured":"Dorit Aharonov and Tomer Naveh. Quantum np - a survey, 2002. URL: https:\/\/arxiv.org\/abs\/quant-ph\/0210077 , arXiv:quant-ph\/0210077."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2003.1238195"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/780542.780546"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213977.2214006"},{"key":"e_1_2_1_9_1","first-page":"1302","volume-title":"Communications in Mathematical Physics","author":"Brand\u00e3o Fernando G. S. L.","year":"2011","unstructured":"Fernando G. S. L. Brand\u00e3o, Matthias Christandl, and Jon Yard. Faithful squashed entanglement. Communications in Mathematical Physics, 2011. doi:10.1007\/ s00220-011-1302-1."},{"key":"e_1_2_1_10_1","volume-title":"Quantum Info. Comput., 2010","author":"Beigi Salman","year":"2011","unstructured":"Salman Beigi. NP vs QMAlog(2). Quantum Info. Comput., 2010. doi:10.5555\/ 2011438.2011448."},{"key":"e_1_2_1_11_1","volume-title":"Quantum Merlin-Arthur with an internally separable proof","author":"Bassirian Roozbeh","year":"2024","unstructured":"Roozbeh Bassirian, Bill Fefferman, Itai Leigh, Kunal Marwaha, and Pei Wu. Quantum Merlin-Arthur with an internally separable proof, 2024. URL: https:\/\/arxiv.org\/ abs\/2410.19152, arXiv:2410.19152."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ITCS.2024.9"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.97"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2488608.2488718"},{"key":"e_1_2_1_15_1","volume-title":"Estimating operator norms using covering nets. CoRR, abs\/1509.05065","author":"Brandao Fernando G. S. L.","year":"2015","unstructured":"Fernando G. S. L. Brandao and Aram W. Harrow. Estimating operator norms using covering nets. CoRR, abs\/1509.05065, 2015. arXiv:1509.05065."},{"key":"e_1_2_1_16_1","unstructured":"Vijay Bhattiprolu. On the Approximability of Injective Tensor Norm. PhD thesis Carnegie Mellon University Pittsburgh PA 2019. URL: http:\/\/reports-archive . adm.cs.cmu.edu\/anon\/2019\/Carnegie Mellon University-CS-19-115.pdf."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.90.012301"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.22331\/q-2025-07-11-1791"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591886"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.22331\/q-2025-08-28-1839"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-61792-9_30"},{"key":"e_1_2_1_23_1","volume-title":"April","author":"Bookatz Adam D.","year":"2014","unstructured":"Adam D. Bookatz. Qma-complete problems. Quantum Info. Comput., 14(5 & 6):361-383, April 2014."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/235809.235813"},{"key":"e_1_2_1_25_1","unstructured":"Fernando G. S. L. Brandao. Entanglement Theory and the Quantum Simulation of Many-Body Physics. PhD thesis University of London 2008. URL: https:\/\/arxiv . org\/abs\/0810.0026 arXiv:0810.0026."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1063\/1.3364793"},{"key":"e_1_2_1_27_1","volume-title":"Sum-of-squares: proofs, beliefs, and algorithms. https:\/\/www.sumofsquares.org","author":"Barak Boaz","year":"2016","unstructured":"Boaz Barak and David Steurer. Sum-of-squares: proofs, beliefs, and algorithms. https:\/\/www.sumofsquares.org, 2016. URL: https:\/\/www.sumofsquares.org"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICQNM.2009.21"},{"key":"e_1_2_1_29_1","volume-title":"Short multi-prover quantum proofs for sat without entangled measurements. CoRR, abs\/1011.0716","author":"Chen Jing","year":"2010","unstructured":"Jing Chen and Andrew Drucker. Short multi-prover quantum proofs for sat without entangled measurements. CoRR, abs\/1011.0716, 2010."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.4086\/cjtcs.2013.001"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00220-007-0189-3"},{"key":"e_1_2_1_32_1","volume-title":"New approaches to complexity via quantum graphs","author":"Culf Eric","year":"2025","unstructured":"Eric Culf and Arthur Mehta. New approaches to complexity via quantum graphs, 2025. URL: https:\/\/arxiv.org\/abs\/2309.12887 , arXiv:2309.12887."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2012.42"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1103\/physreva.69.022308"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-020-01537-7"},{"key":"e_1_2_1_36_1","volume-title":"Quantum merlin arthur with exponentially small gap","author":"Fefferman Bill","year":"2016","unstructured":"Bill Fefferman and Cedric Lin. Quantum merlin arthur with exponentially small gap, 2016. URL: https:\/\/arxiv.org\/abs\/1601.01975 , arXiv:1601.01975."},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.5555\/2011350.2011361"},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2015.v011a003"},{"key":"e_1_2_1_39_1","volume-title":"On the complexity of estimating ground state entanglement and free energy. arXiv preprint arXiv:2510.06796","author":"Gharibian Sevag","year":"2025","unstructured":"Sevag Gharibian and Jonas Kamminga. On the complexity of estimating ground state entanglement and free energy. arXiv preprint arXiv:2510.06796, 2025. doi:10.48550\/ arXiv.2510.06796."},{"key":"e_1_2_1_40_1","volume-title":"Unentanglement and post-measurement branching in quantum interactive proofs. CoRR, abs\/2509.15319","author":"Grewal Sabee","year":"2025","unstructured":"Sabee Grewal and William Kretschmer. Unentanglement and post-measurement branching in quantum interactive proofs. CoRR, abs\/2509.15319, 2025. URL: https: \/\/arxiv.org\/abs\/2509.15319."},{"key":"e_1_2_1_41_1","volume-title":"Geometric algorithms and combinatorial optimization","author":"Gr\u00f6tschel Martin","year":"2012","unstructured":"Martin Gr\u00f6tschel, L\u00e1szl\u00f3 Lov\u00e1sz, and Alexander Schrijver. Geometric algorithms and combinatorial optimization, volume 2. Springer Science & Business Media, 2012."},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.26421\/qic12.7-8-4"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-005-0189-7"},{"key":"e_1_2_1_44_1","volume-title":"On the pure quantum polynomial hierarchy and quantified hamiltonian complexity. CoRR, abs\/2510.06522","author":"Grewal Sabee","year":"2025","unstructured":"Sabee Grewal and Dorian Rudolph. On the pure quantum polynomial hierarchy and quantified hamiltonian complexity. CoRR, abs\/2510.06522, 2025."},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-022-00231-8"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/780542.780545"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.CCC.2024.6"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1007\/s11005-023-01744-1"},{"key":"e_1_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0375-9601(96)00706-2"},{"key":"e_1_2_1_50_1","volume-title":"Harrow and Ashley Montanaro. Testing product states, quantum merlinarthur games and tensor optimization. J. ACM, 60(1), feb","author":"Aram","year":"2013","unstructured":"Aram W. Harrow and Ashley Montanaro. Testing product states, quantum merlinarthur games and tensor optimization. J. ACM, 60(1), feb 2013. doi:10.1145\/ 2432622.2432625."},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00220-017-2859-0"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00220-019-03382-y"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.5555\/2011725.2011730"},{"key":"e_1_2_1_54_1","volume-title":"A cheeger inequality for small set expansion. CoRR, abs\/2304.07612","author":"Jalan Akhil","year":"2023","unstructured":"Akhil Jalan. A cheeger inequality for small set expansion. CoRR, abs\/2304.07612, 2023."},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806768"},{"key":"e_1_2_1_56_1","volume-title":"Coherence in property testing: Quantum-classical collapses and separations. CoRR, abs\/2411.15148","author":"Jeronimo Fernando Granha","year":"2024","unstructured":"Fernando Granha Jeronimo, Nir Magrafta, Joseph Slote, and Pei Wu. Coherence in property testing: Quantum-classical collapses and separations. CoRR, abs\/2411.15148, 2024."},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1145\/3485628"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2009.26"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1145\/3564246.3585248"},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.CCC.2024"},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1145\/509907.510017"},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-24587-2_21"},{"key":"e_1_2_1_63_1","volume-title":"On the complexity of pure-state consistency of local density matrices. CoRR, abs\/2411.03096","author":"Kamminga Jonas","year":"2024","unstructured":"Jonas Kamminga and Dorian Rudolph. On the complexity of pure-state consistency of local density matrices. CoRR, abs\/2411.03096, 2024."},{"key":"e_1_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1090\/gsm\/047"},{"key":"e_1_2_1_65_1","first-page":"608","volume-title":"Proceedings of the 32nd ACM Symposium on Theory of Computing (STOC)","author":"Kitaev Alexei","year":"2000","unstructured":"Alexei Kitaev and John Watrous. Parallelization, amplification, and exponential time simulation of quantum interactive proof systems. In Proceedings of the 32nd ACM Symposium on Theory of Computing (STOC), page 608-617, 2000. doi:10.1145\/ 335305.335387."},{"key":"e_1_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.98.110503"},{"key":"e_1_2_1_67_1","volume-title":"A simple proof of preciseqma = pspace","author":"Li Yulong","year":"2022","unstructured":"Yulong Li. A simple proof of preciseqma = pspace, 2022. URL: https:\/\/arxiv.org\/ abs\/2206.09230, arXiv:2206.09230."},{"key":"e_1_2_1_68_1","doi-asserted-by":"publisher","DOI":"10.1007\/11830924_40"},{"key":"e_1_2_1_69_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.114.160503"},{"key":"e_1_2_1_70_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00220-013-1779-x"},{"key":"e_1_2_1_71_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-005-0194-x"},{"key":"e_1_2_1_72_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.gs.2016.007"},{"key":"e_1_2_1_73_1","doi-asserted-by":"publisher","DOI":"10.1007\/s10107-011-0489-4"},{"key":"e_1_2_1_74_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.80.052306"},{"key":"e_1_2_1_75_1","doi-asserted-by":"publisher","DOI":"10.1145\/3564246.3585208"},{"key":"e_1_2_1_76_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.77.1413"},{"key":"e_1_2_1_77_1","volume-title":"Multi-prover quantum merlin-arthur proof systems with small gap. CoRR, abs\/1205.2761","author":"Pereszl\u00e9nyi Attila","year":"2012","unstructured":"Attila Pereszl\u00e9nyi. Multi-prover quantum merlin-arthur proof systems with small gap. CoRR, abs\/1205.2761, 2012. arXiv:1205.2761."},{"key":"e_1_2_1_78_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0747-7171(10)80003-3"},{"key":"e_1_2_1_79_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0747-7171(10)"},{"key":"e_1_2_1_80_1","doi-asserted-by":"publisher","DOI":"10.1137\/0221060"},{"key":"e_1_2_1_81_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2004.1313849"},{"key":"e_1_2_1_82_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806792"},{"key":"e_1_2_1_83_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2012.43"},{"key":"e_1_2_1_84_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2015.03.031"},{"key":"e_1_2_1_85_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977073.68"},{"key":"e_1_2_1_86_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ITCS.2023.96"},{"key":"e_1_2_1_87_1","doi-asserted-by":"publisher","DOI":"10.1017\/9781316848142"},{"key":"e_1_2_1_88_1","doi-asserted-by":"publisher","DOI":"10.22331\/q-2025-04-18-1717"},{"key":"e_1_2_1_89_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ITCS"}],"container-title":["ACM SIGACT News"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3802807.3802814","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,3,31]],"date-time":"2026-03-31T16:40:45Z","timestamp":1774975245000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3802807.3802814"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,3,31]]},"references-count":89,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2026,3,31]]}},"alternative-id":["10.1145\/3802807.3802814"],"URL":"https:\/\/doi.org\/10.1145\/3802807.3802814","relation":{},"ISSN":["0163-5700"],"issn-type":[{"value":"0163-5700","type":"print"}],"subject":[],"published":{"date-parts":[[2026,3,31]]},"assertion":[{"value":"2026-03-31","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}