Competitive scaling of small-subsystem-optimization heuristics for LABS

Abstract:The low autocorrelation binary sequences (LABS) problem, often formulated as a spin-lattice energy-minimization problem, is a combinatorial optimization problem with a very rugged energy landscape. We demonstrate that iterative optimization of very small subsystems of n spins that are decoupled from the rest of the system achieves global optimization of LABS with a time-to-solution scaling that is competitive with heuristics that optimize the global system of N spins directly. Our isolated-subsystem heuristic with n = 4 achieves a time scaling of O(1.333^N ) on the interval N = [27, 60], while the current state-of-the-art classical and quantum scalings are respectively O(1.34^N ) and O(1.21^N ). Our results suggest that specialized optimization hardware with only small numbers of logical spins may be of practical relevance.

Statistical Mechanics (cond-mat.stat-mech); Quantum Physics (quant-ph)

arXiv:2610.14361 [cond-mat.stat-mech]

(or arXiv:2610.14361v2 [cond-mat.stat-mech] for this version)

https://doi.org/10.48550/arXiv.2610.14361 Focus to learn more arXiv-issued DOI via DataCite

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.