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?"

The practical motivation for this question arises from a previous MathOverflow question "Does $BQP^P = BQP$? That is, is $P$ low for $BQP$?" (to which Aram Harrow supplied the answer "yes", accompanied by good references). The present question asks about the computational resources that are required to accomplish this reduction.

Once this runtime estimation question is answered, I will incorporate it into a summary answer for the previous question "Does $BQP^P = BQP$? That is, is $P$ low for $BQP$?" ... along with my thanks to all who answer.

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?"

The practical motivation for this question arises from a previous MathOverflow question "Does $BQP^P = BQP$? That is, is $P$ low for $BQP$?" (to which Aram Harrow supplied the answer "yes", accompanied by good references). The present question asks about the computational resources that are required to accomplish this reduction.

Once this runtime estimation question is answered, I will incorporate it into a summary answer for the previous question "Does $BQP^P = BQP$? That is, is $P$ low for $BQP$?" ... along with my thanks to all who answer.

Wow, quick service on TCS StackExchange! Emanuele Viola has provided an answer Are runtime bounds in P decidable? Answer: No.

Emanuele's answer illuminates (for me) Luca Trevisan's answer Do runtimes for P require exp resources to upper-bound? Answer: yes.

I am pleased to report slow-but-steady progress toward a summary answer -- a key remaining question, that has just been asked on TCS StackExchange, is Are runtime bounds in P decidable?

Rather slowly, an answer is crystallizing both here and in a parallel discussion on TCS StackExchange.

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 the same as the one asked here, "Do runtimes for P require EXP resources to upper-bound? … are concrete examples known?"

On TCS Stackexchange, Chicago's Joshua Grochow has suggested (provisional) answers that amount to "yes" (EXP resources are required) and "no" (no concrete instance given as yet). There are still several technical issues to be addressed (these issues reflect mainly my slow imperfect understanding), and I will post a summary when the dust settles. My thanks as always go to all who so kindly and generously contribute to these forums.

Wow, quick service on TCS StackExchange! Emanuele Viola has provided an answer Are runtime bounds in P decidable? Answer: No.

Emanuele's answer illuminates (for me) Luca Trevisan's answer Do runtimes for P require exp resources to upper-bound? Answer: yes.

I am pleased to report slow-but-steady progress toward a summary answer -- a key remaining question, that has just been asked on TCS StackExchange, is Are runtime bounds in P decidable?

Rather slowly, an answer is crystallizing both here and in a parallel discussion on TCS StackExchange.

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 the same as the one asked here, "Do runtimes for P require EXP resources to upper-bound? … are concrete examples known?"

On TCS Stackexchange, Chicago's Joshua Grochow has suggested (provisional) answers that amount to "yes" (EXP resources are required) and "no" (no concrete instance given as yet). There are still several technical issues to be addressed (these issues reflect mainly my slow imperfect understanding), and I will post a summary when the dust settles. My thanks as always go to all who so kindly and generously contribute to these forums.

In the meantime, please see Emanuele's and Luca's answers.

In the meantime, please see Emanuele's and Luca's answers, which in aggregate I regard as an answer to the question posed (and I have modified the title to reflect this).