Nearly Optimal Quantum Sample Complexity of Learning Fourier-Sparse Boolean Functions
Abstract
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 Õ(k) sample complexity independent of the input length n. The learner uses only separate measurements of individual examples. This improves the previous O(k3/2log2 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 combines unbiased random approximations into an accurate witness whose Fourier support lies in this set. Granularity then forces the set to contain the entire Fourier support, including subsets never directly sampled. For comparison, we derive the tight classical sample complexity Θ(nk) by combining known sparse-recovery and lower-bound results.
Related
- On the quantum communication complexity of total functions
- Constant-round quantum advantage in communication complexity for total functions
- Improved Separations between Quantum and Classical Communication Complexity of Total Functions
- Near-Optimal Separations of Certificate Complexity from Randomized and Quantum Query Complexity
- Near-Optimal Quantum Lower Bounds for Convex Optimization via Fourier Rank
BibTeX
@misc{ye2026nearly,
title = {{Nearly Optimal Quantum Sample Complexity of Learning Fourier-Sparse Boolean Functions}},
author = {Zekun Ye},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2610.17648},
eprint = {2610.17648},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2610.17648},
}
RIS
TY - UNPB
TI - Nearly Optimal Quantum Sample Complexity of Learning Fourier-Sparse Boolean Functions
AU - Zekun Ye
PY - 2026
DA - 2026/10/13
PB - arXiv
DO - 10.48550/arxiv.2610.17648
UR - https://arxiv.org/abs/2610.17648
AB - 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 Õ(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/2log^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 combines unbiased random approximations into an accurate witness whose Fourier support lies in this set. Granularity then forces the set to contain the entire Fourier support, including subsets never directly sampled. For comparison, we derive the tight classical sample complexity Θ(nk) by combining known sparse-recovery and lower-bound results.
ER -