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.33^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, and that quantum speedups demonstrated in the absence of decomposition may not provide a practical quantum advantage for large-scale problems that require decomposition.
Related
- Stochastic Diversity Stabilization in Nonlinear Competitive Dynamics: A Statistical Mechanics Approach to Fluctuation Suppression and Finite-Size Scaling
- Hyperbolic scaling of the small-exponent limit in magnetic nonlinear electrodynamics
- Scaling Quantum Optimization to the Thousand-Qubit Scale with Distributed Quantum Sampling
- Subsystem Spacetime Code
- Exact subsystem dynamics in the deterministic Floquet-PXP model
BibTeX
@misc{lau2026competitive,
title = {{Competitive scaling of small-subsystem-optimization heuristics for LABS}},
author = {Ginger E. Lau and Adil A. Gangat},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.14361},
eprint = {2610.14361},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.14361},
}
RIS
TY - UNPB
TI - Competitive scaling of small-subsystem-optimization heuristics for LABS
AU - Ginger E. Lau
AU - Adil A. Gangat
PY - 2026
DA - 2026/10/29
PB - arXiv
DO - 10.48550/arxiv.2610.14361
UR - https://arxiv.org/abs/2610.14361
AB - 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.33^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, and that quantum speedups demonstrated in the absence of decomposition may not provide a practical quantum advantage for large-scale problems that require decomposition.
ER -