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

Question

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?

2. 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.

Answer 1

You're mixing up computability theory (also known as recursion theory) and complexity theory (or computational complexity). Computability theory is a vast mathematical subject which studies the ramifications of the concept of computation. It does not deal with the complexity of computation. As your professor mentions, all (Turing-complete) computation models are the same from the point of view of computability theory. Computability theory, while an interesting mathematical subject, is not a good model for real-world computation for this reason, as you mention.

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.

Finally, quantum computers can be modelled in several different ways, such as the quantum Turing machine. Everything computable using quantum computers is also computable using classical computers, and so from the point of view of computability theory, quantum Turing machines are just another equivalent model. However, quantum Turing machines are widely conjectured not to be polynomially equivalent to classical Turing machines: for example, factoring and discrete logarithm are "easy" for quantum Turing machines (solvable in polynomial time), while it is conjectured that they are "hard" for classical Turing machines (cannot be solved in polynomial time; though some people think that integer factoring might be solvable in polynomial time). So from the point of view of complexity theory, quantum Turing machines are different from classical Turing machines.