<p>I apologize; I was too glib when I wrote that.  While I believe it's <i>possible</i> 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!</p>

CC BY-SA 3.0
2014-07-05T14:36:56.717Z
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
CC BY-SA 3.0
2014-07-05T13:58:48.647Z
2014-07-05T13:58:48.647Z
Scott Aaronson
<p>The following problem appears in Aaronson's list <em><a href="http://www.scottaaronson.com/writings/qchallenge.html" rel="nofollow noreferrer">Ten Semi-Grand Challenges for Quantum Computing Theory</a></em>.</p>

<blockquote>
  <p><strong>Is <span class="math-container">$\mathsf{BQP}=\mathsf{BPP}^{\mathsf{BQNC}}$</span></strong> In other words, can the "quantum" part of any quantum algorithm be compressed to <span class="math-container">$\mathrm{polylog}(n)$</span> 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 <strong>oracle separation</strong> between <span class="math-container">$\mathsf{BQP}$</span>
  and <span class="math-container">$\mathsf{BPP}^{\mathsf{BQNC}}$</span>, but the question is whether there's any concrete function "instantiating" such an oracle.</p>
</blockquote>

<p>It has been <a href="http://arxiv.org/pdf/quant-ph/0508124v2.pdf" rel="nofollow noreferrer">conjectured by Jozsa</a> 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 <a href="https://cstheory.stackexchange.com/questions/6912/reading-up-on-bqp-bppbqnc">this related post</a>.</p>

<p><strong>Question</strong>. 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).</p>

CC BY-SA 3.0
2014-07-05T15:22:49.997Z
I would guess that the [glued trees problem](http://arxiv.org/abs/quant-ph/0209131) 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
<cc.complexity-theory><quantum-computing><circuit-complexity><quantum-information><circuit-depth>
Oracular separations between poly- and log-depth quantum circuits
Juan Bermejo Vega
# Oracular separations between poly- and log-depth quantum circuits

(Asked by: username_0 on 2014-07-05)

The following problem appears in Aaronson's list *[Ten Semi-Grand Challenges for Quantum Computing Theory](http://www.scottaaronson.com/writings/qchallenge.html)*.

> **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](http://arxiv.org/pdf/quant-ph/0508124v2.pdf) 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](https://cstheory.stackexchange.com/questions/6912/reading-up-on-bqp-bppbqnc).

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

**Tags:** cc.complexity-theory, quantum-computing, circuit-complexity, quantum-information, circuit-depth
> **Comments:**
> **username_1**: I would guess that the [glued trees problem](http://arxiv.org/abs/quant-ph/0209131) 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.  

---

## 1 answers

### Answer by username_2 on 2014-07-05. Score: 13 | Accepted answer

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!

> **Comments:**
> **username_0**: 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.  

---

