1

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?

TwentyCents
  • 117
  • 4

1 Answers1

1

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.

Mark Spinelli
  • 15,378
  • 3
  • 26
  • 83