# Polynomial time reductions vs. Quantum Polynomial time reductions

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?

• Interesting question that I'd not thought about before. In the examples that I know, it's a classical conversion: you work out on a classical computer what the input should be to your BQP complete problem in order to create the instance of the BQP problem that you're interested in. Mar 17 at 9:49
• I think I read somewhere that it doesn’t matter, or that wlog you don’t get a richer class. I think we could also ask about the uniformity requirement in the definition of BQP - that there be a polynomial time classical Turing machine that gives you a polynomial size circuit for each $n$. I don’t think we get a richer class if we replace “classical Turing machine” with “quantum Turing machine.” I’ll have to look that up (maybe a lecture from O’Donnell). Mar 17 at 12:40

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.