Solving boolean satisfiability problems with the quantum approximate optimization algorithm

The quantum approximate optimization algorithm (QAOA) is one of the most prominent proposed applications for near-term quantum computing. Here we study the ability of QAOA to solve hard constraint satisfaction problems, as opposed to optimization problems. We focus on the fundamental boolean satisfiability problem, in the form of random $k$-SAT. We develop analytic bounds on the average success probability of QAOA over random boolean formulae at the satisfiability threshold, as the number of variables $n$ goes to infinity. The bounds hold for fixed parameters and when $k$ is a power of 2. We complement these theoretical results with numerical results on the performance of QAOA for small $n$, showing that these match the limiting theoretical bounds closely. We then use these results to compare QAOA with leading classical solvers. In the case of random 8-SAT, we find that for around 14 ansatz layers, QAOA matches the scaling performance of the highest-performance classical solver we tested, WalkSATlm. For larger numbers of layers, QAOA outperforms WalkSATlm, with an ultimate level of advantage that is still to be determined. Our methods provide a framework for analysing the performance of QAOA for hard constraint satisfaction problems and finding further speedups over classical algorithms.