Nearly optimal algorithms to learn sparse quantum Hamiltonians in physically motivated distances

Abstract: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/\epsilon))$ experiments and $O(s^2/\epsilon)$ evolution time. For the time-constrained distance, we further establish lower bounds of $\Omega((s/n)\log(1/\epsilon) + s)$ experiments and $\Omega(\sqrt{s}/\epsilon)$ 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 $\epsilon$ in $O(s\log(1/\epsilon))$ experiments and $O(s/\epsilon)$ 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.

39 pages, 1 figure. In this new version, we adapted our algorithm to use no memory, and we updated the discussion of our lower bounds

Quantum Physics (quant-ph); Computational Complexity (cs.CC); Data Structures and Algorithms (cs.DS)

arXiv:2509.09813 [quant-ph]

(or arXiv:2509.09813v2 [quant-ph] for this version)

https://doi.org/10.48550/arXiv.2509.09813 Focus to learn more arXiv-issued DOI via DataCite

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.