arXiv:2610.14361
Competitive scaling of small-subsystem-optimization heuristics for LABS
Ginger E. Lau, Adil A. Gangat
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.
AI Summary
Can optimizing very small, isolated subsystems compete with whole-system heuristics for low-autocorrelation binary sequences (LABS)? This paper studies decomposition-based search for the LABS ground state, discarding every Hamiltonian interaction involving spins outside the selected subsystem. Subsystems are solved by exact enumeration, and their solutions provide updates to the full sequence. Variants test complementary assignments, accept energy-lowering moves with occasional unconditional “kicks,” track subsystem coverage, and select among multiple update proposals. Performance is measured by global-energy evaluations needed to reach known optima, rather than walltime. Exponential fits $\mathrm{TTS}=cb^N$ use per-size medians over 20 seeds, with hyperparameters tuned separately using ten seeds on $N=27,\ldots,50$. Over $N=27,\ldots,60$, the most elaborate four-spin variant gives $b=1.333$ with a 95% regression confidence interval of $[1.300,1.366]$, compared with the cited classical benchmark near $1.34$. Its eight-spin counterpart gives $b=1.375$; a simpler four-spin kicked-descent method has lower observed evaluation counts but a larger fitted base, $1.396$. The cited quantum benchmark is $1.21$, inferred for QAOA with quantum minimum finding. These are finite-range empirical scaling fits, not asymptotic guarantees. Comparisons with prior methods involve different fitting intervals and cost measures. The paper explicitly leaves walltime and power consumption unassessed and identifies generalization to other problems and stronger evidence about subsystem-size dependence as open issues. Implications for small optimization hardware and decomposition-aware quantum advantage are presented as suggestions rather than demonstrated conclusions.
Central claim may not hold: The reported exponential base describes median global-energy evaluation counts and does not establish wall-clock or asymptotic runtime scaling. The headline comparison with memetic tabu combines different fitting intervals and cost statistics, so competitive runtime scaling is not established by a matched benchmark. IsoSubsys_MS pseudocode retains the last improving proposal rather than necessarily the lowest-energy proposal among its Y candidates. IsoSubsys_MS pseudocode does not save the selected proposal's subsystem indices before applying its update. IsoSubsys_MS pseudocode does not initialize or clear seq_best at each outer iteration, making candidate availability undefined or potentially stale.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
- Comments
- 9 pages, 5 figures