8
$\begingroup$

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.

  • 1
    [tag:complexity] theory questions are welcome on [math.se], even the elementary ones like this one. The scope of [cstheory.se] is restricted to research level questions.2012-01-30

2 Answers 2

10

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.

  • 0
    The class $\mathsf{P}$ is defined using Deterministic TMs, if you change the model you ma get different classes, e.g. if you use NTMs you will get $\mathsf{NP}$, while at the computability level they are the same. If you change the model to QTM, in the same way if you will get a different class. Check the Complexity Zoo if you want to know more about these classes and their relations.2012-01-31
10

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