Lower bounds for Learning Hamiltonians from Time Evolution

How can we learn about quantum evolutions, given the ability to observe how it interacts with the real world? More formally, we are given the ability to apply time evolutions of an unknown n-qubit Hamiltonian H, and the question is to learn parametric information about H, using as little time and as few interactions with H as possible. An exciting recent line of work has developed a number of new algorithms for this problem, however, all known algorithms suffer, in the worst case, a polynomial dependence on the number of unknown parameters of H. Obtaining any lower bound that depended on the number of unknown parameters was raised as an open question in recent work by [Bakshi-Liu-Moitra-Tang'24], as well as at a 2024 FOCS workshop.

 

In this work, we demonstrate strong lower bounds for Hamiltonian learning from time evolution. In particular, we show that learning a single parameter of a k-local Hamiltonian, even given knowledge of all of the other parameters, requires n^{Omega (k)} time and/or number of interactions with the Hamiltonian. This resolves the open question of [Bakshi-Liu-Moitra-Tang'24]. We also demonstrate similar lower bounds for non-parametric notions of Hamiltonian learning. Thus, our results demonstrate a qualitative "all-or-nothing" phenomenon: essentially, one cannot learn any information about the Hamiltonian in less than $n^{Theta(k)}$ time, yet in the same complexity, one can learn everything about the Hamiltonian. Our lower bound goes through a reduction to the construction of Boolean functions which are everywhere large on the hypercube, yet which have bounded Fourier coefficients, which may be of independent interest. 

 

No background in quantum learning will be expected. Based on joint work with Ziyun Chen (UW) and Joe Slote (UW).