Yuxuan Liu

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 < \varepsilon_1 < \varepsilon_2 < 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\sqrt{2}\varepsilon_1 < \varepsilon_2$. 2. A non-adaptive tolerant $(\varepsilon_1,\varepsilon_2)$-tester for Boolean functions with $O(k \log k)$ quantum queries when $4\varepsilon_1 < \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+25]. The third tester gives the first tolerant junta unitary testing result for an arbitrary gap. Besides, we adapt the first two quantum algorithms to be implemented using only single-qubit operations, thereby enhancing experimental feasibility, with a slightly more stringent requirement for the parameter gap.