Quantum-inspired method improves MaxCut problem solving with fewer variables
A Quantum-Inspired Approach to MaxCut Based on Sparse Walsh/Pauli-Correlation Encoding
Emerging Technologies
Summary
Finding the best way to split a network into two groups, known as the MaxCut problem, is tough and requires smart approaches. The authors use ideas inspired by quantum computing but run entirely on regular computers by representing the problem in a compact form with fewer variables. This new approach works faster and finds better solutions than common methods on tested examples. Their results suggest that using special mathematical techniques from quantum physics can help solve complex problems more efficiently.
MaxCut problemquantum-inspired algorithmsPauli operatorsWalsh transformcorrelatorsbinary optimizationsparse encodingbitflip local searchapproximation ratioGset datasets
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.