Can quantum computers be used to solve P = NP

Quantum Computing Asked by Peter Morgan on February 27, 2021

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?

One Answer

I see maybe four (4) ways to interpret the question.

  1. 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}subseteqmathsf{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.

  2. The second asks whether a proof that $mathsf{NP}subseteqmathsf{BQP}$ would suffice as a proof that $mathsf{P}=mathsf{NP}$. Although $mathsf{P}subseteqmathsf{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).

  3. The third asks whether a proof that $mathsf{NP}notsubseteqmathsf{BQP}$ would suffice as a proof that $mathsf{P}nemathsf{NP}$. However, even this does not follow.

  4. 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}subsetneqmathsf{NP}$, and further both $mathsf{BQP}notsubseteqmathsf{NP}$ and $mathsf{NP}notsubseteqmathsf{BQP}$ - that is, $mathsf{NP}$ and $mathsf{BQP}$ are incomparable. However, we are likely far away from proving any.

Answered by Mark S on February 27, 2021

Add your own answers!

Ask a Question

Get help from others!

© 2024 All rights reserved. Sites we Love: PCI Database, UKBizDB, Menu Kuliner, Sharing RPP