Testing and Learning Structured Quantum Hamiltonian

We consider the problems of testing and learning an unknown n-qubit quantum Hamiltonian H=λ' λ σ expressed in its Pauli basis, from queries to its evolution operator e^-iHt under the normalized Frobenius norm. To this end, we prove the following results (with and without quantum memory) for Hamiltonians whose Pauli spectrum involves only k-local terms or has sparsity at most s: (1) Local Hamiltonians: We give a tolerant testing protocol to decide if a Hamiltonian is ϵ-close to k-local or ϵ-far from k-local, with O(1/(ϵ-ϵ)⁴) queries, thereby solving two open questions posed in a recent work by Bluhm, Caro and Oufkir [BCO'24]. For learning a k-local Hamiltonian up to error ϵ, we give a protocol with query complexity and total time evolution exp(O(k²+klog(1/ϵ))). Our algorithm leverages the non-commutative Bohnenblust-Hille inequality in order to get a complexity independent of n. (2) Sparse Hamiltonians: We give a protocol for testing whether a Hamiltonian is ϵ-close to being s-sparse or ϵ-far from being s-sparse, with O(s⁶/(ϵ²-ϵ²)⁶) queries. For learning up to error ϵ, we show that O(s⁴/ϵ⁸) queries suffices. (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; increasing the query complexity by a (logn)-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 using Õ(s¹⁴/(ϵ²-ϵ²)¹⁸) query complexity. A key ingredient is showing that s-sparse Pauli channels can be tested in a tolerant fashion as being ϵ-close to being s-sparse or ϵ-far under the diamond norm, using Õ(s²/(ϵ-ϵ)⁶) 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 about the support of the Hamiltonian terms.