Possible Duplicate:
Is the universe a quantum computer - is light speed barrier a computational constraint

Cross-posting this question, since physics.stackexchange has not provided any answers.

There is currently a debate ongoing on leading maths blog Gödel’s Lost Letter, between Gil Kalai and Aram Harrow, with the former arguing that building a quantum computer may not be possible due to noise propagation, and the latter arguing to the contrary.

I am wondering if there is any argument to show that building a quantum computer is possible, by virtue of showing that quantum computation is evident in the physical world.

So the question is:

(A) Are there any known examples of physical interactions where macro level state transitions could be determined to only be in correspondence with an underlying quantum computation? I.e. similarly to Shor's algorithm being exponentially faster than any known classical factoring algorithm, are there any examples of known physical processes, for example perturbation stabilization in a very large particle cluster, that could be shown, assuming P<>NP, to only be efficiently solved by a quantum computation.

Some, I admit highly speculative, additional questions would then be:

(B) Is the speed of light barrier possibly a natural computational limit of our particular universe, so that for the computational complexity class of quantum mechanics, working on an underlying relational network-like spacetime structure, this is the maximum speed that the computational rules can move a particle/wave representation through a network region of the lowest energy/complexity (i.e. a vacuum)?

(C) Is quantum mechanics an actual necessity for the universe to follow classical physical laws at the macro level? The informal argument being that in many-to-many particle quantum level interactions, only the capability of each particle to compute in parallel an infinite or quantum-quasi-infinite number of paths is what allows the universe to resolve a real-time solution at the macro level.

Requesting references to research along these lines, or any arguments to support or contradict these speculations.


merged by David Z May 7 '12 at 6:54

This question was merged with Is the universe a quantum computer - is light speed barrier a computational constraint because it is an exact duplicate of that question.