Computational sentences to ponder

From a very smart correspondent:

“incidentally forgot to say that this is
basically the death of the
“extended Church-Turing hypothesis”
which roughly states that all reasonable computational models can be simulated on a Turing machine with only polynomial cost.  but it now sure looks like quantum computers are physically realisable and are non-polynomially faster

– in other words we now almost certainly know that computational complexity does depend on laws of physics”

The indentation was his, and with reference to this earlier reported quantum computational result from China.


Comments for this post are closed