23
$\begingroup$

If someone were to build a universal quantum computer, would that have any implications on the problem of P vs. NP?

$\endgroup$
37
$\begingroup$

No, there will be absolutely no implication, for several reasons:

  1. The P vs. NP problem is about classical computation rather than quantum computation. Even if quantum computers could solve NP-hard problems in polynomial time (which we don't expect them to be able to do), it could still be the case that classical computers cannot solve them in polynomial time.

  2. Universal quantum computers, in a theoretical sense, are (to the best of my knowledge) already known to exist. These are just the quantum analogs of universal Turing machines: they can execute any given quantum "program".

  3. Both quantum computation and the P vs. NP problem are theoretical notions. What someone can construct in the physical world has absolutely no bearing on anything having to do with them.

Lieuwe Vinkhuijzen gave a different interpretation of your question:

Will quantum computers be able to solve NP-complete problems efficiently?

The expected answer is: no. So even in this sense, physical quantum computers won't enable us to solve NP-complete problems at will.

$\endgroup$
17
$\begingroup$

No implications are known either way: classical simulation of quantum computers tells us nothing about how hard NP search problems are; fast solutions to NP search problems tell us nothing about how fast quantum computers can be simulated classically. The following scenarios are possible:

  • $P=NP=BQP$
  • $P=NP\subsetneq BQP$
  • $P\subsetneq NP=BQP$
  • $P\subsetneq NP\subsetneq BQP$
  • $P\subsetneq NP$, $P\subsetneq BQP$ but $BQP$ and $NP$ are incomparable
  • NP problems require brute force classically, but are solved by fast (though not necessarily polynomial) quantum algorithms

The blog of one influential theoretical quantum computer scientist, Scott Aaronson, has the header "If you take just one piece of information from this blog: Quantum computers would not solve hard search problems instantaneously by just trying all solutions at once".

$\endgroup$
  • 1
    $\begingroup$ You've missed $P\subsetneq BQP \subsetneq NP$, and $P=BQP\subsetneq NP$, either of which could be possible. $\endgroup$ – A Simmons Apr 13 '17 at 13:27
  • 2
    $\begingroup$ @ASimmons True! Any conjecture which respects the usual $P\subseteq BQP$ and $P\subseteq NP$ is admissible. If we introduce the classes $BPP$ and $QMA$, which are mandatory to properly tell the story of how quantum computers relate to the $P$ vs $NP$ question anyway, then we get an exponential number of possible ways in which these classes might relate to one another. Here's to hoping we prune some of those worlds soon. $\endgroup$ – Lieuwe Vinkhuijzen Apr 13 '17 at 13:34
0
$\begingroup$

In one (considered unlikely) scenario, building a universal quantum computer would indeed have implications on the problem of P vs. NP.

This is expanding on the case mentioned by Yuval Filmus, "if quantum computers could solve NP-hard problems in polynomial time".

In such a situation, building a universal quantum computer vs just theoretically reasoning about one, would have implications for the P vs NP problem. It would allow for the possibility of just using quantum computers to search/find a proof that resolves P vs NP, which could then be verified by a classical computer.

However, as mentioned by the other answers, while there is no proof separating BQP and NP-complete, currently the evidence and expectations are that quantum computers will not be able to solve NP-complete problems efficiently.

$\endgroup$
  • $\begingroup$ "It would allow for the possibility of just using quantum computers to search/find a proof that resolves P vs NP, which could then be verified by a classical computer." In general, automated proving is considered somewhere in between uncomputable and undecidable. As QC isn't more 'powerful' (in terms of computability) than a Turing machine, merely 'faster' at some problems, I don't see how we could expect practical quantum algorithms assisting or automating proving P vs NP. Could you elaborate on this? $\endgroup$ – Discrete lizard Apr 27 '18 at 13:07

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.