Polynomial time reductions vs. Quantum Polynomial time reductions

Question

In computer science, a language $A$ reduces to a language $B$ if there exists a computable function (one that can be computed by a Turing machine) $f_{AB} \colon \Sigma^* \mapsto \Sigma^*$ such that $x \in A \iff f_{AB}(x) \in B$.

We call the reduction "polynomial-time" if the Turing machine that computes $f_{AB}$ can be run in polynomial-time.

A problem P is complete for a complexity class if all other problems in that complexity class are "polynomial-time" reducible to P. My question lies in this very statement: Are BQP-complete problems defined in terms of classical Turing machines; i.e. $A \in BQP$ reduces to $B \in BQP$ if there exists a Classical Turing machine that computes $f_{AB}$ in polynomial time. Or, should it be $A$ reduces to $B$ if there exists a Quantum Turing machine that computes $f_{AB}$ in polynomial-time?

Answer 1

Following O'Donnell's answer from a student's question about uniformity in O'Donnell's lecture on the BQP complexity class, I claim that it does not matter whether the reduction is polynomial-time classical (on a classical Turing machine) or polynomial-time quantum (on a quantum Turing machine), and as @DaftWullie hints, it suffices to keep the reduction classical.

---

In more detail, Shor recounts the early history of the definition of quantum Turing machines. It was noted relatively early on that one needs to have a 'uniformity condition'. Namely, there should be a classical algorithm $\mathcal B$ such that for each problem size $n$, the algorithm $\mathcal B$ builds a quantum circuit based on the input $n$. As Shor explains, this requirement is needed to avoid absurdities like secretly encoding the solution to the Halting problem in your problem statement.

O'Donnell describes this uniformity requirement beginning at around 13 minutes in the above lecture. A student asks whether the efficient classical Turing machine for $\mathcal B$ can be replaced with an efficient quantum Turing machine, and O'Donnell states that there are theorems that say that it doesn't matter whether the algorithm $\mathcal B$ that builds the circuit is itself classical or probabilistic or even quantum.

Turning now to the specific problems in the question of polynomial time reductions, say $\mathcal R$, of (promise)-BQP complete problems, I claim that it follows that it would not matter whether $\mathcal R$ is classical or quantum. For, if it's a quantum polynomial-time reduction, then we can prepend this quantum algorithm to the algorithm $\mathcal B$ that builds the quantum circuit in polynomial time to have a new algorithm $\mathcal B'$, and from O'Donnell's comments it doesn't matter whether this algorithm $\mathcal B'$ is classical or quantum.

O'Donnell mentions that there are such theorems about the uniformity condition potentially relying on a quantum circuit, but, at least in the lecture, doesn't mention where they are proved; I don't suspect these theorems are esoteric and I'll look to see if I can find them.