{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T18:57:45Z","timestamp":1781031465429,"version":"3.54.1"},"publisher-location":"New York, NY, USA","reference-count":33,"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"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2026,6,9]]},"DOI":"10.1145\/3798129.3800820","type":"proceedings-article","created":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T17:53:56Z","timestamp":1781027636000},"page":"1085-1091","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Quantum Precomputation: Parallelizing Cascade Circuits and the Moore\u2013Nilsson Conjecture Is False"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-3289-3339","authenticated-orcid":false,"given":"Adam","family":"Bene Watts","sequence":"first","affiliation":[{"name":"University of Calgary, Calgary, Canada"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0005-6988-8006","authenticated-orcid":false,"given":"Charles R.","family":"Chen","sequence":"additional","affiliation":[{"name":"University of California at San Diego, San Diego, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7716-3903","authenticated-orcid":false,"given":"J. William","family":"Helton","sequence":"additional","affiliation":[{"name":"University of California at San Diego, San Diego, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-6363-7821","authenticated-orcid":false,"given":"Joseph","family":"Slote","sequence":"additional","affiliation":[{"name":"University of Washington, Seattle, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2026,6,9]]},"reference":[{"key":"e_1_3_2_1_1_1","first-page":"1209","article-title":"On economical construction of the transitive closure of a directed graph","volume":"194","author":"Arlazarov Vladimir L","year":"1970","unstructured":"Vladimir L Arlazarov, E. A. Dini\u010d, M. A. Kronrod, and IA Farad\u017eev. 1970. On economical construction of the transitive closure of a directed graph. In Dokl. Akad. Nauk SSSR. 194, 1209\u20131210.","journal-title":"Dokl. Akad. Nauk SSSR."},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/3564246.3585153"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","unstructured":"Atul Singh Arora Alexandru Gheorghiu and Uttam Singh. 2022. Oracle separations of hybrid quantum-classical circuits. arxiv:2201.01904. https:\/\/doi.org\/10.1145\/3564246.3585225 10.1145\/3564246.3585225","DOI":"10.1145\/3564246.3585225"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","unstructured":"Adam Bene Watts Charles R. Chen J. William Helton and Joseph Slote. 2025. Quantum precomputation: parallelizing cascade circuits and the Moore-Nilsson conjecture is false. https:\/\/doi.org\/10.48550\/arXiv.2510.04411 10.48550\/arXiv.2510.04411","DOI":"10.48550\/arXiv.2510.04411"},{"key":"e_1_3_2_1_5_1","unstructured":"Guy E. Blelloch. 1990. Prefix sums and their applications."},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1007\/3-540-44598-6_15"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-91098-2_9"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.89.247902"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/775832.775916"},{"key":"e_1_3_2_1_10_1","first-page":"27","article-title":"Asymptotically optimal circuits for arbitrary n-qubit diagonal comutations. Quantum Info","volume":"4","author":"Bullock Stephen S.","year":"2004","unstructured":"Stephen S. Bullock and Igor L. Markov. 2004. Asymptotically optimal circuits for arbitrary n-qubit diagonal comutations. Quantum Info. Comput., 4, 1 (2004), Jan., 27\u201347. issn:1533-7146","journal-title":"Comput."},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(89)90036-9"},{"key":"e_1_3_2_1_12_1","volume-title":"Towards a complexity theory of synchronous parallel computation. Enseign. Math. (2), 27, 1-2","author":"Cook Stephen A.","year":"1981","unstructured":"Stephen A. Cook. 1981. Towards a complexity theory of synchronous parallel computation. Enseign. Math. (2), 27, 1-2 (1981), 99\u2013124. issn:0013-8584"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-90567-5_17"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1137\/18M1182747"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1017\/cbo9780511574931"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1993.366876"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539794261556"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","unstructured":"Gregory D Kahanamoku-Meyer John Blue Thiago Bergamaschi Craig Gidney and Isaac L Chuang. 2025. A log-depth in-place quantum Fourier transform that rarely needs ancillas. arXiv preprint arXiv:2505.00701 https:\/\/doi.org\/10.48550\/arXiv.2505.00701 10.48550\/arXiv.2505.00701","DOI":"10.48550\/arXiv.2505.00701"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01206317"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.TQC.2021.2"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/3564246.3585225"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/3618260.3649650"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1137\/23M158615X"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539799355053"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.93.130502"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","unstructured":"C. C. Paige and M. Wei. 1994. History and generality of the CS decomposition. Linear Algebra Appl. 208-209 (1994) 303\u2013326. issn:0024-3795 https:\/\/doi.org\/10.1016\/0024-3795(94)90446-4 10.1016\/0024-3795(94)90446-4","DOI":"10.1016\/0024-3795(94)90446-4"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/800076.802481"},{"key":"e_1_3_2_1_28_1","volume-title":"Wagner","author":"Rivest Ronald L.","year":"1996","unstructured":"Ronald L. Rivest, Adi Shamir, and David A. Wagner. 1996. Time-Lock Puzzles and Timed-Release Crypto. MIT Laboratory for Computer Science, Cambridge, MA, USA. https:\/\/people.csail.mit.edu\/rivest\/pubs\/RSW96.pdf Revised March 10, 1996"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-68402-9_14"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.134.180602"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977936.13"},{"key":"e_1_3_2_1_32_1","unstructured":"Robert R. Tucci. 1999. A Rudimentary Quantum Compiler(2cnd Ed.). arxiv:quant-ph\/9902062."},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1103\/PhysRevLett.92.177902"}],"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.3800820","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T18:02:32Z","timestamp":1781028152000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3798129.3800820"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,6,9]]},"references-count":33,"alternative-id":["10.1145\/3798129.3800820","10.1145\/3798129"],"URL":"https:\/\/doi.org\/10.1145\/3798129.3800820","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"}}]}}