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(M1/2+1/p/ε) up to logarithmic factors, where the error is quantified by the ℓ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 ℓ1 and ℓ2 error metrics. In contrast to most previous works, our learning protocol requires neither geometric locality nor any other relaxed locality conditions.