Low-Autocorrelation Binary Sequence (LABS) Problem

The Low Autocorrelation Binary Sequence (LABS) problem aims to find a spin sequence $S=(s_i)$ ($s_i=\pm 1, 0\leq i\leq n-1$) that minimizes its autocorrelation. The autocorrelation of $S$ with alignment $d$ is defined as

\[\left(\sum_{i=0}^{n-d-1}s_is_{i+d}\right)^2\]

The LABS objective function is the sum of these autocorrelations over all alignments:

\[\begin{aligned} \text{LABS}(S) &= \sum_{d=1}^{n-1}\left(\sum_{i=0}^{n-d-1}s_is_{i+d}\right)^2 \end{aligned}\]

The LABS problem is to find a sequence $S$ that minimizes $\text{LABS}(S)$.

Spin-to-binary conversion

Since the solvers bundled with PyQBPP do not support spin variables directly, we convert the spin variables to binary variables using the following transformation:

\[\begin{aligned} s_i &\leftarrow 2s_i - 1 \end{aligned}\]

After this conversion, each $s_i$ can be treated as a binary variable, and HUBO solvers for binary variables can be used to find a solution to $\text{LABS}(S)$.

PyQBPP provides this conversion through the spin_to_binary() function.

PyQBPP program for the LABS

The following PyQBPP program formulates and solves the LABS problem:

import pyqbpp as qbpp

n = 30

s = qbpp.var("s", shape=n)
labs = 0
for d in range(1, n):
    temp = 0
    for i in range(n - d):
        temp += s[i] * s[i + d]
    labs += qbpp.sqr(temp)

labs.spin_to_binary()
labs.simplify_as_binary()

solver = qbpp.ABS3Solver(labs)
result = solver.search(time_limit=10.0, best_energy_sols=0)
for i, sol in enumerate(result.sols):
    bits = "".join("+" if sol(s[j]) == 1 else "-" for j in range(n))
    print(f"{i}: LABS = {sol.energy} : {bits}")

In this program, s stores a vector of n variables. The expression labs is constructed using a nested loop, directly following the mathematical definition of the LABS objective.

Afterward, labs is converted into an expression over binary variables using the spin_to_binary() function and simplified by simplify_as_binary().

The ABS3 Solver is then executed with a time limit of 10 seconds. Since best_energy_sols is set to 0 (no limit on the number of kept solutions), all solutions with the best energy that the search finds are stored in result.sols. They are not necessarily all the solutions that achieve this energy.

Using a for loop over result.sols, all stored solutions are printed. A typical output of this program is:

0: LABS = 59 : -----+++++-++-++-+-+-+++--+++-
1: LABS = 59 : -+-++-+-+---+++-------+--++-++
2: LABS = 59 : -+-+--+-+---+++-------+--++-++
3: LABS = 59 : +-+-++-+-+++---+++++++-++--+--
4: LABS = 59 : --+--++-+++++++---+++-+-++-+-+
5: LABS = 59 : ----++++++-++-++-+-+-+++--+++-
6: LABS = 59 : +-+--+-+-+++---+++++++-++--+--
7: LABS = 59 : ++-++--+-------+++---+-+-++-+-
8: LABS = 59 : -+++--+++-+-+-++-++-++++++----
9: LABS = 59 : +---++---+-+-+--+--+-----+++++

In this run, multiple solutions achieving the same minimum LABS value are obtained. The search is randomized, so the solutions and their number vary from run to run.