Spectral estimation for Hamiltonians: a comparison between classical imaginary-time evolution and quantum real-time evolution
Preprint
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 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.Keywords
All Related Versions
This publication has 29 references indexed in Scilit:
- Determining eigenstates and thermal states on a quantum computer using quantum imaginary time evolutionNature Physics, 2019
- Spectral quantum tomographynpj Quantum Information, 2019
- Mean Estimation and Regression Under Heavy-Tailed Distributions: A SurveyFoundations of Computational Mathematics, 2019
- Quantum Monte Carlo Methods2016
- Parameter estimation for nonincreasing exponential sums by Prony-like methodsLinear Algebra and its Applications, 2013
- Quantum Computation and Quantum Information2012
- Quantum Phase Transitions2011
- Matrix Analysis1997
- General theory of fractal path integrals with applications to many-body theories and statistical physicsJournal of Mathematical Physics, 1991
- Perturbation theory for pseudo-inversesBIT Numerical Mathematics, 1973