Performance of Grover-QAOA on 3-SAT: Quadratic Speedup, Fair-Sampling, and Parameter Clustering

The SAT problem stands as a quintessential NP-complete challenge with profound significance across various scientific and engineering disciplines; as such, it has long served as an essential benchmark for classical and quantum algorithms. This study reports numerical evidence for a quadratic speedup of the Grover Quantum Approximate Optimization Algorithm (G-QAOA) over brute-force searching for finding all solutions to 3-SAT problems. G-QAOA presents a reduction in resource demands and heightened adaptability for tackling 3-SAT challenges compared to Grover's algorithm, alongside its superior capacity for solution sampling over the conventional QAOA. This study elucidates these advantages through classical simulations of many-round G-QAOA on thousands of random 3-SAT instances. We also observe G-QAOA advantages on the IonQ Aria quantum computer for small instances, finding that current hardware suffices to determine and sample all solutions. A noteworthy finding is that imposing a single-angle pair constraint markedly reduces the classical computational overhead of optimizing G-QAOA angles, without detracting from its quadratic performance enhancement, and presents a clustering phenomenon of the angles. The single-angle pair constraints and parameter clustering significantly reduce obstacles to classical optimization of the G-QAOA angles, offering opportunities to solve problems beyond SAT.