You're looking at Less Wrong's discussion board. This includes all posts, including those that haven't been promoted to the front page yet. For more information, see About Less Wrong.

chimera comments on 2011 Buhl Lecture, Scott Aaronson on Quantum Complexity - Less Wrong Discussion

8 Post author: p4wnc6 09 July 2011 04:43AM

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

Comments (4)

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

Comment author: [deleted] 09 July 2011 11:10:20AM 0 points [-]

Thanks for pointing out my mistake: where I wrote the precise but wrong "polynomial time and space physical processes can be computed in polynomial time", Scott wrote the imprecise but not-wrong "efficiently realizable physical processes can be computed in polynomial time" and as you demonstrated mine doesn't make sense.

On the other hand, Scott wrote in lecture 14 of his Quantum Computing Since Democritus course:

the argument is that quantum computing must be impossible because it violates the Extended Church-Turing Thesis. That is, we know that quantum computing can't be possible (assuming BPP≠BQP), because we know that BPP defines the limit of the efficiently computable. So, we have this thesis, and quantum computing violates the thesis, so it must be impossible

More recently, there was a lot of discussion in the comments of his blog post about various different attempts at defining an "extended Church-Turing thesis". There doesn't seem to be a good consensus.