A large ongoing research effort focuses on variational quantum algorithms (VQAs), representing leading candidates to achieve computational speed-ups on current quantum devices. The scalability of VQAs to a large number of qubits, beyond the simulation capabilities of classical computers, is still debated. Two major hurdles are the proliferation of low-quality variational local minima, and the exponential vanishing of gradients in the cost-function landscape, a phenomenon referred to as barren plateaus. In this work, we show that by employing iterative search schemes, one can effectively prepare the ground state of paradigmatic quantum many-body models, also circumventing the barren plateau phenomenon. This is accomplished by leveraging the transferability to larger system sizes of a class of iterative solutions, displaying an intrinsic smoothness of the variational parameters, a result that does not extend to other solutions found via random-start local optimization. Our scheme could be directly tested on near-term quantum devices, running a refinement optimization in a favorable local landscape with nonvanishing gradients.
