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.
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.
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 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 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.
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 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 study the problem of learning nearly (s,ε)-sparse unitaries, meaning that the Pauli spectrum is concentrated on at most s components with at most ε residual mass in Pauli ℓ1-norm. This class generalizes well-studied families, including sparse unitaries, quantum k-juntas, 2k-Pauli dimensional channels, and compositions of depth O(loglogn) circuits with near-Clifford circuits.
Given query access to an unknown nearly sparse unitary U, our goal is to efficiently (both in time and query complexity) construct a quantum channel that is close in diamond distance to U. We design a learning algorithm achieving this guarantee using O~(s6/ε4) forward queries to U, and running time polynomial in relevant parameters.
A key contribution is an efficient quantum algorithm that, given query access to an arbitrary unknown unitary U, estimates all Pauli coefficients (up to a shared global phase) whose magnitude exceeds a given threshold θ, extending existing sparse recovery techniques to general unitaries.
We also study the broader class of unitaries with bounded Pauli ℓ1-norm. For that class, we prove an exponential query lower bound Ω(2n/2). We introduce a more relaxed accuracy metric which is the diamond distance restricted to a set of input states. Then, we show that, under this metric, unitaries with Pauli ℓ1-norm uniformly bounded by L1 are learnable with O~(L18/ε16).