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, and thus a potential way to use these quantum devices is using a hybrid scheme that interleaves them with classical computers. For example, the quantum Fourier transform can be implemented by a hybrid of logarithmic-depth quantum circuits and a classical polynomial-time algorithm. Along the line, it seems possible that a general quantum computer may only be polynomially faster than a hybrid quantum-classical computer. Jozsa raised the question of whether $BQP=BP{P}^{BQNC}$ and conjectured that they are equal, where $BQNC$ means $polylog$-depth quantum circuits. Nevertheless, Aaronson conjectured an oracle separation for these two classes and gave a candidate. In this work, we prove Aaronson's conjecture for a different but related oracle problem. Our result also proves that Jozsa's conjecture fails relative to an oracle.

References in corpus (7)

• Quantum Computing in the NISQ era and beyond
• Supplementary information for "Quantum supremacy using a programmable superconducting processor"
• A Quantum Approximate Optimization Algorithm
• Exponential algorithmic speedup by quantum walk
• Classical simulation of commuting quantum computations implies collapse of the polynomial hierarchy
• An introduction to measurement based quantum computation
• Computations with Greater Quantum Depth Are Strictly More Powerful (Relative to an Oracle)

Cited by in corpus (6)

• Learning quantum circuits of some $T$ gates
• Computations with Greater Quantum Depth Are Strictly More Powerful (Relative to an Oracle)
• Parallel Quantum Algorithm for Hamiltonian Simulation
• Quantum Complexity for Discrete Logarithms and Related Problems
• Hybrid Decision Trees: Longer Quantum Time is Strictly More Powerful
• Tight Quantum Depth Lower Bound for Solving Systems of Linear Equations