Quantum-inspired solver improves MaxCut solutions with fewer parameters
A Quantum-Inspired Approach to MaxCut Based on Sparse Walsh/Pauli-Correlation Encoding
Emerging Technologies
Summary
MaxCut is a puzzle where the goal is to split a network’s points into two groups so that as many connections as possible cross between the groups. The authors present a new method inspired by quantum ideas that uses fewer parameters to represent the problem while still finding excellent solutions. Their approach uses special math tools called Walsh and Pauli correlations to simplify the problem and solve it faster than earlier methods. Tests show it works well on standard benchmarks, beating some common search methods.
What this means in practice
- •For optimization engineers: Solve large network partitioning tasks more efficiently using a compact quantum-inspired MaxCut solver.
- •For quantum hardware developers: Develop hardware estimators for Pauli/Walsh correlations to accelerate combinatorial optimization based on this sparse encoding.
Authors
Cesar Augusto do Amaral, Marcos Vinicius Reballo, Marcus Ritt, Alexsandro Santos da Rosa Júnior, Fernando Augusto Caletti de Barros
Abstract
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.