# Hamiltonian locality testing and certification do not achieve the Heisenberg limit

arXiv: https://arxiv.org/abs/2610.03205 · HTML: https://mlsanity.com/paper/2610.03205/

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 20 of its 53 references that are in the map.
- First posted on arXiv 2 Oct 2026.

## Builds on (most cited first, 20 of 20)

- [Sample-efficient learning of quantum many-body systems](https://mlsanity.com/paper/2004.07266/) (2020)
- [Learning many-body Hamiltonians with Heisenberg-limited scaling](https://mlsanity.com/paper/2210.03030/) (2022)
- [Learning Quantum Processes and Hamiltonians via the Pauli Transfer Matrix](https://mlsanity.com/paper/2212.04471/) (2022)
- [Learning quantum Hamiltonians at any temperature in polynomial time](https://mlsanity.com/paper/2310.02243/) (2023)
- [Practical Black Box Hamiltonian Learning](https://mlsanity.com/paper/2206.15464/) (2022)
- [Structure learning of Hamiltonians from real-time evolution](https://mlsanity.com/paper/2405.00082/) (2024)
- [Learning k-body Hamiltonians via compressed sensing](https://mlsanity.com/paper/2410.18928/) (2024)
- [Hamiltonian Property Testing](https://mlsanity.com/paper/2403.02968/) (2024)
- [Amplitude amplification and estimation require inverses](https://mlsanity.com/paper/2507.23787/) (2025)
- [Learning the structure of any Hamiltonian from minimal assumptions](https://mlsanity.com/paper/2410.21635/) (2024)
- [Nearly optimal algorithms to learn sparse quantum Hamiltonians in physically motivated distances](https://mlsanity.com/paper/2509.09813/) (2025)
- [Testing and learning structured quantum Hamiltonians](https://mlsanity.com/paper/2411.00082/) (2024)
- [Ansatz-free Hamiltonian learning with Heisenberg-limited scaling](https://mlsanity.com/paper/2502.11900/) (2025)
- [Hamiltonian Locality Testing via Trotterized Postselection](https://mlsanity.com/paper/2505.06478/) (2025)
- [Optimal detection of dissipation in Lindbladian dynamics](https://mlsanity.com/paper/2603.17736/) (2026)
- [Heisenberg-limited Hamiltonian learning without short-time control](https://mlsanity.com/paper/2604.27838/) (2026)
- [Optimal Ansatz-free Hamiltonian Learning In Situ](https://mlsanity.com/paper/2606.19486/) (2026)
- [Certifying and learning local quantum Hamiltonians](https://mlsanity.com/paper/2603.29809/) (2026)
- [Learning the structure of open quantum systems](https://mlsanity.com/paper/2606.30358/) (2026)
- [Characterizing Arbitrary Lindbladian Dynamics with a Few Pauli Measurements](https://mlsanity.com/paper/2607.23044/) (2026)

## Abstract (arXiv)

We establish lower bounds for Hamiltonian property testing with access to the time-evolution operator but not its inverse. Each experiment may query the time-evolution operator multiple times, and distances between Hamiltonians are measured in the normalized Frobenius norm. In this model, we show that testing whether a Hamiltonian is k-local or varepsilon-far from every k-local Hamiltonian requires Omega(1/varepsilon2) total evolution time, matching the upper bound of Kallaugher and Liang (TQC'25). We also prove that testing whether an unknown Hamiltonian equals a target Hamiltonian or is varepsilon-far from it requires Omega(1/varepsilon2) total evolution time, matching the upper bound of Sinha and Tong (2025). These are the first lower bounds for natural problems in Hamiltonian learning and testing that rule out Heisenberg-limited scaling of 1/varepsilon. As a third result, we show that amplitude estimation to precision varepsilon requires Omega(1/varepsilon2) total time evolution, recovering the result of Tang and Wright (QIP'26) in the continuous-time query model. All three results follow from the hardness of distinguishing the zero Hamiltonian from a suitably chosen ensemble of random Hamiltonians. We establish this hardness by adapting the continuous-time adversary method to forward Hamiltonian evolution.