  The quantum approximate optimization algorithm (QAOA) is a leading candidate
algorithm for solving optimization problems on quantum computers. However, the
potential of QAOA to tackle classically intractable problems remains unclear.
Here, we perform an extensive numerical investigation of QAOA on the low
autocorrelation binary sequences (LABS) problem, which is classically
intractable even for moderately sized instances. We perform noiseless
simulations with up to 40 qubits and observe that the runtime of QAOA with
fixed parameters scales better than branch-and-bound solvers, which are the
state-of-the-art exact solvers for LABS. The combination of QAOA with quantum
minimum finding gives the best empirical scaling of any algorithm for the LABS
problem. We demonstrate experimental progress in executing QAOA for the LABS
problem using an algorithm-specific error detection scheme on Quantinuum
trapped-ion processors. Our results provide evidence for the utility of QAOA as
an algorithmic component that enables quantum speedups.
