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?

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}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.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).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.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

Get help from others!

Recent Questions

- How can I transform graph image into a tikzpicture LaTeX code?
- How Do I Get The Ifruit App Off Of Gta 5 / Grand Theft Auto 5
- Iv’e designed a space elevator using a series of lasers. do you know anybody i could submit the designs too that could manufacture the concept and put it to use
- Need help finding a book. Female OP protagonist, magic
- Why is the WWF pending games (“Your turn”) area replaced w/ a column of “Bonus & Reward”gift boxes?

Recent Answers

- haakon.io on Why fry rice before boiling?
- Jon Church on Why fry rice before boiling?
- Peter Machado on Why fry rice before boiling?
- Joshua Engel on Why fry rice before boiling?
- Lex on Does Google Analytics track 404 page responses as valid page views?

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