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