In the k-junta testing problem, a tester has to efficiently decide whether a given function f: {0,1}n → {0,1} is a k-junta (i.e., depends on at most k of its input bits) or is ∈-far from any k-junta. Our main result is a quantum algorithm for this problem with query complexity Ō(√∈) and time complexity Ō(n√∈). This quadratically improves over the query complexity of the previous best quantum junta tester, due to Atici and Servedio. Our tester is based on a new quantum algorithm for a gapped version of the combinatorial group testing problem, with an up to quartic improvement over the query complexity of the best classical algorithm. For our upper bound on the time complexity we give a near-linear time implementation of a shallow variant of the quantum Fourier transform over the symmetric group, similar to the Schur-Weyl transform. We also prove a lower bound of ω(k1/3) queries for junta-testing (for constant ∈).
In the k-junta testing problem, a tester has to efficiently decide whether a given function f: {0,1}n → {0,1} is a k-junta (i.e., depends on at most k of its input bits) or is ∈-far from any k-junta. Our main result is a quantum algorithm for this problem with query complexity Ō(√∈) and time complexity Ō(n√∈). This quadratically improves over the query complexity of the previous best quantum junta tester, due to Atici and Servedio. Our tester is based on a new quantum algorithm for a gapped version of the combinatorial group testing problem, with an up to quartic improvement over the query complexity of the best classical algorithm. For our upper bound on the time complexity we give a near-linear time implementation of a shallow variant of the quantum Fourier transform over the symmetric group, similar to the Schur-Weyl transform. We also prove a lower bound of ω(k1/3) queries for junta-testing (for constant ∈).
In the k-junta testing problem, a tester has to efficiently decide whether a given function f: {0, 1}n → {0, 1} is a k-junta (i.e., depends on at most k of its input bits) or is ∊-far from any k-junta. Our main result is a quantum algorithm for this problem with query complexity and time complexity . This quadratically improves over the query complexity of the previous best quantum junta tester, due to Atıcı and Servedio. Our tester is based on a new quantum algorithm for a gapped version of the combinatorial group testing problem, with an up to quartic improvement over the query complexity of the best classical algorithm. For our upper bound on the time complexity we give a near-linear time implementation of a shallow variant of the quantum Fourier transform over the symmetric group, similar to the Schur-Weyl transform. We also prove a lower bound of Ω(k1/3) queries for junta-testing (for constant ∊).
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.
In the k-junta testing problem, a tester has to efficiently decide whether a given function f:{0,1}n→{0,1} is a k-junta (i.e., depends on at most k of its input bits) or is ε-far from any k-junta. Our main result is a quantum algorithm for this problem with query complexity O~(k/ε) and time complexity O~(nk/ε). This quadratically improves over the query complexity of the previous best quantum junta tester, due to Atıcı and Servedio. Our tester is based on a new quantum algorithm for a gapped version of the combinatorial group testing problem, with an up to quartic improvement over the query complexity of the best classical algorithm. For our upper bound on the time complexity we give a near-linear time implementation of a shallow variant of the quantum Fourier transform over the symmetric group, similar to the Schur-Weyl transform. We also prove a lower bound of Ω(k1/3) queries for junta-testing (for constant ε).
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.
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 consider the problem of testing and learning quantum k-juntas: n-qubit unitary matrices which act non-trivially on just k of the n qubits and as the identity on the rest. As our main algorithmic results, we give 1. A -query quantum algorithm that can distinguish quantum k-juntas from unitary matrices that are “far” from every quantum k-junta; and 2. A O(4k)-query algorithm to learn quantum k-juntas. We complement our upper bounds for testing and learning quantum k-juntas with near-matching lower bounds of and Ω(4k/k), respectively. Our techniques are Fourier-analytic and make use of a notion of influence of qubits on unitaries. * The full version of the paper can be accessed at https://arxiv.org/abs/2207.05898