Hours for a primal-dual solver. Seconds for Quicopt.

System setup

Quicopt: one CPU core per seed (100 single-threaded shots) on a single AMD EPYC (Rome) node. Baselines reproduced as published by QOBLIB: a leading commercial solver on a 32-core AMD EPYC 7542 with a 2 h limit; ABS2 on two NVIDIA A100 (80 GB) GPUs with a 10 min limit.

The problem, in depth

The Low-Autocorrelation Binary Sequence (LABS) problem asks for a string of N ±1 symbols that looks as little like a shifted copy of itself as possible. For every possible shift you compute the correlation between the sequence and that shifted version, and you want all of those correlations as close to zero as possible: a sequence with no hidden periodicity or self-similarity at any offset. The quality is summarised by a single number, the “energy”; lower is better, and finding the best sequence is the goal. Written out, that energy is a degree-four polynomial in the ±1 symbols: a higher-order (PUBO) objective, not a plain quadratic QUBO, which is what makes LABS a natural showcase for higher-order binary optimization.

This is not an academic curiosity: such sequences are exactly what radar, sonar, and communication systems want for pulses and spreading codes, because a signal that does not resemble its own echoes is easy to detect and hard to confuse. The same object also appears in physics as the ground state of a frustrated spin system: one of the cleanest examples of a “glassy” energy landscape.

What makes LABS notoriously hard is the combination of an exponentially large search space (2ᴺ candidate sequences) with a landscape that offers almost no guidance: the good solutions are isolated needles with no gentle slope leading to them, so the usual tricks (following gradients, local tweaks, smart branching) gain little traction. The optimal sequence is only proven optimal up to N = 66; a state-of-the-art primal-dual solver, given two hours, can certify the optimum only to about N = 41, with running time growing exponentially beyond that. LABS is small to state and brutal to solve, which is precisely why it serves as a benchmark for the hardest optimization methods.

How the benchmark is run

In the upper panel, lower energy is better; the black curve is the proven optimum (Packebusch & Mertens, known up to N = 66). In the lower panel (log scale): TTQ (“Time To Quicopt”) is the time at which the commercial solver’s running incumbent first reaches the energy Quicopt v0.2 finds (its best of 100 seeds); runs that never reach it within the 2 h budget are drawn at the limit and marked “2h timeout”. TTS is ABS2’s reported time to its own best solution; the gray and blue points are Quicopt v0.1’s and v0.2’s own time-to-best on 100 cores, respectively.

ABS2 (Adaptive Bulk Search 2) is a state-of-the-art GPU heuristic for QUBO problems: a genetic-algorithm global search orchestrates many local searches on the GPUs. Applied to the QUBO formulation of LABS, it is QOBLIB’s strong heuristic baseline (the like-for-like comparison for another heuristic such as Quicopt), whereas the commercial solver is a general-purpose primal-dual (branch-and-bound) solver run as an anytime heuristic.

The 100-vs-32 core difference cannot explain away the separation: it is a time-to-solution gap of two to four orders of magnitude that grows with N. Parallel branch-and-bound on LABS scales sublinearly, and spreading cores over independent seeds leaves each run bounded by the same 2 h limit. The commercial solver therefore needs hours to reach a quality Quicopt v0.2 reaches orders of magnitude faster, regardless of core count.