A competitive NISQ and qubit-efficient solver for the LABS problem

Pauli Correlation Encoding (PCE) is as a qubit-efficient variational approach to combinatorial optimization problems. The method offers a polynomial reduction in qubit count and a super-polynomial suppression of barren plateaus. Here, we extend the PCE-based framework to solve the Low Autocorrelation Binary Sequences (LABS) problem, a notoriously hard problem often used as a benchmark for classical and quantum solvers. To illustrate this,we simulate two variants of the PCE quantum solver for LABS instances of up to $N=45$ binary variables: one with commuting and one with maximally non-commuting sets of Pauli operators. The simulations use $4$ qubits and a circuit Ansatz with a total of $30$ two-qubit gates. We benchmark our method against the state-of-the-art classical solver and other quantum schemes. We observe improved scaling in the total time to reach the exact solution, outperforming the best-performing classical heuristic while using only a fraction of the quantum resources required by other quantum approaches. In addition, we perform proof-of-principle demonstrations on IonQ's Forte quantum processor, showing that the final solution is resilient to noise. Our findings point at PCE-based solvers as a promising quantum-inspired classical heuristic for hard problems as well as a tool to reduce the resource requirements for actual quantum algorithms.