Noise-tolerant learnability of shallow quantum circuits from statistics and the cost of quantum pseudorandomness

This work studies the learnability of quantum circuits in the near term. We show the natural robustness of quantum statistical queries for learning quantum processes and provide an efficient way to benchmark global depolarizing noise from statistics, which gives us a powerful framework for developing noise-tolerant algorithms. We adapt a learning algorithm for constant-depth quantum circuits to the quantum statistical query setting with a small overhead in the query complexity. We prove average-case lower bounds for learning random quantum circuits of logarithmic and higher depths within diamond distance with statistical queries. Finally, we prove that pseudorandom unitaries (PRUs) cannot be constructed using circuits of constant depth by constructing an efficient distinguisher and proving a new variation of the quantum no-free lunch theorem.