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 some $k$ -junta or $ε_2$ -far from every $k$ -junta. We show the quantum advantage for a range of parameters close to $1/2$ , for example, $ε_1 = 1/2-1/k$ and $ε_2 = 1/2-1/(2k^2)$ . The (non-adaptive) quantum tester we use was given by a recent work of Bao, Liu, Yao, Ye, and Zhang (SOSA 2026). We slightly adapt their analysis to show that it holds in the above parameter regime. On the other hand, our classical lower bound requires substantial new ideas. Inspired by the lower bound techniques of Chen and Patel (FOCS 2023), we introduce a new hard distribution of ``yes'' instances (i.e., instances with distance at most $ε_1$ to $k$ -juntas) that is based on planting an ``approximate-junta'' as follows: we randomly pick $k$ out of $n$ coordinates, and for each fixing of the $k$ coordinates, the $2^{n-k}$ values in the restricted subcube are drawn randomly except for the set of points in an error-correcting code on which we place the same random bit. We show that this distribution is much closer to $k$ -juntas than the uniform distribution, but on the other hand, they are indistinguishable with respect to any classical algorithm making $k^{o(\log k)}$ queries.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 some $k$-junta or $ε_2$-far from every $k$-junta. We show the quantum advantage for a range of parameters close to $1/2$, for example, $ε_1 = 1/2-1/k$ and $ε_2 = 1/2-1/(2k^2)$. The (non-adaptive) quantum tester we use was given by a recent work of Bao, Liu, Yao, Ye, and Zhang (SOSA 2026). We slightly adapt their analysis to show that it holds in the above parameter regime. On the other hand, our classical lower bound requires substantial new ideas. Inspired by the lower bound techniques of Chen and Patel (FOCS 2023), we introduce a new hard distribution of ``yes'' instances (i.e., instances with distance at most $ε_1$ to $k$-juntas) that is based on planting an ``approximate-junta'' as follows: we randomly pick $k$ out of $n$ coordinates, and for each fixing of the $k$ coordinates, the $2^{n-k}$ values in the restricted subcube are drawn randomly except for the set of points in an error-correcting code on which we place the same random bit. We show that this distribution is much closer to $k$-juntas than the uniform distribution, but on the other hand, they are indistinguishable with respect to any classical algorithm making $k^{o(\log k)}$ queries.

cs.CCCross-listedarXiv:2606.23194Jun 23, 20260 citations

A Exact Quantum Learning Algorithm for the 2-Junta Problem in Constant Time

Chien-Yuan Chen

International Journal of Theoretical PhysicsAug 3, 20224 citations

An exact quantum logarithmic time algorithm for the 3-junta problem

Chien-Yuan Chen

Quantum Information ProcessingJun 7, 20243 citations

An Exact Quantum Algorithm for the 2-Junta Problem

Chien-Yuan Chen

International Journal of Theoretical PhysicsJan 1, 20215 citations

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

ε_1

-close to some

k

-junta or

ε_2

-far from every

k

-junta. We show the quantum advantage for a range of parameters close to

1/2

, for example,

ε_1 = 1/2-1/k

and

ε_2 = 1/2-1/(2k^2)

. The (non-adaptive) quantum tester we use was given by a recent work of Bao, Liu, Yao, Ye, and Zhang (SOSA 2026). We slightly adapt their analysis to show that it holds in the above parameter regime. On the other hand, our classical lower bound requires substantial new ideas. Inspired by the lower bound techniques of Chen and Patel (FOCS 2023), we introduce a new hard distribution of ``yes'' instances (i.e., instances with distance at most

ε_1

k

-juntas) that is based on planting an ``approximate-junta'' as follows: we randomly pick

k

out of

n

coordinates, and for each fixing of the

k

coordinates, the

2^{n-k}

values in the restricted subcube are drawn randomly except for the set of points in an error-correcting code on which we place the same random bit. We show that this distribution is much closer to

k

-juntas than the uniform distribution, but on the other hand, they are indistinguishable with respect to any classical algorithm making

k^{o(\log k)}

queries.