# References on comparison between quantum computers and Turing machines

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?

• You seem to have a registered account on other Stack Exchange sites. You should register your CS account and associate it with the others (see the help center). Among other things, this will let you participate in chat from CS. – Gilles 'SO- stop being evil' Oct 25 '12 at 13:47

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.

• While my beginner's knowledge tells me that a quantum circuit represents a Hadamard matrix transformation, I can't yet see how a programming possibility to do arbitrary matrix computations on a classical computer could be a subsitute of physically having a quantum circuit. For example, my book says about generating random numbers as follows: 1. |x> <-- |0> 2. |x> <-- H|x> 3. Measure |x> What would in particular step 3 correspond to programming on a classical computer? – Mok-Kong Shen Oct 25 '12 at 2:07
• A (properly normalised) Hadamard matrix is only one possible unitary transformation. For your computation, we can recognise that a deterministic Turing machine can compute the probability distribution (0.5, 0.5) consisting of the norms-squared of the first column of the Hadamard matrix $\bigl|\langle b |H|0\rangle\bigr|^2$, and that for a randomised Turing machine (which can perform coin-flips), we can go a step further and produce a sample from that probability distribution. In any case, any function computed by the quantum circuit with error < 1/2, a classical machine also can. – Niel de Beaudrap Oct 25 '12 at 7:54
• @Mok-Kong Shen: in case it isn't clear from my remarks about inefficiency or slowness, it is commonly supposed that quantum computers are more computationally powerful in the sense of being able to compute more quickly. I've been addressing the fact that they are not able to compute things which a classical computer could not also compute (where I discount the notion of "flipping a coin" as computation). – Niel de Beaudrap Oct 25 '12 at 10:10

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.

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.

• I could program matrix computations on a classical computer but don't know how to write a code to simulate a quantum computation. I'll need anyway quantum bits. A quantum bit has 2 values commonly denoted by alpha and beta. What values should I use? See also my comment to the answer of Niel de Beaudrap for the case of random number generation. – Mok-Kong Shen Oct 25 '12 at 7:20
• @Mok-Kong Shen: those values sound like they're coefficients in a superposition $\def\ket#1{|#1\rangle}\ket\psi = \alpha\ket0 + \beta\ket1$. But recall that the Dirac notation is merely a vector notation: this is exactly the same as writing $\pmb\psi = [\alpha\quad\beta]^\top$ using the usual convention. Those coefficients are just vector/matrix coefficients, which is what the classical computer evaluates in order to (slowly) simulate the quantum computer. – Niel de Beaudrap Oct 25 '12 at 8:02
• @Niel de Beaudrap: But when I write a code to simulate a certain quantum compuation, e.g. the random number generation I mentioned, I need to implement simulated quantum bits on classical computer. I am ignorant of how to write code to do that without knowing the values of these coefficients. – Mok-Kong Shen Oct 25 '12 at 8:18
• @Mok-Kong Shen: the point is that at run-time, you do know; and the problem is exactly the same as sampling from a classical probability distribution which is specified at the input, i.e. it reduces to well-studied problems in random sampling. Monte Carlo methods apply here, for instance. – Niel de Beaudrap Oct 25 '12 at 8:25
• @Mok-KongShen Please do not use comments (especially on someone else's post) for extended discussions. Go to chat, either in the general room for this site or in a chatroom created for the purpose. – Gilles 'SO- stop being evil' Oct 25 '12 at 12:53

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.