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

Understand

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.