We study the problem of learning Hamiltonians $H$ that are $s$-sparse in the Pauli basis, given access to their time evolution. Although Hamiltonian learning has been extensively investigated, two issues recur in much of the existing literature: the absence of matching lower bounds and the use of mathematically convenient but physically opaque error measures. We address both challenges by introducing two physically motivated distances between Hamiltonians and designing a nearly optimal algorithm with respect to one of these metrics. The first, time-constrained distance, quantifies distinguishability through dynamical evolution up to a bounded time. The second, temperature-constrained distance, captures distinguishability through thermal states at bounded inverse temperatures. We show that $s$-sparse Hamiltonians with bounded operator norm can be learned in both distances with $O(s \log(1/ε))$ experiments and $O(s^2/ε)$ evolution time. For the time-constrained distance, we further establish lower bounds of $Ω((s/n)\log(1/ε) + s)$ experiments and $Ω(\sqrt{s}/ε)$ evolution time, demonstrating near-optimality in the number of experiments. As an intermediate result, we obtain an algorithm that learns every Pauli coefficient of $s$-sparse Hamiltonians up to error $ε$ in $O(s\log(1/ε))$ experiments and $O(s/ε)$ evolution time, improving upon several recent results. The source of this improvement is a new isolation technique, inspired by the Valiant-Vazirani theorem (STOC'85), which shows that NP is as easy as detecting unique solutions. This isolation technique allows us to query the time evolution of a single Pauli coefficient of a sparse Hamiltonian--even when the Pauli support of the Hamiltonian is unknown--ultimately enabling us to recover the Pauli support itself.
We study the problem of learning Hamiltonians H that are s-sparse in the Pauli basis, given access to their time evolution. Although Hamiltonian learning has been extensively investigated, two issues recur in much of the existing literature: the absence of matching lower bounds and the use of mathematically convenient but physically opaque error measures. We address both challenges by introducing two physically motivated distances between Hamiltonians and designing a nearly optimal algorithm with respect to one of these metrics. The first, time-constrained distance, quantifies distinguishability through dynamical evolution up to a bounded time. The second, temperature-constrained distance, captures distinguishability through thermal states at bounded inverse temperatures. We show that s-sparse Hamiltonians with bounded operator norm can be learned in both distances with O(slog(1/ε)) experiments and O(s2/ε) evolution time. For the time-constrained distance, we further establish lower bounds of Ω((s/n)log(1/ε)+s) experiments and Ω(s/ε) evolution time, demonstrating near-optimality in the number of experiments. As an intermediate result, we obtain an algorithm that learns every Pauli coefficient of s-sparse Hamiltonians up to error ε in O(slog(1/ε)) experiments and O(s/ε) evolution time, improving upon several recent results. The source of this improvement is a new isolation technique, inspired by the Valiant-Vazirani theorem (STOC'85), which shows that NP is as easy as detecting unique solutions. This isolation technique allows us to query the time evolution of a single Pauli coefficient of a sparse Hamiltonian--even when the Pauli support of the Hamiltonian is unknown--ultimately enabling us to recover the Pauli support itself.
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 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).
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 study the problem of learning local Lindbladians from black-box access to the physical evolution, where the goal is to estimate all Hamiltonian and dissipative coefficients. For local Lindbladians with low-intersection dissipators and local dynamical strength at most Λ, we design an algorithm that learns the coefficients to target accuracy ε, whose number of channel uses and total evolution time scale as O(Λ2/ε2) and O(Λ/ε2), respectively, with only logarithmic dependence on the number of qubits. The algorithm is built directly from finite-time channel probes. It runs the unknown evolution for short times, estimates the corresponding Pauli transfer matrices from classical shadows, and converts these estimates into Lindbladian coefficients by stable local Fourier inversions.
The algorithm is non-adaptive, uses no ancillas, and requires only random product states as inputs followed by random Pauli measurements. The method does not require knowing the structure of the Lindbladian in advance. We prove matching lower bounds that establish the near-optimality of the algorithm in both resources. By constructing a family of single-qubit dephasing Lindbladians, we show that any algorithm, even an adaptive one with arbitrary ancillas and measurements, requires Ω(Λ2/ε2) channel uses and Ω(Λ/ε2) total evolution time. In particular, the lower bounds imply that the Heisenberg-limited scaling achievable for Hamiltonian learning is information-theoretically impossible once dissipative coefficients must be estimated.
We study Hamiltonian learning for k-local Hamiltonians at large step size, using only forward time evolution at integer multiples of a fixed time interval. For this task, our new technique, which we call eigenphase engineering, achieves Heisenberg-limited learning with a step size that is optimal up to logarithmic factors. For an unknown s-sparse Hamiltonian with fixed locality k and ∥H∥op≤Λ, our algorithm recovers its Pauli coefficients to ℓ2 error ε in total evolution time O(s/ε), matching the best known scaling while allowing a near-maximal step size Θ(1/Λ). As an independent contribution, we strengthen the evolution-time lower bound to Ωk(s1−1/(2k)/ε), placing our algorithm within a factor O(s1/(2k)) of being optimal. Eigenphase engineering departs from approaches based on dynamical approximation or iteratively canceling the unknown Hamiltonian. It encodes energy expectation differences in the perturbative response of eigenphases of the actual controlled evolution, then extracts them through phase estimation and high-order extrapolation. This avoids the need for polynomially shorter evolution steps as the target precision improves. A version using only single-qubit operations retains the same step size with a n overhead in ℓ2 learning time for n qubits. The method also enables tolerant Hamiltonian certification and estimation of a specified Pauli coefficient, the latter without locality or sparsity assumptions. These results establish eigenphase engineering as a versatile approach to extracting Hamiltonian information with infrequent control.
We study the problem of learning an unknown Markovian open-system generator from access to its physical time evolution. This generator, called a Lindbladian, contains Hamiltonian and dissipative coefficients indexed by an exponentially large family of possible Pauli terms. We propose an efficient algorithm that learns arbitrary Lindbladians from time evolution under minimal assumptions. For a Lindbladian of dynamical strength at most Λ, the algorithm estimates every coefficient to error ε using O(Λ2/ε2) experiments and O(Λ/ε2) total evolution time, together with polynomial classical running time. The algorithm consists of two nonadaptive, ancilla-free, and control-free stages: 1. The support-learning stage outputs a candidate support of size poly(Λ/η) that contains every Hamiltonian and dissipative coordinate of magnitude at least η, using O(Λ2/η2) experiments with preparations of product Pauli eigenstates and single-qubit Pauli measurements. 2.The coefficient-learning stage estimates all coefficients in any candidate support of size M to error ε, using O(Λ2logM/ε2) experiments with preparations of random stabilizer states and measurements in random Clifford bases. Composing the two stages identifies and estimates every coefficient of an arbitrary Lindbladian in polynomial time. The experiment-count and total-evolution-time scalings match the lower bounds up to logarithmic factors, so the algorithm is nearly optimal for learning arbitrary Lindbladians.