# Quantum Computing and Turing Machines: Are Turing Machines still an Accurate Measure?

In class last week, my professor commented and said that Turing machines are used as a standard measure/model of what is computable and are a helpful basis of discussion for that subject. She also said that all variants of Turing machines are proven to be computationally equivalent -- read, just as powerful -- as one another. W

I commented and said yesterday that, regarding computability power, I noticed that some turing machines can take incredibly large amounts of time to compute something very simple, while a turing machine with more tapes can compute something in a lower asymptotic complexity with respect to the number of steps needed.

She said that with respect to class discourse, the runtime of a particular algorithm on a turing machine does not change the definition of computability, or the power with which we measure computability. "We're concerned about what is computable, not what is efficiently computable at this point." So, it doesn't matter if the turing machines has more and more tapes, and more and more tapes implies that it can compute in lesser steps. Okay, I get that we're really focusing on what IS computable, not the speed at which we can compute it.

Something about that just bothers me, because up to this point, algorithms with abnormally large asymptotic time and space complexity really define the limits of what is, maybe I should say, practically, computable.

So, I have a couple of questions:

1. Suppose we have a model for a quantum turing machine, this must be equivalent to a "regular" turing machine, right?

So, the answer to that question I think really is going towards my reason for writing this post. Does quantum computing technology antiquate the classical definitions of what is computable via a turing machine?

1. Is this something above my head and should I delete this post? I don't mean to be precocious, I just didn't see a question similar to mine.
-
You can simulate a quantum computer with a classical computer. It's just exponentially expensive. –  CodesInChaos Mar 28 at 10:50
there is a fairly simple proof that the multitape TM is not really any more "powerful" than a single tape TM, you only get a linear speedup, which is "negligible" wrt complexity theory & big-Oh asymptotic complexity. –  vzn Mar 28 at 15:13
also its an open question subject to major active/ongoing worldwide research both theoretically & practically whether a QM computer is/can be faster than a classical computer. –  vzn Mar 28 at 15:28

Complexity theory started its life as an attempt to address this issue. Complexity theory studies how difficult it is, in terms of time and space, to compute certain predicates and functions. From the point of view of complexity theory, not all computation models are the same, and Turing machines are taken as the reference model. However, even complexity theory is not very realistic, since it treats all computational models polynomially equivalent to Turing machines in the same way (two models are polynomially equivalent if any problem solvable in time $T(n)$ and space $S(n)$ in one model can be solved in time $T(n)^c$ and space $S(n)^c$ in the other, where $n$ is the input size and $c$ is some positive constant). For example, Turing machines are not good models for real computers since they do not support random access (accessing an arbitrary point in memory in time $O(1)$). Of course, random access can be simulated by a Turing machine, but the simulation can be slow. It is often said that sorting can be done in time $O(n\log n)$, but this is not the case for Turing machines, which probably require $\Omega(n^2)$ or move even for sorting integers. Therefore in the area of algorithms, other models such as the RAM machine replace Turing machines.