  Quantum state preparation is a key step in all digital quantum simulation
algorithms. Here we propose methods to initialize on a gate-based quantum
computer a general class of quantum spin wave functions, the so-called
Valence-Bond-Solid (VBS) states, that are important for two reasons. First, VBS
states are the exact ground states of a class of interacting quantum spin
models introduced by Affleck, Kennedy, Lieb and Tasaki (AKLT). Second, the
two-dimensional VBS states are universal resource states for measurement-based
quantum computing. We find that schemes to prepare VBS states based on their
tensor-network representations yield quantum circuits that are too deep to be
within reach of noisy intermediate-scale quantum (NISQ) computers. We then
apply the general non-deterministic method herein proposed to the preparation
of the spin-1 and spin-3/2 VBS states, the ground states of the AKLT models
defined in one dimension and in the honeycomb lattice, respectively. Shallow
quantum circuits of depth independent of the lattice size are explicitly
derived for both cases, making use of optimization schemes that outperform
standard basis gate decomposition methods. Given the probabilistic nature of
the proposed routine, two strategies that achieve a quadratic reduction of the
repetition overhead for any VBS state defined on a bipartite lattice are
devised. Our approach should permit to use NISQ processors to explore the AKLT
model and variants thereof, outperforming conventional numerical methods in the
near future.
