9
$\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.

$\endgroup$
5
  • 2
    $\begingroup$ 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. $\endgroup$ Jan 29, 2012 at 22:11
  • 1
    $\begingroup$ See en.wikipedia.org/wiki/…. $\endgroup$ Jan 29, 2012 at 22:15
  • 1
    $\begingroup$ 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. $\endgroup$ Jan 29, 2012 at 23:51
  • 1
    $\begingroup$ @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 $\endgroup$ Jan 30, 2012 at 2:32
  • 1
    $\begingroup$ 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. $\endgroup$
    – Kaveh
    Jan 30, 2012 at 6:05

2 Answers 2

11
$\begingroup$

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.

$\endgroup$
6
  • 1
    $\begingroup$ BQP ?= NP is also an open problem, by the way (as is BQP ?= P). $\endgroup$
    – Lopsy
    Jan 29, 2012 at 22:20
  • $\begingroup$ 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... $\endgroup$ Jan 29, 2012 at 22:33
  • 6
    $\begingroup$ @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. $\endgroup$
    – sxd
    Jan 29, 2012 at 22:38
  • $\begingroup$ 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"? $\endgroup$ Jan 30, 2012 at 3:15
  • 1
    $\begingroup$ @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. $\endgroup$ Jan 30, 2012 at 4:05
10
$\begingroup$

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

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .