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 poly(k) quantum queries, whereas any classical algorithm requires at least kΩ(logk) queries.
The problem of tolerant k-junta testing is as follows: given parameters (k,ε1,ε2), with 0≤ε1<ε2≤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/(2k2). 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 2n−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 ko(logk) 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 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, ε₁, ε₂), with 0 ≤ ε₁ < ε₂ ≤ 1/2, and black-box access to a Boolean function f (defined on n variables), distinguish whether f is ε₁-close to some k-junta or ε₂-far from every k-junta. We show the quantum advantage for a range of parameters close to 1/2, for example, ε₁ = 1/2-1/k and ε₂ = 1/2-1/(2k²). (As such, the problem is more naturally captured using the notion of correlation with closest k-junta.) 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 ε₁ 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 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 study the query complexity of testing quantum juntas. Given an unknown n-qubit unitary or quantum channel, the goal is to decide whether it acts nontrivially on at most k qubits or is ε-far from every such operation. For unitaries, we consider the forward-only model, where the tester has access to U, but not to U† or controlled-U. We give tight bounds for both unitary and channel junta testing. For sufficiently large k, n≥2k, and a broad range of ε, both problems have query complexity Θ(k/(ε2logk)). Our upper bounds are achieved by simple nonadaptive testers using product inputs and single-qubit measurements. For junta channels, this closes the gap by Bao and Yao (COLT 23, TPAMI 2025) between an O(k) upper bound and a Ω(k) lower bound at constant ε, establishing the optimal Θ(k/logk) query complexity. At the heart of both bounds is a strong connection between quantum junta testing and classical support-size testing. For the upper bounds, we reduce quantum junta testing to a generalized support-size problem for distributions over random subsets, and develop a new tester with improved sample complexity. For the lower bounds, we proceed in the reverse direction, reducing classical support-size testing to quantum junta testing through a phase-masked hard ensemble and showing that forward quantum queries can be exactly classicalized on average. Together, these reductions identify support-size testing as the classical core of quantum junta testing and yield matching lower bounds. At constant ε, they also give a separation between Θ(k/logk) forward queries and O(k) queries with inverse access.
Junta testing for Boolean functions has sparked a long line of work over recent decades in theoretical computer science, and recently has also been studied for unitary operators in quantum computing. Tolerant junta testing is more general and challenging than the standard version. While optimal tolerant junta testers have been obtained for Boolean functions, there has been no knowledge about tolerant junta testers for unitary operators, which was thus left as an open problem in [Chen, Nadimpalli, and Yuen, SODA2023]. In this paper, we settle this problem by presenting the first algorithm to decide whether a unitary is ε1-close to some quantum k-junta or is ε2-far from any quantum k-junta, where an n-qubit unitary U is called a quantum k-junta if it only non-trivially acts on just k of the n qubits. More specifically, we present a tolerant tester with ε1=8ρε, ε2=ε, and ρ∈(0,1), and the query complexity is O(ε2ρ(1−ρ)kklogk), which demonstrates a trade-off between the amount of tolerance and the query complexity. Note that our algorithm is non-adaptive which is preferred over its adaptive counterparts, due to its simpler as well as highly parallelizable nature. At the same time, our algorithm does not need access to U†, whereas this is usually required in the literature.
We consider the problem of deciding whether an n-qubit unitary (or n-bit Boolean function) is ε1-close to some k-junta or ε2-far from every k-junta, where k-junta unitaries act non-trivially on at most k qubits and as the identity on the rest, and k-junta Boolean functions depend on at most k variables. For constant numbers ε1,ε2 such that 0<ε1<ε2<1, we show the following.1.A non-adaptive O(klogk)-query tolerant (ε1,ε2)-tester for k-junta unitaries when 22ε1<ε2.2.A non-adaptive tolerant (ε1,ε2)-tester for k-junta Boolean functions with O(klogk) quantum queries when 4ε1<ε2.3.A 2O(k)-query tolerant (ε1,ε2)-tester for k-junta unitaries for any ε1,ε2.The first algorithm provides an exponential improvement over the best-known quantum algorithms [CLL24, ADG25]. The second algorithm shows an exponential quantum advantage over any non-adaptive classical algorithm [CDL+24]. The third tester gives the first tolerant junta unitary testing result for an arbitrary gap.
Aaronson and Ambainis (Theory of Computing, 2014) conjectured that quantum query algorithms admit efficient almost-everywhere classical simulation: for any T-query quantum algorithm, its acceptance probability can be approximated on a (1−δ) fraction of inputs, up to ε additive error, using poly(T,1/ε,1/δ) classical queries. At a high level, the conjecture suggests that exponential quantum speedups are possible only on sufficiently structured inputs.
In this work, we make progress on this conjecture by proving it for quantum algorithms that make massively parallel quantum queries. In contrast, Yamakawa and Zhandry (Journal of the ACM, 2024) showed that quantum algorithms restricted to parallel queries can still achieve exponential speedups over classical algorithms for sampling problems. We establish our simulation theorem by proving the stronger statement that parallel-query quantum algorithms cannot distinguish the uniform distribution over oracles from oracles drawn from so-called "dense distributions". Our main technical contribution is a coupling theorem that relates the uniform distribution over oracles to oracles drawn from dense distributions.
We further extend this approach beyond the purely parallel setting. We prove simulation theorems for quantum algorithms with constant rounds of adaptivity, and for quantum algorithms with a bounded quantum-query prefix followed by a massively parallel quantum-query stage.
In the search with wildcards problem [Ambainis, Montanaro, Quantum Inf.~Comput.'14], one's goal is to learn an unknown bit-string x∈{−1,1}n. An algorithm may, at unit cost, test equality of any subset of the hidden string with a string of its choice. Ambainis and Montanaro showed a quantum algorithm of cost O(nlogn) and a near-matching lower bound of Ω(n). Belovs [Comput.~Comp.'15] subsequently showed a tight O(n) upper bound.
We consider a natural generalization of this problem, parametrized by a subset Q⊆2[n], where an algorithm may test whether xS=b for an arbitrary S∈Q and b∈{−1,1}S of its choice, at unit cost. We show near-tight bounds when Q is any of the following collections: bounded-size sets, contiguous blocks, prefixes, and only the full set.
All of these results are derived using a framework that we develop. Using symmetries of the task at hand we show that the quantum query complexity of learning x is characterized, up to a constant factor, by an optimization program, which is succinctly described as follows: `maximize over all odd functions f:{−1,1}n→R the ratio of the maximum value of f to the maximum (over T∈Q) standard deviation of f on a subcube whose free variables are exactly T.'
To the best of our knowledge, ours is the first work to use the primal version of the negative-weight adversary bound (which is a maximization program typically used to show lower bounds) to show new quantum query upper bounds without explicitly resorting to SDP duality.