2025/11/06 by Cadavid, Alejandro Gomez, Chandarana, Pranav, Romero, Sebastián V. +4
#FOS: Physical sciences #Quantum Physics (quant-ph) #Statistical Mechanics (cond-mat.stat-mech)
paper · doi:10.48550/arxiv.2511.04553
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.24N) for sequence length N ∈ [27,37]. This scaling surpasses the best-known classical heuristic O(1.34N) and improves upon the O(1.46N) 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 \gtrsim 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.