  A candidate application for quantum computers is to simulate the
low-temperature properties of quantum systems. For this task, there is a
well-studied quantum algorithm that performs quantum phase estimation on an
initial trial state that has a nonnegligible overlap with a low-energy state.
However, it is notoriously hard to give theoretical guarantees that such a
trial state can be prepared efficiently. Moreover, the heuristic proposals that
are currently available, such as with adiabatic state preparation, appear
insufficient in practical cases. This paper shows that, for most random sparse
Hamiltonians, the maximally mixed state is a sufficiently good trial state, and
phase estimation efficiently prepares states with energy arbitrarily close to
the ground energy. Furthermore, any low-energy state must have nonnegligible
quantum circuit complexity, suggesting that low-energy states are classically
nontrivial and phase estimation is the optimal method for preparing such states
(up to polynomial factors). These statements hold for two models of random
Hamiltonians: (i) a sum of random signed Pauli strings and (ii) a random signed
$d$-sparse Hamiltonian. The main technical argument is based on some new
results in nonasymptotic random matrix theory. In particular, a refined
concentration bound for the spectral density is required to obtain complexity
guarantees for these random Hamiltonians.
