6
$\begingroup$

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?

$\endgroup$
2
  • 1
    $\begingroup$ 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. $\endgroup$
    – DaftWullie
    Mar 17, 2023 at 9:49
  • $\begingroup$ 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). $\endgroup$ Mar 17, 2023 at 12:40

1 Answer 1

2
$\begingroup$

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.

$\endgroup$

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.