15
$\begingroup$

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

$\endgroup$
  • 5
    $\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$ – Robin Kothari Jul 5 '14 at 15:22
12
$\begingroup$

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!

$\endgroup$
  • 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$ – Juan Bermejo Vega Jul 5 '14 at 14:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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