Hours for an exact 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: Gurobi 11.0.0 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 exact 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 Gurobi’s running incumbent first reaches the energy Quicopt finds (its best of 100 seeds); Gurobi 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 blue points are Quicopt’s own time-to-best on 100 cores.

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 Gurobi is a general-purpose exact (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. Gurobi therefore needs hours to reach the quality Quicopt reaches in seconds, regardless of core count.