  We show that a trapped ion chain interacting with an optical spin-dependent
force shows strong frustration effects due to the interplay between long-range
interactions and the dressing by optical phases. We consider a strong
spin-phonon coupling regime and predict a quantum phase diagram with different
competing magnetic and structural orders. In a highly frustrated region, the
system shows enhanced quantum fluctuations and entanglement characteristic of
spin-liquid phases. We propose and describe within a mean-field approach a
quantum annealing process to induce a quasi-adiabatic evolution towards the
ground state.
