Query Learning Nearly Pauli Sparse Unitaries in Diamond Distance

We study the problem of learning nearly $(s,\epsilon )$-sparse unitaries, meaning that the Pauli spectrum is concentrated on at most $s$ components with at most $\epsilon$ residual mass in Pauli ${\ell }_1$-norm. This class generalizes well-studied families, including sparse unitaries, quantum $k$-juntas, $2^k$-Pauli dimensional channels, and compositions of depth $O(\log \log n)$ circuits with near-Clifford circuits. Given only forward query access to an unknown nearly sparse unitary $U$, our goal is to efficiently (both in time and query complexity) construct a quantum mapping that is close in diamond distance to $U$. We design a learning algorithm achieving this guarantee using $\tilde{O}(s^3/{\epsilon }^2)$ (non-controlled) forward queries to $U$, and running time polynomial in relevant parameters. A key contribution is an efficient quantum algorithm that, given query access to an arbitrary unknown unitary $U$, estimates all Pauli coefficients (up to a shared global phase) whose magnitude exceeds a given threshold $\theta$. We also study the broader class of unitaries with bounded Pauli ${\ell }_1$-norm. For that class, we prove an exponential query lower bound $\Omega (2^{n/2})$. We introduce a more relaxed accuracy metric, which is the diamond distance restricted to a set of input states. Then, we show that, under this metric, unitaries with Pauli ${\ell }_1$-norm uniformly bounded by $L_1$ are learnable with $\tilde{O}(L_1^4/{\epsilon }^8)$ queries.