<p>Back in 2005, Scott Aaronson posted a list of <a href="http://www.scottaaronson.com/writings/qchallenge.html">10 "semi-grand" challenges for quantum computing theory</a> which contained the following challenge: </p>

<blockquote>
  <p><strong>The power of small-depth quantum circuits.</strong> Is $BQP = BPP^{BQNC}$? In other words, can the "quantum" part of any quantum algorithm be compressed to 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 $BQP$ and $BPP^{BQNC}$, but the question is whether there's any concrete function "instantiating" such an oracle. </p>
</blockquote>

<p>I am currently searching for  a Ph.D. project and this is the kind of stuff that interests me. I would certainly like to contribute to solving this problem, if it is still open. That is why I would like to know some of the recent developments on this. Is this still an open problem? What contributions were made in the last decade?</p>

CC BY-SA 3.0
2012-08-14T20:54:04.357Z
This is very close to be a duplicate: http://cstheory.stackexchange.com/q/6912/1542
Alessandro Cosentino
CC BY-SA 3.0
2012-08-30T16:02:20.193Z
@PhillipeLamontagne is there a reason why the link Alessandro mentions does not answer your question ?
Suresh Venkat
CC BY-SA 3.0
2012-08-30T19:12:03.690Z
The asker of the other question wanted to understand the problem quoted from Scott. I understand what the problem is, what I am asking for are recent results related to that problem that I could read in order to contribute myself.
lamontap
CC BY-SA 3.0
2013-03-01T00:44:03.933Z
S. Iblisdir, M. Cirio, O. Boada, G. K. Brennen, [Low Depth Quantum Circuits for Ising Models](http://arxiv.org/abs/1208.3918).
xsi
CC BY-SA 3.0
2014-07-05T13:58:24.893Z
I sincerely think this question is very interesting and not a duplicate. The "duplicated post" only discusses results found before 2005. In my view, the OP is asking about the current status of the question and whether there is been progress in the last 8 years. I would like to hear about this myself.
Juan Bermejo Vega
<cc.complexity-theory><reference-request><quantum-computing><open-problem>
What are the most recent developments in small-depth quantum circuits?
lamontap
# What are the most recent developments in small-depth quantum circuits?

(Asked by: username_0 on 2012-08-14)

Back in 2005, Scott Aaronson posted a list of [10 "semi-grand" challenges for quantum computing theory](http://www.scottaaronson.com/writings/qchallenge.html) which contained the following challenge:

> **The power of small-depth quantum circuits.** Is $BQP = BPP^{BQNC}$? In other words, can the "quantum" part of any quantum algorithm be compressed to 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 $BQP$ and $BPP^{BQNC}$, but the question is whether there's any concrete function "instantiating" such an oracle.

I am currently searching for a Ph.D. project and this is the kind of stuff that interests me. I would certainly like to contribute to solving this problem, if it is still open. That is why I would like to know some of the recent developments on this. Is this still an open problem? What contributions were made in the last decade?

**Tags:** cc.complexity-theory, reference-request, quantum-computing, open-problem

> **Comments:**
> **username_1**: This is very close to be a duplicate: http://cstheory.stackexchange.com/q/6912/1542  
> **username_2**: @PhillipeLamontagne is there a reason why the link Alessandro mentions does not answer your question ?  
> **username_0**: The asker of the other question wanted to understand the problem quoted from Scott. I understand what the problem is, what I am asking for are recent results related to that problem that I could read in order to contribute myself.  
> **username_3**: S. Iblisdir, M. Cirio, O. Boada, G. K. Brennen, [Low Depth Quantum Circuits for Ising Models](http://arxiv.org/abs/1208.3918).  
> **username_4**: I sincerely think this question is very interesting and not a duplicate. The "duplicated post" only discusses results found before 2005. In my view, the OP is asking about the current status of the question and whether there is been progress in the last 8 years. I would like to hear about this myself.  

---

## 0 answers

