Preparation of MPS with log-depth quantum circuits

We consider the preparation of matrix-product states (MPS) via quantum circuits of local gates. We first prove that it is impossible to faithfully prepare translation-invariant normal MPS of length N with depth T = o(logN). We then introduce a circuit based on the renormalization-group transformation that can prepare this class with T = O(log N/ε) for error ε, and thus has optimal scaling. Our protocol naturally generalizes to inhomogeneous MPS. We also show that measurement and feedback lead to an exponential speed-up of the algorithm, to T = O(log log(N/ε)), and allows one to prepare all translationally-invariant MPS in the same depth.