Abstract
Characterizing noisy quantum devices requires methods for learning the underlying quantum Hamiltonian which governs their dynamics. Often, such methods compare measurements to simulations of candidate Hamiltonians, a task which requires exponential computational complexity. Here, we propose efficient measurement schemes based on short-time dynamics which circumvent this exponential difficulty. We provide estimates for the optimal measurement schedule and reconstruction error, and verify these estimates numerically. We demonstrate that the reconstruction requires a system-size independent number of experimental shots, and identify a minimal set of state preparations and measurements which yields optimal accuracy for learning short-ranged Hamiltonians. Finally, we show how grouping of commuting observables and use of Hamiltonian symmetries improve the accuracy of the Hamiltonian reconstruction.