37
$\begingroup$

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

$\endgroup$
4
  • 3
    $\begingroup$ I'm pretty sure this has been asked before but I can't find it. Can anyone else? $\endgroup$ Commented Apr 12, 2017 at 17:39
  • 7
    $\begingroup$ Helpful reading in comic form. $\endgroup$
    – Dan Bryant
    Commented Apr 12, 2017 at 23:09
  • $\begingroup$ Being able to build two-way quantum computers: fixing both initial state with state preparation, but also some final states with its CPT symmetry analog (e.g. pull-push, negative-positive radiation pressure, stimulated emission-absorption), in theory would allow to solve NP-complete problems: techrxiv.org/articles/preprint/… $\endgroup$
    – Jarek Duda
    Commented Aug 25, 2023 at 3:33
  • $\begingroup$ A machine taking n^100 nanoseconds takes about 30 trillion years to solve a problem with n=2. So P=NP may be of very little help. $\endgroup$
    – gnasher729
    Commented Sep 6, 2023 at 17:24

4 Answers 4

41
$\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$
2
  • 4
    $\begingroup$ This answer is more dodging the question than answering it. The reason why people are interested in P=NP is because of the implications of being able to make any real machine that can solve NP problems in a reasonable time. A quantum computer that can solve NP problems (or a proof that BQP=NP) would absolutely change the P=NP debate. $\endgroup$
    – WolfLink
    Commented May 24, 2021 at 6:53
  • $\begingroup$ @WolfLink I don't think it's dodging the question. The P vs. NP problem is a mathematical question not dependent on whether we can build a quantum computer. Whether quantum computers can solve NP-complete problems in polynomial time is a different question. If that's what Barte wanted to ask he should edit his question and drop the mention to P vs. NP. $\endgroup$
    – QuantumWiz
    Commented Sep 6, 2023 at 7:06
22
$\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$
3
  • 1
    $\begingroup$ You've missed $P\subsetneq BQP \subsetneq NP$, and $P=BQP\subsetneq NP$, either of which could be possible. $\endgroup$
    – A Simmons
    Commented Apr 13, 2017 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$ Commented Apr 13, 2017 at 13:34
  • $\begingroup$ If NP-complete problems require brute force classically, then quantum computers also need exponential run time by the BBBV theorem $\endgroup$ Commented Dec 6, 2023 at 22:46
1
$\begingroup$

If there would be an efficient quantum computer algorithm for $NP$-complete problems, then the $P$ vs. $NP$ problem would be still unsolved. But if one can show, that there is no quantum computer to solve an $NP$-hard problem in polynomial time, then $P$ is unequal $NP$, because $P\subseteq BQP$.

It is unlikely, that an $NP$-complete problem is in $BQP$. Due to the BBBV-Theorem Grover's algorithm is optimal for search problems $\{ x \in\{0,1\}^n\mid f(x)=1\}$ where f is a computable black-box function. In this case we need $\Theta(\sqrt(2^n))$ steps.

If $M$ is an arbitrary Turing machine, then $L(M)$ is undecidable. Assume there is an oracle to compute $M$. Then one need $\Theta(\sqrt(2^n))$ accesses to the oracle with a QC. The set $\{\langle M, x, 1^t \rangle \mid \text{ TM }M \text{ accepts }x\in \{0,1\}^n\text{ within }t\text{ steps} \}$ is $NP$-complete. If $t$ is big enough, then $M$ accepts an $x\in\{0,1\}^n$ within $t$ steps iff $x\in L(M)$. In this case a QC can not search faster than Grover-like algorithm. So, quantum computers still need exponential run time for $NP$-complete problems. There are good reasons to believe, that $NP$-hard problems are not in $BQP$.

$\endgroup$
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$
2
  • 1
    $\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
    Commented Apr 27, 2018 at 13:07
  • $\begingroup$ @Discretelizard automatic proving may be undecidable, but determining if there is a proof (in a specific formal proof system) of size less than $n$ is surely NP. We can then just run the algorithm for $n = 10^5$ or so (assuming its linear) for P=NP and P!=NP and then either we find the proof or we conclude its unprovable with a proof of length less than $10^5$, which is very strong evidence that it is undecidable. $\endgroup$ Commented Sep 6, 2023 at 17:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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