Learning the structure of any Hamiltonian from minimal assumptions

We study the problem of learning an unknown quantum many-body Hamiltonian H from black-box queries to its time evolution e^-iHt. Prior proposals for solving this task either impose some assumptions on H, such as its interaction structure or locality, or otherwise use an exponential amount of computational postprocessing. In this paper, we present efficient algorithms to learn any n-qubit Hamiltonian, assuming only a bound on the number of Hamiltonian terms, m ≤ poly(n). Our algorithms do not need to know the terms in advance, nor are they restricted to local interactions. We consider two models of control over the time evolution: the first has access to time reversal (t < 0), enabling an algorithm that outputs an ε-accurate classical description of H after querying its dynamics for a total of Õ(m/ε) evolution time. The second access model is more conventional, allowing only forward-time evolutions; our algorithm requires Õ(‖H‖³/ε⁴) evolution time in this setting. Central to our results is the recently introduced concept of a pseudo-Choi state of H. We extend the utility of this learning resource by showing how to use it to learn the Fourier spectrum of H, how to achieve nearly Heisenberg-limited scaling with it, and how to prepare it even under our more restricted access models.