{"id":"arxiv/2609.08907","url":"https://arxiv.org/abs/2609.08907","tags":["cs.ET","quant-ph"],"score":0,"title":"Sparse Walsh-Pauli Correlation Encoding for MaxCut: A Quantum-Inspired Formulation with Quantum-Hardware Validation","domain":"cs.ET","source":"arxiv","authors":["Cesar Augusto do Amaral","Nicolás Legnazzi","Marcos Vinicius Reballo","Marcus Ritt","Alexsandro Santos da Rosa Júnior","Fernando Augusto Caletti de Barros"],"reviews":0,"subject":"cs.ET","summary":"We introduce a sparse Walsh-Pauli correlation encoding for MaxCut, in which graph variables are represented by diagonal Pauli-string expectation values computed classically as normalized XOR autocorrelations of Walsh coefficients. The complete Walsh basis can reproduce the diagonal correlators of arbitrary quantum states, while a structured sparse support reduces the number of trainable coefficients to $m+1$ for $m$ graph variables. We evaluate the method on $1{,}400$ held-out random graphs with up to $7{,}000$ vertices, obtaining empirical approximation ratios near $0.98$ relative to MQLib…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-09-08","reactions":{}}