Quantum Advantage in Tolerant Junta Testing (opens in new tab)

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^{\Omega(\log k)}$ queries. The problem of tolerant $k$-junta testing is as follows: given parameters $(k, \ep...