{"id":"arxiv/2610.40941","url":"https://arxiv.org/abs/2610.40941","tags":["quant-ph","cs.DS","stat.CO"],"score":0,"title":"Hypergraph cycle enumeration for efficient inference of planted k-XOR with smooth trade-off","domain":"quant-ph","source":"arxiv","authors":["Arman Babakhani","Enrico Fontana","Junhyung Lyle Kim","Shouvanik Chakrabarti","Ruslan Shaydulin"],"reviews":0,"subject":"quant-ph","summary":"We introduce hypergraph cycle enumeration (HCE), a simple spectral framework for detecting and recovering planted signals in noisy hypergraph inference problems. We study HCE on one representative problem from this class, namely planted noisy k-XOR, also known as sparse Learning Parity with Noise (LPN). Both theoretically and empirically, HCE achieves comparable recovery behavior to Kikuchi method, matching Kikuchi hierarchy. We identify parameter regimes where HCE outperforms Kikuchi method, showing that neither algorithm is universally better. We also show a subquadratic quantum speedup…","category":"research","comments":0,"disputed":false,"division":"physics","mentions":0,"discussed":0,"published":"2026-10-29","reactions":{}}