Back in 2005, Scott Aaronson posted a list of 10 "semi-grand" challenges for quantum computing theory 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?

  • 5
    $\begingroup$ This is very close to be a duplicate: cstheory.stackexchange.com/q/6912/1542 $\endgroup$ Commented Aug 14, 2012 at 20:54
  • $\begingroup$ @PhillipeLamontagne is there a reason why the link Alessandro mentions does not answer your question ? $\endgroup$ Commented Aug 30, 2012 at 16:02
  • $\begingroup$ 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. $\endgroup$
    – lamontap
    Commented Aug 30, 2012 at 19:12
  • 2
    $\begingroup$ S. Iblisdir, M. Cirio, O. Boada, G. K. Brennen, Low Depth Quantum Circuits for Ising Models. $\endgroup$
    – xsi
    Commented Mar 1, 2013 at 0:44
  • 1
    $\begingroup$ 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. $\endgroup$ Commented Jul 5, 2014 at 13:58


Your Answer

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