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

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.

-
Your answer is right. NP is defined in terms of a specific model of computation, the Turing machine or equivalent. Of course factorization could be also be in P. We just don't know. – André Nicolas Jan 29 '12 at 22:11
– Dan Brumleve Jan 29 '12 at 22:15
Do you have a reference for integer factorisation being considered to not be in P? I don't believe that many people have strong beliefs either way. – Peter Taylor Jan 29 '12 at 23:51
@PeterTaylor I think that most people consider it to be in NP-Intermediate, which may or may not be in P. en.wikipedia.org/wiki/NP-intermediate – Real John Connor Jan 30 '12 at 2:32
complexity theory questions are welcome on Mathematics, even the elementary ones like this one. The scope of Theoretical Computer Science is restricted to research level questions. – Kaveh Jan 30 '12 at 6:05

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.

-
BQP ?= NP is also an open problem, by the way (as is BQP ?= P). – Lopsy Jan 29 '12 at 22:20
What do you mean by "Quantum computers are neither deterministic nor Turing?" Surely a quantum Turing machine is not less powerful then a classical Turing machine, and as I understand it, nothing is suspected of being more powerful than a Turing machine... – Real John Connor Jan 29 '12 at 22:33
@RealJohnConnor we are not talking about decidability, but about how many time or space it needs to compute. Computational complexity only considers problems which are decidable. – sxd Jan 29 '12 at 22:38
I always understood that any problem in BQP was at the very least in EXP, just by computing out the (exponentially large) state descriptions. Further, I figured that "Turing" here refers to "Turing-complete," that is, simulatable by a Turing machine, and capable of simulating a Turing machine. How, then do quantum computers fail to be "Turing"? – Louis Wasserman Jan 30 '12 at 3:15
@LouisWasserman That was more or less my question. From what I can figure out, quantum Turing machines are Turing-complete. However they are able to compute more efficiently than we have figured out how to compute with classical Turing machines. So they are not more powerful, only more efficient. At least that's what I am taking away from this. – Real John Connor Jan 30 '12 at 4:05

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}$.

-