*Result*: On the Need for Large Quantum Depth.

*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 “Any quantum polynomial-time algorithm can be implemented with only O(logn) quantum depth interspersed with polynomial-time classical computations.” This can be formalized as asserting the equivalence of BQP and “BQNC^BPP.” However, Aaronson conjectured that “there exists an oracle separation between BQP and BPP^BQNC.” BQNC^BPP and BPP^BQNC are two natural and seemingly incomparable ways of hybrid classical-quantum computation. In thiswork,wemanage to prove Aaronson’s conjecture and in themeantime prove that Jozsa’s conjecture, relative to an oracle, is false. In fact, we prove a stronger statement that for any depth parameter d, there exists an oracle that separates quantum depth d and 2d+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. [ABSTRACT FROM AUTHOR]

Copyright of Journal of the ACM is the property of Association for Computing Machinery and its content may not be copied or emailed to multiple sites without the copyright holder's express written permission. Additionally, content may not be used with any artificial intelligence tools or machine learning technologies. However, users may print, download, or email articles for individual use. This abstract may be abridged. No warranty is given about the accuracy of the copy. Users should refer to the original published version of the material for the full abstract. (Copyright applies to all Abstracts.)*