- Contemporary messages sorted: [ by date ] [ by thread ] [ by subject ] [ by author ] [ by messages with attachments ]

From: Stephen Paul King <stephenk1.domain.name.hidden>

Date: Mon, 30 Dec 2002 11:30:27 -0500

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

Date: Mon, 30 Dec 2002 11:30:27 -0500

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

quantum

a

two

problem"

can

way

Received on Mon Dec 30 2002 - 11:31:54 PST

*
This archive was generated by hypermail 2.3.0
: Fri Feb 16 2018 - 13:20:07 PST
*