{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T18:56:48Z","timestamp":1781031408548,"version":"3.54.1"},"publisher-location":"New York, NY, USA","reference-count":66,"publisher":"ACM","license":[{"start":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T00:00:00Z","timestamp":1780963200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/legalcode"}],"funder":[{"name":"Google PhD fellowship","award":["N\/A"],"award-info":[{"award-number":["N\/A"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2026,6,9]]},"DOI":"10.1145\/3798129.3800788","type":"proceedings-article","created":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T17:53:56Z","timestamp":1781027636000},"page":"734-743","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Quantum Circuit Lower Bounds in the Magic Hierarchy"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-8792-1229","authenticated-orcid":false,"given":"Natalie","family":"Parham","sequence":"first","affiliation":[{"name":"Columbia University, New York, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2026,6,9]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1098\/rspa.2005.1546"},{"key":"e_1_3_2_1_2_1","volume-title":"Improved simulation of stabilizer circuits. Physical Review A\u2014Atomic, Molecular, and Optical Physics, 70, 5","author":"Aaronson Scott","year":"2004","unstructured":"Scott Aaronson and Daniel Gottesman. 2004. Improved simulation of stabilizer circuits. Physical Review A\u2014Atomic, Molecular, and Optical Physics, 70, 5 (2004), 052328."},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2491533.2491549"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2013.2244643"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"crossref","unstructured":"Faidon Andreadakis and Paolo Zanardi. 2025. An Exact Link between Nonlocal Magic and Operator Entanglement. arXiv preprint arXiv:2504.09360.","DOI":"10.1103\/9x56-2b45"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/3564246.3585114"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"crossref","unstructured":"Anurag Anshu Yangjing Dong Fengning Ou and Penghui Yao. 2024. On the Computational Power of QAC0 with Barely Superlinear Ancillae. arXiv preprint arXiv:2410.06499.","DOI":"10.1145\/3717823.3718189"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1754399.1754401"},{"key":"e_1_3_2_1_9_1","volume-title":"Improved classical simulation of quantum circuits dominated by Clifford gates. Physical review letters, 116, 25","author":"Bravyi Sergey","year":"2016","unstructured":"Sergey Bravyi and David Gosset. 2016. Improved classical simulation of quantum circuits dominated by Clifford gates. Physical review letters, 116, 25 (2016), 250501."},{"key":"e_1_3_2_1_10_1","volume-title":"Lieb-Robinson bounds and the generation of correlations and topological quantum order. Physical review letters, 97, 5","author":"Bravyi Sergey","year":"2006","unstructured":"Sergey Bravyi, Matthew B Hastings, and Frank Verstraete. 2006. Lieb-Robinson bounds and the generation of correlations and topological quantum order. Physical review letters, 97, 5 (2006), 050401."},{"key":"e_1_3_2_1_11_1","unstructured":"Sergey Bravyi Isaac Kim Alexander Kliesch and Robert Koenig. 2022. Adaptive constant-depth circuits for manipulating non-abelian anyons. arXiv preprint arXiv:2205.01933."},{"key":"e_1_3_2_1_12_1","volume-title":"Tradeoffs for reliable quantum information storage in 2D systems. Physical review letters, 104, 5","author":"Bravyi Sergey","year":"2010","unstructured":"Sergey Bravyi, David Poulin, and Barbara Terhal. 2010. Tradeoffs for reliable quantum information storage in 2D systems. Physical review letters, 104, 5 (2010), 050503."},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.22331\/q-2024-12-09-1552"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.5555\/2982445.2982455"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2019.v015a010"},{"key":"e_1_3_2_1_16_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_17_1","volume-title":"Local unitary transformation, long-range quantum entanglement, wave function renormalization, and topological order. Physical Review B\u2014Condensed Matter and Materials Physics, 82, 15","author":"Chen Xie","year":"2010","unstructured":"Xie Chen, Zheng-Cheng Gu, and Xiao-Gang Wen. 2010. Local unitary transformation, long-range quantum entanglement, wave function renormalization, and topological order. Physical Review B\u2014Condensed Matter and Materials Physics, 82, 15 (2010), 155138."},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.5555\/795666.796591"},{"key":"e_1_3_2_1_19_1","unstructured":"Nolan J Coble Matthew Coudron Jon Nelson and Seyed Sajjad Nezhadi. 2023. Local hamiltonians with no low-energy stabilizer states. arXiv preprint arXiv:2302.14755."},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.22331\/q-2019-08-12-174"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.22331\/q-2020-09-24-331"},{"key":"e_1_3_2_1_22_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_23_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_24_1","unstructured":"Stephen Fenner Daniel Grier Daniel Pad\u00e9 and Thomas Thierauf. 2025. Tight bounds on depth-2 QAC-circuits computing parity. arxiv:2504.06433. arxiv:2504.06433"},{"key":"e_1_3_2_1_25_1","unstructured":"Michael H Freedman and Matthew B Hastings. 2013. Quantum systems on non- k -hyperfinite complexes: A generalization of classical statistical mechanics on expander graphs. arXiv preprint arXiv:1301.1363."},{"key":"e_1_3_2_1_26_1","volume-title":"circuits, and the polynomial-time hierarchy. Mathematical systems theory, 17, 1","author":"Furst Merrick","year":"1984","unstructured":"Merrick Furst, James B Saxe, and Michael Sipser. 1984. Parity, circuits, and the polynomial-time hierarchy. Mathematical systems theory, 17, 1 (1984), 13\u201327."},{"key":"e_1_3_2_1_27_1","unstructured":"Craig Gidney and Thiago Bergamaschi. 2025. A Constant Rate Quantum Computer on a Line. arXiv preprint arXiv:2502.16132."},{"key":"e_1_3_2_1_28_1","volume-title":"Computational limitations for small depth circuits. Ph. D. Dissertation","author":"H\u00e5stad Johan","unstructured":"Johan H\u00e5stad. 1986. Computational limitations for small depth circuits. Ph. D. Dissertation. Massachusetts Institute of Technology."},{"key":"e_1_3_2_1_29_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_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/3618260.3649722"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1137\/060649057"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"crossref","unstructured":"David Aram Korbany Michael J Gullans and Lorenzo Piroli. 2025. Long-range nonstabilizerness and phases of matter. arXiv preprint arXiv:2502.19504.","DOI":"10.1103\/1hlj-h6t9"},{"key":"e_1_3_2_1_33_1","volume-title":"Pseudorandom functions in and cryptographic limitations to proving lower bounds. computational complexity, 10, 4","author":"Krause Matthias","year":"2001","unstructured":"Matthias Krause and Stefan Lucks. 2001. Pseudorandom functions in and cryptographic limitations to proving lower bounds. computational complexity, 10, 4 (2001), 297\u2013313."},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1137\/0222080"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevB.108.115144"},{"key":"e_1_3_2_1_36_1","volume-title":"The finite group velocity of quantum spin systems. Communications in mathematical physics, 28, 3","author":"Lieb Elliott H","year":"1972","unstructured":"Elliott H Lieb and Derek W Robinson. 1972. The finite group velocity of quantum spin systems. Communications in mathematical physics, 28, 3 (1972), 251\u2013257."},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/174130.174138"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1103\/PRXQuantum.3.040337"},{"key":"e_1_3_2_1_39_1","unstructured":"Cristopher Moore. 1999. Quantum circuits: Fanout parity and counting. arXiv preprint quant-ph\/9903046."},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/3618260.3649662"},{"key":"e_1_3_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1145\/972639.972643"},{"key":"e_1_3_2_1_42_1","volume-title":"Lower bounds on the complexity of quantum proofs","author":"Nirkhe Chinmay","unstructured":"Chinmay Nirkhe. 2022. Lower bounds on the complexity of quantum proofs. University of California, Berkeley."},{"key":"e_1_3_2_1_43_1","unstructured":"Chinmay Nirkhe. 2023. Making the Leap to Quantum PCPs. https:\/\/simons.berkeley.edu\/talks\/chinmay-nirkhe-ibm-2023-07-12"},{"key":"e_1_3_2_1_44_1","unstructured":"Igor C Oliveira and Rahul Santhanam. 2016. Conspiracies between learning algorithms circuit lower bounds and pseudorandomness. arXiv preprint arXiv:1611.01190."},{"key":"e_1_3_2_1_45_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_46_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.127.220503"},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.133.230401"},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1145\/3530258"},{"key":"e_1_3_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/195058.195134"},{"key":"e_1_3_2_1_50_1","volume-title":"12th Innovations in Theoretical Computer Science Conference (ITCS","author":"Rosenthal Gregory","year":"2021","unstructured":"Gregory Rosenthal. 2021. Bounds on the QAC^0 Complexity of Approximating Parity. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)."},{"key":"e_1_3_2_1_51_1","volume-title":"Quantum State and Unitary Complexity. Ph. D. Dissertation","author":"Rosenthal Gregory","unstructured":"Gregory Rosenthal. 2023. Quantum State and Unitary Complexity. Ph. D. Dissertation. University of Toronto (Canada)."},{"key":"e_1_3_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977912.89"},{"key":"e_1_3_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2015.67"},{"key":"e_1_3_2_1_54_1","article-title":"Quantum error correction thresholds for the universal Fibonacci Turaev-Viro code","author":"Schotte Alexis","year":"2022","unstructured":"Alexis Schotte, Guanyu Zhu, Lander Burgelman, and Frank Verstraete. 2022. Quantum error correction thresholds for the universal Fibonacci Turaev-Viro code. Physical Review X, 12, 2 (2022), 021012.","journal-title":"Physical Review"},{"key":"e_1_3_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevB.111.115160"},{"key":"e_1_3_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1103\/PRXQuantum.5.030344"},{"key":"e_1_3_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1145\/28395.28404"},{"key":"e_1_3_2_1_58_1","volume-title":"Collapse of the hierarchy of constant-depth exact quantum circuits. computational complexity, 25","author":"Takahashi Yasuhiro","year":"2016","unstructured":"Yasuhiro Takahashi and Seiichiro Tani. 2016. Collapse of the hierarchy of constant-depth exact quantum circuits. computational complexity, 25 (2016), 849\u2013881."},{"key":"e_1_3_2_1_59_1","article-title":"Long-range entanglement from measuring symmetry-protected topological phases","author":"Tantivasadakarn Nathanan","year":"2024","unstructured":"Nathanan Tantivasadakarn, Ryan Thorngren, Ashvin Vishwanath, and Ruben Verresen. 2024. Long-range entanglement from measuring symmetry-protected topological phases. Physical Review X, 14, 2 (2024), 021040.","journal-title":"Physical Review"},{"key":"e_1_3_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.131.060405"},{"key":"e_1_3_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1103\/PRXQuantum.4.020339"},{"key":"e_1_3_2_1_62_1","unstructured":"Barbara M Terhal and David P DiVincenzo. 2002. Adaptive quantum computation constant depth quantum circuits and Arthur-Merlin games. arXiv preprint quant-ph\/0205133."},{"key":"e_1_3_2_1_63_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_64_1","doi-asserted-by":"publisher","DOI":"10.22331\/q-2022-09-22-815"},{"key":"e_1_3_2_1_65_1","unstructured":"Fuchuan Wei and Zi-Wen Liu. 2025. Long-range nonstabilizerness from topology and correlation. arXiv preprint arXiv:2503.04566."},{"key":"e_1_3_2_1_66_1","volume-title":"Classical Simulability of Quantum Circuits with Shallow Magic Depth. ArXiv, abs\/2409.13809","author":"Zhang Yifan","year":"2024","unstructured":"Yifan Zhang and Yuxuan Zhang. 2024. Classical Simulability of Quantum Circuits with Shallow Magic Depth. ArXiv, abs\/2409.13809 (2024), https:\/\/api.semanticscholar.org\/CorpusID:272827863"}],"event":{"name":"STOC '26: 58th Annual ACM Symposium on Theory of Computing","location":"Salt Lake City UT USA","acronym":"STOC '26","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 58th Annual ACM Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3798129.3800788","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T17:56:43Z","timestamp":1781027803000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3798129.3800788"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,6,9]]},"references-count":66,"alternative-id":["10.1145\/3798129.3800788","10.1145\/3798129"],"URL":"https:\/\/doi.org\/10.1145\/3798129.3800788","relation":{},"subject":[],"published":{"date-parts":[[2026,6,9]]},"assertion":[{"value":"2026-06-09","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}