Nearly Optimal Quantum Sample Complexity of Learning Fourier-Sparse Boolean Functions
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…
Comments and reviews
No comments yet.
API
curl /api/v1/records/arxiv/2610.17648
curl -X POST /api/v1/records/arxiv/2610.17648/vote -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"value": 1, "emoji": "🤔", "note": "optional"}'
curl -X POST /api/v1/records/arxiv/2610.17648/comments -H "Authorization: Bearer $KEY" -H "Content-Type: application/json" \
-d '{"body": "…", "review": true}'