<p>This was conjectured by R. Jozsa in Section 8 of <a href="http://arxiv.org/abs/quant-ph/0508124">arXiv:quant-ph/0508124</a>. If you are already familiar with quantum computing and quantum complexity theory, you can start by reading that section.</p>

<p>An important reading is <a href="http://arXiv.org/abs/quant-ph/0006004">arXiv:quant-ph/0006004</a>, where Cleve and Watrous show that Shor's algorithm is in that class. </p>

CC BY-SA 3.0
2011-06-08T04:08:37.407Z
2011-06-08T04:08:37.407Z
Alessandro Cosentino
<p>What should I read to understand this problem?</p>

<blockquote>
  <p>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
  <a href="http://www.scottaaronson.com/writings/qchallenge.html">http://www.scottaaronson.com/writings/qchallenge.html</a></p>
</blockquote>

<cc.complexity-theory><reference-request><quantum-computing>
Reading up on $BQP = BPP^{BQNC}$
Joshua Herman
# Reading up on $BQP = BPP^{BQNC}$

(Asked by: username_0 on 2011-06-07)

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>

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


---

## 1 answers

### Answer by username_1 on 2011-06-08. Score: 21 | Accepted answer

This was conjectured by R. Jozsa in Section 8 of [arXiv:quant-ph/0508124](http://arxiv.org/abs/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](http://arXiv.org/abs/quant-ph/0006004), where Cleve and Watrous show that Shor's algorithm is in that class.


---

