We consider the problems of testing and learning an n -qubit Hamiltonian
H=∑xλxσx expressed in its Pauli basis, from queries to its evolution operator
U=e−iHt . To this end, we prove the following results. Testing : We give a tolerant testing protocol to decide if a Hamiltonian is
ε1 -close to k -local or
ε2 -far from k -local in the
ℓ2 norm of the coefficients, with
O(1/(ε2−ε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
ε1 -close to being s -sparse or
ε2 -far from being s -sparse in the
ℓ2 norm of the coefficients, with
O(s6/(ε22−ε12)6) queries. Learning : We give a protocol to
ε -learn unstructured Hamiltonian in the
ℓ∞ norm of the coefficients with
O(1/ε4) queries. Combining this with the non-commutative Bohnenblust-Hille inequality, we obtain an algorithm for learning k -local Hamiltonians in
ℓ2 norm of the coefficients that only uses
O(exp(k2+klog(1/ε))) queries. For Hamiltonians that are s -sparse in the Pauli basis, we can learn them in the
ℓ2 norm with
O(s2/ε4) queries. 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
(logn) -factor in the local case and an n -factor in the sparse case. Testing without quantum memory : We give a new subroutine called Pauli hashing , which allows one to tolerantly test s -sparse Hamiltonians in the
ℓ2 norm using
O~(s14/(ε22−ε12)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
O~(s2/(ε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 of the support of the Hamiltonian.
We establish lower bounds for Hamiltonian property testing with access to the time-evolution operator but not its inverse. Each experiment may query the time-evolution operator multiple times, and distances between Hamiltonians are measured in the normalized Frobenius norm.
In this model, we show that testing whether a Hamiltonian is
k-local or
ε-far from every
k-local Hamiltonian requires
Ω(1/ε2) total evolution time, matching the upper bound of Kallaugher and Liang (TQC'25). We also prove that testing whether an unknown Hamiltonian equals a target Hamiltonian or is
ε-far from it requires
Ω(1/ε2) total evolution time, matching the upper bound of Sinha and Tong (2025). These are the first lower bounds for natural problems in Hamiltonian learning and testing that rule out Heisenberg-limited scaling of
1/ε.
As a third result, we show that amplitude estimation to precision
ε requires
Ω(1/ε2) total time evolution, recovering the result of Tang and Wright (QIP'26) in the continuous-time query model. All three results follow from the hardness of distinguishing the zero Hamiltonian from a suitably chosen ensemble of random Hamiltonians. We establish this hardness by adapting the continuous-time adversary method to forward Hamiltonian evolution.
We consider the problems of testing and learning an
n-qubit
k-local Hamiltonian from queries to its evolution operator with respect the 2-norm of the Pauli spectrum, or equivalently, the normalized Frobenius norm. For testing whether a Hamiltonian is
ε1-close to
k-local or
ε2-far from
k-local, we show that
O(1/(ε2−ε1)8) queries suffice. This solves two questions posed in a recent work by Bluhm, Caro and Oufkir. For learning up to error
ε, we show that
exp(O(k2+klog(1/ε))) queries suffice. Our proofs are simple, concise and based on Pauli-analytic techniques.
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 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.