Efficient Non-Adaptive Quantum Algorithms for Tolerant Junta Testing

We consider the problem of deciding whether an \(n\)-qubit unitary (or \(n\)-bit Boolean function) is \(\varepsilon_1\)-close to some \(k\)-junta or \(\varepsilon_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 \(\varepsilon_1, \varepsilon_2\) such that \(0 \lt \varepsilon_1 \lt \varepsilon_2 \lt 1\), we show the following.1.A non-adaptive \(O(k \log k)\)-query tolerant (\(\varepsilon_1, \varepsilon_2\))-tester for \(k\)-junta unitaries when \(2\sqrt2\varepsilon_1 \lt \varepsilon_2\).2.A non-adaptive tolerant (\(\varepsilon_1, \varepsilon_2\))-tester for \(k\)-junta Boolean functions with \(O(k \log k)\) quantum queries when \(4\varepsilon_1 \lt \varepsilon_2\).3.A \(2^{\widetilde{O}(k)}\)-query tolerant (\(\varepsilon_1, \varepsilon_2\))-tester for \(k\)-junta unitaries for any \(\varepsilon_1, \varepsilon_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.