1
$\begingroup$

The title of this question is somewhat convoluted. Essentially, a problem is in BQP if there is a Turing machine that runs in polynomial time that computes a polynomial depth quantum circuit that solves the problem.

What about something like this:

Suppose we have a polynomial time Turing machine that computes a quantum circuit that computes another quantum circuit. The final circuit solves a problem X. Is X necessarily in BQP?

$\endgroup$

1 Answer 1

1
$\begingroup$

Welcome to QCSE. Your wording is a little informal but I think you are asking whether BQP is "low for itself", that is, if $\mathsf{BQP}^\mathsf{BQP}=\mathsf{BQP}$.

That is, I think you would like to rephrase your question as:

Suppose we have a polynomial time classical Turing machine that generates a polynomial-size quantum circuit that itself calls another polynomial-size quantum circuit. The final circuit solves a problem X. Is X necessarily in BQP?

The answer is "yes". Aaronson explains, in his Quantum Computing Since Democritus, that this question is not entirely trivial, insofar as garbage must be uncomputed.

Aaronson goes on to explain how recursion wreaks havoc on this uncomputation, but an efficient quantum algorithm calling another efficient quantum algorithm (non-recursively) does not create such headaches.

$\endgroup$
1
  • $\begingroup$ Wow, I didn’t know that my question was equivalent to this, but yeah, I can see it is now. Thanks for the answer. $\endgroup$ Commented Mar 17, 2023 at 17:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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