2 Clarification of Shor's algorithm result

First, Alon's summary of applications of quantum computing is not complete. What Shor's algorithm (or more precisely, Simon-Shor-Kitaev) really does is that it fully analyzes any finite abelian group in polynomial time (polynomial in log |G|), provided that inverses and the group law are available in black-box form, and elements have unique names. Thus, you can factor N by analyzing the multiplicative group of Z/N. You can analyze elliptic curves, other abelian varieties, D-modules, etc. You can find the cardinality, find orders of elements, compute discrete logarithms, etc.

There are other quantum algorithms that do black-box things that certainly look like they could be useful. What makes Shor's algorithm special is that there are lots of obvious ways to replace the black box by a "white box", i.e., by an explicit computational problem.

These algorithms provide strong evidence that the quantum polynomial time class, BQP, is larger than P, polynomial time (and BPP, randomized polynomial time).

And that is the original question about the strong Church-Turing thesis. The strong Church-Turing thesis posits that all natural models of polynomial-time computation are equivalent. At the moment, it looks like there are two natural models, P (which is conjectured to equal BPP) and BQP. As Alon says, factoring is not known to be NP-complete, but there is nothing unfortunate about that. It would surprise a lot of people if NP turned out to be a natural class, and it is a standard conjecture that BQP does not contain NP.

1

First, Alon's summary of applications of quantum computing is not complete. What Shor's algorithm (or more precisely, Simon-Shor-Kitaev) really does is that it fully analyzes any finite abelian group in polynomial time (polynomial in log |G|), provided that inverses and the group law are available in black-box form. Thus, you can factor N by analyzing the multiplicative group of Z/N. You can analyze elliptic curves, other abelian varieties, D-modules, etc. You can find the cardinality, find orders of elements, compute discrete logarithms, etc.

There are other quantum algorithms that do black-box things that certainly look like they could be useful. What makes Shor's algorithm special is that there are lots of obvious ways to replace the black box by a "white box", i.e., by an explicit computational problem.

These algorithms provide strong evidence that the quantum polynomial time class, BQP, is larger than P, polynomial time (and BPP, randomized polynomial time).

And that is the original question about the strong Church-Turing thesis. The strong Church-Turing thesis posits that all natural models of polynomial-time computation are equivalent. At the moment, it looks like there are two natural models, P (which is conjectured to equal BPP) and BQP. As Alon says, factoring is not known to be NP-complete, but there is nothing unfortunate about that. It would surprise a lot of people if NP turned out to be a natural class, and it is a standard conjecture that BQP does not contain NP.