TY - JOUR

T1 - On the Need for Large Quantum Depth

AU - Chia, Nai Hui

AU - Chung, Kai Min

AU - Lai, Ching Yi

N1 - Publisher Copyright:
© 2023 Association for Computing Machinery.

PY - 2023/1/16

Y1 - 2023/1/16

N2 - 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 "BQNCBPP."However, Aaronson conjectured that "there exists an oracle separation between BQP and BPPBQNC."BQNCBPP and BPPBQNC 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 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.

AB - 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 "BQNCBPP."However, Aaronson conjectured that "there exists an oracle separation between BQP and BPPBQNC."BQNCBPP and BPPBQNC 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 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.

KW - d-shuffling Simon's problem

KW - hybrid quantum-classical computer

KW - near-term quantum computer

KW - oracle separation

KW - Small-depth quantum circuit

UR - http://www.scopus.com/inward/record.url?scp=85147330120&partnerID=8YFLogxK

U2 - 10.1145/3570637

DO - 10.1145/3570637

M3 - Article

AN - SCOPUS:85147330120

SN - 0004-5411

VL - 70

JO - Journal of the ACM

JF - Journal of the ACM

IS - 1

M1 - 3570637

ER -