Quartic quantum speedups for planted inference

arXiv:2406.19378v1 Announce Type: cross
Abstract: 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 …

algorithm arxiv cs.cc cs.cr noise noisy power problem quant-ph quantum qubits using work xor