On the need for large quantum depth

Nai Hui Chia, Kai Min Chung, Ching Yi Lai

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract

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 "BQNCBPP". On the other hand, Aaronson conjectured that "there exists an oracle separation between BQP and BPPBQNC." BQNCBPP and BPPBQNC are two natural and seeming incomparable ways of hybrid classical-quantum computation. In this work, we manage to prove Aaronson's conjecture and disproves Jozsa's conjecture relative to an oracle. 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 indeed gives the hybrid model more power, and this cannot be traded by classical computation.

Original languageEnglish
Title of host publicationSTOC 2020 - Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing
EditorsKonstantin Makarychev, Yury Makarychev, Madhur Tulsiani, Gautam Kamath, Julia Chuzhoy
PublisherAssociation for Computing Machinery
Pages902-915
Number of pages14
ISBN (Electronic)9781450369794
DOIs
StatePublished - 8 Jun 2020
Event52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020 - Chicago, United States
Duration: 22 Jun 202026 Jun 2020

Publication series

NameProceedings of the Annual ACM Symposium on Theory of Computing
ISSN (Print)0737-8017

Conference

Conference52nd Annual ACM SIGACT Symposium on Theory of Computing, STOC 2020
CountryUnited States
CityChicago
Period22/06/2026/06/20

Keywords

  • D-shuffling Simon's problem
  • Hybrid quantum-classical computer
  • Near-term quantum computer
  • Oracle separation
  • Small-depth quantum circuit

Fingerprint Dive into the research topics of 'On the need for large quantum depth'. Together they form a unique fingerprint.

  • Cite this

    Chia, N. H., Chung, K. M., & Lai, C. Y. (2020). On the need for large quantum depth. In K. Makarychev, Y. Makarychev, M. Tulsiani, G. Kamath, & J. Chuzhoy (Eds.), STOC 2020 - Proceedings of the 52nd Annual ACM SIGACT Symposium on Theory of Computing (pp. 902-915). (Proceedings of the Annual ACM Symposium on Theory of Computing). Association for Computing Machinery. https://doi.org/10.1145/3357713.3384291