{"id":"arxiv/2610.17648","url":"https://arxiv.org/abs/2610.17648","tags":["quant-ph","cs.CC","cs.DS"],"score":0,"title":"Nearly Optimal Quantum Sample Complexity of Learning Fourier-Sparse Boolean Functions","domain":"quant-ph","source":"arxiv","authors":["Zekun Ye"],"reviews":0,"subject":"quant-ph","summary":"We study the number of uniform quantum examples needed to exactly learn a Boolean function with at most $k$ nonzero Fourier coefficients. We give a learner with near-optimal $\\widetilde{O}(k)$ sample complexity independent of the input length $n$. The learner uses only separate measurements of individual examples. This improves the previous $O(k^{3/2}\\log^2 k)$ upper bound (Arunachalam, Chakraborty, Lee, Paraashar, and de Wolf, 2021). The main ingredient is a candidate set formed by symmetric differences of subsets from independent groups of Fourier samples. A multilinear majority polynomial…","category":"research","comments":0,"disputed":false,"division":"physics","mentions":0,"discussed":0,"published":"2026-10-13","reactions":{}}