{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,10]],"date-time":"2026-06-10T07:56:08Z","timestamp":1781078168235,"version":"3.54.1"},"publisher-location":"New York, NY, USA","reference-count":46,"publisher":"ACM","license":[{"start":{"date-parts":[[2023,6,2]],"date-time":"2023-06-02T00:00:00Z","timestamp":1685664000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"N S F","award":["CNS-2154705"],"award-info":[{"award-number":["CNS-2154705"]}]},{"name":"MC2 post-doctoral fellowship","award":[""],"award-info":[{"award-number":[""]}]},{"name":"ETH Z\u00fcrich Foundation","award":[""],"award-info":[{"award-number":[""]}]},{"name":"NSF","award":["NSF Grant PHY-112556"],"award-info":[{"award-number":["NSF Grant PHY-112556"]}]},{"DOI":"10.13039\/100000936","name":"Gordon and Betty Moore Foundation","doi-asserted-by":"publisher","award":["BMF-1250002"],"award-info":[{"award-number":["BMF-1250002"]}],"id":[{"id":"10.13039\/100000936","id-type":"DOI","asserted-by":"publisher"}]},{"name":"MURI grant","award":["A9550-18-1-0161"],"award-info":[{"award-number":["A9550-18-1-0161"]}]},{"name":"Dr. Max R\u00f6ssler","award":[""],"award-info":[{"award-number":[""]}]},{"name":"Walter Haefner Foundation","award":[""],"award-info":[{"award-number":[""]}]},{"DOI":"10.13039\/100000001","name":"NSF (National Science Foundation)","doi-asserted-by":"publisher","award":["QLCI Grant No. 2016245"],"award-info":[{"award-number":["QLCI Grant No. 2016245"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"name":"DARPA","award":["HR0011202002"],"award-info":[{"award-number":["HR0011202002"]}]},{"name":"Polish National Science Center (NCN)","award":["Grant No. 2019\/35\/B\/ST2\/01896"],"award-info":[{"award-number":["Grant No. 2019\/35\/B\/ST2\/01896"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2023,6,2]]},"DOI":"10.1145\/3564246.3585153","type":"proceedings-article","created":{"date-parts":[[2023,5,16]],"date-time":"2023-05-16T17:34:20Z","timestamp":1684258460000},"page":"1111-1124","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":8,"title":["Quantum Depth in the Random Oracle Model"],"prefix":"10.1145","author":[{"given":"Atul Singh","family":"Arora","sequence":"first","affiliation":[{"name":"California Institute of Technology, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Andrea","family":"Coladangelo","sequence":"additional","affiliation":[{"name":"University of Washington, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Matthew","family":"Coudron","sequence":"additional","affiliation":[{"name":"National Institute of Standards and Technology, USA \/ University of Maryland, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Alexandru","family":"Gheorghiu","sequence":"additional","affiliation":[{"name":"Chalmers University of Technology, Sweden \/ ETH Zurich, Switzerland"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Uttam","family":"Singh","sequence":"additional","affiliation":[{"name":"Polish Academy of Sciences, Poland \/ IIIT Hyderabad, India"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Hendrik","family":"Waldner","sequence":"additional","affiliation":[{"name":"University of Maryland, College Park, USA \/ MPI-SP, Germany"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2023,6,2]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806711"},{"key":"e_1_3_2_1_2_1","unstructured":"Scott Aaronson and Andris Ambainis. 2009. The need for structure in quantum speedups. arXiv preprint arXiv:0911.0996. \t\t\t\t  Scott Aaronson and Andris Ambainis. 2009. The need for structure in quantum speedups. arXiv preprint arXiv:0911.0996."},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2746539.2746547"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/1008731.1008735"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/276698.276708"},{"key":"e_1_3_2_1_6_1","unstructured":"Dorit Aharonov and Yonathan Touati. 2018. Quantum circuit depth lower bounds for homological codes. arXiv preprint arXiv:1810.03912. \t\t\t\t  Dorit Aharonov and Yonathan Touati. 2018. Quantum circuit depth lower bounds for homological codes. arXiv preprint arXiv:1810.03912."},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/237814.237838"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-26951-7_10"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539705446950"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"crossref","unstructured":"Atul Singh Arora Andrea Coladangelo Matthew Coudron Alexandru Gheorghiu Uttam Singh and Hendrik Waldner. 2022. Quantum Depth in the Random Oracle Model. arxiv:2210.06454. \t\t\t\t  Atul Singh Arora Andrea Coladangelo Matthew Coudron Alexandru Gheorghiu Uttam Singh and Hendrik Waldner. 2022. Quantum Depth in the Random Oracle Model. arxiv:2210.06454.","DOI":"10.1145\/3564246.3585153"},{"key":"e_1_3_2_1_11_1","unstructured":"Atul Singh Arora Alexandru Gheorghiu and Uttam Singh. [n. d.]. Oracle Separations of Hybrid Quantum-Classical Circuits. https:\/\/doi.org\/10.48550\/arXiv.2201.01904 arxiv:2201.01904. \t\t\t\t    10.48550\/arXiv.2201.01904\nAtul Singh Arora Alexandru Gheorghiu and Uttam Singh. [n. d.]. Oracle Separations of Hybrid Quantum-Classical Circuits. https:\/\/doi.org\/10.48550\/arXiv.2201.01904 arxiv:2201.01904."},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/2160158.2160159"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-44381-1_5"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/2840728.2840745"},{"key":"e_1_3_2_1_15_1","unstructured":"Jeremiah Blocki Seunghoon Lee and Samson Zhou. [n. d.]. On the Security of Proofs of Sequential Work in a Post-Quantum World. arxiv:2006.10972. arxiv:2006.10972 \t\t\t\t  Jeremiah Blocki Seunghoon Lee and Samson Zhou. [n. d.]. On the Security of Proofs of Sequential Work in a Post-Quantum World. arxiv:2006.10972. arxiv:2006.10972"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-96884-1_25"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.TQC.2020.8"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1038\/nphys1157"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"crossref","unstructured":"Ran Canetti Yilei Chen and Leonid Reyzin. 2016. On the correlation intractability of obfuscated pseudorandom functions. In Theory of cryptography conference. 389\u2013415. \t\t\t\t  Ran Canetti Yilei Chen and Leonid Reyzin. 2016. On the correlation intractability of obfuscated pseudorandom functions. In Theory of cryptography conference. 389\u2013415.","DOI":"10.1007\/978-3-662-49096-9_17"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1008731.1008734"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/3357713.3384291"},{"key":"#cr-split#-e_1_3_2_1_22_1.1","unstructured":"Nai-Hui Chia and Shih-Han Hung. 2022. Classical verification of quantum depth. https:\/\/doi.org\/10.48550\/ARXIV.2205.04656 10.48550\/ARXIV.2205.04656"},{"key":"#cr-split#-e_1_3_2_1_22_1.2","unstructured":"Nai-Hui Chia and Shih-Han Hung. 2022. Classical verification of quantum depth. https:\/\/doi.org\/10.48550\/ARXIV.2205.04656"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/780542.780552"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-77886-6_21"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.2000.892140"},{"key":"e_1_3_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/3519935.3520019"},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-78381-9_9"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/3357713.3384269"},{"key":"e_1_3_2_1_29_1","unstructured":"Edward Farhi Jeffrey Goldstone and Sam Gutmann. 2014. A quantum approximate optimization algorithm. arXiv preprint arXiv:1411.4028. \t\t\t\t  Edward Farhi Jeffrey Goldstone and Sam Gutmann. 2014. A quantum approximate optimization algorithm. arXiv preprint arXiv:1411.4028."},{"key":"e_1_3_2_1_30_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. 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":"#cr-split#-e_1_3_2_1_31_1.1","unstructured":"Atsuya Hasegawa and Fran\u00e7ois Le Gall. 2022. An optimal oracle separation of classical and quantum hybrid schemes. https:\/\/doi.org\/10.48550\/ARXIV.2205.04633 10.48550\/ARXIV.2205.04633"},{"key":"#cr-split#-e_1_3_2_1_31_1.2","unstructured":"Atsuya Hasegawa and Fran\u00e7ois Le Gall. 2022. An optimal oracle separation of classical and quantum hybrid schemes. https:\/\/doi.org\/10.48550\/ARXIV.2205.04633"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/12130.12132"},{"key":"e_1_3_2_1_33_1","first-page":"09","article-title":"An introduction to measurement based quantum computation","volume":"199","author":"Jozsa Richard","year":"2005","unstructured":"Richard Jozsa . 2005 . An introduction to measurement based quantum computation . Quantum Information Processing , 199 (2005), 09 . Richard Jozsa. 2005. An introduction to measurement based quantum computation. Quantum Information Processing, 199 (2005), 09.","journal-title":"Quantum Information Processing"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"crossref","unstructured":"Yael Tauman Kalai Guy N Rothblum and Ron D Rothblum. 2017. From obfuscation to the security of Fiat-Shamir for proofs. In Annual international cryptology conference. 224\u2013251. \t\t\t\t  Yael Tauman Kalai Guy N Rothblum and Ron D Rothblum. 2017. From obfuscation to the security of Fiat-Shamir for proofs. In Annual international cryptology conference. 224\u2013251.","DOI":"10.1007\/978-3-319-63715-0_8"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1016\/0020-0190(92)90225-K"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-26948-7_4"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1038\/ncomms5213"},{"key":"e_1_3_2_1_38_1","volume-title":"A one-way quantum computer. Physical review letters, 86, 22","author":"Raussendorf Robert","year":"2001","unstructured":"Robert Raussendorf and Hans J Briegel . 2001. A one-way quantum computer. Physical review letters, 86, 22 ( 2001 ), 5188. Robert Raussendorf and Hans J Briegel. 2001. A one-way quantum computer. Physical review letters, 86, 22 (2001), 5188."},{"key":"e_1_3_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/195058.195134"},{"key":"e_1_3_2_1_40_1","unstructured":"Ronald L Rivest Adi Shamir and David A Wagner. 1996. Time-lock puzzles and timed-release crypto. \t\t\t\t  Ronald L Rivest Adi Shamir and David A Wagner. 1996. Time-lock puzzles and timed-release crypto."},{"key":"e_1_3_2_1_41_1","unstructured":"Gregory Rosenthal. 2020. Bounds on the QAC^0 Complexity of Approximating Parity. arXiv preprint arXiv:2008.07470. \t\t\t\t  Gregory Rosenthal. 2020. Bounds on the QAC^0 Complexity of Approximating Parity. arXiv preprint arXiv:2008.07470."},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539796298637"},{"key":"e_1_3_2_1_43_1","unstructured":"Takashi Yamakawa and Mark Zhandry. [n. d.]. Verifiable Quantum Advantage without Structure. arxiv:2204.02063. arxiv:2204.02063 \t\t\t\t  Takashi Yamakawa and Mark Zhandry. [n. d.]. Verifiable Quantum Advantage without Structure. arxiv:2204.02063. arxiv:2204.02063"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-26951-7_9"}],"event":{"name":"STOC '23: 55th Annual ACM Symposium on Theory of Computing","location":"Orlando FL USA","acronym":"STOC '23","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 55th Annual ACM Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3564246.3585153","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3564246.3585153","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3564246.3585153","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T01:17:27Z","timestamp":1750295847000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3564246.3585153"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,6,2]]},"references-count":46,"alternative-id":["10.1145\/3564246.3585153","10.1145\/3564246"],"URL":"https:\/\/doi.org\/10.1145\/3564246.3585153","relation":{},"subject":[],"published":{"date-parts":[[2023,6,2]]},"assertion":[{"value":"2023-06-02","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}