Computations with Greater Quantum Depth Are Strictly More Powerful (Relative to an Oracle)

Abstract

A conjecture of Jozsa (arXiv:quant-ph/0508124) states that any polynomial-time quantum computation can be simulated by polylogarithmic-depth quantum computation interleaved with polynomial-depth classical computation. Separately, Aaronson conjectured that there exists an oracle $\mathcal{O}$ such that ${\text{BQP}}^{\mathcal{O}}\ne ({\text{BPP}}^{\text{BQNC}}{)}^{\mathcal{O}}$. These conjectures are intriguing allusions to the unresolved potential of combining classical and low-depth quantum computation. In this work we show that the Welded Tree Problem, which is an oracle problem that can be solved in quantum polynomial time as shown by Childs et al. (arXiv:quant-ph/0209131), cannot be solved in ${\text{BPP}}^{\text{BQNC}}$, nor can it be solved in the class that Jozsa describes. This proves Aaronson's oracle separation conjecture and provides a counterpoint to Jozsa's conjecture relative to the Welded Tree oracle problem. More precisely, we define two complexity classes, $\text{HQC}$ and $\text{JC}$ whose languages are decided by two different families of interleaved quantum-classical circuits. $\text{HQC}$ contains ${\text{BPP}}^{\text{BQNC}}$ and is therefore relevant to Aaronson's conjecture, while $\text{JC}$ captures the model of computation that Jozsa considers. We show that the Welded Tree Problem gives an oracle separation between either of $\{\text{JC},\text{HQC}\}$ and $\text{BQP}$. Therefore, even when interleaved with arbitrary polynomial-time classical computation, greater "quantum depth" leads to strictly greater computational ability in this relativized setting.

39 pages, revised

References in corpus (5)

• Exponential algorithmic speedup by quantum walk
• An introduction to measurement based quantum computation
• Computations with Greater Quantum Depth Are Strictly More Powerful (Relative to an Oracle)
• On the Need for Large Quantum Depth
• A note on the classical lower bound for a quantum walk algorithm

Cited by in corpus (15)

• Quantum advantage in learning from experiments
• Quantum Algorithmic Measurement
• Learning quantum circuits of some $T$ gates
• Computations with Greater Quantum Depth Are Strictly More Powerful (Relative to an Oracle)
• What the foundations of quantum computer science teach us about chemistry
• On the Need for Large Quantum Depth
• Quantum Depth in the Random Oracle Model
• Parallel Quantum Algorithm for Hamiltonian Simulation
• Quantum Complexity for Discrete Logarithms and Related Problems
• A Hierarchy for Replica Quantum Advantage
• On estimating the entropy of shallow circuit outputs
• Exponential speedups for quantum walks in random hierarchical graphs
• Syndrome decoding by quantum approximate optimization
• Hybrid Decision Trees: Longer Quantum Time is Strictly More Powerful
• Offloading Quantum Computation by Superposition Masking