3 ms·

As was proved recently, there are quantum algorithms that can not: https://www.quantamagazine.org/finally-a-problem-that-only-quantum-computers-will-ever-be-abl

• atq2119 8y ago
  First of all, the paper that this article is reporting on doesn't actually prove a separation between quantum and classical algorithms at all. It's an oracle separation result, which makes it an important result in complexity theory, but not a statement about actual classical or quantum algorithms. Second, the result is unrelated to the Church-Turing thesis in the first place, since it's only about relative efficiency, whereas the Church-Turing thesis is about computability. Every quantum algorithm can be simulated by a classical computer, so quantum computing cannot possibly disprove the Church-Turing thesis. However, there's a stronger variant of the Church-Turing thesis which also takes performance into account, and it's plausible that quantum computers can contradict this stronger version (although we're very far away from actually proving that).