Dear Jesse, Please read the below referenced paper. It shows that QM comp *CAN* " "solve an undecidable problem" (relative to a classical computer)." I do not see how I misread Feynman's claim, but I do admit that the quotation what I reproduced is insufficient to support my claim. It is not an issue of "speed" that I am trying to point out, it is an issue of computational "expressiveness". Unless I am mistaken, UTMs of all kinds operate in the space of Integers, QM comps operate, at least, in the space of the Reals. ...

## Advertising

Kindest regards, Stephen ----- Original Message ----- From: "Jesse Mazer" <[EMAIL PROTECTED]> To: <[EMAIL PROTECTED]> Sent: Monday, December 30, 2002 11:01 AM Subject: Re: Quantum Probability and Decision Theory snip http://www.cs.auckland.ac.nz/~cristian/coinsQIP.pdf > > > > > >** > >1. INTRODUCTION > > > >For over fifty years the Turing machine model of computation has defined > >what it means to ''compute'' something; the foundations of the modern > >theory of computing are based on it. Computers are reading text, > >recognizing > >speech, and robots are driving themselves across Mars. Yet this > >exponential race will not produce solutions to many intractable and > >undecidable > >problems. Is there any alternative? Indeed, quantum computing > >offers one such alternative (see Ref. 7, 10, 11, 23, 35). To date, quantum > >computing has been very successful in ''beating'' Turing machines in the > >race of solving intractable problems, with Shor and Grover algorithms > >achieving the most impressive successes; the progress in quantum hardware > >is also impressive. Is there any hope for quantum computing to challenge > >the > >Turing barrier, i.e., to solve an undecidable problem, to compute an > >uncomputable function? According to Feynman's argument (see Ref. 20, a > >paper reproduced also in Ref. 25, regarding the possibility of simulating a > >quantum system on a (probabilistic) Turing machine) the answer is > >negative. > > This seems to say the opposite of what you are arguing. Look at the last two > sentences--they ask if quantum computers can "solve an undecidable problem" > (relative to a classical computer) or "compute an uncomputable function", > but according to Feynman "the answer is negative"--ie a quantum computer can > *not* solve any classically-unsolvable problems. I take it you interpreted > Feynman's negative answer to refer to "the possibility of simulating a > quantum system on a (probabilistic) Turing machine", but because of the way > the sentences are constructed I think you misread it. I suspect that > "Feynman's argument" involved showing that you *can* simulate a quantum > system on a probabilistic Turing machine, and that he used that to prove > that quantum computers cannot do anything fundamentally new, even if they > may in some cases work much faster.