Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2610.40941

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

Arman Babakhani, Enrico Fontana, Junhyung Lyle Kim, Shouvanik Chakrabarti, Ruslan Shaydulin

quant-phcs.DSstat.COSubmitted Oct 29, 2026• Announced Nov 2, 2026• 0 citations
arXivHTMLPDF

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.

AI Summary

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.

Little sign of AI-generated textOverclaims

Central claim may not hold: The advertised quantum HCE recovery speedup is unsupported: the reported quantum runtime counts finding one witness per variable pair, whereas HCE recovery requires signed sums over witnesses, and no aggregation algorithm or recovery guarantee at that runtime is supplied.

Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.

Related papers

The Kikuchi Hierarchy is Sharp for kkkXOR

Alexander Schmidhuber, Matthew B. Hastings

Planted noisy $k$XOR and the strong refutation of random $k$XOR are governed by a conjectured trade-off between signal strength and time: Level $\ell$ of the Kikuchi hierarchy should achieve the smooth curve \begin{equation*} m\ \gtrsim\ ρ^{-2}n^{k/2}/\ell^{k/2-1}\ \text{clauses} \quad\Longleftrightarrow\quad \text{solvable in time }n^{O(\ell)}, \end{equation*} where $ρ$ is the bias of the planted signal or, for refutation, the target advantage. However, every spectral analysis of sparse $k$XOR to date loses polylogarithmic factors against this curve, a loss that enters the exponent of the running time. We show that a normalized variant of the Kikuchi hierarchy achieves the sharp conjectured trade-off, with no logarithmic loss, at every arity $k\ge3$. At the scale above, our algorithms achieve strong detection, weak recovery, and strong refutation; an additional cleanup step boosts weak recovery to exact recovery, and the refutation certificates yield sum-of-squares proofs of degree $O_k(\ell)$. We also prove matching lower bounds in the same model. The inference and refutation upper bounds transfer to more general planting laws and predicates. Finally, we give a quantum algorithm that achieves a quartic speedup over the classical spectral algorithms for detection and weak recovery. The proofs rest on two key ingredients: a normalization of the sparse Kikuchi matrix, and a sharp count of the closed walks in its trace expansion. We use a closely related trace-walk count to prove Feige's 2008 hypergraph Moore bound conjecture in a companion paper.

cs.DSCross-listedarXiv:2607.29672•Aug 3, 2026

Quartic Quantum Speedups for Planted Inference

Alexander Schmidhuber, Ryan O’Donnell, Robin Kothari +1 more

We describe a quantum algorithm for the Planted Noisy k XOR Problem (also known as Sparse Learning Parity with Noise) that achieves a nearly (fourth-power) speedup over the best known classical algorithm while using exponentially less space. Our work generalizes and simplifies prior work of Hastings [], by building on his quantum algorithm for the tensor principal component analysis (PCA) problem. We achieve our quantum speedup using a general framework based on the Kikuchi method (recovering the quartic speedup for Tensor PCA), and we anticipate it will yield similar speedups for further planted inference problems. These speedups rely on the fact that planted inference problems naturally instantiate the guided sparse Hamiltonian problem. Since the Planted Noisy k XOR Problem has been used as a component of certain cryptographic constructions, our work suggests that some of these are susceptible to superquadratic quantum attacks.

arXiv:2406.19378•Physical Review X•Jun 2, 2025•20 citations

Quartic quantum speedups for planted inference

Alexander Schmidhuber, Ryan O’Donnell, Robin Kothari +1 more

We describe a quantum algorithm for the Planted Noisy kXOR problem (also known as sparse Learning Parity with Noise) that achieves a nearly quartic (4th power) speedup over the best known classical algorithm while also only using logarithmically many qubits. Our work generalizes and simplifies prior work of Hastings [Has20], by building on his quantum algorithm for the Tensor Principal Component Analysis (PCA) problem. We achieve our quantum speedup using a general framework based on the Kikuchi Method (recovering the quartic speedup for Tensor PCA), and we anticipate it will yield similar speedups for further planted inference problems. These speedups rely on the fact that planted inference problems naturally instantiate the Guided Sparse Hamiltonian problem. Since the Planted Noisy kXOR problem has been used as a component of certain cryptographic constructions, our work suggests that some of these are susceptible to super-quadratic quantum attacks.

Society for Industrial and Applied Mathematics eBooks•Jan 1, 2025•1 citation

Quartic quantum speedups for community detection

Alexander Schmidhuber, Alexander Zlokapa

Community detection is a foundational problem in data science. Its natural extension to hypergraphs captures higher-order correlations beyond pairwise interactions. In this work, we develop a quantum algorithm for hypergraph community detection that achieves a quartic quantum speedup over the best known classical algorithm, along with superpolynomial savings in space. Our algorithm is based on the Kikuchi method, which we extend beyond previously considered problems such as Tensor PCA and $p$XORSAT to a broad family of generalized stochastic block models. To demonstrate (near) optimality of this method, we prove matching lower bounds (up to logarithmic factors) in the low-degree framework, showing that the algorithm saturates a smooth statistical-computational tradeoff. The quantum speedup arises from a quantized version of the Kikuchi method and is based on the efficient preparation of a guiding state correlated with the underlying community structure. Our work suggests that prior quantum speedups using the Kikuchi method are sufficiently robust to encompass a broader set of problems than previously believed; we conjecture that a quantity known as marginal order characterizes the existence of these quantum speedups.

arXiv:2510.08494•Oct 9, 2025•6 citations

Quantum Speedup for Hypergraph Sparsification

C. L. Liu, Minbo Gao, Zhengfeng Ji +1 more

Graph sparsification serves as a foundation for many algorithms, such as approximation algorithms for graph cuts and Laplacian system solvers. As its natural generalization, hypergraph sparsification has recently gained increasing attention, with broad applications in graph machine learning and other areas. In this work, we propose the first quantum algorithm for hypergraph sparsification, addressing an open problem proposed by Apers and de Wolf (FOCS'20). For a weighted hypergraph with $n$ vertices, $m$ hyperedges, and rank $r$, our algorithm outputs a near-linear size $\varepsilon$-spectral sparsifier in time $\widetilde O(r\sqrt{mn}/\varepsilon)$. This algorithm matches the quantum lower bound for constant $r$ and demonstrates quantum speedup when compared with the state-of-the-art $\widetilde O(mr)$-time classical algorithm. As applications, our algorithm implies quantum speedups for computing hypergraph cut sparsifiers, approximating hypergraph mincuts and hypergraph $s$-$t$ mincuts.

arXiv:2505.01763•May 3, 2025•2 citations

A Classical Quadratic Speedup for Planted kkk xor

Meghal Gupta, William He, Ryan O’Donnell +1 more

A recent work of Schmidhuber et al. (QIP, SODA, & Phys. Rev. X 2025) exhibited a quantum algorithm for the noisy planted \(k\)xor problem running quartically faster than all known classical algorithms. In this work, we design a new classical algorithm that is quadratically faster than the best previous one, in the case of large constant \(k\). Thus for such \(k\), the quantum speedup of Schmidhuber et al. becomes only quadratic (though it retains a space advantage). Our algorithm, which also works in the semirandom case, combines tools from sublinear-time algorithms (essentially, the birthday paradox) and polynomial anticoncentration.

arXiv:2508.09422•Society for Industrial and Applied Mathematics eBooks•Jan 1, 2026•7 citations
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 kkk-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 lll-clause sets whose supports XOR to the empty set for detection, or to {i,j}\{i,j\}{i,j} for recovery. The latter products define an n×nn\times nn×n matrix whose leading eigenvector estimates the planted assignment.
For detection, HCE achieves m≳γkρ−2n(n/l)k/2−1m\gtrsim\gamma_k\rho^{-2}n(n/l)^{k/2-1}m≳γk​ρ−2n(n/l)k/2−1, with γk=k−k/2ek/2−1\gamma_k=k^{-k/2}e^{k/2-1}γk​=k−k/2ek/2−1 and explicit error-dependent factors tending to one as admissible lll increases. Recovery follows the same algebraic curve up to polylogarithmic losses: the sufficient density includes (log⁡n)(k+1)l+3(\log n)^{(k+1)l+3}(logn)(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-kkk recovery at l≥6l\ge6l≥6 requires support-based trimming and additional density restrictions.
Meet-in-the-middle construction takes O~(n3+m⌈l/2⌉+nm⌊l/2⌋)\widetilde O(n^3+m^{\lceil l/2\rceil}+nm^{\lfloor l/2\rfloor})O(n3+m⌈l/2⌉+nm⌊l/2⌋) time and O~(n2+m⌈l/2⌉)\widetilde O(n^2+m^{\lceil l/2\rceil})O(n2+m⌈l/2⌉) 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 lll; 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.
Planted noisy kkkXOR and the strong refutation of random kkkXOR are governed by a conjectured trade-off between signal strength and time: Level ℓ\ellℓ of the Kikuchi hierarchy should achieve the smooth curve \begin{equation*} m\ \gtrsim\ ρ^{-2}n^{k/2}/\ell^{k/2-1}\ \text{clauses} \quad\Longleftrightarrow\quad \text{solvable in time }n^{O(\ell)}, \end{equation*} where ρρρ is the bias of the planted signal or, for refutation, the target advantage. However, every spectral analysis of sparse kkkXOR to date loses polylogarithmic factors against this curve, a loss that enters the exponent of the running time. We show that a normalized variant of the Kikuchi hierarchy achieves the sharp conjectured trade-off, with no logarithmic loss, at every arity k≥3k\ge3k≥3. At the scale above, our algorithms achieve strong detection, weak recovery, and strong refutation; an additional cleanup step boosts weak recovery to exact recovery, and the refutation certificates yield sum-of-squares proofs of degree Ok(ℓ)O_k(\ell)Ok​(ℓ). We also prove matching lower bounds in the same model. The inference and refutation upper bounds transfer to more general planting laws and predicates. Finally, we give a quantum algorithm that achieves a quartic speedup over the classical spectral algorithms for detection and weak recovery. The proofs rest on two key ingredients: a normalization of the sparse Kikuchi matrix, and a sharp count of the closed walks in its trace expansion. We use a closely related trace-walk count to prove Feige's 2008 hypergraph Moore bound conjecture in a companion paper.
We describe a quantum algorithm for the Planted Noisy k XOR Problem (also known as Sparse Learning Parity with Noise) that achieves a nearly (fourth-power) speedup over the best known classical algorithm while using exponentially less space. Our work generalizes and simplifies prior work of Hastings [], by building on his quantum algorithm for the tensor principal component analysis (PCA) problem. We achieve our quantum speedup using a general framework based on the Kikuchi method (recovering the quartic speedup for Tensor PCA), and we anticipate it will yield similar speedups for further planted inference problems. These speedups rely on the fact that planted inference problems naturally instantiate the guided sparse Hamiltonian problem. Since the Planted Noisy k XOR Problem has been used as a component of certain cryptographic constructions, our work suggests that some of these are susceptible to superquadratic quantum attacks.
We describe a quantum algorithm for the Planted Noisy kXOR problem (also known as sparse Learning Parity with Noise) that achieves a nearly quartic (4th power) speedup over the best known classical algorithm while also only using logarithmically many qubits. Our work generalizes and simplifies prior work of Hastings [Has20], by building on his quantum algorithm for the Tensor Principal Component Analysis (PCA) problem. We achieve our quantum speedup using a general framework based on the Kikuchi Method (recovering the quartic speedup for Tensor PCA), and we anticipate it will yield similar speedups for further planted inference problems. These speedups rely on the fact that planted inference problems naturally instantiate the Guided Sparse Hamiltonian problem. Since the Planted Noisy kXOR problem has been used as a component of certain cryptographic constructions, our work suggests that some of these are susceptible to super-quadratic quantum attacks.
Community detection is a foundational problem in data science. Its natural extension to hypergraphs captures higher-order correlations beyond pairwise interactions. In this work, we develop a quantum algorithm for hypergraph community detection that achieves a quartic quantum speedup over the best known classical algorithm, along with superpolynomial savings in space. Our algorithm is based on the Kikuchi method, which we extend beyond previously considered problems such as Tensor PCA and pppXORSAT to a broad family of generalized stochastic block models. To demonstrate (near) optimality of this method, we prove matching lower bounds (up to logarithmic factors) in the low-degree framework, showing that the algorithm saturates a smooth statistical-computational tradeoff. The quantum speedup arises from a quantized version of the Kikuchi method and is based on the efficient preparation of a guiding state correlated with the underlying community structure. Our work suggests that prior quantum speedups using the Kikuchi method are sufficiently robust to encompass a broader set of problems than previously believed; we conjecture that a quantity known as marginal order characterizes the existence of these quantum speedups.
Graph sparsification serves as a foundation for many algorithms, such as approximation algorithms for graph cuts and Laplacian system solvers. As its natural generalization, hypergraph sparsification has recently gained increasing attention, with broad applications in graph machine learning and other areas. In this work, we propose the first quantum algorithm for hypergraph sparsification, addressing an open problem proposed by Apers and de Wolf (FOCS'20). For a weighted hypergraph with nnn vertices, mmm hyperedges, and rank rrr, our algorithm outputs a near-linear size ε\varepsilonε-spectral sparsifier in time O~(rmn/ε)\widetilde O(r\sqrt{mn}/\varepsilon)O(rmn​/ε). This algorithm matches the quantum lower bound for constant rrr and demonstrates quantum speedup when compared with the state-of-the-art O~(mr)\widetilde O(mr)O(mr)-time classical algorithm. As applications, our algorithm implies quantum speedups for computing hypergraph cut sparsifiers, approximating hypergraph mincuts and hypergraph sss-ttt mincuts.
A recent work of Schmidhuber et al. (QIP, SODA, & Phys. Rev. X 2025) exhibited a quantum algorithm for the noisy planted kkkxor problem running quartically faster than all known classical algorithms. In this work, we design a new classical algorithm that is quadratically faster than the best previous one, in the case of large constant kkk. Thus for such kkk, the quantum speedup of Schmidhuber et al. becomes only quadratic (though it retains a space advantage). Our algorithm, which also works in the semirandom case, combines tools from sublinear-time algorithms (essentially, the birthday paradox) and polynomial anticoncentration.