On quantum versions of record-breaking algorithms for SAT

Abstract

It is well known that a straightforward application of Grover's quantum search algorithm enables to solve SAT in O (2 n /2 ) steps. Ambainis (SIGACT News, 2004) observed that it is possible to use Grover's technique to similarly speed up a sophisticated algorithm for solving 3-SAT. In this note, we show that a similar speed up can be obtained for all major record-breaking algorithms for satisfiability. We also show that if we use Grover's technique only, then we cannot do better than quadratic speed up.