Classical algorithms can solve 3-SAT in $1.3071^n$ time (randomized) or $1.3303^n$ time (deterministic). (Reference: Best Upper Bounds on SAT )

For comparison, using Grover's algorithm on a quantum computer would look for and provide a solution in $1.414^n$, randomized. (This may still require some knowledge of how many solutions there may or may not be, I'm not sure how necessary those bounds still are.) This is clearly significantly worse. Are there are any quantum algorithms that do better than the best classical algorithms (or at least -- almost as good?)

Of course the classical algorithms could be used on a quantum computer assuming sufficient working space; I'm wondering about inherently quantum algorithms.

  • $\begingroup$ I wonder if besides the academic interest, is this industrially interesting? I mean - what are the SAT practical problems that the world is still struggling to solve, and improvement of SAT by SQRT, will bring justification for a quantum computer? $\endgroup$
    – Ron Cohen
    Commented Dec 2, 2021 at 19:10
  • 1
    $\begingroup$ @RonCohen "what are the SAT practical problems that the world is still struggling to solve" So many problems can be reformulated in terms of a SAT problem; Knuth: "SAT is evidently a killer app, because it is key to the solution of so many other problems." Also, what do you mean by "SQRT"? $\mathcal{O}(\sqrt n)$? $\endgroup$
    – Geremia
    Commented Mar 16, 2022 at 17:17
  • $\begingroup$ Couldn't Grover be used for DPLL? DPLL is a search algorithm. $\endgroup$
    – Geremia
    Commented Mar 16, 2022 at 17:21
  • $\begingroup$ @Geremia Yes, my understanding now (5 years later -- I've learned a lot) is that you certainly could. While that would likely be the first practical improvement on SAT, I think it's less theoretically useful as the bounds on DPLL are not that good iirc. $\endgroup$ Commented Mar 16, 2022 at 20:29

2 Answers 2


I think one can obtain a non-trivial upper bound from quantum computing by speeding up the randomized algorithms of Schöning for 3-SAT. The algorithm of Schöning runs in time $(4/3)^n$ and using standard amplitude amplification techniques one can obtain a quantum algorithm that runs in time $(2/\sqrt{3})^n=1.15^n$ which is significantly faster than the classical algorithm.

  • 1
    $\begingroup$ Nice, that looks right. Shows that I should've looked at the classical algorithms once before asking! :) Some more skimming suggests the best randomized algorithm for (non-necessarily unique) 3-SAT is $1.32065^n$, so I guess we could expect $1.1492^n$ from a quantum computer... thanks! $\endgroup$ Commented Aug 17, 2016 at 20:48
  • 2
    $\begingroup$ You might also enjoy this paper: digitalcommons.utep.edu/cgi/… $\endgroup$ Commented Aug 18, 2016 at 11:57

Indeed, as wwjohnsmith1 said, you can get a square root speed-up over Schöning's algorithm for 3-SAT, but also more generally for Schöning's algorithm for k-SAT. In fact, many randomized algorithms for k-SAT can be implemented quadratically faster on a quantum computer.

The reason for this general phenomenon is the following. Many randomized algorithms for k-SAT that run in time $O(T(n) \mathrm{poly}(n))$ (where $T(n)$ is some exponentially growing function of $n$) actually do something stronger. At their core, there is a polynomial-time algorithm that outputs a satisfying assignment, if one exists, with probability at least $1/T(n)$. From this it is clear that if you repeat this poly-time algorithm $O(T(n))$ many times and accept if any of the runs returns a solution, you will get a randomized algorithm for k-SAT that runs in time $O(T(n) \mathrm{poly}(n))$.

Now instead of running this algorithm $O(T(n))$ times, you can run amplitude amplification on this poly-time algorithm. Amplitude amplification is a general quantum algorithm that can decide if another algorithm accepts with probability 0 or with probability $1/T$ using only $O(\sqrt{T})$ uses of this algorithm. Applying amplitude amplification to such a k-SAT solver will immediately yield a quantum algorithm for k-SAT with running time $O(\sqrt{T(n)}\mathrm{poly}(n))$, which is quadratically faster (ignoring the poly(n) term).

  • 4
    $\begingroup$ Can you give a little more details about how to apply amplitude amplification together with Schöning algorithm? $\endgroup$ Commented May 18, 2020 at 18:56

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.