Grover QAOA for 3-SAT: Quadratic Speedup, Fair Sampling, and Parameter Clustering

The Boolean satisfiability (SAT) problem, the first to be proven NP-complete, serves as a benchmark for quantum algorithms. We demonstrate a quadratic speedup over classical brute force search by the quantum approximate optimization algorithm (QAOA) with a Grover mixer for 3-SAT problems. In contrast to QAOA with the standard transverse field mixer, the Grover QAOA's samples all solutions uniformly, while in contrast to running the standard Grover search with an oracle implementing the 3-SAT instances, the Grover QAOA requires less quantum resources. These advantages come at the cost of requiring optimization of the variational parameters in the QAOA, but we find that simply assuming the angles are independent of the round of QAOA retains the speedup, and the optimal angles can easily be found. We find evidence for even further parameter clustering over different problem instances. These findings are corroborated through experiments up to 2 rounds of QAOA on the IonQ Aria quantum computer. Furthermore, the observed parameter clustering suggests the possibility of reducing the classical optimization overhead for QAOA.