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! 🙂
Best Answer
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 .