Learning quantum Hamiltonians from high-temperature Gibbs states and real-time evolutions

The behaviour of a system is determined by its Hamiltonian. In many cases, the exact Hamiltonian is not known and has to be extracted by analysing the outcome of measurements. We study the problem of learning a local Hamiltonian H to a given precision, supposing either we are given copies of its Gibbs state ρ = e^−βH/Tr(e^−βH) at a known inverse temperature β or we have access to unitary real-time evolution e^−itH for a known evolution time t. Improving on recent results, we show how to learn the coefficients of a local Hamiltonian H to error ε with S = O(logN/(βε)²) Gibbs states or with Q = O(logN/(tε)²) runs of the real-time evolution, where N is the number of qubits in the system and if β < β_c and t < t_c for some critical inverse temperature β_c and critical evolution time t_c. We design a classical post-processing algorithm with time complexity linear in the sample size in both cases, namely, O(NS) and O(NQ). In the Gibbs-state input case, we prove a matching lower bound, showing that our algorithm’s sample complexity is optimal, and hence, our time complexity is also optimal.