Church-Turing Thesis vs Quantum Measurement
In this paper, [quant-ph/0402128] Computable Functions, the Church-Turing Thesis and the Quantum Measurement Problem, the authors argue that quantum mechanics cannot break the "Turing barrier." If true, on the one hand, it would be bit disappointing that quantum computers will never do anything truly new (only faster, in some cases. It was already known that qubit-based quantum computers cannot break the "Turing barrier," but quantum mechanics was an open question). On the other hand, it is exciting that the Church-Turing thesis would seem to be not just a statement on the limits of classical computation, but also a limit of physical reality.
- posted by Jonathan @ 10:21 AM