Learning Quantum States Prepared by Shallow Circuits in Polynomial Time

We give a polynomial time algorithm that, given copies of an unknown quantum state |ψ = U |0 n that is prepared by an unknown constant depth circuit U on a finite-dimensional lattice, learns a constant depth quantum circuit that prepares |ψ . 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 |ψ 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.