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.

  • 2
    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.2012-01-29
  • 1
    See http://en.wikipedia.org/wiki/BQP#Relationship_to_other_complexity_classes.2012-01-29
  • 1
    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.2012-01-29
  • 1
    @PeterTaylor I think that most people consider it to be in NP-Intermediate, which may or may not be in P. http://en.wikipedia.org/wiki/NP-intermediate2012-01-30
  • 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

9

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.

  • 1
    BQP ?= NP is also an open problem, by the way (as is BQP ?= P).2012-01-29
  • 0
    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...2012-01-29
  • 5
    @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.2012-01-29
  • 0
    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"?2012-01-30
  • 0
    @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.2012-01-30
  • 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}$.