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