Penghui Yao

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.

Ma and Huang recently proved that the PFC construction, introduced by Metger, Poremba, Sinha and Yuen [MPSY24], gives an adaptive-secure pseudorandom unitary family (PRU). Their proof developed a new path recording technique. In this work, we show that a linear number of sequential repetitions of the parallel Kac's Walk, introduced by Lu, Qin, Song, Yao and Zhao [LQSY+24], also forms an adaptive-secure PRU, confirming a conjecture therein. Moreover, it additionally satisfies strong security against adversaries making inverse queries. This gives an alternative PRU construction, and provides another instance demonstrating the power of the path recording technique. We also discuss some further simplifications and implications.