Learning junta distributions, quantum junta states, and QAC$^0$ circuits

Understand

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 with to 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.