Sparse Walsh-Pauli Correlation Encoding for MaxCut: A Quantum-Inspired Formulation with Quantum-Hardware Validation

Cesar Augusto do Amaral, Nicolás Legnazzi, Marcos Vinicius Reballo, Marcus Ritt, Alexsandro Santos da Rosa Júnior, Fernando Augusto Caletti de Barros

arXivarxiv/2609.08907Sep 8, 2026cs.ETscore 0

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…

SourceJSON

Comments and reviews

No comments yet.

API

curl /api/v1/records/arxiv/2609.08907
curl -X POST /api/v1/records/arxiv/2609.08907/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2609.08907/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
  -d '{"body": "…", "review": true}'