We provide an efficient and general route for preparing non-trivial quantum states that are not adiabatically connected to unentangled product states. Our approach is a hybrid quantum-classical variational protocol that incorporates a feedback loop between a quantum simulator and a classical computer, and is experimentally realizable on near-term quantum devices of synthetic quantum systems. We find explicit protocols which prepare with perfect fidelities (i) the Greenberger-Horne-Zeilinger (GHZ) state, (ii) a quantum critical state, and (iii) a topologically ordered state, with $L$ variational parameters and physical runtimes $T$ that scale linearly with the system size $L$. We furthermore conjecture and support numerically that our protocol can prepare, with perfect fidelity and similar operational costs, the ground state of every point in the one dimensional transverse field Ising model phase diagram. Besides being practically useful, our results also illustrate the utility of such variational ansatze as good descriptions of non-trivial states of matter.