4 ms·
Yes, quantum supremacy disproves the extended church-turing thesis (Bernstein-Vazirani). This thesis states that any computation that can be computed efficientl
by joak 7y ago
Yes, quantum supremacy disproves the extended church-turing thesis (Bernstein-Vazirani). This thesis states that any computation that can be computed efficiently can be computed efficiently with a classical computer (ie a Turing machine).
ECT thesis means that quantum computers will never be able to compute something significantly faster that classical ones.
However, technically, google haven't proved yet quantum supremacy since they just did the classical calculation using the best known classical algorithm. And there is no proof that there is no significantly better algorithm.
But this not a serious objection, no one thinks that there is an exponentially better way of classically simulating quantum computers.
- abdullahkhalids 7y ago> However, technically, google haven't proved yet quantum supremacy To be absolutely clear, an experiment (or a set of replicated experiments) can't prove quantum supremacy. Quantum supremacy is a statement about about the asymptotic behavior of quantum and classical computers, and obviously, a finite set of data points cannot prove anything about asymptotes. What these experiments are doing are gathering evidence against the extended Church-Turing thesis - in the same way other experiments are used to gather evidence in favor of/against general relativity or some other physical theory. The proof of quantum supremacy within the framework of the currently accepted laws of physics (quantum theory), has to be a mathematical proof. Currently, we have no idea how to construct such a proof.