{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:48:51Z","timestamp":1781077731202,"version":"3.54.1"},"publisher-location":"New York, NY, USA","reference-count":52,"publisher":"ACM","license":[{"start":{"date-parts":[[2024,6,10]],"date-time":"2024-06-10T00:00:00Z","timestamp":1717977600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"NSF","award":["IIS-1838154, CCF-2106429, CCF-2211238, CCF-1763970, and CCF-2107187, DGE-2146752"],"award-info":[{"award-number":["IIS-1838154, CCF-2106429, CCF-2211238, CCF-1763970, and CCF-2107187, DGE-2146752"]}]},{"name":"NSF (National Science Foundation)","award":["CAREER award CCF-2144219"],"award-info":[{"award-number":["CAREER award CCF-2144219"]}]},{"name":"Sloan Foundation","award":[""],"award-info":[{"award-number":[""]}]},{"name":"AFOSR","award":["FA9550-21-1-0040"],"award-info":[{"award-number":["FA9550-21-1-0040"]}]},{"name":"Vannevar Bush Faculty Fellowship Program","award":["N00014-21-1-2941"],"award-info":[{"award-number":["N00014-21-1-2941"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2024,6,10]]},"DOI":"10.1145\/3618260.3649662","type":"proceedings-article","created":{"date-parts":[[2024,6,11]],"date-time":"2024-06-11T19:25:02Z","timestamp":1718133902000},"page":"1498-1506","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":13,"title":["On the Pauli Spectrum of QAC0"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-1825-6122","authenticated-orcid":false,"given":"Shivam","family":"Nadimpalli","sequence":"first","affiliation":[{"name":"Columbia University, New York, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-8792-1229","authenticated-orcid":false,"given":"Natalie","family":"Parham","sequence":"additional","affiliation":[{"name":"Columbia University, New York, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4758-2944","authenticated-orcid":false,"given":"Francisca","family":"Vasconcelos","sequence":"additional","affiliation":[{"name":"University of California, Berkeley, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2684-1129","authenticated-orcid":false,"given":"Henry","family":"Yuen","sequence":"additional","affiliation":[{"name":"Columbia University, New York, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2024,6,11]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/3564246.3585234"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/3564246.3585114"},{"key":"e_1_3_2_1_3_1","unstructured":"Zongbo Bao and Penghui Yao. 2023. Nearly Optimal Algorithms for Testing and Learning Quantum Junta Channels. arXiv preprint arXiv:2305.12097."},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1272729.1272739"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1536414.1536437"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1038\/s41586-022-04592-6"},{"key":"e_1_3_2_1_7_1","volume-title":"The average sensitivity of bounded-depth circuits. Information processing letters, 63, 5","author":"Boppana Ravi B","year":"1997","unstructured":"Ravi B Boppana. 1997. The average sensitivity of bounded-depth circuits. Information processing letters, 63, 5 (1997), 257\u2013261."},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/CCC.2009.35"},{"key":"e_1_3_2_1_9_1","unstructured":"Matthias C. Caro. 2023. Learning Quantum Processes and Hamiltonians via the Pauli Transfer Matrix. arxiv:2212.04471."},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2019.v015a010"},{"key":"e_1_3_2_1_11_1","volume-title":"10th Innovations in Theoretical Computer Science Conference (ITCS","author":"Chattopadhyay Eshan","year":"2018","unstructured":"Eshan Chattopadhyay, Pooya Hatami, Shachar Lovett, and Avishay Tal. 2018. Pseudorandom generators from the second Fourier level and applications to AC0 with parity gates. In 10th Innovations in Theoretical Computer Science Conference (ITCS 2019)."},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS52979.2021.00063"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977554.ch43"},{"key":"e_1_3_2_1_14_1","volume-title":"Local Hamiltonians whose ground states are hard to approximate. In 2017 IEEE 58th annual symposium on foundations of computer science (FOCS). 427\u2013438","author":"Eldar Lior","unstructured":"Lior Eldar and Aram W Harrow. 2017. Local Hamiltonians whose ground states are hard to approximate. In 2017 IEEE 58th annual symposium on foundations of computer science (FOCS). 427\u2013438."},{"key":"e_1_3_2_1_15_1","unstructured":"Alexandros Eskenazis Paata Ivanisvili and Lauritz Streck. 2022. Low-degree learning and the metric entropy of polynomials. arXiv preprint arXiv:2203.09659."},{"key":"e_1_3_2_1_16_1","unstructured":"Maosen Fang Stephen Fenner Frederic Green Steven Homer and Yong Zhang. 2003. Quantum lower bounds for fanout. arXiv preprint quant-ph\/0312208."},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/509907.509977"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01744431"},{"key":"e_1_3_2_1_19_1","volume-title":"Noise sensitivity of Boolean functions and percolation. 5","author":"Garban Christophe","unstructured":"Christophe Garban and Jeffrey E Steif. 2014. Noise sensitivity of Boolean functions and percolation. 5, Cambridge University Press."},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/QCE52317.2021.00045"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevResearch.4.L042016"},{"key":"e_1_3_2_1_22_1","volume-title":"Computational Limitations for Small Depth Circuits","author":"H\u00e5stad J.","unstructured":"J. H\u00e5stad. 1986. Computational Limitations for Small Depth Circuits. MIT Press, Cambridge, MA."},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.2001.1803"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1137\/120897432"},{"key":"e_1_3_2_1_25_1","volume-title":"Quantum fan-out is powerful. Theory of computing, 1, 1","author":"H\u00f8yer Peter","year":"2005","unstructured":"Peter H\u00f8yer and Robert \u0160palek. 2005. Quantum fan-out is powerful. Theory of computing, 1, 1 (2005), 81\u2013103."},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"crossref","unstructured":"Hsin-Yuan Huang Sitan Chen and John Preskill. 2022. Learning to predict arbitrary quantum processes. arXiv preprint arXiv:2210.14894.","DOI":"10.1103\/PRXQuantum.4.040337"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1038\/s41567-020-0932-7"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973099.77"},{"key":"e_1_3_2_1_29_1","volume-title":"Proceedings of the 46th IEEE Symposium on Foundations of Computer Science (FOCS). 11\u201320","author":"Kalai A.","unstructured":"A. Kalai, A. Klivans, Y. Mansour, and R. Servedio. 2005. Agnostically Learning Halfspaces. In Proceedings of the 46th IEEE Symposium on Foundations of Computer Science (FOCS). 11\u201320."},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/167088.167197"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1137\/16M1065872"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1137\/0222080"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/174130.174138"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","unstructured":"M. Mohseni A. T. Rezakhani and D. A. Lidar. 2008. Quantum-process tomography: Resource analysis of different strategies. Phys. Rev. A 77 (2008) Mar 032322. https:\/\/doi.org\/10.1103\/PhysRevA.77.032322 10.1103\/PhysRevA.77.032322","DOI":"10.1103\/PhysRevA.77.032322"},{"key":"e_1_3_2_1_35_1","unstructured":"Ashley Montanaro and Tobias J Osborne. 2008. Quantum boolean functions. arXiv preprint arXiv:0810.2435."},{"key":"e_1_3_2_1_36_1","unstructured":"Cristopher Moore. 1999. Quantum circuits: Fanout parity and counting. arXiv preprint quant-ph\/9903046."},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(05)80043-1"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1017\/cbo9781139814782.013"},{"key":"e_1_3_2_1_39_1","unstructured":"Daniel Pad\u00e9 Stephen Fenner Daniel Grier and Thomas Thierauf. 2020. Depth-2 QAC circuits cannot simulate quantum parity. arXiv preprint arXiv:2005.12169."},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/3530258"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01137685"},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ITCS.2021.32"},{"key":"e_1_3_2_1_43_1","unstructured":"Cambyse Rouz\u00e9 Melchior Wirth and Haonan Zhang. 2022. Quantum Talagrand KKL and Friedgut\u2019s theorems and the learnability of quantum Boolean functions. arXiv preprint arXiv:2209.07279."},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevApplied.17.014014"},{"key":"e_1_3_2_1_45_1","volume-title":"15th Innovations in Theoretical Computer Science Conference (ITCS","author":"Slote Joseph","year":"2024","unstructured":"Joseph Slote. 2024. Parity vs. AC0 with simple quantum preprocessing. In 15th Innovations in Theoretical Computer Science Conference (ITCS 2024)."},{"key":"e_1_3_2_1_46_1","unstructured":"Joseph Slote Alexander Volberg and Haonan Zhang. 2023. Noncommutative Bohnenblust-Hille inequality in the Heisenberg-Weyl and Gell-Mann bases with applications to fast learning. arXiv preprint arXiv:2301.01438."},{"key":"e_1_3_2_1_47_1","volume-title":"Parallel Distributed Processing: Volume 1: Foundations, D","author":"Smolensky P.","unstructured":"P. Smolensky. 1987. Information Processing in Dynamical Systems: Foundations of Harmony Theory. In Parallel Distributed Processing: Volume 1: Foundations, D. E. Rumelhart and J. L. McClelland (Eds.). MIT Press, Cambridge. 194\u2013281."},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.5555\/3135595.3135610"},{"key":"e_1_3_2_1_49_1","unstructured":"Ruben Verresen Nathanan Tantivasadakarn and Ashvin Vishwanath. 2021. Efficiently preparing Schr\u00f6dinger\u2019s cat fractons and non-Abelian topological order in quantum devices. arXiv preprint arXiv:2112.03061."},{"key":"e_1_3_2_1_50_1","first-page":"1","article-title":"Noncommutative Bohnenblust\u2013Hille inequalities","author":"Volberg Alexander","year":"2023","unstructured":"Alexander Volberg and Haonan Zhang. 2023. Noncommutative Bohnenblust\u2013Hille inequalities. Math. Ann., 1\u201320.","journal-title":"Math. Ann."},{"key":"e_1_3_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevA.84.052328"},{"key":"e_1_3_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1985.49"}],"event":{"name":"STOC '24: 56th Annual ACM Symposium on Theory of Computing","location":"Vancouver BC Canada","acronym":"STOC '24","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 56th Annual ACM Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3618260.3649662","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3618260.3649662","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T00:03:51Z","timestamp":1750291431000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3618260.3649662"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2024,6,10]]},"references-count":52,"alternative-id":["10.1145\/3618260.3649662","10.1145\/3618260"],"URL":"https:\/\/doi.org\/10.1145\/3618260.3649662","relation":{},"subject":[],"published":{"date-parts":[[2024,6,10]]},"assertion":[{"value":"2024-06-11","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}