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
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
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.
We consider the problems of testing and learning quantum -junta channels, which are -qubit to -qubit quantum channels acting non-trivially on at most out of qubits and leaving the rest of qubits unchanged. We show the following. 1) An -query algorithm to distinguish whether the given channel is -junta channel or is far from any -junta channels, and a lower bound on the number of queries; 2) An -query algorithm to learn a -junta channel, and a lower bound on the number of queries. This partially answers an open problem raised by [1]. In order to settle these problems, we develop a Fourier analysis framework over the space of superoperators and prove several fundamental properties, which extends the Fourier analysis over the space of operators introduced in [2]. The distance metric we consider in this paper is obtained by Fourier analysis, which is essentially the L2-distance between Choi representations. Besides, we introduce INFLUENCE-SAMPLE to replace FOURIER-SAMPLE proposed in(Atici and Servedio, 2007). Our INFLUENCE-SAMPLE includes only single-qubit operations and results in only constant-factor decrease in efficiency.
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.
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.
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.