A Classical Quadratic Speedup for Planted $k$XOR

Meghal Gupta, William He, Ryan O'Donnell +1

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