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
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
The term ``observables'' here is used for quantum propositions, some of
which (the complementary ones) might not be co-measurable, see Gudder .
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.
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
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:
A stronger no-cloning theorem
Authors: Richard Jozsa (University of Bristol UK)
Comments: 4 pages. An error in version 1 corrected. Further interpretational
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
I could go on and on.
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