Learning Quantum States Prepared by Shallow Circuits in Polynomial Time

Abstract

We give a polynomial time algorithm that, given copies of an unknown quantum state ψ=U0n 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.