Learning Junta Distributions, Quantum Junta States, and QAC$^0$ Circuits

In this work, we consider the problems of learning junta distributions, their quantum counterparts (quantum junta states), and $\mathsf{QAC}^0$ circuits, which we show to be close to juntas. (1) Junta distributions. A probability distribution $p:${-1,1}$^n\to \mathbb [0,1]$ is a $k$-junta if it only depends on $k$ bits. We show that they can be learned to within additive error $\varepsilon$ in total variation distance from $O(2^k\log(n)/\varepsilon^2)$ samples, which quadratically improves the upper bound of Aliakbarpour et al. (COLT'16) and matches their lower bound in every parameter. (2) Junta states. We initiate the study of $n$-qubit states that are $k$-juntas, those that are the tensor product of a $k$-qubit state and an $(n-k)$-qubit maximally mixed state. We show that these states can be learned with error $\varepsilon$ in trace distance with $O(12^{k}\log(n)/\varepsilon^2)$ single copies. We also prove a lower bound of $\Omega((4^k+\log (n))/\varepsilon^2)$ copies. Additionally, we show that, for constant $k$, $\widetilde{\Theta}(2^n/\varepsilon^2)$ copies are necessary and sufficient to test whether a state is $\varepsilon$-close or $7\varepsilon$-far from being a $k$-junta. (3) $\mathsf{QAC}^0$ circuits. We show that $n$-qubit $\mathsf{QAC}^0$ circuits with size $s$, depth $d$ and $a$ auxiliary qubits can be learned from $2^{O(\log(s^22^a)^d)}\log(n)$ copies of the Choi state, improving the $n^{O(\log(s^22^a)^d)}$ by Nadimpalli et al. (STOC'24). Along the way, we give new proof of the optimal performance of Classical Shadows based on Pauli analysis. We also strengthen the lower bounds against $\mathsf{QAC}^0$ to compute the address function.

Modern learning algorithms often face very large systems where most variables are irrelevant, and the challenge is to identify and learn only the few that matter. This paper studies the challenge for classical probability distributions, quantum states, and a standard model of shallow quantum circuits. We focus on ``juntas'': objects that may involve many bits or qubits, but whose behavior is actually controlled by only a small hidden subset. We show how to learn such distributions with the optimal number of samples, improving the best previous guarantee. We also introduce and analyze a quantum version, where only a few qubits carry useful information while the rest behave like pure noise. Our methods reveal that certain shallow quantum circuits have a similar “few relevant parts” structure, which lets us learn them more efficiently than before. The key idea is to look for simple, sparse patterns in the mathematical fingerprints of these objects, rather than treating the whole system as equally important. These results sharpen our understanding of when high-dimensional classical and quantum systems can be learned efficiently, and they provide new tools for studying the limits of shallow quantum computation.