18

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

Joshua Herman
  • 1,661
  • 17
  • 38

1 Answers1

20

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.

Alessandro Cosentino
  • 4,000
  • 35
  • 43