Learning quantum states prepared by shallow circuits in polynomial time

We give a polynomial time algorithm that, given copies of an unknown quantum state $\mathrm{\mid }\psi ⟩=U\mathrm{\mid }{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 $\mathrm{\mid }\psi ⟩$. The algorithm extends to the case when the depth of $U$ is $\mathrm{p}\mathrm{o}\mathrm{l}\mathrm{y}\mathrm{l}\mathrm{o}\mathrm{g}(n)$, with a quasi-polynomial run-time. The key new idea is a simple and general procedure that efficiently reconstructs the global state $\mathrm{\mid }\psi ⟩$ 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.