Sparse Walsh-Pauli Correlation Encoding for MaxCut: A Quantum-Inspired Formulation with Quantum-Hardware Validation
Abstract
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 heuristic references. On Gset instances G14, G23, G60, and G64, the sparse model achieves mean refined approximation ratios of $0.9828$, $0.9926$, $0.9781$, and $0.9369$, respectively, with 80.4%-89.3% fewer parameters than the complete Walsh representation. The trained coefficients are transferred without retraining to quantum circuits. Statevector simulations of the four Gset instances achieve fidelities above $0.99994$ and preserve all correlator signs. Separately, a seven-qubit experiment on a $15$-vertex graph executed on IBM quantum hardware achieves a correlator-sign agreement of 0.927±0.049 relative to the corresponding noiseless circuit. These results demonstrate the potential of sparse Walsh-PCE for large-instance quantum-inspired MaxCut optimization while validating the transfer of classically trained parameters to quantum hardware.
Related
- Bio-inspired minimal hardware implementation of spike-time dependent plasticity for intelligent spiking neural networks
- Benchmarking Ansatze for Pauli Correlation Encoding in the Maximum Independent Set Problem
- Qubit-Efficient Variational Quantum Optimization via Pauli Correlation Encoding: Application to Large-Scale Power Demand Portfolio Optimization
- Toward Resilient Many-Body Formulations under Incomplete Correlation Models: A Dual-Space Variational Formulation
- Enhancing Pauli Correlation Encoding for quantum optimization via systematic expressivity analysis
BibTeX
@misc{amaral2026sparse,
title = {{Sparse Walsh-Pauli Correlation Encoding for MaxCut: A Quantum-Inspired Formulation with Quantum-Hardware Validation}},
author = {Cesar Augusto do Amaral and Nicolás Legnazzi and Marcos Vinicius Reballo and Marcus Ritt and Alexsandro Santos da Rosa Júnior and Fernando Augusto Caletti de Barros},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2609.08907},
eprint = {2609.08907},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.08907},
}
RIS
TY - UNPB
TI - Sparse Walsh-Pauli Correlation Encoding for MaxCut: A Quantum-Inspired Formulation with Quantum-Hardware Validation
AU - Cesar Augusto do Amaral
AU - Nicolás Legnazzi
AU - Marcos Vinicius Reballo
AU - Marcus Ritt
AU - Alexsandro Santos da Rosa Júnior
AU - Fernando Augusto Caletti de Barros
PY - 2026
DA - 2026/10/18
PB - arXiv
DO - 10.48550/arxiv.2609.08907
UR - https://arxiv.org/abs/2609.08907
AB - 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 heuristic references. On Gset instances G14, G23, G60, and G64, the sparse model achieves mean refined approximation ratios of $0.9828$, $0.9926$, $0.9781$, and $0.9369$, respectively, with 80.4%-89.3% fewer parameters than the complete Walsh representation. The trained coefficients are transferred without retraining to quantum circuits. Statevector simulations of the four Gset instances achieve fidelities above $0.99994$ and preserve all correlator signs. Separately, a seven-qubit experiment on a $15$-vertex graph executed on IBM quantum hardware achieves a correlator-sign agreement of 0.927±0.049 relative to the corresponding noiseless circuit. These results demonstrate the potential of sparse Walsh-PCE for large-instance quantum-inspired MaxCut optimization while validating the transfer of classically trained parameters to quantum hardware.
ER -