# Oracular separations between poly- and log-depth quantum circuits

The following problem appears in Aaronson's list Ten Semi-Grand Challenges for Quantum Computing Theory.

Is $\mathsf{BQP}=\mathsf{BPP}^{\mathsf{BQNC}}$ In other words, can the "quantum" part of any quantum algorithm be compressed to $\mathrm{polylog}(n)$ depth, provided we're willing to do polynomial-time classical postprocessing? (This is known to be true for Shor's algorithm.) If so, building a general-purpose quantum computer would be much easier than is generally believed! Incidentally, it's not hard to give an oracle separation between $\mathsf{BQP}$ and $\mathsf{BPP}^{\mathsf{BQNC}}$, but the question is whether there's any concrete function "instantiating" such an oracle.

It has been conectured by Jozsa that the answer to the question is yes. See also this related post.

Question. I would like to know about the currently-known oracular separations between this classes (or, at least, the oracle separation to which Aaronson is referring to).

-
I would guess that the glued trees problem is a good candidate for separation. The intuition being that a classical computer is essentially useless for this task, and a polylog depth quantum circuit can only reach polylog deep into the glued trees, but you need to reach the exit vertex which is polynomially far away from the entry vertex. –  Robin Kothari Jul 5 at 15:22

I apologize; I was too glib when I wrote that. While I believe it's possible to prove an oracle separation between $BQP$ and $BPP^{BQNC}$ using current techniques, it hasn't been done (12 years after I first thought about the problem, then put it off!), and would certainly be worth a paper for whoever did it. Maybe your post will help motivate me to finally kill this problem off!