Lower Bounds for Learning Hamiltonians from Time Evolution

2025/09/25 by Ziyun Chen, Chen, Ziyun, Jerry Li +2
Computer Science · #Computability, Logic, AI Algorithms #FOS: Physical sciences #Neural Networks and Applications #Quantum Physics (quant-ph) #Reinforcement Learning in Robotics

paper · pdf · doi:10.48550/arxiv.2509.20665

openalex publication_date 2025/09/25 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

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.

Citations

• Learning and certification of local time-dependent quantum dynamics and noise
• Improved Hamiltonian learning and sparsity testing through Bell sampling
• Ansatz-free Hamiltonian learning with Heisenberg-limited scaling
• Testing and learning structured quantum Hamiltonians
• Learning k-body Hamiltonians via compressed sensing
• Learning the structure of any Hamiltonian from minimal assumptions
• Improved algorithms for learning quantum Hamiltonians, via flat polynomials
• Hamiltonian Property Testing
• Quantum Hamiltonian Learning for the Fermi-Hubbard Model
• Certified algorithms for equilibrium states of local quantum Hamiltonians
• Learning quantum Hamiltonians at any temperature in polynomial time
• Efficient Pauli channel estimation with logarithmic quantum memory
• Heisenberg-limited Hamiltonian learning for interacting bosons
• Efficient and robust estimation of many-qubit Hamiltonians
• Optimal short-time measurements for Hamiltonian learning
• Optimal learning of quantum Hamiltonians from high-temperature Gibbs states
• Entanglement is Necessary for Optimal Quantum Property Testing
• Quantum Hamiltonian-Based Models and the Variational Quantum Thermalizer Algorithm
• The Theory of Quantum Information
• Analysis of Boolean Functions
• Quantum-Enhanced Measurements: Beating the Standard Quantum Limit

Related

• Nearly optimal algorithms to learn sparse quantum Hamiltonians in physically motivated distances
• Learning the structure of any Hamiltonian from minimal assumptions
• Optimal learning of quantum Hamiltonians from high-temperature Gibbs states
• Learning quantum Hamiltonians at any temperature in polynomial time with Chebyshev and bit complexity
• Quantum Hamiltonian Certification