  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.
