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. 1. Testing: We give a tolerant testing protocol to decide if a Hamiltonian is \(\varepsilon _1\) -close to k-local or \(\varepsilon _2\) -far from k-local in the \(\ell _2\) norm of the coefficients, with \(O(1/(\varepsilon _2-\varepsilon _1)^{4})\) queries, thereby solving two open questions posed in a recent work by Bluhm, Caro and Oufkir (Bluhm, A., Caro, M.C., Oufkir, A.). We give a protocol for testing whether a Hamiltonian is \(\varepsilon _1\) -close to being s-sparse or \(\varepsilon _2\) -far from being s-sparse in the \(\ell _2\) norm of the coefficients, with \(O(s^{6}/(\varepsilon _2^2-\varepsilon _1^2)^{6})\) queries.
2. Learning: We give a protocol to \(\varepsilon \) -learn unstructured Hamiltonian in the \(\ell _\infty \) norm of the coefficients with \(O(1/\varepsilon ^4)\) queries. Combining this with the non-commutative Bohnenblust-Hille inequality, we obtain an algorithm for learning k-local Hamiltonians in \(\ell _2\) norm of the coefficients that only uses \(O(\exp (k^2+k\log (1/\varepsilon )))\) queries. For Hamiltonians that are s-sparse in the Pauli basis, we can learn them in the \(\ell _2\) norm with \(O(s^2/\varepsilon ^4)\) queries.
3. Learning without quantum memory: The learning results stated above have no dependence on the system size n, but require n-qubit quantum memory. We give subroutines that allow us to reproduce all the above learning results without quantum memory; squaring the query complexity and paying a \((\log n)\) -factor in the local case and an n-factor in the sparse case.
4. Testing without quantum memory: We give a new subroutine called Pauli hashing, which allows one to tolerantly test s-sparse Hamiltonians in the \(\ell _2\) norm using \(\tilde{O}(s^{14}/(\varepsilon _2^2-\varepsilon _1^2)^{18})\) query complexity. A key ingredient is showing that s-sparse Pauli channels can be tested in a tolerant fashion as being \(\varepsilon _1\) -close to being s-sparse or \(\varepsilon _2\) -far under the diamond norm, using \(\tilde{O}(s^2/(\varepsilon _2-\varepsilon _1)^6)\) queries via Pauli hashing.
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.
