References on comparison between quantum computers and Turing machines

Question

I was told that quantum computers are not computationally more powerful than Turing machines. Could someone kindly help in giving some literature references explaining that fact?

Answer 1

What is actually the case is that anything a quantum computer can compute, a Turing machine can also compute. (This is without commenting at all on how long it takes the Turing machine to compute the function compared to a quantum computer.)

This is actually not difficult to see, provided you understand quantum computation. For a quantum circuit over a typical gate set, for example, the outcome is governed by a probability distribution, which is determined by the coefficients of a unitary matrix. That unitary matrix is just a matrix product of those of the gates, and can be computed — if you're patient enough — by a classical computer. So for sheer computability (as opposed to efficiency), there is no advantage to using quantum computers.

The whole challenge arising from quantum mechanics is to determine whether such coefficients can be computed efficiently, which is a more demanding problem than whether they can be computed at all.

Answer 2

Consider a quantum gate. Smoothing out all the technical details, it can be represented as a matrix $G$. An input to the gate, say $\vert \phi \rangle$ is just a vector $v$, and the output of the gate is the vector $Gv$.

Now, consider a circuit. A circuit is just a bunch of gates $\{G_1, G_2, ... \}$, and the circuit itself can be seen as a "generalized gate" $C=G_n \cdots G_2 G_1$, which operates on the input state (the vector $v$).
[Again, this is a very coarse abstraction.]

So basically, computing a circuit on an input $\vert \phi \rangle$, is merely computing the vector $Cv$ or $ G_n \cdots G_2 G_1 v$. It's clear that such a task (matrix multiplication and multiplication of matrix by vector) can be done by a classical TM, therefore, TM is at least as strong as a quantum-TM (QTM)
[ok, classical circuits are as strong as quantum circuits. nevermind that.]

On the other hand QTM is trivially as strong as TM, and therefore, both models are equivalent.

---

EDIT due to comments
In order to ask which "computer" is more powerful, we need to first clarify what it means to be more "computationally powerful". And this semi-philosophical discussion begins with the question

What is computation?

Is "playing MP3" files a computation? Is outputting random numbers a computation?

The standard definition says that a computation is "computing a function". That is, for every input $x$ (which can be any string of any finite length), output $y=f(x)$, where again $y$ can be a string of arbitrary (finite) length. If your computer can output $y$ for any $x$, we say that it can compute $f$.

Now, to say that computer "A" is more powerful than "B" just means that A computes more functions $f$ than $B$. Similarly,

Two models, $A$ and $B$ are considered equivalent if, for any function $f$, $A$ computes $f$ if and only if $B$ computes $f$.

OK, you say, but wait a second, there is randomization.. A quantum computer does not just output $y$. It outputs $y_1$ with probability $p_1$, or $y_2$ with probability $p_2$, or ....$^0$

Indeed.. And this extends the standard definition of computing a function. We can resolve it, and generalize our definitions in several ways. (1) one option is to say that the answer of $f(x)$ is that specific $y_i$ that has probability $p_i>0.75$ (and there is at most one such value)$^1$. If we Assume that $f$ outputs only a single bit, then "the output of $f(x)$ is always well defined$^2$. Otherwise, if no such value exists, and all the outputs have small probability we can say $f$ is not defined on that input; (2) A second option is to say that the output of $f(x)$ is the list $(y_1,p_1), (y_2,p_2),...$. For this to be well defined, we must have a finite list, since we required the output string to be finite.

With the above, it should be clear that having probabilities doesn't change the power of the model, and a classical TM can just output the list of possible outputs along with the probability for each output. this is exactly what happens when a TM multiplies matrices and outputs a vector — the vector represents the probability of each and every possible measurement output.

^{$^0$This issue is not unique to quantum computing. Classical probabilistic computing "suffers" from the same issue.
$^1$Why $p=0.75$? No reason. Any constant larger than $1/2$ would work.
$^2$Why assuming $f$ outputs one bit? because it is enough.. We can reduce any more complex function to one or more functions with a single-bit output. But this doesn't matter to our discussion.}

Answer 3

other answers are valid, just want to add one that emphasizes this is really a very deep (largely still open/unresolved) question at the heart of much modern research into complexity class separations and quantum vs classical computing. they are functionally equivalent as far as TMs and QM computers are both proven Turing complete; there are several ways to prove this.

but equivalence in complexity theory very much hinges on time and space subtleties/efficiencies ie resources to compute particular algorithms. and theres also a huge amount of research looking at "noise" in QM computing that considers that theoretical noiseless models may not be "real" or achievable in practice and real models may/will have significant noise. there are complex schemes to mitigate this noise, etc.; there is some excellent commentary on this in various posts in RJ Liptons blog eg flying machines of the 21st century

for example it has been proven that factoring is in BQP, the class of quantum algorithms that run in P time, by Shor in a famous proof that at the time also launched a large amount of serious study/reseach into QM computing because of the dramatic result.

however even with "noiseless" QM models its an open question whether P $\stackrel{?}{=}$ BQP where the former denotes a classical complexity class of efficient Poly-time algorithms and BQP is the class of efficient/Poly-time QM algorithms. and there are various similar open questions.

Scott Aaronson is an excellent writer/researcher on the subj and has written some papers accessable to the layman. see eg The limits of QM computers, SciAm or QM computing promises new insights, NYT.