  Establishing quantum advantage for variational quantum algorithms is an
important direction in quantum computing. In this work, we apply the Quantum
Approximate Optimisation Algorithm (QAOA) -- a popular variational quantum
algorithm for general combinatorial optimisation problems -- to a variant of
the satisfiability problem (SAT): Not-All-Equal SAT (NAE-SAT). We focus on
regimes where the problems are known to have solutions with low probability and
introduce a novel classical solver that outperforms existing solvers.
Extensively benchmarking QAOA against this, we show that while the runtime of
both solvers scales exponentially with the problem size, the scaling exponent
for QAOA is smaller for large enough circuit depths. This implies a polynomial
quantum speedup for solving NAE-SAT.
