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 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.
- Received 3 November 2022
- Accepted 18 April 2023
© 2023 American Physical Society
Quantum InformationStatistical Physics