Curator's Take
AI Commentary
This article shows that a carefully crafted quantum‑inspired representation—using only a few hundred diagonal Pauli/Walsh observables—can solve benchmark MaxCut instances with near‑optimal approximation ratios while beating standard random and tabu searches in speed. By exploiting sparse autocorrelations rather than a full 2^n Walsh space, the authors demonstrate that classical optimization can capture much of the expressive power traditionally associated with variational quantum circuits, hinting at a practical bridge between algorithmic theory and near‑term hardware estimations of Pauli correlators. The results suggest a scalable pathway for leveraging quantum‑style relaxations on conventional processors, which could accelerate combinatorial optimisation workloads before fault‑tolerant quantum computers become available.
— Mark Eatherly
Summary
We present a quantum-inspired Walsh/PCE solver for MaxCut based on sparse Pauli-correlation encodings. Instead of assigning one qubit or one variable to each graph vertex directly, the method represents relaxed binary variables through expectation values of diagonal Pauli/Walsh observables. These correlators are computed classically from sparse Walsh autocorrelations, producing a compact differentiable relaxation of the MaxCut objective. We evaluate the method on selected Gset instances, G1, G6, G12, and G18, and compare it with random search and tabu search over 10 independent seeds. The proposed model uses $801$ active parameters, corresponding to only $0.306\%$ of the full Walsh space over $18$ qubits. After a final bitflip local search, Walsh/PCE achieves approximation ratios of $0.99033 \pm 0.00226$ on G1, $0.95647 \pm 0.01604$ on G6, $0.96007 \pm 0.00951$ on G12, and $0.92964 \pm 0.02202$ on G18, outperforming both baselines on all tested instances. The method also yields the lowest average runtime in all cases. These results suggest that sparse Walsh/PCE representations provide an efficient quantum-inspired route for MaxCut and may be further extended to hardware-based estimation of Pauli/Walsh correlators.