  The SAT problem is a prototypical NP-complete problem of fundamental
importance in computational complexity theory with many applications in science
and engineering; as such, it has long served as an essential benchmark for
classical and quantum algorithms. This study shows numerical evidence for a
quadratic speedup of the Grover Quantum Approximate Optimization Algorithm
(G-QAOA) over random sampling for finding all solutions to 3-SAT problems
(All-SAT). G-QAOA is less resource-intensive and more adaptable for 3-SAT and
Max-SAT than Grover's algorithm, and it surpasses conventional QAOA in its
ability to sample all solutions. We show these benefits by 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. Interestingly, a single-angle-pair constraint that uses the same
pair of angles at each G-QAOA round greatly reduces the classical computational
overhead of optimizing the G-QAOA angles while preserving its quadratic
speedup. We also find parameter clustering of the angles. The single-angle-pair
protocol and parameter clustering significantly reduce obstacles to classical
optimization of the G-QAOA angles.
