Sparse Walsh-Pauli Correlation Encoding for MaxCut: A Quantum-Inspired Formulation with Quantum-Hardware Validation
The method proposes a sparse Walsh/PCE solver for MaxCut, an NP-hard problem. It represents binary variables using expectation values of restricted Pauli-Z observables and trains a sparse set of Walsh coefficients to create compact, differentiable relaxations. This approach achieves competitive approximation ratios with significantly reduced runtime and provides a pathway for hardware estimation of correlators.