  Simulating time evolution is one of the most natural applications of quantum
computers and is thus one of the most promising prospects for achieving
practical quantum advantage. Here we develop quantum algorithms to extract
thermodynamic properties by estimating the density of states (DOS), a central
object in quantum statistical mechanics. We introduce key innovations that
significantly improve the practicality and extend the generality of previous
techniques. First, our approach allows one to estimate the DOS for a specific
subspace of the full Hilbert space. This is crucial for fermionic systems,
since fermion-to-qubit mappings partition the full Hilbert space into subspaces
of fixed number, on which both canonical and grand canonical ensemble
properties depend. Second, in our approach, by time evolving very simple,
random initial states (e.g. random computational basis states), we can exactly
recover the DOS on average. Third, due to circuit-depth limitations, we only
reconstruct the DOS up to a convolution with a Gaussian window - thus all
imperfections that shift the energy levels by less than the width of the
convolution window will not significantly affect the estimated DOS. For these
reasons we find the approach is a promising candidate for early quantum
advantage as even short-time, noisy dynamics yield a semi-quantitative
reconstruction of the DOS (convolution with a broad Gaussian window), while
early fault tolerant devices will likely enable higher resolution DOS
reconstruction through longer time evolution. We demonstrate the practicality
of our approach in representative Fermi-Hubbard and spin models and find that
our approach is highly robust to algorithmic errors in the time evolution and
to gate noise. We show that our approach is compatible with NISQ-friendly
variational methods, introducing a new technique for variational time evolution
in noisy DOS computations.
