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

+ 0 like - 1 dislike
723 views

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.

(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)
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)
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)

+ 1 like - 0 dislike

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)
answered Mar 12, 2012 by (285 points)

 Please use answers only to (at least partly) answer questions. To comment, discuss, or ask for clarification, leave a comment instead. To mask links under text, please type your text, highlight it, and click the "link" button. You can then enter your link URL. Please consult the FAQ for as to how to format your post. This is the answer box; if you want to write a comment instead, please use the 'add comment' button. Live preview (may slow down editor)   Preview Your name to display (optional): Email me at this address if my answer is selected or commented on: Privacy: Your email address will only be used for sending these notifications. Anti-spam verification: If you are a human please identify the position of the character covered by the symbol $\varnothing$ in the following word:p$\hbar$ysicsOverflo$\varnothing$Then drag the red bullet below over the corresponding character of our banner. When you drop it there, the bullet changes to green (on slow internet connections after a few seconds). To avoid this verification in future, please log in or register.