Spectral estimation for stoquastic Hamiltonians: a comparison between classical imaginary-time evolution and quantum real-time evolution

Authors:
  • MSMaarten Stroeks
    Maarten Stroeks
  • JHJonas Helsen
    Jonas Helsen
  • BTBarbara Terhal
    Barbara Terhal

Abstract
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 initial 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. 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. These results thus quantify some opportunities and limitations of classical Monte Carlo methods for spectral estimation of stoquastic Hamiltonians. We numerically compare these MC and QPE eigenvalue estimation schemes by implementing them for an archetypal stoquastic Hamiltonian system: the transverse field Ising chain.