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. ...
Kindest regards,
Stephen
----- Original Message -----
From: "Jesse Mazer" <lasermazer.domain.name.hidden>
To: <everything-list.domain.name.hidden>
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.
Received on Mon Dec 30 2002 - 11:31:54 PST