principleMinor
Quantum vs classic in NP-hard problems
Viewed 0 times
problemshardclassicquantum
Problem
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?
Solution
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}$.
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}$.
Context
StackExchange Computer Science Q#110448, answer score: 3
Revisions (0)
No revisions yet.