Return to Answer

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, all problems that we consider 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)

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)

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, all problems that we consider 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 CH thesis does not care about computation time. The strong Extended Church-Turing thesis however, does get contradicted by this result (that is, if scalable quantum computers actually get built)

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, all problems that we consider 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)

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, all problems that we consider 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 CH thesis does not care about computation time. The strong Extended Church-Turing thesis however, does get contradicted by this result (that is, if scalabquantum computers

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, all problems that we consider 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 CH thesis does not care about computation time. The strong Extended Church-Turing thesis however, does get contradicted by this result (that is, if scalable quantum computers actually get built)