Learning about a Hamiltonian $H$ from its time evolution $e^{-iHt}$ is a fundamental task in quantum science. A flurry of recent work has developed powerful new algorithms with provable guarantees for this task, for a variety of natural settings. Despite this, relatively little is known about lower bounds for learning Hamiltonians. In particular, in the natural setting where we assume $H$ is a $k$-local Hamiltonian on $n$ qubits, all existing algorithms require total evolution time at least $n^{Ω(k)}$ to learn the parameters of $H$, and it remained open whether one could obtain even faster algorithms -- or at the very least, if one could obtain better runtimes for simpler tasks, such as estimating a single designated coefficient of the Hamiltonian. In this work we show the answer is essentially no, by obtaining strong lower bounds for these problems. We find that not only do $k$-local Hamiltonians require $n^{Ω(k)}$ time evolution or interactions to learn, but also that in several senses, learning anything about a Hamiltonian is just as hard as learning everything. In particular, we find the same $n^{Ω(k)}$ lower bound holds for learning a single coefficient of a $k$-local Hamiltonian $H$, even if the rest of $H$ is already known. We also show an $n^{Ω(k)}$ lower bound for the task of effective Hamiltonian learning, where one seeks only to learn a unitary that approximately implements time evolution of $H$. Several related lower bounds, such as for general sparse (but not necessarily local) $H$ are also given. On the technical side, we make a new connection between Hamiltonian learning lower bounds and the analysis of Boolean functions, where we introduce a novel extremal property that may be of independent interest.
Learning about a Hamiltonian H from its time evolution e−iHt is a fundamental task in quantum science. A flurry of recent work has developed powerful new algorithms with provable guarantees for this task, for a variety of natural settings. Despite this, relatively little is known about lower bounds for learning Hamiltonians. In particular, in the natural setting where we assume H is a k-local Hamiltonian on n qubits, all existing algorithms require total evolution time at least nΩ(k) to learn the parameters of H, and it remained open whether one could obtain even faster algorithms -- or at the very least, if one could obtain better runtimes for simpler tasks, such as estimating a single designated coefficient of the Hamiltonian. In this work we show the answer is essentially no, by obtaining strong lower bounds for these problems. We find that not only do k-local Hamiltonians require nΩ(k) time evolution or interactions to learn, but also that in several senses, learning anything about a Hamiltonian is just as hard as learning everything. In particular, we find the same nΩ(k) lower bound holds for learning a single coefficient of a k-local Hamiltonian H, even if the rest of H is already known. We also show an nΩ(k) lower bound for the task of effective Hamiltonian learning, where one seeks only to learn a unitary that approximately implements time evolution of H. Several related lower bounds, such as for general sparse (but not necessarily local) H are also given. On the technical side, we make a new connection between Hamiltonian learning lower bounds and the analysis of Boolean functions, where we introduce a novel extremal property that may be of independent interest.
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 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.
Characterizing quantum systems by learning their underlying Hamiltonians is a central task in quantum information science. While recent algorithmic advances have achieved near-optimal efficiency in this task, they critically rely on accessing arbitrarily short-time dynamics. This reliance poses severe experimental challenges due to finite control bandwidth and transient pulse errors. In this work, we demonstrate that Heisenberg-limited Hamiltonian learning can be achieved without short-time control. We introduce a framework in which every query to the unknown dynamics has duration at least a prescribed minimum time T, and show that this restriction does not preclude Heisenberg-limited scaling. The key ingredient is a method for emulating the continuous quantum control required by iterative learning algorithms using only such lower-bounded evolution times. This reduces the learning task to sparse pure-state tomography. Notably, for logarithmically sparse Hamiltonians, our algorithm achieves the information-theoretically optimal 1/ε scaling in total evolution time for any arbitrary constant minimum evolution time T. For many-body (polynomially sparse) systems, we uncover a rigorous quantitative tradeoff, showing that the minimum required evolution time can be significantly relaxed from the standard limit at a polynomial cost in total evolution time. Our results affirmatively resolve a prominent open problem in the field and reveal that high-bandwidth, ultra-short pulses are not fundamentally necessary for optimal quantum learning.
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.
Near-Optimal Bounds on the Density of Low-Energy States of k-Local Hamiltonians and Faster Quantum Algorithms
Low-energy estimation and state preparation for general k-local Hamiltonians are fundamental challenges in quantum complexity theory. Buhrman et al.~ [BGLGST, PRL 2025] recently broke the natural Grover bound O∗(2n/2) for both problems, with the improvement depending on the relative accuracy ε and the locality k. In this work, we present faster exponential quantum algorithms for these problems, where the binary entropy function governs the runtime exponent. For sufficiently small ε/k, our algorithms improve the exponent by a factor of log(k/ε) over [BGLGST, PRL 2025]. Our main technical result is an entropy-governed lower bound on the dimension of the Hamiltonian's low-energy subspace, obtained by depolarizing its ground state. For fixed k, this bound is optimal up to constant factors in the exponent. The same framework yields tighter bounds for Heisenberg, XY, and Ising models on arbitrary interaction graphs.