We introduce protocols to prepare many-body quantum states with quantum circuits assisted by local operations and classical communication. We show that by lifting the requirement of exact preparation, one can substantially save resources. In particular, the so-called W and, more generally, Dicke states require a circuit depth and number of ancillas per site that are independent of the system size. As a by-product of our work, we introduce an efficient scheme to implement certain nonlocal, non-Clifford unitary operators. We also discuss how similar ideas may be applied in the preparation of eigenstates of well-known spin models, both free and interacting.
