{"id":"arxiv/2606.23194","url":"https://arxiv.org/abs/2606.23194","tags":["cs.CC","quant-ph"],"score":0,"title":"Quantum Advantage in Tolerant Junta Testing","domain":"cs.CC","source":"arxiv","authors":["Avishay Tal","Weiqiang Yuan"],"reviews":0,"subject":"cs.CC","summary":"We establish the first super-polynomial quantum advantage for the tolerant junta testing problem in the adaptive setting. Specifically, we show that within a certain parameter regime, tolerant $k$-junta testing with high precision can be solved using $\\mathrm{poly}(k)$ quantum queries, whereas any classical algorithm requires at least $k^{Ω(\\log k)}$ queries. The problem of tolerant $k$-junta testing is as follows: given parameters $(k, ε_1, ε_2)$, with $0\\le ε_1<ε_2 \\le 1/2$, and black-box access to a Boolean function $f$ (defined on $n$ variables), distinguish whether $f$ is $ε_1$-close to…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-06-22","reactions":{}}