  We present a classical Monte Carlo (MC) scheme which efficiently estimates an
imaginary-time, decaying signal for stoquastic (i.e. sign-problem-free) local
Hamiltonians. The decay rates in this signal correspond to Hamiltonian
eigenvalues (with associated eigenstates present in an input state) and can be
classically extracted using a classical signal processing method like ESPRIT.
We compare the efficiency of this MC scheme to its quantum counterpart in which
one extracts eigenvalues of a general local Hamiltonian from a real-time,
oscillatory signal obtained through quantum phase estimation circuits, again
using the ESPRIT method. We prove that the ESPRIT method can resolve S =
poly(n) eigenvalues, assuming a 1/poly(n) gap between them, with poly(n)
quantum and classical effort through the quantum phase estimation circuits,
assuming efficient preparation of the input state. We prove that our Monte
Carlo scheme plus the ESPRIT method can resolve S = O(1) eigenvalues, assuming
a 1/poly(n) gap between them, with poly(n) purely classical effort for
stoquastic Hamiltonians, requiring some access structure to the input state.
However, we also show that under these assumptions, i.e. S = O(1) eigenvalues,
assuming a 1/poly(n) gap between them and some access structure to the input
state, one can achieve this with poly(n) purely classical effort for general
local Hamiltonians. These results thus quantify some opportunities and
limitations of classical Monte Carlo methods for spectral estimation of
Hamiltonians. We numerically compare the MC eigenvalue estimation scheme (for
stoquastic Hamiltonians) and the QPE eigenvalue estimation scheme by
implementing them for an archetypal stoquastic Hamiltonian system: the
transverse field Ising chain.
