Simple algorithms to test and learn local Hamiltonians
Francisco Escudero Gutiérrez
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/(\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/\epsilon)))$ queries suffice. Our proofs are simple,
concise and based on Pauli-analytic techniques.