What should I read to understand this problem?

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. --Scott Aaronson http://www.scottaaronson.com/writings/qchallenge.html


1 Answer 1


This was conjectured by R. Jozsa in Section 8 of arXiv:quant-ph/0508124. If you are already familiar with quantum computing and quantum complexity theory, you can start by reading that section.

An important reading is arXiv:quant-ph/0006004, where Cleve and Watrous show that Shor's algorithm is in that class.


Your Answer

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

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