Hamiltonian locality testing and certification do not achieve the Heisenberg limit

arXiv:2610.03205v1 Announce Type: cross Abstract: 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 arepsilon-far from every k-local Hamiltonian requires Omega(1/arepsilon^2) 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 arepsilon-far from it requires Omega(1/arepsilon^2) 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/arepsilon. As a third result, we show that amplitude estimation to precision arepsilon requires Omega(1/arepsilon^2) 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.

Source: arXiv cs.LG | 2026-10-05