World's most popular travel blog for travel bloggers.

# [Answers] Does the fact that there exists a polynomial time quantum algorithm for integer factorization suggest that integer factorization is in P?

, ,
Problem Detail:

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?

No.

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:

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