Why is integer factorization considered to be in NP if a quantum computer can compute a factorization in polynomial time?

Question

Sorry if this seems off topic, the cstheory guys told me it was off topic over there, and sent me here.

Shor's algorithm on a quantum computer can solve an integer factorization problem in polynomial time. So why is this problem considered to not be in P? Do quantum computers not count? I have looked around and see some discussion on the matter, but no clear answers.

Answer 1

In short, quantum computers don't count. We mean a lot when we say that something is in P or NP of BPP, whatnot. In particular, P means that the problem can be solved by a deterministic Turing machine in polynomial time. Quantum computers are neither deterministic nor Turing.

This is why factoring is in BQP, which is like quantum polynomial time.

Answer 2

The title of the question is different from the question's content. Since the version you asked over cstheory is the one in the title, I will answer that.

Factoring is both in $\mathsf{NP}$ and $\mathsf{BQP}$ (polynomial time quantum TM). This is not strange at all, e.g. every problem in $\mathsf{P}$ is also in both of them. Being in $\mathsf{NP}$ does not mean the problem is difficult, it is an upperbound on difficulty of the problem. A problem in $\mathsf{NP}$ can be arbitrary easy. I am guessing that you are confusing $\mathsf{NP}$ and $\mathsf{NP\text{-}complete}$. It is not known (in fact very unlikely) that Factoring is $\mathsf{NP\text{-}complete}$.