Question

First of all, I apologize if this has been asked, but I truly didn't find anything.

I've stumbled across this article. It says that there is a problem that only Quantum Computers can solve. In my understanding, this should mean, intuitively, that this problem is "effectively computable", since we have an effective, real method to compute it: build a quantum computer and solve it. But, since a Turing Machine (turing machines are not quantum computers, I think?) can not solve it, this is not turing-computable.

Hence, does this mean that "effectively computable" and "turing-computable" are not the same concept? So, is the Church-Turing thesis wrong? My intuition says "no", because in that case, this would be very big news. So, if not, why not?

Also, I am aware that there exist already models of computation that are more powerful than turing machines, but those are only "theoretic", aren't they? Quantum computers, on the other hand, are physically buildable.

No correct solution

Licensed under: CC-BY-SA with attribution
Not affiliated with cs.stackexchange
scroll top