Learning Many-Body Hamiltonians with Heisenberg-Limited Scaling

Abstract

Learning a many-body Hamiltonian from its dynamics is a fundamental problem in physics. In this Letter, we propose the first algorithm to achieve the Heisenberg limit for learning an interacting 𝑁-qubit local Hamiltonian. After a total evolution time of 𝒪⁡(𝜀⁻¹), the proposed algorithm can efficiently estimate any parameter in the 𝑁-qubit Hamiltonian to 𝜀 error with high probability. Our algorithm uses ideas from quantum simulation to decouple the unknown 𝑁-qubit Hamiltonian 𝐻 into noninteracting patches and learns 𝐻 using a quantum-enhanced divide-and-conquer approach. The proposed algorithm is robust against state preparation and measurement error, does not require eigenstates or thermal states, and only uses polylog⁡(𝜀⁻¹) experiments. In contrast, the best existing algorithms require 𝒪⁡(𝜀⁻²) experiments and total evolution time. We prove a matching lower bound to establish the asymptotic optimality of our algorithm.

Files

Additional details