We investigate the problem of predicting the output behavior of unknown quantum channels. Given query access to an (n)-qubit channel (E) and an observable (O), we aim to learn the mapping \begin{equation} \rho \mapsto \mathrm{Tr}(O E[\rho]) \end{equation} to within a small error for most (\rho) sampled from a distribution (D). Previously, Huang, Chen, and Preskill proved a surprising result that even if (E) is arbitrary, this task can be solved in time roughly (n^{O(log(1/\epsilon))}), where (\epsilon) is the target prediction error. However, their guarantee applied only to input distributions (D) invariant under all single-qubit Clifford gates, and their algorithm fails for important cases such as general product distributions over product states (\rho). In this work, we propose a new approach that achieves accurate prediction over essentially any product distribution (D), provided it is not “classical” in which case there is a trivial exponential lower bound. Our method employs a “biased Pauli analysis,” analogous to classical biased Fourier analysis. Implementing this approach requires overcoming several challenges unique to the quantum setting, including the lack of a basis with appropriate orthogonality properties. The techniques we develop to address these issues may have broader applications in quantum information.