{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,28]],"date-time":"2025-10-28T13:16:18Z","timestamp":1761657378661,"version":"build-2065373602"},"reference-count":56,"publisher":"Association for Computing Machinery (ACM)","issue":"4","funder":[{"DOI":"10.13039\/501100000266","name":"EPSRC","doi-asserted-by":"crossref","award":["EP\/W014882\/1"],"award-info":[{"award-number":["EP\/W014882\/1"]}],"id":[{"id":"10.13039\/501100000266","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Research Fellowship from the Royal Commission for the Exhibition of 1851"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Quantum Comput."],"published-print":{"date-parts":[[2025,12,31]]},"abstract":"<jats:p>We prove that the computation of the Kronecker coefficients of the symmetric group is contained in the complexity class #BQP. This improves a recent result of Bravyi, Chowdhury, Gosset, Havlicek, and Zhu. We use the same quantum algorithmic tools that are used in their paper, combined with additional classical representation theoretic insights. We also prove the analogous result for the plethysm coefficients and the row sums of the symmetric group character table.<\/jats:p>","DOI":"10.1145\/3762673","type":"journal-article","created":{"date-parts":[[2025,8,22]],"date-time":"2025-08-22T11:50:42Z","timestamp":1755863442000},"page":"1-13","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Kronecker Coefficients in #BQP"],"prefix":"10.1145","volume":"6","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-4654-177X","authenticated-orcid":false,"given":"Christian","family":"Ikenmeyer","sequence":"first","affiliation":[{"name":"Department of Computer Science, University of Warwick","place":["Coventry, United Kingdom of Great Britain and Northern Ireland"]}],"role":[{"role":"author","vocabulary":"crossref"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-8716-3424","authenticated-orcid":false,"given":"Sathyawageeswar","family":"Subramanian","sequence":"additional","affiliation":[{"name":"Department of Computer Science, University of Warwick","place":["Coventry, United Kingdom of Great Britain and Northern Ireland"]},{"name":"Department of Computer Science and Technology, University of Cambridge","place":["Coventry, United Kingdom of Great Britain and Northern Ireland"]}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2025,10,28]]},"reference":[{"key":"e_1_3_2_2_2","doi-asserted-by":"crossref","unstructured":"Scott Aaronson. 2008. On perfect completeness for QMA. Quantum Information & Computation 9 1 (2008) 81\u201389.","DOI":"10.26421\/QIC9.1-2-5"},{"key":"e_1_3_2_3_2","first-page":"B54Af","article-title":"A combinatorial interpretation for the coefficients in the Kronecker product  \\(s_{(n-p, p)}\\ast s_\\lambda\\)","volume":"54","author":"Ballantine Cristina","year":"2006","unstructured":"Cristina Ballantine and Rosa Orellana. 2006. A combinatorial interpretation for the coefficients in the Kronecker product \\(s_{(n-p, p)}\\ast s_\\lambda\\) . S\u00e9minaire Lotharingien de Combinatoire 54 (2006), B54Af.","journal-title":"S\u00e9minaire Lotharingien de Combinatoire"},{"key":"e_1_3_2_4_2","unstructured":"Markus Bl\u00e4ser and Christian Ikenmeyer. 2018. Introduction to geometric complexity theory. (2018). Retrieved 03 September 2025 from https:\/\/www.dcs.warwick.ac.uk\/u2270030\/teaching_sb\/summer17\/introtogct\/gct.pdf"},{"key":"e_1_3_2_5_2","first-page":"2016","article-title":"Kronecker coefficients for one hook shape","volume":"77","author":"Blasiak Jonah","year":"2017","unstructured":"Jonah Blasiak. 2017. Kronecker coefficients for one hook shape. S\u00e9minaire Lotharingien de Combinatoire 77 (2017), 2016\u20132017.","journal-title":"S\u00e9minaire Lotharingien de Combinatoire"},{"key":"e_1_3_2_6_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcta.2018.02.007"},{"key":"e_1_3_2_7_2","volume-title":"Memoirs of the AMS","author":"Blasiak Jonah","year":"2015","unstructured":"Jonah Blasiak, Ketan Mulmuley, and Milind Sohoni. 2015. Geometric complexity theory IV: Nonstandard quantum group for the Kronecker problem. In Memoirs of the AMS. Vol. 235. American Mathematical Society."},{"key":"e_1_3_2_8_2","doi-asserted-by":"publisher","DOI":"10.1103\/prxquantum.5.010329"},{"issue":"4","key":"e_1_3_2_9_2","doi-asserted-by":"crossref","first-page":"040501","DOI":"10.1103\/PhysRevLett.107.040501","article-title":"Computational difficulty of computing the density of states","volume":"107","author":"Brown Brielin","year":"2011","unstructured":"Brielin Brown, Steven T. Flammia, and Norbert Schuch. 2011. Computational difficulty of computing the density of states. Physical Review Letters 107, 4 (2011), 040501.","journal-title":"Physical Review Letters"},{"issue":"3","key":"e_1_3_2_10_2","doi-asserted-by":"crossref","first-page":"1247","DOI":"10.1090\/proc\/13310","article-title":"Permanent versus determinant: Not via saturations","volume":"145","author":"B\u00fcrgisser Peter","year":"2017","unstructured":"Peter B\u00fcrgisser, Jesko H\u00fcttenhain, and Christian Ikenmeyer. 2017. Permanent versus determinant: Not via saturations. Proceedings of the AMS 145, 3 (2017), 1247\u20131258.","journal-title":"Proceedings of the AMS"},{"key":"e_1_3_2_11_2","first-page":"509","volume-title":"Proceedings of the 43rd Annual ACM Symposium on Theory of Computing","author":"B\u00fcrgisser Peter","year":"2011","unstructured":"Peter B\u00fcrgisser and Christian Ikenmeyer. 2011. Geometric complexity theory and tensor rank. In Proceedings of the 43rd Annual ACM Symposium on Theory of Computing. 509\u2013518."},{"key":"e_1_3_2_12_2","first-page":"141","volume-title":"Proceedings of the 45th Annual ACM Symposium on Theory of Computing","author":"B\u00fcrgisser Peter","year":"2013","unstructured":"Peter B\u00fcrgisser and Christian Ikenmeyer. 2013. Explicit lower bounds via geometric complexity theory. In Proceedings of the 45th Annual ACM Symposium on Theory of Computing. 141\u2013150."},{"issue":"1","key":"e_1_3_2_13_2","first-page":"163","article-title":"No occurrence obstructions in geometric complexity theory","volume":"32","author":"B\u00fcrgisser Peter","year":"2019","unstructured":"Peter B\u00fcrgisser, Christian Ikenmeyer, and Greta Panova. 2019. No occurrence obstructions in geometric complexity theory. Journal of the AMS 32, 1 (2019), 163\u2013193.","journal-title":"Journal of the AMS"},{"issue":"4","key":"e_1_3_2_14_2","doi-asserted-by":"crossref","first-page":"1179","DOI":"10.1137\/090765328","article-title":"An overview of mathematical issues arising in the geometric complexity theory approach to VP \\(\\ne\\) VNP","volume":"40","author":"B\u00fcrgisser Peter","year":"2011","unstructured":"Peter B\u00fcrgisser, Joseph M. Landsberg, Laurent Manivel, and Jerzy Weyman. 2011. An overview of mathematical issues arising in the geometric complexity theory approach to VP \\(\\ne\\) VNP. SIAM Journal on Computing 40, 4 (2011), 1179\u20131209.","journal-title":"SIAM Journal on Computing"},{"issue":"1","key":"e_1_3_2_15_2","doi-asserted-by":"crossref","first-page":"69","DOI":"10.1016\/S0012-365X(00)00260-0","article-title":"Thomason\u2019s algorithm for finding a second Hamiltonian circuit through a given edge in a cubic graph is exponential on Krawczyk\u2019s graphs","volume":"235","author":"Cameron Kathie","year":"2001","unstructured":"Kathie Cameron. 2001. Thomason\u2019s algorithm for finding a second Hamiltonian circuit through a given edge in a cubic graph is exponential on Krawczyk\u2019s graphs. Discrete Mathematics 235, 1\u20133 (2001), 69\u201377.","journal-title":"Discrete Mathematics"},{"key":"e_1_3_2_16_2","first-page":"815","volume-title":"Annales de l\u2019institut Fourier","author":"Cameron Kathie","year":"1999","unstructured":"Kathie Cameron and Jack Edmonds. 1999. Some graphic uses of an even number of odd nodes. Annales de l\u2019institut Fourier 49, 3 (1999), 815\u2013827."},{"key":"e_1_3_2_17_2","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9781139192361","volume-title":"Representation Theory of the Symmetric Groups: The Okounkov-Vershik Approach, Character Formulas, and Partition Algebras","author":"Ceccherini-Silberstein Tullio","year":"2010","unstructured":"Tullio Ceccherini-Silberstein, Fabio Scarabotti, and Filippo Tolli. 2010. Representation Theory of the Symmetric Groups: The Okounkov-Vershik Approach, Character Formulas, and Partition Algebras. Vol. 121. Cambridge University Press."},{"key":"e_1_3_2_18_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00220-014-2144-4"},{"key":"e_1_3_2_19_2","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2012.43"},{"issue":"11","key":"e_1_3_2_20_2","doi-asserted-by":"crossref","first-page":"8013","DOI":"10.1090\/tran\/8481","article-title":"Plethysms of symmetric functions and highest weight representations","volume":"374","author":"Boeck Melanie de","year":"2021","unstructured":"Melanie de Boeck, Rowena Paget, and Mark Wildon. 2021. Plethysms of symmetric functions and highest weight representations. Transactions of the AMS 374, 11 (2021), 8013\u20138043.","journal-title":"Transactions of the AMS"},{"issue":"2","key":"e_1_3_2_21_2","doi-asserted-by":"crossref","first-page":"354","DOI":"10.1137\/19M1287638","article-title":"On geometric complexity theory: Multiplicity obstructions are stronger than occurrence obstructions","volume":"4","author":"D\u00f6rfler Julian","year":"2020","unstructured":"Julian D\u00f6rfler, Christian Ikenmeyer, and Greta Panova. 2020. On geometric complexity theory: Multiplicity obstructions are stronger than occurrence obstructions. SIAM Journal on Applied Algebra and Geometry 4, 2 (2020), 354\u2013376.","journal-title":"SIAM Journal on Applied Algebra and Geometry"},{"key":"e_1_3_2_22_2","first-page":"1","article-title":"The computational complexity of plethysm coefficients","volume":"29","author":"Fischer Nick","year":"2020","unstructured":"Nick Fischer and Christian Ikenmeyer. 2020. The computational complexity of plethysm coefficients. Computational Complexity 29 (2020), 1\u201343.","journal-title":"Computational Complexity"},{"key":"e_1_3_2_23_2","series-title":"London Mathematical Society Student Texts","volume-title":"Young Tableaux: With Applications to Representation Theory and Geometry","author":"Fulton William","year":"1997","unstructured":"William Fulton. 1997. Young Tableaux: With Applications to Representation Theory and Geometry. Number 35 in London Mathematical Society Student Texts. Cambridge University Press."},{"key":"e_1_3_2_24_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-0-387-79852-3"},{"key":"e_1_3_2_25_2","volume-title":"Geometric Complexity Theory, Tensor Rank, and Littlewood-Richardson Coefficients","author":"Ikenmeyer Christian","year":"2012","unstructured":"Christian Ikenmeyer. 2012. Geometric Complexity Theory, Tensor Rank, and Littlewood-Richardson Coefficients. Ph.D. Dissertation. Paderborn, Universit\u00e4t Paderborn, Diss., 2012."},{"key":"e_1_3_2_26_2","doi-asserted-by":"publisher","DOI":"10.1145\/3357713.3384257"},{"key":"e_1_3_2_27_2","doi-asserted-by":"publisher","DOI":"10.1007\/s00037-017-0158-y"},{"key":"e_1_3_2_28_2","doi-asserted-by":"crossref","first-page":"860","DOI":"10.1109\/FOCS54457.2022.00087","volume-title":"Proceedings of the 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science","author":"Ikenmeyer Christian","year":"2022","unstructured":"Christian Ikenmeyer and Igor Pak. 2022. What is in #P and what is not?. In Proceedings of the 2022 IEEE 63rd Annual Symposium on Foundations of Computer Science. 860\u2013871."},{"key":"e_1_3_2_29_2","doi-asserted-by":"crossref","first-page":"3573","DOI":"10.1137\/1.9781611977554.ch136","volume-title":"Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms","author":"Ikenmeyer Christian","year":"2023","unstructured":"Christian Ikenmeyer, Igor Pak, and Greta Panova. 2023. Positivity of the symmetric group characters is as hard as the polynomial time hierarchy. In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms. SIAM, 3573\u20133586."},{"key":"e_1_3_2_30_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.aim.2017.08.024"},{"key":"e_1_3_2_31_2","doi-asserted-by":"publisher","DOI":"10.5555\/2230996.2231003"},{"key":"e_1_3_2_32_2","doi-asserted-by":"publisher","DOI":"10.1007\/s10208-015-9275-7"},{"key":"e_1_3_2_33_2","doi-asserted-by":"publisher","unstructured":"Alexander Klyachko. 2004. Quantum marginal problem and representations of the symmetric group. arXiv:quant-ph\/0409113. Retrieved from https:\/\/arxiv.org\/abs\/0409113. DOI:DOI:10.48550\/ARXIV.QUANT-PH\/0409113","DOI":"10.48550\/ARXIV.QUANT-PH\/0409113"},{"key":"e_1_3_2_34_2","doi-asserted-by":"crossref","first-page":"189","DOI":"10.1007\/978-3-540-24587-2_21","volume-title":"Proceedings of the International Symposium on Algorithms and Computation","volume":"2906","author":"Kobayashi Hirotada","year":"2003","unstructured":"Hirotada Kobayashi, Keiji Matsumoto, and Tomoyuki Yamakami. 2003. Quantum Merlin-Arthur proof systems: Are multiple Merlins more helpful to Arthur?. In Proceedings of the International Symposium on Algorithms and Computation, Vol. 2906. Springer, 189\u2013198."},{"key":"e_1_3_2_35_2","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1998.1611"},{"issue":"2","key":"e_1_3_2_36_2","doi-asserted-by":"crossref","first-page":"292","DOI":"10.1112\/S0010437X14007660","article-title":"A study of the representations supported by the orbit closure of the determinant","volume":"151","author":"Kumar Shrawan","year":"2015","unstructured":"Shrawan Kumar. 2015. A study of the representations supported by the orbit closure of the determinant. Compositio Mathematica 151, 2 (2015), 292\u2013312.","journal-title":"Compositio Mathematica"},{"issue":"9","key":"e_1_3_2_37_2","doi-asserted-by":"crossref","first-page":"3657","DOI":"10.1090\/proc\/13692","article-title":"A simplified Kronecker rule for one hook shape","volume":"145","author":"Liu Ricky Ini","year":"2017","unstructured":"Ricky Ini Liu. 2017. A simplified Kronecker rule for one hook shape. Proceedings of the AMS 145, 9 (2017), 3657\u20133664.","journal-title":"Proceedings of the AMS"},{"key":"e_1_3_2_38_2","doi-asserted-by":"publisher","DOI":"10.1145\/1198513.1198525"},{"key":"e_1_3_2_39_2","doi-asserted-by":"publisher","DOI":"10.1137\/S009753970038715X"},{"key":"e_1_3_2_40_2","doi-asserted-by":"publisher","DOI":"10.1137\/080718115"},{"key":"e_1_3_2_41_2","unstructured":"Anand Natarajan and Chinmay Nirkhe. 2023. A randomized classical oracle separating QMA and QCMA. (2023). To appear in the Proceedings of the Computational Complexity Conference (CCC 2023)."},{"key":"e_1_3_2_42_2","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511976667"},{"issue":"5","key":"e_1_3_2_43_2","doi-asserted-by":"crossref","first-page":"1153","DOI":"10.1112\/plms.12210","article-title":"Generalized Foulkes modules and maximal and minimal constituents of plethysms of Schur functions","volume":"118","author":"Paget Rowena","year":"2019","unstructured":"Rowena Paget and Mark Wildon. 2019. Generalized Foulkes modules and maximal and minimal constituents of plethysms of Schur functions. Proceedings of the London Mathematical Society 118, 5 (2019), 1153\u20131187.","journal-title":"Proceedings of the London Mathematical Society"},{"key":"e_1_3_2_44_2","unstructured":"Igor Pak. 2022. What is a combinatorial interpretation?arXiv:2209.06142. Retrieved from https:\/\/arxiv.org\/abs\/2209.06142"},{"key":"e_1_3_2_45_2","doi-asserted-by":"crossref","unstructured":"Greta Panova. 2023. Complexity and asymptotics of structure constants. Proceedings of Symposia in Pure Mathematics 110 (2024) 371.","DOI":"10.1090\/pspum\/110\/02016"},{"key":"e_1_3_2_46_2","doi-asserted-by":"publisher","unstructured":"Greta Panova. 2023. Computational complexity in algebraic combinatorics. Current Developments in Mathematics 2024 1 (2024) 241\u2013280. DOI:10.4310\/CDM.250429173831","DOI":"10.4310\/CDM.250429173831"},{"issue":"2","key":"e_1_3_2_47_2","doi-asserted-by":"crossref","first-page":"193","DOI":"10.1112\/jlms\/s2-15.2.193","article-title":"A topological transformation algorithm which relates the Hamiltonian circuits of a cubic planar map","volume":"2","author":"Price W. L.","year":"1977","unstructured":"W. L. Price. 1977. A topological transformation algorithm which relates the Hamiltonian circuits of a cubic planar map. Journal of the London Mathematical Society 2, 2 (1977), 193\u2013196.","journal-title":"Journal of the London Mathematical Society"},{"issue":"1","key":"e_1_3_2_48_2","doi-asserted-by":"crossref","first-page":"100","DOI":"10.1016\/0021-8693(89)90191-9","article-title":"A formula for the Kronecker products of Schur functions of hook shapes","volume":"120","author":"Remmel Jeffrey","year":"1989","unstructured":"Jeffrey Remmel. 1989. A formula for the Kronecker products of Schur functions of hook shapes. Journal of Algebra 120, 1 (1989), 100\u2013118.","journal-title":"Journal of Algebra"},{"issue":"5","key":"e_1_3_2_49_2","first-page":"649","article-title":"On the Kronecker product of Schur functions of two row shapes","volume":"1","author":"Remmel Jeffrey","year":"1994","unstructured":"Jeffrey Remmel and Tamsen Whitehead. 1994. On the Kronecker product of Schur functions of two row shapes. Bulletin of the Belgian Mathematical Society-Simon Stevin 1, 5 (1994), 649\u2013683.","journal-title":"Bulletin of the Belgian Mathematical Society-Simon Stevin"},{"key":"e_1_3_2_50_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4757-6804-6"},{"key":"e_1_3_2_51_2","article-title":"Note on quantum counting classes","author":"Shi Yaoyun","year":"2009","unstructured":"Yaoyun Shi and Shengyu Zhang. 2009. Note on quantum counting classes. Available from Shengyu Zhang\u2019s Homepage (2009). Retrieved 03 September 2025 from http:\/\/www.cse.cuhk.edu.hk\/syzhang\/papers\/SharpBQP.pdf","journal-title":"Available from Shengyu Zhang\u2019s Homepage"},{"key":"e_1_3_2_52_2","first-page":"295","article-title":"Positivity problems and conjectures in algebraic","author":"Stanley Richard P.","year":"2000","unstructured":"Richard P. Stanley. 2000. Positivity problems and conjectures in algebraic. Mathematics: Frontiers and Perspectives: Frontiers and Perspectives (2000), 295.","journal-title":"Mathematics: Frontiers and Perspectives: Frontiers and Perspectives"},{"key":"e_1_3_2_53_2","unstructured":"Catharina Stroppel. 2022. The Beauty of Braids. (2022). Plenary talk at the ICM 2022. Retrieved 03 September 2025 from http:\/\/www.math.uni-bonn.de\/ag\/stroppel\/TheBeautyofBraids_ICMVortragStroppel.pdf"},{"key":"e_1_3_2_54_2","doi-asserted-by":"publisher","DOI":"10.1016\/j.jalgebra.2015.01.018"},{"key":"e_1_3_2_55_2","first-page":"259","volume-title":"Annals of Discrete Mathematics","author":"Thomason Andrew G.","year":"1978","unstructured":"Andrew G. Thomason. 1978. Hamiltonian cycles and uniquely edge colourable graphs. In Annals of Discrete Mathematics, B\u00e9la Bollob\u00e1s (Ed.). Vol. 3, Elsevier, 259\u2013268."},{"issue":"2","key":"e_1_3_2_56_2","doi-asserted-by":"crossref","first-page":"98","DOI":"10.1112\/jlms\/s1-21.2.98","article-title":"On Hamiltonian circuits","volume":"1","author":"Tutte William T.","year":"1946","unstructured":"William T. Tutte. 1946. On Hamiltonian circuits. Journal of the London Mathematical Society 1, 2 (1946), 98\u2013101.","journal-title":"Journal of the London Mathematical Society"},{"key":"e_1_3_2_57_2","unstructured":"Michael Walter. 2015. On the computational complexity of the membership problem for moment polytopes. (2015). Talk at the Simons Reunion Workshop for the program \u201cAlgorithms and Complexity in Algebraic Geometry\u201d mentions an unpublished work by Harrow-Christandl-Walter containing \\({{\\rm K}{\\rm\\small{RON}}}\\in {{\\bf \\#BQP}}\\) . Retrieved 03 September 2025 from https:\/\/qi.rub.de\/talks\/momenttalk_simons.pdf"}],"container-title":["ACM Transactions on Quantum Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3762673","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,10,28]],"date-time":"2025-10-28T13:12:28Z","timestamp":1761657148000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3762673"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,10,28]]},"references-count":56,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2025,12,31]]}},"alternative-id":["10.1145\/3762673"],"URL":"https:\/\/doi.org\/10.1145\/3762673","relation":{},"ISSN":["2643-6809","2643-6817"],"issn-type":[{"type":"print","value":"2643-6809"},{"type":"electronic","value":"2643-6817"}],"subject":[],"published":{"date-parts":[[2025,10,28]]},"assertion":[{"value":"2025-04-15","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-07-28","order":2,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2025-10-28","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}