Structure learning of Hamiltonians from real-time evolution

We study the problem of Hamiltonian structure learning from real-time evolution: given the ability to apply e-i Ht for an unknown local Hamiltonian H = suma = 1m λa Ea on n qubits, the goal is to recover H. This problem is already well-understood under the assumption that the interaction terms, Ea, are given, and only the interaction strengths, λa, are unknown. But how efficiently can we learn a local Hamiltonian without prior knowledge of its interaction structure? We present a new, general approach to Hamiltonian learning that not only solves the challenging structure learning variant, but also resolves other open questions in the area, all while achieving the gold standard of Heisenberg-limited scaling. In particular, our algorithm recovers the Hamiltonian to varepsilon error with total evolution time O(log (n)/varepsilon), and has the following appealing properties: (1) it does not need to know the Hamiltonian terms; (2) it works beyond the short-range setting, extending to any Hamiltonian H where the sum of terms interacting with a qubit has bounded norm; (3) it evolves according to H in constant time t increments, thus achieving constant time resolution. As an application, we can also learn Hamiltonians exhibiting power-law decay up to accuracy varepsilon with total evolution time beating the standard limit of 1/varepsilon2.