11
$\begingroup$

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?

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

Your Answer

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

Browse other questions tagged or ask your own question.