We consider the problems of testing and learning an unknown $n$-qubit quantum Hamiltonian $H=Σ_x λ_x σ_x$ 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 $ε_1$-close to $k$-local or $ε_2$-far from $k$-local, with $O(1/(ε_2-ε_1)^4)$ 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^2+k\mathrm{log} (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 $ε_1$-close to being $s$-sparse 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 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 (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 using $Õ(s^{14}/(ε{_2}^2-ε{_1}^2)^{18})$ query complexity. A key ingredient is showing that $s$-sparse Pauli channels can be tested in a tolerant fashion as being $ε_1$-close to being $s$-sparse or $ε_2$-far under the diamond norm, using $Õ(s^2/(ε_2-ε_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 about the support of the Hamiltonian terms.

We consider the problem of learning low-degree quantum objects up to $\varepsilon$-error in $\ell_2$-distance. We show the following results: $(i)$ unknown $n$-qubit degree-$d$ (in the Pauli basis) quantum channels and unitaries can be learned using $O(1/\varepsilon^d)$ queries (independent of $n$), $(ii)$ polynomials $p:\{-1,1\}^n\rightarrow [-1,1]$ arising from $d$-query quantum algorithms can be classically learned from $O((1/\varepsilon)^d\cdot \log n)$ many random examples $(x,p(x))$ (which implies learnability even for $d=O(\log n)$), and $(iii)$ degree-$d$ polynomials $p:\{-1,1\}^n\to [-1,1]$ can be learned through $O(1/\varepsilon^d)$ queries to a quantum unitary $U_p$ that block-encodes $p$. Our main technical contributions are new Bohnenblust-Hille inequalities for quantum channels and completely bounded~polynomials.