Testing and Learning Quantum Juntas Nearly Optimally

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