  Highly excited states of quantum many-body systems are central objects in the
study of quantum dynamics and thermalization that challenge classical
computational methods due to their volume-law entanglement content. In this
work, we explore the potential of variational quantum algorithms to approximate
such states. We propose an adaptive variational algorithm, adaptive VQE-X, that
self-generates a variational ansatz for arbitrary eigenstates of a many-body
Hamiltonian $H$ by attempting to minimize the energy variance with respect to
$H$. We benchmark the method by applying it to an Ising spin chain with
integrable and nonintegrable regimes, where we calculate various quantities of
interest, including the total energy, magnetization density, and entanglement
entropy. We also compare the performance of adaptive VQE-X to an adaptive
variant of the folded-spectrum method. For both methods, we find a strong
dependence of the algorithm's performance on the choice of operator pool used
for the adaptive construction of the ansatz. In particular, an operator pool
including long-range two-body gates accelerates the convergence of both
algorithms in the nonintegrable regime. We also study the scaling of the number
of variational parameters with system size, finding that an exponentially large
number of parameters may be necessary to approximate individual highly excited
states. Nevertheless, we argue that these methods lay a foundation for the use
of quantum algorithms to study finite-energy-density properties of many-body
systems.
