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

Society for Industrial and Applied Mathematics eBooks

Quartic quantum speedups for planted inference

Alexander Schmidhuber, Ryan O’Donnell, Robin Kothari, Ryan Babbush

Published Jan 1, 2025• 1 citation
Publisher

Abstract

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.

DOI
10.1137/1.9781611978322.26

Related papers

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 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

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

Arman Babakhani, Enrico Fontana, Junhyung Lyle Kim +2 more

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.

quant-pharXiv:2610.40941•Nov 2, 2026•0 citations

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

End-to-end quantum algorithms for tensor problems

Fontana, Enrico, Sivaprasad Omanakuttan, Junhyung Lyle Kim +4 more

We present a comprehensive end-to-end quantum algorithm for tensor problems, including tensor PCA and planted kXOR, that achieves potential superquadratic quantum speedups over classical methods. We build upon prior works by Hastings~(\textit{Quantum}, 2020) and Schmidhuber~\textit{et al.}~(\textit{Phys.~Rev.~X.}, 2025), we address key limitations by introducing a native qubit-based encoding for the Kikuchi method, enabling explicit quantum circuit constructions and non-asymptotic resource estimation. Our approach substantially reduces constant overheads through a novel guiding state preparation technique as well as circuit optimizations, reducing the threshold for a quantum advantage. We further extend the algorithmic framework to support recovery in sparse tensor PCA and tensor completion, and generalize detection to asymmetric tensors, demonstrating that the quantum advantage persists in these broader settings. Detailed resource estimates show that 900 logical qubits, $\sim 10^{15}$ gates and $\sim 10^{12}$ gate depth suffice for a problem that classically requires $\sim 10^{23}$ FLOPs. The gate count and depth for the same problem without the improvements presented in this paper would be at least $10^{19}$ and $10^{18}$ respectively. These advances position tensor problems as a candidate for quantum advantage whose resource requirements benefit significantly from algorithmic and compilation improvements; the magnitude of the improvements suggest that further enhancements are possible, which would make the algorithm viable for upcoming fault-tolerant quantum hardware.

arXiv:2510.07273•Oct 8, 2025•4 citations

Accelerating Classical and Quantum Tensor PCA

Matthew B. Hastings

Spectral methods are a leading approach for tensor PCA with a ``spiked" Gaussian tensor. The methods use the spectrum of a linear operator in a vector space with exponentially high dimension and in Ref. 1 it was shown that quantum algorithms could then lead to an exponential space saving as well as a quartic speedup over classical. Here we show how to accelerate both classical and quantum algorithms quadratically, while maintaining the same quartic separation between them. That is, our classical algorithm here is quadratically faster than the original classical algorithm, while the quantum algorithm is eigth-power faster than the original classical algorithm. We then give a further modification of the quantum algorithm, increasing its speedup over the modified classical algorithm to the sixth power. We only prove these speedups for detection, rather than recovery, but we give a strong plausibility argument that our algorithm achieves recovery also. Note added: After this paper was prepared, A. Schmidhuber pointed out to me Ref. 3. This improves the best existing bounds on the spectral norm of a certain random operator. Because the norm of this operator enters into the runtime, with this improvement on the norm, we no longer have a provable polynomial speedup. Our results are phrased in terms of certain properties of the spectrum of this operator (not merely the largest eigenvalue but also the density of states). So, if these properties still hold, the speedup still holds. Rather than modify the paper, I have left it unchanged but added a section at the end discussing the needed property of density of states and considering for which problems (there are several problems for which this kind of quartic quantum speedup has been used and the techniques here will likely be applicable to several of them) the property is likely to hold.

quant-pharXiv:2602.10366•Feb 12, 2026•1 citation
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.
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.
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.
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.
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 present a comprehensive end-to-end quantum algorithm for tensor problems, including tensor PCA and planted kXOR, that achieves potential superquadratic quantum speedups over classical methods. We build upon prior works by Hastings~(\textit{Quantum}, 2020) and Schmidhuber~\textit{et al.}~(\textit{Phys.~Rev.~X.}, 2025), we address key limitations by introducing a native qubit-based encoding for the Kikuchi method, enabling explicit quantum circuit constructions and non-asymptotic resource estimation. Our approach substantially reduces constant overheads through a novel guiding state preparation technique as well as circuit optimizations, reducing the threshold for a quantum advantage. We further extend the algorithmic framework to support recovery in sparse tensor PCA and tensor completion, and generalize detection to asymmetric tensors, demonstrating that the quantum advantage persists in these broader settings. Detailed resource estimates show that 900 logical qubits, ∼1015\sim 10^{15}∼1015 gates and ∼1012\sim 10^{12}∼1012 gate depth suffice for a problem that classically requires ∼1023\sim 10^{23}∼1023 FLOPs. The gate count and depth for the same problem without the improvements presented in this paper would be at least 101910^{19}1019 and 101810^{18}1018 respectively. These advances position tensor problems as a candidate for quantum advantage whose resource requirements benefit significantly from algorithmic and compilation improvements; the magnitude of the improvements suggest that further enhancements are possible, which would make the algorithm viable for upcoming fault-tolerant quantum hardware.
Spectral methods are a leading approach for tensor PCA with a ``spiked" Gaussian tensor. The methods use the spectrum of a linear operator in a vector space with exponentially high dimension and in Ref. 1 it was shown that quantum algorithms could then lead to an exponential space saving as well as a quartic speedup over classical. Here we show how to accelerate both classical and quantum algorithms quadratically, while maintaining the same quartic separation between them. That is, our classical algorithm here is quadratically faster than the original classical algorithm, while the quantum algorithm is eigth-power faster than the original classical algorithm. We then give a further modification of the quantum algorithm, increasing its speedup over the modified classical algorithm to the sixth power. We only prove these speedups for detection, rather than recovery, but we give a strong plausibility argument that our algorithm achieves recovery also. Note added: After this paper was prepared, A. Schmidhuber pointed out to me Ref. 3. This improves the best existing bounds on the spectral norm of a certain random operator. Because the norm of this operator enters into the runtime, with this improvement on the norm, we no longer have a provable polynomial speedup. Our results are phrased in terms of certain properties of the spectrum of this operator (not merely the largest eigenvalue but also the density of states). So, if these properties still hold, the speedup still holds. Rather than modify the paper, I have left it unchanged but added a section at the end discussing the needed property of density of states and considering for which problems (there are several problems for which this kind of quartic quantum speedup has been used and the techniques here will likely be applicable to several of them) the property is likely to hold.