If someone were to build a universal quantum computer, would that have any implications on the problem of P vs. NP?
$\begingroup$
$\endgroup$
2
-
3$\begingroup$ I'm pretty sure this has been asked before but I can't find it. Can anyone else? $\endgroup$– David RicherbyApr 12, 2017 at 17:39
-
7$\begingroup$ Helpful reading in comic form. $\endgroup$– Dan BryantApr 12, 2017 at 23:09
Add a comment
|
4 Answers
$\begingroup$
$\endgroup$
1
No, there will be absolutely no implication, for several reasons:
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.
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".
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.
answered Apr 12, 2017 at 17:43
-
2$\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$– WolfLinkMay 24, 2021 at 6:53
$\begingroup$
$\endgroup$
2
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".
answered Apr 12, 2017 at 17:23
-
1$\begingroup$ You've missed $P\subsetneq BQP \subsetneq NP$, and $P=BQP\subsetneq NP$, either of which could be possible. $\endgroup$ 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$ Apr 13, 2017 at 13:34
$\begingroup$
$\endgroup$
1
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.
-
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 ♦Apr 27, 2018 at 13:07
$\begingroup$
$\endgroup$
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$.
