Abstract
We introduce quantum-enhanced memetic tabu search (QE-MTS), a non-variational hybrid algorithm that achieves state-of-the-art scaling for the low-autocorrelation binary sequence (LABS) problem. By seeding the classical MTS with high-quality initial states from digitized counterdiabatic quantum optimization (DCQO), our method suppresses the empirical time-to-solution scaling to O(1.24^N) for sequence length N ∈ [27,37]. This scaling surpasses the best-known classical heuristic O(1.34^N) and improves upon the O(1.46^N) of the quantum approximate optimization algorithm, achieving superior performance with a 6× reduction in circuit depth. A two-stage bootstrap analysis confirms the scaling advantage and projects a crossover point at N 47, beyond which QE-MTS outperforms its classical counterpart. These results provide evidence that quantum enhancement can directly improve the scaling of classical optimization algorithms for the paradigmatic LABS problem.