  While classical spin systems in random networks have been intensively
studied, much less is known about quantum magnets in random graphs. Here, we
investigate interacting quantum spins on small-world networks, building on
mean-field theory and extensive quantum Monte Carlo simulations. Starting from
one-dimensional (1D) rings, we consider two situations: all-to-all interacting
and long-range interactions randomly added. The effective infinite dimension of
the lattice leads to a magnetic ordering at finite temperature $T_\mathrm{c}$
with mean-field criticality. Nevertheless, in contrast to the classical case,
we find two distinct power-law behaviors for $T_\mathrm{c}$ versus the average
strength of the extra couplings. This is controlled by a competition between a
characteristic length scale of the random graph and the thermal correlation
length of the underlying 1D system, thus challenging mean-field theories. We
also investigate the fate of a gapped 1D spin chain against the small-world
effect.
