Update #3:

Over on TCS StackExchange, I have rated as "accepted" an ingenious construction by Luca Trevisan, which answers a two-part question (as reframed by Tsuyoshi Ito) that is in essence "Do runtimes for P require EXP resources to upper-bound? … are concrete examples known?"

Hopefully I have grasped correctly that, in brief, Luca's construction yields the answers "yes" and "yes for all practical purposes" (FAPP).

It will take awhile (for me anyway) to appreciate whether Luca's $M$-machines obstruct the $P$-time uniform reduction of ${BQP}^{P}\,\to\,{BQP}$ that is at the heart of the original question posed here on on MathOverflow, that question being, "Does BQP^P = BQP? ... and what proof machinery is available?", which in turn generalized a question that was posed by Dick Lipton and Ken Regan on their weblog Gödel's Lost Letter and P=NP, the question "Is Factoring Really In BQP? Really?"

After some further reflection (which may take a few days) I will attempt a summary back-trace of this chain of questions, which so enjoyably unites elements of mathematics, science and practical engineering, and will post that summary both here and on TCS StackExchange.

In the meantime, my thanks and appreciation are extended to everyone ... and further comments are very welcome, of course!

Update #2:

I've plowed through a pretty considerable portion of the (excellent) references that Aram provided, and hope to write a summary soon. One topic that I have not found addressed in these references (or it may be that I am too inexpert to perceive it) has been asked as a separate MathOverflow question "Do runtimes for P require EXP resources to upper-bound? … are concrete examples known?".

Update #1:

So far, this topic has a ratio of views-to-answers (presently 285-to-1) that is large relative to other MathOverflow questions ... greater diversity in the answers would be good ... perhaps this draft summary posted on Shtetl Optimized will stimulate more of the "flaming arrow" responses that were hoped-for ... although the references that Aram's answer provides are terrific, needless to say.

Does $BQP^P = BQP$ ? That is, is $P$ low for $BQP$?

Here P is the standard complexity class that is associated to polynomial-time algorithms implemented on (classical) Turing machines, and BQP is the standard (quantum) complexity class Bounded Error Quantum Polynomial Time.

We have specifically in mind a logic-gate instantiation of BQP, that is, a polynomial-time uniform family of quantum circuits (that is, a standard gate-based quantum computer), and for P we have in mind a single-tape Turing machine. So in practical terms, the proposition $BQP^P = BQP$ is about the feasiblity of compiling algorithms in P into polynomially-many reversible logic gates.

This question arose on Dick Lipton and Ken Regan's weblog Gödel's Lost Letter and P=NP as a natural generalization of the question: "Is Shor's algorithm for factoring in BQP?," and it is intimately linked to what Nielsen and Chuang's textbook calls "the Principles of Deferred and Implicit Measurement."

For engineers, proof machinery associated to this question is at least as interesting as the answer itself, because this class of problems arises commonly in engineering practice, in the guise (for example) of compiling a procedural algorithm (written in C and instantiated in a thread, for example) into a circuit diagram (written in Verilog and instantiated on an FPGA, for example). In practice, these algorithm-to-circuit translations are not so easy to solve ... particularly when there is no formal proof that the procedural algorithm is in $P$, but rather, only the empirical (ie, oracular) observation that it so behaves.

One point is that in both practical engineering and in computational complexity theory, procedural algorithms are in general not accompanied by documentation of how they work—perhaps it is infeasible even in principle to document how all the algorithms in the complexity class P work? (an answer to this question too would be very welcome).

Hence the proof machinery for dealing with undocumented (and even undocumentable?) algorithms, both classical and quantum, has both fundamental and practical significance, beyond the significance of the answer to the question asked. This practical/physical context is discussed more fully on Dick and Ken's weblog.

It wasn't so easy to decide whether to post this question of here on MathOverflow versus TCS StackExchange ... in the end, MathOverflow was chosen in hope that the question will attract a mathematically broad range of answers.

Suggestions are especially welcomed, as to how this question might be amended, to make it better-posed and/or more broadly interesting. Thanks! :)

  • $\begingroup$ Please allow me to commend Aram's post (below), which I have just now rated as an "answer." In particular, on first read-through it seems reasonably probable that in aggregate Aram's references describe the reduction of BQP^P to a quantum circuit of polynomial depth. It is less clear (to me so far) that the circuits so constructed reside in PSPACE ... but surely, these matters are "known to the knowers" (in Gil Kalai's happy phrase) ... and so further answers, comments, and references are very welcome. $\endgroup$ Jan 27, 2011 at 19:34

1 Answer 1


Yes, P is contained in BQP (Benioff, 1982; http://prl.aps.org/abstract/PRL/v48/i23/p1581_1 ) and $BQP^{BQP}=BQP$, for pretty much the same reason $BPP^{BPP}=BPP$. This second point first appeared (that I know of) as Cor 4.15 of BBBV'97: http://www.cs.berkeley.edu/~vazirani/pubs/bbbv.ps .

  • $\begingroup$ Aram, thank you especially for the second reference, which is to Bennet, Breassard, Bernstein, and Vazirani Strengths and weaknesses of quantum computing (1997). Lance Fortnow too has written a terrific article One Complexity Theorist’s View of Quantum Computing (2000) that ties a lot of these threads together. It will take several days (if not longer) to digest & comment upon this material ... the task being to translate classical algorithms that we don't understand into quantum ones ... so thanks for your patience ... $\endgroup$ Jan 27, 2011 at 18:47

Your Answer

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

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