Learning $k$-body Hamiltonians via compressed sensing

We study the problem of learning a k-body Hamiltonian with M unknown Pauli terms that are not necessarily geometrically local. We propose a protocol that learns the Hamiltonian to precision ε with total evolution time {O}(M^{1/2+1/p}/ε) up to logarithmic factors, where the error is quantified by the \ell^p-distance between Pauli coefficients. Our learning protocol uses only single-qubit control operations and a GHZ state initial state, is non-adaptive, is robust against SPAM errors, and performs well even if M and k are not precisely known in advance or if the Hamiltonian is not exactly M-sparse. Methods from the classical theory of compressed sensing are used for efficiently identifying the M terms in the Hamiltonian from among all possible k-body Pauli operators. We also provide a lower bound on the total evolution time needed in this learning task, and we discuss the operational interpretations of the \ell^1 and \ell^2 error metrics. In contrast to most previous works, our learning protocol requires neither geometric locality nor any other relaxed locality conditions.