Testing and learning structured quantum Hamiltonians

We consider the problems of testing and learning an unknown $n$-qubit Hamiltonian $H$ from queries to its evolution operator $e^{-iHt}$ under the normalized Frobenius norm. We prove: 1. Local Hamiltonians: We give a tolerant testing protocol to decide if $H$ is $ε_1$-close to $k$-local or $ε_2$-far from $k$-local, with $O(1/(ε_2-ε_1)^{4})$ queries, solving open questions posed in a recent work by Bluhm et al. For learning a $k$-local $H$ up to error $ε$, we give a protocol with query complexity $\exp(O(k^2+k\log(1/ε)))$ independent of $n$, by leveraging the non-commutative Bohnenblust-Hille inequality. 2. Sparse Hamiltonians: We give a protocol to test if $H$ is $ε_1$-close to being $s$-sparse (in the Pauli basis) or $ε_2$-far from being $s$-sparse, with $O(s^{6}/(ε_2^2-ε_1^2)^{6})$ queries. For learning up to error $ε$, we show that $O(s^{4}/ε^{8})$ queries suffice. 3. Learning without memory: The learning results stated above have no dependence on $n$, but require $n$-qubit quantum memory. We give subroutines that allow us to learn without memory; increasing the query complexity by a $(\log n)$-factor in the local case and an $n$-factor in the sparse case. 4. Testing without memory: We give a new subroutine called Pauli hashing, which allows one to tolerantly test $s$-sparse Hamiltonians with $O(s^{14}/(ε_2^2-ε_1^2)^{18})$ queries. A key ingredient is showing that $s$-sparse Pauli channels can be tolerantly tested under the diamond norm with $O(s^2/(ε_2-ε_1)^6)$ queries. Along the way, we prove new structural theorems for local and sparse Hamiltonians. We complement our learning results with polynomially weaker lower bounds. Furthermore, our algorithms use short time evolutions and do not assume prior knowledge of the terms in the support of the Pauli spectrum.