  This work studies the learnability of unknown quantum circuits in the near
term. We prove the natural robustness of quantum statistical queries for
learning quantum processes and provide an efficient way to benchmark various
classes of 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. Additionally, we show the hardness
of the quantum threshold search problem from quantum statistical queries and
discuss its implications for the learnability of shallow quantum circuits.
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.
