patternModerate
Does this article imply that Turing-Computability is not the same as "effectively computable"?
Viewed 0 times
thisimplysamethecomputablecomputabilityeffectivelythatdoesturing
Problem
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, could be physically buildable.
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, could be physically buildable.
Solution
First of all, quantum computers (or rather, theoretical quantum computation models), are in fact, not more powerful than Turing machines, in the sense that they can be emulated on a Turing machine and can emulate a Turing machine themselves. Note that the article itself doesn't use the word 'computable', and for a good reason. Computability isn't what they're talking about.
The difference between quantum computers and classical ones is speed. This is where complexity theory comes in. Here, we want to know more than just whether a problem is computable. Most problems considered by this field are computable, but some may be very inefficient to solve in terms of asymptotic running time or memory usage.
The polynomial Hierarchy (PH) is a big class that contains problems which are basically an alternating game between non-deterministically guessing a solution and finding one (or rather, alternating existential and universal quantifiers), but all in polynomial time. P is the most basic class inside the PH and roughly corresponds to problems we can solve in reasonable time on classical computers. NP is another basic subclass of PH.
BQP is the analogue for P for quantum computers. Well, not entirely, BQP is closer to BPP, where we allow our classical computer to give a wrong answer with only small probability. The quantum effects cannot really be exploited without involving probability in a meaningful manner. In any case, BPP is still within PH.
This article is about a problem that has been proven to not lie in PH, but in BQP. In a way, the 'quantum step' allows to solve a problem that isn't even close to P or BPP classically, not even in the same infinite hierarchy, in polynomial time on a quantum computer. So, this is strong evidence for the (theoretical) power of the quantum computing model.
As for the Church-Turing thesis, quantum computation being faster than classical does not contradict it, as the thesis does not care about computation time. The stronger Extended Church-Turing thesis however, does get contradicted by this result (that is, if scalable quantum computers actually get built)
The difference between quantum computers and classical ones is speed. This is where complexity theory comes in. Here, we want to know more than just whether a problem is computable. Most problems considered by this field are computable, but some may be very inefficient to solve in terms of asymptotic running time or memory usage.
The polynomial Hierarchy (PH) is a big class that contains problems which are basically an alternating game between non-deterministically guessing a solution and finding one (or rather, alternating existential and universal quantifiers), but all in polynomial time. P is the most basic class inside the PH and roughly corresponds to problems we can solve in reasonable time on classical computers. NP is another basic subclass of PH.
BQP is the analogue for P for quantum computers. Well, not entirely, BQP is closer to BPP, where we allow our classical computer to give a wrong answer with only small probability. The quantum effects cannot really be exploited without involving probability in a meaningful manner. In any case, BPP is still within PH.
This article is about a problem that has been proven to not lie in PH, but in BQP. In a way, the 'quantum step' allows to solve a problem that isn't even close to P or BPP classically, not even in the same infinite hierarchy, in polynomial time on a quantum computer. So, this is strong evidence for the (theoretical) power of the quantum computing model.
As for the Church-Turing thesis, quantum computation being faster than classical does not contradict it, as the thesis does not care about computation time. The stronger Extended Church-Turing thesis however, does get contradicted by this result (that is, if scalable quantum computers actually get built)
Context
StackExchange Computer Science Q#108757, answer score: 18
Revisions (0)
No revisions yet.