Just as the title says: Does the fact that there exists a polynomial time quantum algorithm for integer factorization suggest that integer factorization is in P? Additionally, if one could show that a problem known to be in NP had a polynomial time quantum solution, would that be enough to show that P=NP?

  • $\begingroup$ Why do you think that it might suggest that? This would be a better question if you edited it to share your thoughts -- we might be in a better position to give you answers that you'll find more useful. $\endgroup$ – D.W. Jul 21 '16 at 17:45
  • $\begingroup$ @D.W. I'm far from an expert on the topic but I took a parallel computing course at my university. For my final project in the course I wrote a parallel algorithm to do integer factorization of large numbers. I was talking to one of my professors about the topic and we got onto the discussion of the time complexity of the problem and he mentioned that the fact that there is a polynomial time quantum solution to the integer factorization problem might be evidence that it belongs to P. So, I wanted to get some more input on the topic. $\endgroup$ – Budge Jul 21 '16 at 20:32


The class $P$ refers to the classical Turing machine model, we don't know if $BQP\subseteq P$ (we suspect that it isn't), thus this does not mean that factoring is in $P$. We don't know how to simulate a quantum algorithm in a classical machine with only polynomial slowdown (the naive translation would result in an exponential algorithm for factoring).

Many problems in $NP$ have a quantum polynomial time solution, and also classical polynomial time solution, since $P\subseteq NP$. See our reference question for an overview and precise definitions.

The more interesting question would be if quantum computers can solve NP-hard problems efficiently, or formally, if $NP\subseteq BQP$. We suspect that this statement is false, though even $PH\subseteq BQP$ is still open. Proving $NP\not\subset BQP$ would also in turn prove that $P\neq NP$ (since $P\subseteq BQP)$.

It is also worth mentioning that factoring in not known to be NP-hard (and believed not to be) so we can still have both $NP\not\subset BQP$, and a polynomial algorithm for factoring in a quantum computer.

See these questions:

Consequences of SAT∈BQP,

Can a parallel computer simulate a quantum computer? Is BQP inside NP?,

for a discussion on the possibility of $NP\subseteq BQP$.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.