Polynomial system-size cost for learning a local Hamiltonian coefficient

The next two open problems deal with Hamiltonian learning from real-time evolutions. The standard setup (see e.g. [HTFS23] and [HKT22] ) is as follows. Let $H = \sum_{a = 1}^m \lambda_a E_a$ be an $n$-qubit $k$-local (but not necessarily geometrically local) Hamiltonian, where we are told the $E_a$’s but do not know the $\lambda_a$’s.

We are given the ability to perform the channel $\rho \mapsto e^{-iHt} \rho e^{iHt}$ for all $t > 0$, and we want to learn a specified coefficient $\lambda_a$ to $\varepsilon$ error (with success probability $\geq 0.99$, say). For such a learning algorithm we consider its total time evolution, i.e. the amount of evolution time of $H$ used over the course of the algorithm.

We know how to solve this problem with $m/\varepsilon$ total evolution time (note that $m = \operatorname{poly}(n)$), and when the Hamiltonian has some underlying geometric locality, we can exploit that to get an algorithm with mild-to-no dependence on the system size, something like $\operatorname{log}(n)/\varepsilon$.

It makes physical sense that assuming geometric locality would effectively remove the dependence on system size. If we think about evolving with respect to a local Hamiltonian, at infinitesimal times, the effect of the particular $\lambda_aE_a$ term we’re interested only affects the support of $E_a$, so most of the $n$ qubits play no role. But at infinitesimal times, we cannot learn the coefficient, since the effect size is similarly infinitesimal. On the other hand, at larger times, the effect of $\lambda_a E_a$ is large, but we expect this effect to be “scrambled” across all $n$ qubits. So, to extract out this information we’d need to pay a system size-type cost to “unscramble” it. If the Hamiltonian is geometrically local, then the “scrambling” only happens in a ball around the support of $E_a$, and so to learn a coefficient you only have to understand that ball, which is independent of system size.

This intuitive argument is not easy to formalize. So, we can ask, is the cost of Hamiltonian learning actually intrinsically linked to geometric locality? I would find such a result interesting, because real-time evolutions are a very strong form of access to $H$; it’s not obvious to me that you really need geometric locality with such a strong form of access. The simplest version of this question is as follows:

Question. Does learning local (but not necessarily geometrically local) Hamiltonians require a total time evolution of $\operatorname{poly}(n)$?

What’s known? This question has been posed previously here and here. We know very little (embarrassingly little, imo) about lower bounds for Hamiltonian learning. The best lower bound is $1/\varepsilon$, which follows from a simple “hybrid” argument: perturbing a coefficient by $\varepsilon$ only affects the algorithm by $O(\varepsilon T)$ where $T$ is the total evolution time, so $T$ has to be large enough to detect this difference.

The task of proving stronger lower bounds has been tackled by papers of Huang, Tong, Fang, and Su and Ma, Flammia, Preskill, and Tong. Neither give improved lower bounds on the problem stated here.

Source definitions

A Hamiltonian on $n$ qubits is a Hermitian matrix $H \in \mathbb{C}^{2^n \times 2^n}$. We typically imagine this matrix being specified as a linear combination of terms $E_a \in \mathbb{C}^{2^n \times 2^n}$ with coefficients $\lambda_a \in \mathbb{R}$. In other words,

We call a Hamiltonian $k$-local if every $E_a$ is supported on at most $k$ qubits. Throughout, we additionally impose the constraint that $E_a$ is a tensor product of Pauli matrices, like $\sigma_X \otimes \sigma_Z \otimes I \otimes \dots \otimes I$. This can be done without loss of generality (though note that this blows up the number of terms for non-local $H$), and it’s important to specify some kind of basis like this so that we can make a sensible definition for what “learning” the Hamiltonian means.

For normalization, we also assume that $-1 \leq \lambda_a \leq 1$ for all $a = 1,\dots,m$.

We call our Hamiltonian geometrically local if there is some additional ‘geometric’ structure to the terms that appear; the strongest version of this assumption is that we imagine the $n$ qubits are nodes on a lattice (represented by a graph $G = ([n], E)$); and every term $E_a$ has a support $\operatorname{supp}(E_a)$ with diameter at most $\Delta$.

A Hamiltonian is gapped if its largest eigenvalue and second largest eigenvalue differ by at least (say) a constant.

For these open problems, we imagine that these parameters $k$ (and $\Delta$ if we assume geometric locality) are constant, say 2.

Historical source dated 2025-04-22. Current resolution status has not been independently reassessed; bounds and claims in the source context refer to that date.