  Recently, there has been much interest in the efficient preparation of
complex quantum states using low-depth quantum circuits, such as Quantum
Approximate Optimization Algorithm (QAOA). While it has been numerically shown
that such algorithms prepare certain correlated states of quantum spins with
surprising accuracy, a systematic way of quantifying the efficiency of QAOA in
general classes of models has been lacking. Here, we propose that the success
of QAOA in preparing ordered states is related to the interaction distance of
the target state, which measures how close that state is to the manifold of all
Gaussian states in an arbitrary basis of single-particle modes. We numerically
verify this for several examples of non-integrable quantum models, including
Ising models with two- and three-spin interactions and the cluster model in an
external field. Our results suggest that the structure of the entanglement
spectrum, as witnessed by the interaction distance, correlates with the success
of QAOA state preparation, and that this correlation also contains information
about different phases present in the model. We conclude that QAOA typically
finds a solution that perturbs around the closest free-fermion state.
