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 conjectured by Jozsa that the answer to the question is yes in the ''measurement-based model of quantum computation": where local measurements, adaptive local gates and efficient classical post-processing are allowed. 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).

  • 6
    $\begingroup$ 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. $\endgroup$ Jul 5, 2014 at 15:22

1 Answer 1


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!

  • 1
    $\begingroup$ I see, thanks Scott. Well, I personally like this BQP=BPP^BQNC? question, due to its signficance for building quantum computers. I think it should be worth to give it one or two thoughts. $\endgroup$ Jul 5, 2014 at 14:36
  • 2
    $\begingroup$ This question seems to have been resolved: see arXiv:1909.10303 and arXiv:1909.10503. $\endgroup$
    – user45987
    Dec 8, 2019 at 3:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.