  Despite fundamental interests in learning quantum circuits, the existence of
a computationally efficient algorithm for learning shallow quantum circuits
remains an open question. Because shallow quantum circuits can generate
distributions that are classically hard to sample from, existing learning
algorithms do not apply. In this work, we present a polynomial-time classical
algorithm for learning the description of any unknown $n$-qubit shallow quantum
circuit $U$ (with arbitrary unknown architecture) within a small diamond
distance using single-qubit measurement data on the output states of $U$. We
also provide a polynomial-time classical algorithm for learning the description
of any unknown $n$-qubit state $\lvert \psi \rangle = U \lvert 0^n \rangle$
prepared by a shallow quantum circuit $U$ (on a 2D lattice) within a small
trace distance using single-qubit measurements on copies of $\lvert \psi
\rangle$. Our approach uses a quantum circuit representation based on local
inversions and a technique to combine these inversions. This circuit
representation yields an optimization landscape that can be efficiently
navigated and enables efficient learning of quantum circuits that are
classically hard to simulate.
