Do any quantum algorithms improve on classical SAT?

Question

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.

Answer 1

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.

Answer 2

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).