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.
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(k2+klog(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(s6/(ε22−ε12)6) queries. For learning up to error ε, we show that O(s4/ε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 (logn)-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(s14/(ε22−ε12)18) queries. A key ingredient is showing that s-sparse Pauli channels can be tolerantly tested under the diamond norm with O(s2/(ε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.
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.
Learning algorithms for structured quantum unitaries and Hamiltonians have primarily considered classes of processes that are local or sparse in the Pauli basis. We turn our attention to learning n-qubit quantum unitaries U and Hamiltonians H, given query access to U or the unitary evolution of H, that may be dense in the Pauli basis but still admit concise Clifford decompositions. Specifically, we consider unitaries (or Hamiltonians) of the form U=∑iαiCi over Cliffords Ci with bounded Clifford extent ∑i∣αi∣. To extract this Clifford structure, we introduce an agnostic tomography protocol for Clifford unitaries that given query access to an unknown unitary U with optimal Clifford fidelity opt, outputs a Clifford unitary witnessing fidelity ≥opt−ε for some error ε>0, in time poly(n,(1/ε)log(1/ε)). We then apply this protocol to obtain tomography protocols for unitaries and Hamiltonians that have bounded Clifford extent. This extends learnability of Hamiltonians from those with sparse Pauli decompositions to those that are dense (i.e., has sparsity Ω(2n)) in the Pauli basis but are Clifford structured.
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.
In this work, we study the problems of certifying and learning quantum k-local Hamiltonians, for a constant k. Our main contributions are as follows:
- Certification of Hamiltonians. We show that certifying a local Hamiltonian in normalized Frobenius norm via access to its time-evolution operator can be achieved with only O(1/ε) evolution time. This is optimal, as it matches the Heisenberg-scaling lower bound of Ω(1/ε). To our knowledge, this is the first optimal algorithm for testing a Hamiltonian property. A key ingredient in our analysis is the Bonami Hypercontractivity Lemma from Fourier analysis.
- Learning Gibbs states. We design an algorithm for learning Gibbs states of local Hamiltonians in trace norm that is sample-efficient in all relevant parameters. In contrast, previous approaches learned the underlying Hamiltonian (which implies learning the Gibbs state), and thus inevitably suffered from exponential sample complexity scaling in the inverse temperature.
- Certification of Gibbs states. We give an algorithm for certifying Gibbs states of local Hamiltonians in trace norm that is both sample and time-efficient in all relevant parameters, thereby solving a question posed by Anshu (Harvard Data Science Review, 2022).
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 present an efficient protocol for learning an unknown k-local Lindblad generator on n qubits using only product-state preparations, short-time evolution, and single-qubit Pauli measurements, without prior knowledge of the interaction structure. For fixed k and a supplied weighted interaction-strength bound αˉ, the protocol estimates all Hamiltonian and dissipative Pauli--GKSL coefficients with total coefficient error at each site at most ε with probability at least 1−δ using Ok(αˉ2n2k−2ε−2log(n/δ)) samples and polylogarithmically many distinct evolution times. This guarantee requires no degree, sparsity, or tail promise. A convex optimization converts these estimates into a valid k-local Lindblad generator with diamond-norm error at most ε using Ok(αˉ2n2kε−2log(n/δ)) samples and polynomial-time classical postprocessing. With a supplied local effective-sparsity bound r and a sufficiently small sitewise subthreshold tail Ok(ε), coefficient recovery requires only Ok(αˉ2r2ε−2log(n/δ)) samples, without a supplied threshold or coefficient locations and without a coefficient-gap assumption. In particular, exactly sparse bounded-degree models have logarithmic sample dependence on n. We also provide guard-band support recovery and complementary supplied-candidate guarantees, extend the guarantees to model misspecification, and prove complementary sample-complexity lower bounds.