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).[SPK]Also, any quantum computer or physical system can be simulated by a classical computer.

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?

Let me quote from aThis 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.

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].

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.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.

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.

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

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.

--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