# What are the essential differences between Quantum & Classical Turing Machines?

The classical Turing machine comes in a variety of different flavours. The basic version is the one first outlined by Turing, the non-deterministic version allows finite branching at every computation and in which every branch is followed, or in the probabilistic one, a single branch is randomly chosen.

A Non-deterministic turing machine provably solves exactly the same problems as the basic one, but it does it exponentially faster, and the probabilistic machines can be efficiently simulated by the basic one with polynomial slowdown.

Hence it appears that despite differences these flavours, as far as solvability goes (but not computational power) are equivalent.

What does the qualifier Quantum add here. The article in Wikipedia is not clear here on:

a. How does it differ from the classical version in terms of solvability. That is does it solve exactly the same class of problems, or do they differ in some essential aspect.

b. How do they differ in terms of computational power? The simplest guess would be exponential speedup - which would take us to non-determinsitic turing machines. Is this right?

• Suggested reading: scottaaronson.com/democritus – user3164 Jul 13 '13 at 8:35
• This post is off-topic here: it would best fit in [cs.stackexchange.com]. – Niel de Beaudrap Jul 15 '13 at 13:30
• @debeaudrap: Why aren't fundamental differences in computation of philosophical interest? – Mozibur Ullah Jul 30 '13 at 22:57

Compare the complexity classes BQP (quantum) and BPP (classical). You might be more acquainted with P vs. NP; note that BPP ⊆ BQP and we don't know how BPP relates to NP. BPP is a probabilistic version of P. According to the BQP model of quantum computation, quantum computers are merely faster at solving some kinds of problems. I mean two things by using the very computer-sciency term 'merely faster':

1. 'faster': because many interesting problems in computation have exponential increase in time as the input size grows, they cannot in practice be solved, except by approximation; if we can find exponential speed-ups, like Shor's algorithm, we change what is physically possible to compute (in a finite universe)
2. 'merely': there is nothing that BQP in theory can solve which BPP cannot solve

Why can BQP be faster? Well, it turns out that we can exploit physically computable 'functions', such as period-finding, which is what allows prime factoring to be in the BQP complexity class. For more, see quantum algorithm. It is not correct to view quantum computation as "trying every answer simultaneously"—this would allow solving NP problems in P time—for there is no known physical model of computation which would allow this. Now, computer scientists do talk about "what if we could solve NP problems in constant time?"; see oracle machines.

What would be a more powerful kind of computation than Turing machines? Take a look at undecidable problem. In case you're not quite familiar with decision problems, you can think of a computation which produces some complex output upon some input as, instead, a computation which takes two inputs—the input and 'attempt' at a solution—and simply gives you a 'yes' or a 'no' as output. For examples of problems that something 'stronger' than classical or [known] quantum computing might address, see list of undecidable problems.

A characteristic of undecidable problems is that the problem requires us to find whether there exists some arbitrarily long sequence which solves our problem. Remember those problems where you have to get from one word to another through a few steps, each involving a single letter change, and each intermediate 'word' being valid? Imagine if you can have as many steps as necessary: it won't always be the case that a Turing machine could tell you whether some set of steps exists in any known time/space bound. This is because the time/space bound is a function of the input, not the output. If the output can be arbitrarily large, 'all bets are off', as it were.

If we step past 'quantum' to "true description of the universe", we might find that our universe is more powerful than Turing machines. For example, we might be able to somehow perform infinite (or arbitrarily large) computations in bounded times—times that don't 'explode' in the way that makes certain problems undecidable under the Turing machine model. The classical → quauntum transition doesn't get us this, but if we perform induction on that step, we could expect future transitions that are equally as unexpected; one of them might shatter the Turing machine model of physical reality.

Some of the differences between the capabilities of classical Turing machines and quantum computers described here:

http://www.cs.berkeley.edu/~christos/classics/Deutsch_quantum_theory.pdf

In this section I present a general, fully quantum model for computation. I then describe the universal quantum computer Q, which is capable of perfectly simulating every ﬁnite, realizable physical system. It can simulate ideal closed (zero temperature) systems, including all other instances of quantum computers and quantum simulators, with arbitrarily high but not perfect accuracy. In computing strict functions from Z to Z it generates precisely the classical recursive functions C(T ) (a manifestation of the correspondence principle). Unlike T , it can simulate any ﬁnite classical discrete stochastic process perfectly. Furthermore, as we shall see in x3, it as many remarkable and potentially useful capabilities that have no classical analogues.

• I'm not a physicist, but it's a bit strange to call classical physics "false". That would mean that "false physics" is still taught at universities all over the world. Classical mechanics is incomplete, yes, but still very useful for many purposes. – Ben Jul 13 '13 at 19:00
• @ChaosAndOrder - maybe bad choice of word on my part. What would you recommend? "imprecise"? – obelia Jul 13 '13 at 19:07
• I would not use any adjectives. I think most people here are aware that classical physics (just like any other physics theory) has limitations. I actually also wouldn't say that quantum physics describes the real world, since that, while true, seems to imply that classical mechanics does not. – Ben Jul 13 '13 at 19:12
• I am very tempted to downvote for the implication that classical Turing machines cannot simulate QM to arbitrary accuracy, which is false; you might require exponentially much space and/or time to do so, however, which rather limits the practical use of a conventional Turing machine in some regimes. The link is good enough to make up for this inaccuracy, but it would be better to revise the summary. – Rex Kerr Jul 13 '13 at 19:28
• Ok, edited to remove the (erroneous) pronouncement. – obelia Jul 13 '13 at 19:59