  A common requirement of quantum simulations and algorithms is the preparation
of complex states through sequences of 2-qubit gates. For a generic quantum
state, the number of gates grows exponentially with the number of qubits,
becoming unfeasible on near-term quantum devices. Here, we aim at creating an
approximate encoding of the target state using a limited number of gates. As a
first step, we consider a quantum state that is efficiently represented
classically, such as a one-dimensional matrix product state. Using tensor
network techniques, we develop an optimization algorithm that approaches the
optimal implementation for a fixed number of gates. Our algorithm runs
efficiently on classical computers and requires a polynomial number of
iterations only. We demonstrate the feasibility of our approach by comparing
optimal and suboptimal circuits on real devices. We, next, consider the
implementation of the proposed optimization algorithm directly on a quantum
computer and overcome inherent barren plateaus by employing a local cost
function rather than a global one. By simulating realistic shot noise, we
verify that the number of required measurements scales polynomially with the
number of qubits. Our work offers a universal method to prepare target states
using local gates and represents a significant improvement over known
strategies.
