Learning quantum states prepared by shallow circuits in polynomial time

We give a polynomial time algorithm that, given copies of an unknown quantum state vertpsirangle=Uvert 0nrangle that is prepared by an unknown constant depth circuit U on a finite-dimensional lattice, learns a constant depth quantum circuit that prepares vertpsirangle. The algorithm extends to the case when the depth of U is polylog(n), with a quasi-polynomial run-time. The key new idea is a simple and general procedure that efficiently reconstructs the global state vertpsirangle from its local reduced density matrices. As an application, we give an efficient algorithm to test whether an unknown quantum state on a lattice has low or high quantum circuit complexity.