Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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).

share|cite|improve this question
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 '14 at 15:22
up vote 11 down vote accepted

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!

share|cite|improve this answer
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. – Juan Bermejo Vega Jul 5 '14 at 14:36

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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