This paper presents polynomial-time classical algorithms for learning shallow quantum circuits and their output states. The authors show that it is possible to learn the description of an unknown n-qubit shallow quantum circuit U within a small diamond distance using single-qubit measurement data on the output states of U. They also provide a polynomial-time algorithm for learning the description of an unknown n-qubit state $ |\psi\rangle = U|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 $ |\psi\rangle $. The main challenges in learning shallow quantum circuits are twofold: (1) the computational power of shallow quantum circuits makes them classically hard to simulate, and (2) the optimization landscape for learning shallow quantum circuits is swamped with exponentially many suboptimal local minima. To address these challenges, the authors introduce a quantum circuit representation based on local inversions, which yields an optimization landscape that can be efficiently navigated. This representation allows for efficient learning of quantum circuits that are classically hard to simulate. The authors also show that learning shallow quantum circuits can be done efficiently using quantum queries, which allows for an exponential improvement in query complexity. Furthermore, they demonstrate that learning the output states of shallow quantum circuits can be done efficiently using a combination of local inversions and constraint satisfaction techniques. The paper concludes with a discussion of the implications of these results for quantum computing and quantum learning theory. The authors highlight the importance of efficient learning algorithms for shallow quantum circuits in the context of quantum advantage and the development of quantum algorithms based on learning parameterized shallow quantum circuits.This paper presents polynomial-time classical algorithms for learning shallow quantum circuits and their output states. The authors show that it is possible to learn the description of an unknown n-qubit shallow quantum circuit U within a small diamond distance using single-qubit measurement data on the output states of U. They also provide a polynomial-time algorithm for learning the description of an unknown n-qubit state $ |\psi\rangle = U|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 $ |\psi\rangle $. The main challenges in learning shallow quantum circuits are twofold: (1) the computational power of shallow quantum circuits makes them classically hard to simulate, and (2) the optimization landscape for learning shallow quantum circuits is swamped with exponentially many suboptimal local minima. To address these challenges, the authors introduce a quantum circuit representation based on local inversions, which yields an optimization landscape that can be efficiently navigated. This representation allows for efficient learning of quantum circuits that are classically hard to simulate. The authors also show that learning shallow quantum circuits can be done efficiently using quantum queries, which allows for an exponential improvement in query complexity. Furthermore, they demonstrate that learning the output states of shallow quantum circuits can be done efficiently using a combination of local inversions and constraint satisfaction techniques. The paper concludes with a discussion of the implications of these results for quantum computing and quantum learning theory. The authors highlight the importance of efficient learning algorithms for shallow quantum circuits in the context of quantum advantage and the development of quantum algorithms based on learning parameterized shallow quantum circuits.