Quantum-enhanced LABS optimisation

Problem

Low Autocorrelation Binary Sequences. Find a sequence of ±1 values minimising the sidelobe energy of its autocorrelation — the merit-factor problem behind radar pulse compression, spread-spectrum communications and cryptographic key design. It's NP-hard over a 2^N search space, and the energy landscape is famously rugged: classical solvers spend most of their budget escaping local minima rather than descending.

The question we set was narrow on purpose. Not “can quantum beat classical” — can a quantum circuit produce better starting points for a classical solver than random sampling can?

Method

A hybrid pipeline. A variational circuit samples candidate sequences; the best become initial seeds for a memetic tabu search that does the actual refinement. Three seeding strategies were compared at fixed sample budget: uniform random, standard QAOA at depth 2, and Trotterized counterdiabatic driving.

QAOA underperformed. A depth-2 ansatz doesn't have the expressivity to encode LABS structure, and the optimiser stalled on the rugged landscape. We replaced it with counterdiabatic driving — an adiabatic sweep with correction terms that suppress diabatic transitions — implemented with both two-body and four-body interaction terms.

The largest speedup in the project was classical. Tabu search re-evaluated the full O(N²) energy after every single bit flip; deriving a closed-form delta update reduced that to O(N), making the classical solver roughly 33× faster at N=33. Pure algebra, no hardware involved. Worth stating plainly rather than burying.

On the engineering side, CUDA-Q kernels forbid Python built-ins, so all gate angles were precomputed outside the kernel and the nested interaction loops flattened into precomputed lists. Running on the GPU target gave roughly 1000× over CPU simulation.

Findings

At N=20, counterdiabatic seeding found a best seed energy of 34 against QAOA's 50 — a 32% reduction. The advantage persisted at N=24 but narrowed to 5%.

It is not a better sampler on average. Over 1,000 samples at N=20 it showed a higher mean energy and a wider spread than QAOA. It is a better tail sampler: it reaches rare low-energy regions the others never visit, which is exactly what a seeding strategy needs and exactly the wrong thing to measure with a mean.

Memetic tabu search reached the optimum in 12.7 generations from CD seeds versus 32.7 from QAOA — 1.58× faster, and 1.57× faster than random. At N=24 the gap fell to 1.07×.

Below N≈16 the quantum seeding is worthless — random sampling does as well for less overhead. The useful window is N≈20–30, and the advantage shrinks as N grows. Whether it survives past N=30 is unresolved.

Next

Ensemble seeding combining QAOA and CD, since they explore disjoint regions. Larger N. Adaptive scheduling. A run on real hardware rather than simulation.