{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,12,2]],"date-time":"2025-12-02T15:07:04Z","timestamp":1764688024960,"version":"3.41.0"},"reference-count":25,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2023,1,16]],"date-time":"2023-01-16T00:00:00Z","timestamp":1673827200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"Scott Aaronson\u2019s Vannevar Bush Faculty Fellowship"},{"DOI":"10.13039\/100000005","name":"US Department of Defense","doi-asserted-by":"crossref","id":[{"id":"10.13039\/100000005","id-type":"DOI","asserted-by":"crossref"}]},{"name":"Academia Sinica Career Development Award from the Ministry of Science and Technology (MOST) in Taiwan","award":["23-17 MOST, and MOST 107-2627-E-002-002"],"award-info":[{"award-number":["23-17 MOST, and MOST 107-2627-E-002-002"]}]},{"name":"Ching-Yi","award":["110-2628-E-A49-007"],"award-info":[{"award-number":["110-2628-E-A49-007"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2023,2,28]]},"abstract":"<jats:p>\n            Near-term quantum computers are likely to have small depths due to short coherence time and noisy gates. A natural approach to leverage these quantum computers is interleaving them with classical computers. Understanding the capabilities and limits of this hybrid approach is an essential topic in quantum computation. Most notably, the quantum Fourier transform can be implemented by a hybrid of logarithmic-depth quantum circuits and a classical polynomial-time algorithm. Therefore, it seems possible that quantum polylogarithmic depth is as powerful as quantum polynomial depth in the presence of classical computation. Indeed, Jozsa conjectured that \u201c\n            <jats:italic>\n              Any quantum polynomial-time algorithm can be implemented with only\n              <jats:italic>O<\/jats:italic>\n              (log\n              <jats:italic>n<\/jats:italic>\n              ) quantum depth interspersed with polynomial-time classical computations.\n            <\/jats:italic>\n            \u201d This can be formalized as asserting the equivalence of\n            <jats:monospace>BQP<\/jats:monospace>\n            and \u201c\n            <jats:monospace>\n              BQNC\n              <jats:sup>BPP<\/jats:sup>\n            <\/jats:monospace>\n            .\u201d However, Aaronson conjectured that \u201c\n            <jats:italic>\n              there exists an oracle separation between\n              <jats:monospace>BQP<\/jats:monospace>\n              and\n              <jats:monospace>\n                BPP\n                <jats:sup>BQNC<\/jats:sup>\n              <\/jats:monospace>\n              .\n            <\/jats:italic>\n            \u201d\n            <jats:monospace>\n              BQNC\n              <jats:sup>BPP<\/jats:sup>\n            <\/jats:monospace>\n            and\n            <jats:monospace>\n              BPP\n              <jats:sup>BQNC<\/jats:sup>\n            <\/jats:monospace>\n            are two natural and seemingly incomparable ways of hybrid classical-quantum computation.\n          <\/jats:p>\n          <jats:p>\n            In this work, we manage to prove Aaronson\u2019s conjecture and in the meantime prove that Jozsa\u2019s conjecture, relative to an oracle, is false. In fact, we prove a stronger statement that for any depth parameter\n            <jats:italic>d<\/jats:italic>\n            , there exists an oracle that separates quantum depth\n            <jats:italic>d<\/jats:italic>\n            and 2\n            <jats:italic>d<\/jats:italic>\n            +1 in the presence of classical computation. Thus, our results show that relative to oracles, doubling the quantum circuit depth does make the hybrid model more powerful, and this cannot be traded by classical computation.\n          <\/jats:p>","DOI":"10.1145\/3570637","type":"journal-article","created":{"date-parts":[[2022,11,23]],"date-time":"2022-11-23T11:51:38Z","timestamp":1669204298000},"page":"1-38","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":8,"title":["On the Need for Large Quantum Depth"],"prefix":"10.1145","volume":"70","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-4138-7956","authenticated-orcid":false,"given":"Nai-Hui","family":"Chia","sequence":"first","affiliation":[{"name":"Department of Computer Science, Rice University, Houston, USA"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3356-369X","authenticated-orcid":false,"given":"Kai-Min","family":"Chung","sequence":"additional","affiliation":[{"name":"Institute of Information Science, Academia Sinica, Taipei, Taiwan"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1970-8167","authenticated-orcid":false,"given":"Ching-Yi","family":"Lai","sequence":"additional","affiliation":[{"name":"Institute of Communications Engineering, National Yang Ming Chiao Tung University, Hsinchu, Taiwan"}]}],"member":"320","published-online":{"date-parts":[[2023,1,16]]},"reference":[{"key":"e_1_3_3_2_2","unstructured":"Scott Aaronson. 2005. Ten Semi-grand Challenges for Quantum Computing Theory. Retrieved from https:\/\/www.scottaaronson.com\/writings\/qchallenge.html."},{"key":"e_1_3_3_3_2","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806711"},{"key":"e_1_3_3_4_2","unstructured":"Scott Aaronson. 2011. Projects Aplenty. Retrieved from https:\/\/www.scottaaronson.com\/blog\/?p=663."},{"key":"e_1_3_3_5_2","unstructured":"Scott Aaronson. 2019. Personal communication."},{"key":"e_1_3_3_6_2","doi-asserted-by":"publisher","DOI":"10.5555\/3135595.3135617"},{"key":"e_1_3_3_7_2","first-page":"904","article-title":"Quantum security proofs using semi-classical oracles","volume":"2018","author":"Ambainis Andris","year":"2018","unstructured":"Andris Ambainis, Mike Hamburg, and Dominique Unruh. 2018. Quantum security proofs using semi-classical oracles. IACR Cryptology ePrint Archive 2018 (2018), 904.","journal-title":"IACR Cryptology ePrint Archive"},{"key":"e_1_3_3_8_2","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511804090"},{"key":"e_1_3_3_9_2","doi-asserted-by":"publisher","DOI":"10.1038\/s41586-019-1666-5"},{"key":"e_1_3_3_10_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-44381-1_5"},{"key":"e_1_3_3_11_2","doi-asserted-by":"publisher","DOI":"10.1098\/rspa.2010.0301"},{"key":"e_1_3_3_12_2","doi-asserted-by":"publisher","DOI":"10.1145\/780542.780552"},{"key":"e_1_3_3_13_2","doi-asserted-by":"crossref","first-page":"526","DOI":"10.1109\/SFCS.2000.892140","volume-title":"41st Annual Symposium on Foundations of Computer Science","author":"Cleve R.","year":"2000","unstructured":"R. Cleve and J. Watrous. 2000. Fast parallel circuits for the quantum Fourier transform. In 41st Annual Symposium on Foundations of Computer Science. 526\u2013536."},{"key":"e_1_3_3_14_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-78381-9_9"},{"key":"e_1_3_3_15_2","doi-asserted-by":"crossref","unstructured":"Matthew Coudron and Sanketh Menda. 2019. Computations with Greater Quantum Depth Are Strictly More Powerful (Relative to an Oracle). arXiv:arXiv:1909.10503.","DOI":"10.1145\/3357713.3384269"},{"key":"e_1_3_3_16_2","unstructured":"Matthew Coudron and Sanketh Menda. 2019. Personal communication."},{"key":"e_1_3_3_17_2","first-page":"234","volume-title":"Symposium on Theoretical Aspects of Computer Science","author":"H\u00f8yer Peter","year":"2003","unstructured":"Peter H\u00f8yer and Robert \u0160palek. 2003. Quantum circuits with unbounded fan-out. In Symposium on Theoretical Aspects of Computer Science. Springer Berlin, 234\u2013246."},{"key":"e_1_3_3_18_2","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2005.v001a005"},{"key":"e_1_3_3_19_2","unstructured":"IBM. 2017. IBM Announces Advances to IBM Quantum Systems & Ecosystem. Retrieved from https:\/\/www-03.ibm.com\/press\/us\/en\/pressrelease\/53374.wss."},{"key":"e_1_3_3_20_2","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. Quant. Inf. Process. 199 (092005).","journal-title":"Quant. Inf. Process."},{"key":"e_1_3_3_21_2","unstructured":"Julian Kelly. 2018. A Preview of Bristlecone Google\u2019s New Quantum Processor. Retrieved from https:\/\/ai.googleblog.com\/2018\/03\/a-preview-of-bristlecone-googles-new.html."},{"key":"e_1_3_3_22_2","unstructured":"Cristopher Moore and Martin Nilsson. 1998. Parallel Quantum Computation and Quantum Codes. arXiv:arXiv:quant-ph\/9808027."},{"key":"e_1_3_3_23_2","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1994.365701"},{"key":"e_1_3_3_24_2","doi-asserted-by":"publisher","DOI":"10.5555\/2011577.2011582"},{"key":"e_1_3_3_25_2","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-74143-5_12"},{"key":"e_1_3_3_26_2","doi-asserted-by":"publisher","DOI":"10.1145\/2817206"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3570637","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3570637","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T17:49:34Z","timestamp":1750182574000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3570637"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,1,16]]},"references-count":25,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2023,2,28]]}},"alternative-id":["10.1145\/3570637"],"URL":"https:\/\/doi.org\/10.1145\/3570637","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"type":"print","value":"0004-5411"},{"type":"electronic","value":"1557-735X"}],"subject":[],"published":{"date-parts":[[2023,1,16]]},"assertion":[{"value":"2020-09-16","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2022-10-24","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2023-01-16","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}