  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 $\textrm{BQP}^{\mathcal{O}} \neq
(\textrm{BPP}^\textrm{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
$\textrm{BPP}^{\textrm{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, $\textrm{HQC}$ and
$\textrm{JC}$ whose languages are decided by two different families of
interleaved quantum-classical circuits. $\textrm{HQC}$ contains
$\textrm{BPP}^\textrm{BQNC}$ and is therefore relevant to Aaronson's
conjecture, while $\textrm{JC}$ captures the model of computation that Jozsa
considers. We show that the Welded Tree Problem gives an oracle separation
between either of $\{\textrm{JC}, \textrm{HQC}\}$ and $\textrm{BQP}$.
Therefore, even when interleaved with arbitrary polynomial-time classical
computation, greater "quantum depth" leads to strictly greater computational
ability in this relativized setting.
