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

AI summary

Overview

Research area: Quantum and classical algorithms for average-case inference — specifically spectral hierarchies for planted noisy k-XOR (sparse Learning Parity with Noise), with a quantum-walk speedup component.

Technical level: Intermediate to Advanced. The paper is written for researchers comfortable with spectral methods, random hypergraphs, and asymptotic runtime analysis; the core idea (multiplying clauses around cycles) is explainable without that background.

Scope: The paper introduces hypergraph cycle enumeration (HCE), a hierarchical spectral algorithm for detecting and recovering planted signals in noisy k-XOR instances, proves detection and weak-recovery guarantees with a smooth runtime–sample trade-off, compares it against the Kikuchi hierarchy in theory and experiment, and gives a subquadratic quantum speedup for one of its steps. From JPMorganChase Global Technology Applied Research (arXiv:2610.40941v1 [quant-ph], 29 Oct 2026).

What This Paper Is About

Many high-dimensional inference problems ask when a weak, noisy signal hidden in random data can be detected, and when it can be recovered efficiently. This paper studies planted noisy k-XOR, also called sparse LPN: a hidden vector x ∈ {±1}^n is observed only through m clauses, each revealing the parity of k coordinates, with each label flipped by noise of mean ρ. The goal is to build an algorithm that recovers x while offering a tunable trade-off between sample complexity and runtime — the "smooth trade-off" property that makes hierarchies like Kikuchi and sum-of-squares interesting — but with a much smaller spectral problem at every level.

Key Contributions

1. A new hierarchy, HCE. The authors introduce hypergraph cycle enumeration, a hierarchical algorithm where level l aggregates sets of l clauses whose supports XOR to a pair {i, j}, producing an n × n recovery matrix. Unlike Kikuchi, whose level-ℓ operator acts on a lifted space of dimension binom(n, ℓ), HCE keeps the spectral problem in the original variable space, so matrix size is independent of l.

2. Detection and recovery guarantees with a smooth trade-off. The paper proves a detection theorem with no logarithmic loss (Theorem 3) and a weak-recovery theorem for even k (Theorem 4, with Corollary 5 for the trade-off). HCE succeeds at threshold clause density m/n = Ω̃(ρ⁻²(n/l)^{k/2−1}), tracing the same threshold curve as Kikuchi and SoS.

3. A head-to-head complexity and empirical comparison with Kikuchi. At matched even levels and k = 4, the stated runtime bounds have the same leading exponent, while HCE uses a smaller matrix representation. Experiments at k = 4, 5, 6 show HCE matches Kikuchi recovery overlap at equal level while using substantially less memory and runtime, with the advantage largest in the sparsest regime.

4. A subquadratic quantum speedup for HCE. Replacing one algorithm step with a quantum walk (quantum-walk claw finding) yields a quantum HCE runtime of Õ(C^{l/3} n^{kl/6+2}), without refuting the quartic quantum speedup of quantum Kikuchi.

Main Findings

• Cycles carry the signal. For an even l-cover F — a set of l distinct hyperedges in which every vertex appears an even number of times — the product of labels X_F has mean ρ^{l} and variance 1 − ρ^{2l}. Under the null (ρ = 0) the mean vanishes, so even covers are exactly the local structures that certify planting. This is the conceptual core of the method.

• Detection threshold matches the hierarchy curve. Detection works when m ≫ γ_k ρ⁻² n(n/l)^{k/2−1}, with γ_k := k^{−k/2} e^{k/2−1}. Up to logarithmic factors this is the Kikuchi detection threshold with γ_k replaced by binom(k, k/2)⁻¹ and l replaced by the Kikuchi level ℓ; at k = 4 the two constants agree to within 2%.

• The detection result is log-free. Theorem 3 gives explicit false-positive and false-negative probabilities each at most δ, and also supplies a decision rule that does not use ρ: declare planted when Z_l > 0 and X(l) > √(2/(δ Z_l)). The recovery result, by contrast, is a soft-asymptotic statement with logarithmic factors suppressed.

• Deeper levels make overlapping covers rarer. The variance-to-mean-squared ratio of the cover count scales as Θ_{k,C}(l^{−(k−2)π_k}), where π_k = 3 for even k and π_k = 4 for odd k (the smallest level carrying an even cover). This is the mechanism behind the trade-off: at fixed density, the level-l discriminator behaves like an average of independent ±1 variables of mean ρ^{l}.

• Parity obstruction at odd levels. Since |△(F)| ≡ kl (mod 2), a level can carry even covers or witnesses only when kl is even. For odd k and odd l this forces Z_l = 0 and makes the recovery matrix vanish identically.

• Recovery is a signal-to-noise comparison. The recovery matrix satisfies A^{(l)} = ρ^{l} N_l xx^⊤ + R^{(l)}, with planted eigenvalue ρ^{l} N_l(n − 1). The top eigenvector aligns with x once ‖R^{(l)}‖op is small compared with θ_l = ρ^{l} d_l, where d_l := nN_l. The proof bounds high trace moments of the centered residual, splitting witnesses into boundary-connected and boundary-disconnected sectors; for even k a parity argument gives R^{(l)}{bd} = 0 identically.

• Neither algorithm is universally better. HCE generally wins when shallow levels suffice or the density parameter C (with m = C n^{k/2}) is small; Kikuchi is faster when low ρ requires deeper levels and large C makes HCE's clause enumeration costly. HCE's recovery guarantee carries a logarithmic loss that Kikuchi's sharp analysis (Schmidhuber and Hastings) does not.

• Large empirical speed-up in the hardest regime. At n = 50, k = 4, level 6, HCE completes in ≈300 s versus ≈5.5 h per instance for Kikuchi — a ∼60× speed-up (Appendix G) — allowing HCE to solve some instances beyond Kikuchi's capability.

• Quantum comparison is nuanced. The quantum HCE speedup is subquadratic (Õ(C^{l/3} n^{kl/6+2})), while quantum Kikuchi has runtime Õ(C n^{ℓ/4+k/2+1}). The authors state explicitly that their classical and quantum algorithms do not refute the quartic quantum speedup of quantum Kikuchi, which remains valid for the practically relevant regime of large size and high noise strength.

Methodology in Plain English

The starting point is an analogy with Gaussian elimination. In the noiseless case, combining clauses so that variables cancel pairwise leaves a simple constraint on the hidden bits. The authors ask whether a similar cancellation trick survives noise.

HCE does this systematically. At level l, it looks for "witnesses": sets of l clauses whose supports, XORed together, leave exactly two variables {i, j}. Multiplying the l labels along such a set gives x_i x_j times a product of l noise variables — a noisy estimate of the product of two entries of the hidden vector. Accumulating all such witnesses into an n × n matrix gives a rank-one signal plus noise; the top eigenvector, thresholded by sign, estimates the hidden vector.

The key engineering trick is that this accumulation is done by meet-in-the-middle rather than brute force. The algorithm hashes r-sets and s-sets (with r = ⌊l/2⌋, s = ⌈l/2⌉) by their boundaries, then probes partners — same-size partners by swapping one element, size-difference-two partners by deleting two elements — and accumulates matches with their multiplicities. Because the spectral step always acts on an n × n matrix, memory does not blow up with the level the way Kikuchi's binom(n, ℓ)-dimensional operator does.

The theory proceeds in two tracks. For detection, the authors compute the mean and variance of the cover count exactly on the complete hypergraph using a Kravchuk-polynomial count, then transfer to the sampled hypergraph; the variance controls the error probabilities. For recovery, they bound the operator norm of the residual via trace moments and Weyl/Davis–Kahan, then count witnesses asymptotically to convert the spectral condition into a condition on clause density alone. The quantum version swaps the witness-search step for a quantum-walk claw-finding routine. Experiments use sparse storage, Lanczos, and a voting-matrix decoder for Kikuchi, and the meet-in-the-middle construction plus post-processing for HCE.

Why This Matters

Impact on research. The paper adds HCE to the small family of hierarchies — SoS, Kikuchi, and the gadget-based methods of Li, Mao, and Gupta et al. — that achieve a smooth sample-versus-time trade-off. Its distinctive claim is not a new statistical regime but an "exact final-boundary compression": an n × n spectral endpoint at every level, a cycle interpretation of the statistic, explicit witness-count constants, and an empirical memory frontier. The unifying observation — that Gupta et al.'s random walks, Li and Mao's restricted gadgets, Kikuchi's closed walks, and HCE's full enumeration are all different weightings of even covers — is a useful lens for understanding where spectral thresholds come from. The detection theorem is log-free, unlike the recovery theorem, sharpening the boundary of what is currently provable.

Real-world applications (contextual). The paper is a theory-and-algorithms contribution; it does not run on application data.

• Cryptographic design and cryptanalysis. LPN is a standard hardness assumption behind lightweight and post-quantum-style constructions; better algorithms probe the concrete parameter regimes those schemes rely on.
• Coding and decoding. Sparse parity checks over noisy channels are structurally the same object as noisy k-XOR instances.
• Sparse constraint satisfaction. Refutation of random sparse CSPs is a cited relative, relevant to hardness certification and benchmark generation.
• High-dimensional statistics and tensor methods. The problem sits alongside tensor PCA, so the spectral machinery transfers to planted-signal estimation more broadly.

Industry relevance. The work comes from a bank's applied research group, and the practical payoff is resource efficiency: at n = 50, k = 4, level 6, HCE solves in ≈300 s what takes ≈5.5 h for Kikuchi, with substantially less memory. For anyone benchmarking quantum and classical heuristics on planted-signal problems, having a cheaper classical baseline in the ultra-sparse regime changes which instances are even feasible to study.

Future Directions

1. Remove the logarithmic loss in recovery. The authors conjecture that a normalized or suitably trimmed HCE recovery operator removes the logarithmic slack uniformly over a non-trivial range of growing levels l = l(n); proving this remains open. They note that Li and Mao avoid the log factor, possibly because they use a different recovery method.

2. Characterize the crossover more precisely. Figure 1 is explicitly schematic and illustrates finite-size behavior at k = 4, n large, not the asymptotic scaling of Table 1. A quantitative map of where HCE beats Kikuchi as a function of C and ρ would make the choice of algorithm routine rather than a judgment call.

3. Extend and tighten the quantum speedup. The quantum HCE result is subquadratic and does not overturn the quartic quantum speedup of quantum Kikuchi for large size and high noise strength. Whether a better quantum witness-search primitive closes the gap, or whether the two quantum speedups are fundamentally different in character, is unresolved.

4. Handle odd k more cleanly. The parity obstruction forces Z_l = 0 at odd levels for odd k, requiring a separate unbalanced construction (Definition D.35) at l ≥ 6. A unified treatment across parities would simplify both the algorithm and its analysis.

Target Audience

Researchers in average-case complexity, random inference, and spectral algorithms; quantum algorithm researchers interested in provable speedups for combinatorial search steps; and practitioners benchmarking classical versus quantum heuristics on planted-signal problems. Readers need comfort with asymptotic notation, random hypergraphs, and matrix perturbation arguments to follow the proofs, though the algorithm and its motivation are accessible at an intermediate level. Experimentalists will find Table 1 and the k = 4, 5, 6 runtime comparisons most directly useful; theorists will find the log-free detection theorem and the open recovery conjecture the most actionable parts.

Authors’ 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.