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

From: Jesse Mazer <lasermazer.domain.name.hidden>

Date: Mon, 30 Dec 2002 11:01:28 -0500

Stephen Paul King wrote:

*>>Also, any quantum computer or physical system can be simulated by a
*

*>>classical computer.
*

*>
*

*>[SPK]
*

*>
*

*> Bruno has made similar statements and I do not understand how this is
*

*>true. I have it from multiple sources that this is not true. Do you recall
*

*>the famous statement by Richard Feynman regarding the "exponential
*

*>slowdown"
*

*>of classical system attempting to simulate QM systems?
*

It is true that classical computers will take an exponentially long time to

simulate quantum ones, but as far as I know it's still true that there are

no problems that are solvable by a quantum computer that cannot also be

solved by a classical computer (possibly much more slowly).

*>Let me quote from a
*

*>paper by Karl Svozil et al: http://tph.tuwien.ac.at/~svozil/publ/embed.htm
*

*>
*

*>
*

*>***
*

*>4 Summary
*

*>We have reviewed several options for a classical ``understanding'' of
*

*>quantum mechanics. Particular emphasis has been given to techniques for
*

*>embedding quantum universes into classical ones. The term ``embedding'' is
*

*>formalized here as usual. That is, an embedding is a mapping of the entire
*

*>set of quantum observables into a (bigger) set of classical observables
*

*>such
*

*>that different quantum observables correspond to different classical ones
*

*>(injectivity).
*

*>The term ``observables'' here is used for quantum propositions, some of
*

*>which (the complementary ones) might not be co-measurable, see Gudder [14].
*

This problem of "embedding" seems different from the question of whether

quantum computers can do anything classical computers cannot--for example,

the last sentence above talks about the problem of whether complementary

observables might have definite classical values, but a quantum computer's

output must be measurable--you can't have an "output" which involves two

bits encoded in terms of complementary observables, since it would be

impossible to measure the value of both those bits simultaneously.

Perhaps someone who understands that paper better could comment further, but

I don't think it supports the view that a quantum computer could solve

problems which are unsolvable by a classical one.

*> Let me quote from some other papers to reinforce my argument.
*

*>
*

*>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 machine4) 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.

*>
*

*>We also have:
*

*>
*

*>http://xxx.lanl.gov/abs/quant-ph/0204153
*

*>
*

*>
*

*>A stronger no-cloning theorem
*

*>Authors: Richard Jozsa (University of Bristol UK)
*

*>Comments: 4 pages. An error in version 1 corrected. Further
*

*>interpretational
*

*>comments added
*

*>
*

*>
*

*> It is well known that (non-orthogonal) pure states cannot be cloned so
*

*>one
*

*>may ask: how much or what kind of additional (quantum) information is
*

*>needed
*

*>to supplement one copy of a quantum state in order to be able to produce
*

*>two
*

*>copies of that state by a physical operation? For classical information, no
*

*>supplementary information is required. However for pure quantum
*

*>(non-orthogonal) states, we show that the supplementary information must
*

*>always be as large as it can possibly be i.e. the clone must be able to be
*

*>generated from the additional information alone, independently of the first
*

*>(given) copy.
*

*>***
*

*>
*

*> I could go on and on.
*

I don't see how this supports your argument either.

--Jesse

_________________________________________________________________

Add photos to your e-mail with MSN 8. Get 3 months FREE*.

http://join.msn.com/?page=features/featuredemail&xAPID=42&PS=47575&PI=7324&DI=7474&SU=

http://www.hotmail.msn.com/cgi-bin/getmsg&HL=1216hotmailtaglines_addphotos_3mf

Received on Mon Dec 30 2002 - 11:02:36 PST

Date: Mon, 30 Dec 2002 11:01:28 -0500

Stephen Paul King wrote:

It is true that classical computers will take an exponentially long time to

simulate quantum ones, but as far as I know it's still true that there are

no problems that are solvable by a quantum computer that cannot also be

solved by a classical computer (possibly much more slowly).

This problem of "embedding" seems different from the question of whether

quantum computers can do anything classical computers cannot--for example,

the last sentence above talks about the problem of whether complementary

observables might have definite classical values, but a quantum computer's

output must be measurable--you can't have an "output" which involves two

bits encoded in terms of complementary observables, since it would be

impossible to measure the value of both those bits simultaneously.

Perhaps someone who understands that paper better could comment further, but

I don't think it supports the view that a quantum computer could solve

problems which are unsolvable by a classical one.

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.

I don't see how this supports your argument either.

--Jesse

_________________________________________________________________

Add photos to your e-mail with MSN 8. Get 3 months FREE*.

http://join.msn.com/?page=features/featuredemail&xAPID=42&PS=47575&PI=7324&DI=7474&SU=

http://www.hotmail.msn.com/cgi-bin/getmsg&HL=1216hotmailtaglines_addphotos_3mf

Received on Mon Dec 30 2002 - 11:02:36 PST

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