On the Need for Large Quantum Depth
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 (log n ) 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.
Document Details
- Document Type
- Pub Defense Publication
- Publication Date
- Jan 16, 2023
- Source ID
- 10.1145/3570637
Entities
People
- Ching-Yi Lai
- Kai-Min Chung
- Nai-Hui Chia
Organizations
- Academia Sinica
- National Yang Ming Chiao Tung University
- Rice University
- United States Department of Defense