This paper addresses the challenge of efficiently learning shallow quantum circuits, which are classically hard to simulate due to their ability to generate distributions with nontrivial correlations. The authors present polynomial-time classical algorithms for two main tasks: (1) learning the description of an unknown n-qubit shallow quantum circuit \( U \) within a small diamond distance, given access to \( U \); and (2) learning the description of an unknown n-qubit state \( |\psi\rangle = U|0\rangle^n \) prepared by a shallow quantum circuit \( U \) on a 2D lattice within a small trace distance, given copies of \( |\psi\rangle \). The key approach involves a quantum circuit representation based on local inversions, which allows for an efficient optimization landscape. Local inversions disentangle qubits in each local region without perturbing the remaining system. The authors combine these local inversions to build up the entire circuit, overcoming the challenge of exponentially many suboptimal local minima in the optimization landscape. The main results include: 1. **Learning General Shallow Quantum Circuits**: An algorithm that learns a constant-depth circuit approximating \( U \) to a diamond distance \( \epsilon \) with high probability from \( N = O(n^2 \log(n)/\epsilon^2) \) samples about \( U \) and in polynomial time. 2. **Learning Geometrically-Local Shallow Quantum Circuits**: An algorithm that learns a geometrically-local shallow circuit that approximates \( U \) to a diamond distance \( \epsilon \) with high probability from \( N = O(n^2 \log(n)/\epsilon^2) \) classical data samples, with either: - \( O(n^3 \log(n)/\epsilon^2) \) classical running time and a learned circuit depth of \( (k + 1) 4^{(8kd)^k} + 1 \). - \( (n/\epsilon) O((8kd)^{k+1}) \) classical running time with a learned circuit depth of \( (k + 1)(2d + 1) + 1 \). The paper also discusses the application of quantum queries to further improve the query complexity and the verification of the learned shallow quantum circuit. The authors provide a detailed technical overview of the key ideas and techniques used in the algorithms, including the use of local inversions and Heisenberg-evolved Pauli operators.This paper addresses the challenge of efficiently learning shallow quantum circuits, which are classically hard to simulate due to their ability to generate distributions with nontrivial correlations. The authors present polynomial-time classical algorithms for two main tasks: (1) learning the description of an unknown n-qubit shallow quantum circuit \( U \) within a small diamond distance, given access to \( U \); and (2) learning the description of an unknown n-qubit state \( |\psi\rangle = U|0\rangle^n \) prepared by a shallow quantum circuit \( U \) on a 2D lattice within a small trace distance, given copies of \( |\psi\rangle \). The key approach involves a quantum circuit representation based on local inversions, which allows for an efficient optimization landscape. Local inversions disentangle qubits in each local region without perturbing the remaining system. The authors combine these local inversions to build up the entire circuit, overcoming the challenge of exponentially many suboptimal local minima in the optimization landscape. The main results include: 1. **Learning General Shallow Quantum Circuits**: An algorithm that learns a constant-depth circuit approximating \( U \) to a diamond distance \( \epsilon \) with high probability from \( N = O(n^2 \log(n)/\epsilon^2) \) samples about \( U \) and in polynomial time. 2. **Learning Geometrically-Local Shallow Quantum Circuits**: An algorithm that learns a geometrically-local shallow circuit that approximates \( U \) to a diamond distance \( \epsilon \) with high probability from \( N = O(n^2 \log(n)/\epsilon^2) \) classical data samples, with either: - \( O(n^3 \log(n)/\epsilon^2) \) classical running time and a learned circuit depth of \( (k + 1) 4^{(8kd)^k} + 1 \). - \( (n/\epsilon) O((8kd)^{k+1}) \) classical running time with a learned circuit depth of \( (k + 1)(2d + 1) + 1 \). The paper also discusses the application of quantum queries to further improve the query complexity and the verification of the learned shallow quantum circuit. The authors provide a detailed technical overview of the key ideas and techniques used in the algorithms, including the use of local inversions and Heisenberg-evolved Pauli operators.