3
$\begingroup$

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?

$\endgroup$
2
$\begingroup$

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

$\endgroup$

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.