Learning Hamiltonians

Abstract: We study the problems of certifying and learning local quantum Hamiltonians and their associated Gibbs states. We first address Hamiltonian certification given real-time access to the dynamics of an unknown k-local Hamiltonian. Given oracle access to its time-evolution operator and a fully specified target Hamiltonian, the task is to decide whether the two Hamiltonians are identical or differ by at least a prescribed accuracy in normalized Frobenius norm, while minimizing the total evolution time. We introduce the first certification protocol that achieves optimal performance for all constant-locality Hamiltonians. For general n-qubit, k-local, traceless Hamiltonians, our algorithm succeeds with high probability using total evolution time that scales inversely with the target accuracy, and for constant locality this matches the fundamental lower bound, achieving Heisenberg-limit scaling. In contrast to prior approaches, our method requires neither inverse evolution nor controlled operations, and relies only on forward real-time dynamics. We then turn to thermal states generated by local Hamiltonians. We develop algorithms for both learning and certifying Gibbs states that are fully sample-efficient in all relevant parameters. For polynomially bounded temperature, our methods achieve exponential improvements over general quantum state tomography. While the learning algorithm is inherently time-inefficient due to covering arguments, the certification algorithm is both sample- and time-efficient, resolving a previously open question on efficient Gibbs state testing. Together, these results establish optimal or near-optimal complexity bounds for characterizing local quantum systems in both dynamical and thermal regimes.

Abstract: We study the problem of learning Hamiltonians H that are s-sparse in the Pauli basis, given access to their time-evolution operators. Although Hamiltonian learning has been extensively investigated, two issues recur in much of the existing literature: the absence of lower bounds establishing optimality and the use of mathematically convenient but physically opaque error measures. We address both challenges by introducing two physically motivated notions of distance between Hamiltonians and designing a nearly optimal algorithm with respect to one of these metrics. The first, the time-constrained distance, quantifies distinguishability through dynamical evolution up to a bounded time. The second, the 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 under both distances using only $O(s log(1/ε))$ experiments and $O(s^2/ε)$ total evolution time. For the time-constrained distance, we further establish lower bounds of $Ω((s/n) log(1/ε) + s)$ experiments and $Ω(√s/ε)$ total 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/ε)$ total 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.

Abstract: Hamiltonian learning protocols are quickly establishing themselves as valuable tools to benchmark and verify quantum computers and simulators. However, virtually no rigorous protocols exist to learn time-dependent Hamiltonians and Lindbladians, despite their widespread applications. In this work, we address this gap and show how to learn the time-dependent evolution of a locally interacting $n$-qubit system arranged on a graph $\mathsf{G}$ of effective dimension $D$ by resorting only to the preparation of product Pauli eigenstates, evolution by the time-dependent generator for given times and measurements in product Pauli bases. We assume that the time-dependent parameters are well-approximated by functions in a known space of dimension $m$ and for which we can efficiently perform stable interpolation, say by polynomial functions. Our protocol outputs an expansion in that basis that approximates the parameters up to $\epsilon$ in an interval. The protocol only requires $\widetilde{\cO}\big(\epsilon^{-2}\,\poly{m}\,\log(n\delta^{-1})\big)$ samples and $\poly{n,m}$ preprocessing and postprocessing to learn the parameters with probability of success $1-\delta$, making it highly scalable. Importantly, the scaling in the dimension $m$ is polynomial, whereas naive extensions of previous methods yield a dependency that is exponential in $m$. Like previous protocols for the time-independent case, ours is mostly based on estimating time derivatives of expectation values of various observables through interpolation techniques. We then obtain well-conditioned linear equations that allow us to evaluate the value of the time-dependent function for a local generator. However, whereas in the time-independent case it sufficed to only consider derivatives at time $t=0$, here we need to evaluate them at finite times while still being able to relate the derivatives to parameters of the evolution. Thus, besides dealing with technical intricacies related to the time-dependent case, our main innovation is to show how to combine Lieb-Robinson bounds, process shadows and semidefinite programs to estimate the parameters of the evolution efficiently at constant times. Along the way, we extend state-of-the-art Lieb-Robinson bounds on general graphs to the time-dependent, dissipative setting, a result of independent interest. In addition, we show how our technique can be used to verify the outputs of time-dependent dynamics for polynomial times from access to short-time dynamics for cases of interest like linear adiabatic schedules. As such, our protocol is a valuable tool to verify various state preparation procedures on quantum computers and simulators, such as adiabatic preparation, or to characterize time-dependent Markovian noise.