  Several quantum many-body models in one dimension possess exact solutions via
the Bethe ansatz method, which has been highly successful for understanding
their behavior. Nevertheless, there remain physical properties of such models
for which analytic results are unavailable, and which are also not
well-described by approximate numerical methods. Preparing Bethe ansatz
eigenstates directly on a quantum computer would allow straightforward
extraction of these quantities via measurement. We present a quantum algorithm
for preparing Bethe ansatz eigenstates of the XXZ spin chain that correspond to
real-valued solutions of the Bethe equations. The algorithm is polynomial in
the number of T gates and circuit depth, with modest constant prefactors.
Although the algorithm is probabilistic, with a success rate that decreases
with increasing eigenstate energy, we employ amplitude amplification to boost
the success probability. The resource requirements for our approach are lower
than other state-of-the-art quantum simulation algorithms for small
error-corrected devices, and thus may offer an alternative and computationally
less-demanding demonstration of quantum advantage for physically relevant
problems.
