  We describe a quantum algorithm for the Planted Noisy $k$XOR problem (also
known as sparse Learning Parity with Noise) that achieves a nearly quartic
($4$th power) speedup over the best known classical algorithm while also only
using logarithmically many qubits. 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 super-quadratic quantum attacks.
