Hypergraph cycle enumeration for efficient inference of planted k-XOR with smooth trade-off

Abstract

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 for HCE by replacing one of the algorithm's steps with a quantum walk. Our classical and quantum algorithms do not refute the quartic quantum speedup of quantum Kikuchi method, which remains valid for the practically relevant regime of large size and high noise strength.

The paper studies detection and recovery in planted noisy $k$-XOR (sparse LPN), asking whether the sample–runtime trade-off of Kikuchi spectral methods can be obtained without diagonalizing a lifted operator. Hypergraph cycle enumeration (HCE) multiplies labels over $l$-clause sets whose supports XOR to the empty set for detection, or to $\{i,j\}$ for recovery. The latter products define an $n\times n$ matrix whose leading eigenvector estimates the planted assignment. For detection, HCE achieves $m\gtrsim\gamma_k\rho^{-2}n(n/l)^{k/2-1}$, with $\gamma_k=k^{-k/2}e^{k/2-1}$ and explicit error-dependent factors tending to one as admissible $l$ increases. Recovery follows the same algebraic curve up to polylogarithmic losses: the sufficient density includes $(\log n)^{(k+1)l+3}$. Detection is established through even-cover counts and overlap covariances; recovery uses a Hoeffding decomposition, high trace moments, and eigenvector perturbation bounds. Odd-$k$ recovery at $l\ge6$ requires support-based trimming and additional density restrictions. Meet-in-the-middle construction takes $\widetilde O(n^3+m^{\lceil l/2\rceil}+nm^{\lfloor l/2\rfloor})$ time and $\widetilde O(n^2+m^{\lceil l/2\rceil})$ memory. Small-instance experiments report comparable recovery to matched-level Kikuchi with lower measured resource costs in ultra-sparse regimes. These experiments use an older probing implementation and additional decoding. Guarantees hold at fixed levels, not uniformly for growing $l$; removing recovery’s logarithmic slack remains open. Quantum claw finding accelerates witness search, but the stated search bound does not establish an end-to-end recovery speedup because matrix construction requires signed sums over witnesses.