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

Question

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.

This post has been migrated from (A51.SE)

Comments

http://rjlipton.wordpress.com/2012/01/30/perpetual-motion-of-the-21st-century/

This post has been migrated from (A51.SE)

---

Cross-posted from Physics.SE: http://physics.stackexchange.com/q/22120/2451

This post has been migrated from (A51.SE)

---

I don't know what your question (A) means. You seem to be assuming that quantum computers can do things classical computers cannot. Classical computation can do anything that quantum computation can, although it might possibly take exponentially longer.

This post has been migrated from (A51.SE)

---

Well, I am certainly aware that quantum computers are not a counterexample to the church-turing conjecture, and think I am reasonably aware of current understanding of BQP's position in the hierarchy of complexity classes. I was merely wondering, that similarly to your factoring algorithm being exponentially faster than any known classical algorithm, there are any examples of physical reactions, for example perturbation stabilization in a very large particle cluster, that could be shown to only be efficiently solved by a quantum computation.

This post has been migrated from (A51.SE)

---

And to further clarify, if the answer to question (A) is "no", i.e. the universe in no case functions like a quantum computer, despite having all the building blocks available, then I would tend to believe that our attempts to build a quantum computer would likely be futile. To be clear, I believe the answer is yes. –

This post has been migrated from (A51.SE)

---

Now that you've explained it, I see that it's a reasonable question.

This post has been migrated from (A51.SE)

---

@Grigori. Let me introduce you to some policies of this site. In general, it is *encouraged* not to extend your question in comments (you are commenting way too much in my answer). In order to keep the site useful, you should read the [FAQ](http://theoreticalphysics.stackexchange.com/faq#howtoask) to understand SE's policies on "how to ask" and "how to comment". We can not help you much with this question if you do not reorganise to meet the standards. I would personally delete (B) and (C) and try to focus (A) to make it more answerable.

This post has been migrated from (A51.SE)

---

Shortened and clarified question.

This post has been migrated from (A51.SE)

---

Thanks, now it is a bit more clear. Yet I think the connection of (A) with (B) and (C) is too weak. To a lot of people it would sound like you are asking three different questions. We try to have one question per post in this site, so why don't you drop them?

This post has been migrated from (A51.SE)

---

Also, I am not sure that there is a relation between speed of light and complexity in the sense you ask. Complexity theory is written in terms of the number of fundamental operations you need to do some operation. The fundamental operations have all a small (unit) cost. It looks like in your argument the speed of light could be related to the fundamental operations themselves, but not the number of times you can use them.

This post has been migrated from (A51.SE)

---

Updated (B) to clarify question further.

This post has been migrated from (A51.SE)

Answer 1

I just wanted to comment, but it was getting to long. I wanted to say something about (A).

Spin-flips are obviously in a natural correspondence with quantum computations and they occur all the time. Yet, I would not dare to argue that they are "only in correspondence with quantum computations", for you could make then "correspond" to absolutely anything that you want. In fact, you can also say that they correspond to classical coin-tosses. A more quantum (perhaps not very meaningful) example: you "could" still always say the universe is an analog quantum-computer which is simulating itself.

Maybe more relevant, why would any argument of this nature be a hint that quantum computers can be constructed? Assume that the argument you propose is valid in a strong sense and, in addition, that quantum computers can not be constructed. Since classical computers can be constructed. Then, you could perfectly argue that we "should" consider the universe to be a classical computer, using an $\epsilon$-far line of reasoning. Even if you do not believe on quantum computation, this does not look like a useful picture of reality for a modern physicist. What do you with all quantum effect that have been experimentally demonstrated?

This post has been migrated from (A51.SE)