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?

, , No Comments
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?

Asked By : Budge

Answered By : Ariel

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:

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

Best Answer from StackOverflow

Question Source : http://cs.stackexchange.com/questions/60842

3.2K people like this

 Download Related Notes/Documents

0 comments:

Post a Comment

Let us know your responses and feedback