<p>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.</p>

<p>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))$.</p>

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

CC BY-SA 4.0
2020-05-18T18:56:43.990Z
Can you give a little more details about how to apply amplitude amplification together with Schöning algorithm?
Özlem Salehi
CC BY-SA 3.0
2016-08-17T20:34:41.390Z
2016-08-17T20:34:41.390Z
Robin Kothari
<p>I think one can obtain a non-trivial upper bound from quantum computing by speeding up the randomized algorithms of Sch&ouml;ning for 3-SAT. The algorithm of Sch&ouml;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. </p>

CC BY-SA 3.0
2016-08-17T20:48:32.823Z
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!
Alex Meiburg
CC BY-SA 3.0
2016-08-18T11:57:37.027Z
You might also enjoy this paper: http://digitalcommons.utep.edu/cgi/viewcontent.cgi?article=1256&context=cs_techrep
Martin Schwarz
CC BY-SA 3.0
2016-08-17T20:02:08.120Z
2016-08-18T09:22:11.890Z
2016-08-18T09:22:11.890Z
wwjohnsmith1
<p>Classical algorithms can solve 3-SAT in $1.3071^n$ time (randomized) or $1.3303^n$ time (deterministic). (Reference: <a href="https://cstheory.stackexchange.com/questions/1060/best-upper-bounds-on-sat">Best Upper Bounds on SAT</a> )</p>

<p>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 -- <em>almost</em> as good?)</p>

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

CC BY-SA 4.0
2021-12-02T19:10:58.133Z
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?
Ron Cohen
CC BY-SA 4.0
2022-03-16T17:17:28.990Z
@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)$?
Geremia
CC BY-SA 4.0
2022-03-16T17:21:10.400Z
Couldn't Grover be used for DPLL? DPLL is a search algorithm.
Geremia
CC BY-SA 4.0
2022-03-16T20:29:26.597Z
@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.
Alex Meiburg
<quantum-computing><sat><exp-time-algorithms>
Do any quantum algorithms improve on classical SAT?
Alex Meiburg
# Do any quantum algorithms improve on classical SAT?

(Asked by: username_0 on 2016-08-17)

Classical algorithms can solve 3-SAT in $1.3071^n$ time (randomized) or $1.3303^n$ time (deterministic). (Reference: [Best Upper Bounds on SAT](https://cstheory.stackexchange.com/questions/1060/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.

**Tags:** quantum-computing, sat, exp-time-algorithms
> **Comments:**
> **username_1**: 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?  
> **username_2**: @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)$?  
> **username_2**: Couldn't Grover be used for DPLL? DPLL is a search algorithm.  
> **username_0**: @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.  

---

## 2 answers

### Answer by username_5 on 2016-08-17. Score: 31 | Accepted answer

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.

> **Comments:**
> **username_0**: 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!  
> **username_6**: You might also enjoy this paper: http://digitalcommons.utep.edu/cgi/viewcontent.cgi?article=1256&context=cs_techrep  

---

### Answer by username_3 on 2016-08-17. Score: 42

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

> **Comments:**
> **username_4**: Can you give a little more details about how to apply amplitude amplification together with Schöning algorithm?  

---

