Simple algorithms to test and learn local Hamiltonians

We consider the problems of testing and learning an $n$-qubit $k$-local Hamiltonian from queries to its evolution operator with respect the 2-norm of the Pauli spectrum, or equivalently, the normalized Frobenius norm. For testing whether a Hamiltonian is ${\epsilon }_1$-close to $k$-local or ${\epsilon }_2$-far from $k$-local, we show that $O(1\mathrm{/}({\epsilon }_2-{\epsilon }_1{)}^8)$ queries suffice. This solves two questions posed in a recent work by Bluhm, Caro and Oufkir. For learning up to error $\epsilon$, we show that $\exp (O(k^2+k\log (1\mathrm{/}\epsilon )))$ queries suffice. Our proofs are simple, concise and based on Pauli-analytic techniques.