Is there any quantum algorithm (algorithm for quantum computers) for any NP-hard problem that has better runtime than the best known classic algorithm's runtime?
$\begingroup$
$\endgroup$
-
$\begingroup$ related: Can a parallel computer simulate a quantum computer?, Are there problems in which quantum computers are known to provide an exponential advantage?, and Is there any general statement about what kinds of problems can be solved more efficiently using a quantum computer? $\endgroup$ – glS Jun 10 '19 at 9:20
$\begingroup$
$\endgroup$
It is conjectured that the complexity of SAT on $n$ variables is $\tilde\Omega(2^n)$ (a version of this is SETH, the strong exponential time hypothesis). In contrast, Grover's algorithm solves it in $\tilde O(2^{n/2})$.
On the other hand, it is conjectured that quantum computers cannot solve NP-hard problems in polynomial time, that is $\mathsf{NP} \not\subseteq \mathsf{BQP}$.
answered Jun 10 '19 at 9:22
