Testing and Learning Structured Quantum Hamiltonians

We consider the problems of testing and learning an n-qubit Hamiltonian $$H=\sum _x \lambda _x \sigma _x$$ expressed in its Pauli basis, from queries to its evolution operator $$U=e^{-iHt}$$ . To this end, we prove the following results. In order to prove these results, we prove new structural theorems for local Hamiltonians, sparse Pauli channels and sparse Hamiltonians. We complement our learning algorithms with lower bounds that are polynomially weaker. Furthermore, our algorithms use short time evolutions and do not assume prior knowledge of the terms on which the Pauli spectrum is supported on, i.e., we do not require prior knowledge of the support of the Hamiltonian.