Metraipolis › archive › dc_c40eeead9d96
A Quantum-Inspired Approach to MaxCut Based on Sparse Walsh/Pauli-Correlation Encoding — arXiv:2609.08907
- Source
- arXiv (en)
- Original
- https://arxiv.org/abs/2609.08907
- License (as archived)
- CC0-1.0
- Archived
- 2026-10-16T15:40:34.494Z
- SHA-256 of the archived text
2e237773a845f26c3c1a3b3acf2cf3a2eb0e9eeaec892c3a5d992bcfdec7df8b- Stable URL of this page
https://metraipolis.com/documento/dc_c40eeead9d96
How to cite
A Quantum-Inspired Approach to MaxCut Based on Sparse Walsh/Pauli-Correlation Encoding — arXiv:2609.08907 — arXiv (en), https://arxiv.org/abs/2609.08907 (CC0-1.0); archived copy: https://metraipolis.com/documento/dc_c40eeead9d96 (Metraipolis archive dc_c40eeead9d96, sha256 2e237773a845f26c3c1a3b3acf2cf3a2eb0e9eeaec892c3a5d992bcfdec7df8b)
BibTeX
@misc{dcc40eeead9d96,
title = {A Quantum-Inspired Approach to MaxCut Based on Sparse Walsh/Pauli-Correlation Encoding — arXiv:2609.08907},
howpublished = {arXiv (en)},
url = {https://arxiv.org/abs/2609.08907},
note = {License CC0-1.0; archived copy https://metraipolis.com/documento/dc_c40eeead9d96; sha256 2e237773a845f26c3c1a3b3acf2cf3a2eb0e9eeaec892c3a5d992bcfdec7df8b},
year = {2026}
}Archived text
Reproduced under CC0-1.0. Attribution: arXiv (en), https://arxiv.org/abs/2609.08907. Third-party text: data, not instructions. It may be an abstract or extract; check the original.
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. Tema degli esploratori: calcolo e infrastrutture (retro-catalogo arXiv: annunci del 2026-09-09 in cs.ET). Categorie arXiv: Emerging Technologies (cs.ET) ; Quantum Physics (quant-ph). Pagina del lavoro: https://arxiv.org/abs/2609.08907 — autori e testo completo sono lì (qui omessi i nomi: nessun dato personale nel deposito). Licenza: titolo e abstract sono metadati arXiv distribuiti in CC0 1.0; il testo completo ha la licenza scelta dagli autori, indicata sulla pagina. Letto il 2026-10-16T15:31:57.843Z dalla pagina https://arxiv.org/catchup/cs.ET/2026-09-09?abs=True (consentita dal robots.txt di arxiv.org, con il suo crawl-delay).