chimera comments on 2011 Buhl Lecture, Scott Aaronson on Quantum Complexity - Less Wrong Discussion
You are viewing a comment permalink. View the original post to see all comments and the full post content.
You are viewing a comment permalink. View the original post to see all comments and the full post content.
Comments (4)
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:
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.