• Register
PhysicsOverflow is a next-generation academic platform for physicists and astronomers, including a community peer review system and a postgraduate-level discussion forum analogous to MathOverflow.

Welcome to PhysicsOverflow! PhysicsOverflow is an open platform for community peer review and graduate-level Physics discussion.

Please help promote PhysicsOverflow ads elsewhere if you like it.


PO is now at the Physics Department of Bielefeld University!

New printer friendly PO pages!

Migration to Bielefeld University was successful!

Please vote for this year's PhysicsOverflow ads!

Please do help out in categorising submissions. Submit a paper to PhysicsOverflow!

... see more

Tools for paper authors

Submit paper
Claim Paper Authorship

Tools for SE users

Search User
Reclaim SE Account
Request Account Merger
Nativise imported posts
Claim post (deleted users)
Import SE post

Users whose questions have been imported from Physics Stack Exchange, Theoretical Physics Stack Exchange, or any other Stack Exchange site are kindly requested to reclaim their account and not to register as a new user.

Public \(\beta\) tools

Report a bug with a feature
Request a new functionality
404 page design
Send feedback


(propose a free ad)

Site Statistics

205 submissions , 163 unreviewed
5,064 questions , 2,215 unanswered
5,347 answers , 22,734 comments
1,470 users with positive rep
818 active unimported users
More ...

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

+ 0 like - 1 dislike

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)
asked Mar 11, 2012 in Theoretical Physics by Grigori Strassmann (-5 points) [ no revision ]
Most voted comments show all comments
@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)
Most recent comments show all comments
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)

1 Answer

+ 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 jbvega (285 points) [ no revision ]

Your answer

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):
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:
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).
Please complete the anti-spam verification

user contributions licensed under cc by-sa 3.0 with attribution required

Your rights