Back to Search
Start Over
On the Need for Large Quantum Depth
- Source :
- STOC
- Publication Year :
- 2023
- Publisher :
- Association for Computing Machinery (ACM), 2023.
-
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. In this work, we manage to prove Aaronson’s conjecture and in the meantime 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 2 d +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.
- Subjects :
- FOS: Computer and information sciences
Discrete mathematics
Quantum Physics
Polynomial
Computer science
Computation
FOS: Physical sciences
Computational Complexity (cs.CC)
Computer Science::Computational Complexity
Oracle
Computer Science - Computational Complexity
Quantum circuit
BQP
Artificial Intelligence
Hardware and Architecture
Control and Systems Engineering
Quantum Fourier transform
Quantum Physics (quant-ph)
Quantum
Software
Quantum computer
Information Systems
Subjects
Details
- ISSN :
- 1557735X and 00045411
- Volume :
- 70
- Database :
- OpenAIRE
- Journal :
- Journal of the ACM
- Accession number :
- edsair.doi.dedup.....b40f7f0c7d42c73a55ae36a9e46fcd59