Ray writes
1) By definition, if something can be computed by a turing machine, then it is an algorithm (Lewis and Papadimitriou)
Suppose we have a spatial transform performed by light flowing through a grid. Is that an algorithm? Perhaps it is, but I am about to describe a case that will stretch your definition of algorithm rather more drastically.
2) a quantum computer can be simulated by a TM with exponential slowdown. (claimed by you on the Extropians list, but also claimed by Feynmann I believe, not about qm computers, but qm systems in general)
True.
then by (1) and (2), it follows that 3) quantum computers are algorithmic (if not, it would contradict 2) and possibly 1)
Suppose our quantum system has thirty two bytes. Then a classical simulation of our quantum system would require 2^257 words of memory The computer would require more matter than exists in the universe. Each step of the simulation would require 2^514 steps by the computer, which even for a computer constructed of very tiny components out of all the matter in the universe would still require vastly longer than the entire lifetime of the univers.
It doesn't matter how slow the turing machine runs the simulation because we allow an arbitrary time along with the infinite tape to complete the computation. -Ray
It does not sound like a very useful algorithm, nor is it one that is easy to describe. The difference is like the difference in my example of light flowing through a grid, as against a fourier transform etc, but the difference is enormously greater. You say it makes no difference by definition. I say such definitions are misleading when we discuss how problems are to be solved. -- --------------------------------------------------------------------- We have the right to defend ourselves and our property, because of the kind of animals that we James A. Donald are. True law derives from this right, not from the arbitrary power of the omnipotent state. jamesd@netcom.com