JoshuaZ comments on Can somebody explain this to me?: The computability of the laws of physics and hypercomputation - Less Wrong

12 Post author: ChrisHallquist 21 April 2013 09:22PM

You are viewing a comment permalink. View the original post to see all comments and the full post content.

Comments (53)

You are viewing a single comment's thread. Show more comments above.

Comment author: JoshuaZ 22 April 2013 04:18:22AM *  2 points [-]

if you could build one, actually lets you solve more problems efficiently than you could with a classical computer; this is the question of whether P = BQP.

This isn't quite what this question asks. We know that some things are faster with a quantum computer than what can be one in the best case classical situation. Grover's algorithm is one example. The question of whether P=BQP is one formulation of that for yes and no questions. But even this isn't quite accurate. For example, it could be that quantum computers can do some extremely high degree polynomial speed-up even while P=BQP. But this is essentially a minor nitpick.