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.

jsteinhardt 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.

Article Navigation

Comments (4)
Tags: complexity quantum computation

Comments (4)

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

Comment author: jsteinhardt 09 July 2011 09:38:53AM 3 points [-]

In the talk he gives lots of examples and evidence for a sharpened version "the extended Church-Turing thesis" which says that polynomial time and space physical processes can be computed in polynomial time. It's true that quantum computation can compute some things more efficiently but we don't have any reason to think they break this thesis yet.

Can you elaborate on this a bit? There are problems that are suspected to not be in P (such as factoring) but that are in BQP. Since factoring is in BQP, we could create a physical process that factors numbers in polynomial time, and would be (conjecturally) unable to simulate that process in polynomial time.

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.

Powered by Reddit Powered by Reddit