The P versus NP problem is a major unsolved problem in computer science. It asks whether every problem whose solution can be quickly verified can also be solved quickly. It is one of the seven Millennium Prize Problems selected by the Clay Mathematics Institute, each of which carries a US$1,000,000 prize for the first correct solution. My question is, can a quantum computer be used to solve P = NP?
2
-
3$\begingroup$ Please see cs.virginia.edu/~robins/The_Limits_of_Quantum_Computers.pdf here $\endgroup$– Mark SpinelliCommented Jul 28, 2020 at 1:58
-
3$\begingroup$ see cs.stackexchange.com/q/73864/26286 $\endgroup$– glS ♦Commented Jul 28, 2020 at 6:57
Add a comment
|
2 Answers
$\begingroup$
$\endgroup$
I see maybe four (4) ways to interpret the question.
The first asks whether we can use a quantum computer to efficiently solve $\mathsf{NP}$ problems. The class of problems efficiently solvable by a quantum computer is called $\mathsf{BQP}$, and so the question would ask whether $\mathsf{NP}\subseteq\mathsf{BQP}$. As is indicted in the comments, quantum computers are not known to efficiently solve arbitrary $\mathsf{NP}$ problems, and are suspected not to be able to.
The second asks whether a proof that $\mathsf{NP}\subseteq\mathsf{BQP}$ would suffice as a proof that $\mathsf{P}=\mathsf{NP}$. Although $\mathsf{P}\subseteq\mathsf{BQP}$, such a containment does not necessarily follow. For example, there may be problems in $\mathsf{BQP}$ that are not in $\mathsf{P}$ or even in $\mathsf{NP}$ - a famous candidate being related to knot theory. I don't think you'd win the Clay \$1M for such a containment. (You might get other riches, but that's a different story).
The third asks whether a proof that $\mathsf{NP}\not\subseteq\mathsf{BQP}$ would suffice as a proof that $\mathsf{P}\ne\mathsf{NP}$. However, even this does not follow.
The fourth interpretation asks whether a quantum computer could provide any leverage in answering the question of if the classical complexity class $\mathsf{P}$ is equal to $\mathsf{NP}$. That is, could one pose the $\mathsf{P}$ vs. $\mathsf{NP}$ problem as a a problem to be fed through a quantum computer? Although this may be interesting, I doubt one could envision a way to ask such a finite question.
The "standard model" that many people believe is that $\mathsf{P}\subsetneq\mathsf{NP}$, and further both $\mathsf{BQP}\not\subseteq\mathsf{NP}$ and $\mathsf{NP}\not\subseteq\mathsf{BQP}$ - that is, $\mathsf{NP}$ and $\mathsf{BQP}$ are incomparable. However, we are likely far away from proving any.
answered Jul 29, 2020 at 0:28
$\begingroup$
$\endgroup$
6
Maybe.
Grovers algorithm can definitely be used to reduce the time complexity of NP complete problems to $O(\sqrt{2^n})$ ; which isn't polynomial but is a lot faster. But the relationship between BQP and NP is unknown. For all we know $PH \subseteq BQP$ could be true.
It's thought to be unlikely but we cannot rule it out and in my opinion its useless to speculate without a proof.
-
5$\begingroup$ Welcome to QCSE. What evidence do you have that BQP is in NP? I think many people believe that there are problems in NP that are not in BQP, such as 3SAT, while there are many problems in BQP that are not in NP, such as calculating the Jones polynomial. That is, the two classes may indeed be incomparable. $\endgroup$ Commented Jan 7, 2022 at 3:55
-
$\begingroup$ @Mark S My mistake. There are BQP problems outside NP. But we really don't know much about BQP. For all we know $NP ⊆ BQP$ or even PH⊆BQP. could be true. More research needs to be done as Quantum computing is very new. It's not ruled out that we find an NP complete problem in BQP. Or we find a problem outside of NP in BQP. But to my knowledge, all current exclusive BQP problems are known to be in NP but not NP complete. But in my opinion its somewhat useless to speculate without a proof. We have been wrong about math before. And there is no reason to believe we couldn't be again. $\endgroup$ Commented Jan 7, 2022 at 21:58
-
2$\begingroup$ It is very fun and reasonable to speculate about the relation between BQP and NP. In particular this has led to a couple of recent breakthroughs. For example I really like this Quanta magazine article on Mahadev's approach to classical verification of BQP proofs, and also this article on Raz and Tal's breakthrough on whether BQP$\subseteq$PH. $\endgroup$ Commented Jan 7, 2022 at 22:39
-
$\begingroup$ @Mark S I meant not to assume the relationship between BQP and NP without a proof. Asking that question can lead us too other results, but it should not be done idlely. Math has given us some big surprises before and there is no reason to think it won't do so again. See the negative answer to the Entscheidungsproblem. That was a big surprise at the time. Again not saying that it is or isn't. I'm saying its useless to assume either way without a proof. $\endgroup$ Commented Jan 8, 2022 at 2:21
-
$\begingroup$ One concept: nonlinear quantum mechanics. It seems we still have no experimental evidence it's possible at all. $\endgroup$ Commented Jul 24, 2023 at 17:05