Hamiltonian locality testing and certification do not achieve the Heisenberg limit

1 Introduction

• Hamiltonian learning aims to characterize an unknown Hamiltonian, while Hamiltonian testing asks whether it satisfies a specified property.The motivating access model uses multiple queries to the evolution operator at positive times.Source: §1 · p. 2

1.1 Our results

• With constant success probability, locality testing under 0 < ε < 1/4, k ≤ n/8, and ε2 ≥24/2n requires Ω(1/ε2) evolution time; additive-error-ε amplitude estimation under 0 < ε < 1/16 and ε2 ≥6/2n requires Ω(1/ε2) worst-case total evolution time.Source: §1.1.1 · p. 3, §1.1.3 · p. 4

1.1.1 Hamiltonian locality testing does not achieve the Heisenberg limit

• Ω(1/ε^2) evolution time is required to test whether a Hamiltonian is k-local or ε-far from every k-local Hamiltonian.The bound has a matching upper bound by Kallaugher and Liang [KL25], and assumes k ≤ n/8 and ε^2 ≥ 24/2^n.Source: §1.1.1 · p. 3

1.1.2 Hamiltonian certification does not achieve the Heisenberg limit

• Ω(1/ε^2) evolution time is required to certify whether an unknown Hamiltonian equals a target or is ε-far from it.The bound matches the upper bound by Sinha and Tong [ST25].Source: §1.1.2 · pp. 3–4

1.1.3 Quantum amplitude estimation requires inverses, even with fractional queries

• Ω(1/ε^2) total evolution time is required for amplitude estimation to additive error ε with constant success probability.This recovers Tang and Wright’s lower bound [TW25] in the continuous-time query model.Source: §1.1.3 · p. 4

1.1.4 Our main technical result

• Distinguishing zero from a suitably chosen random Hamiltonian ensemble requires Ω(1/ε^2) total evolution time.The ensemble is far from zero with constant probability when 2^nε^2 is sufficiently large; concentration inequalities support reductions from this distinction to the three problems.Source: §1.1.4 · pp. 4–5

1.2 Technical overview

• The proof adapts the continuous-time adversary method to forward Hamiltonian evolution and bounds a progress function’s rate of change.The method uses a corrected distinguishability progress function for purified evolutions of zero and random Hamiltonians.Source: §1.2 · pp. 5–6

1.3 Future directions

• The lower bounds assume a restriction of the form 1/ε = 2^{cn} for some constant c; how far they extend into higher precision remains open.The paper also asks whether the adversary method can yield an optimal lower bound for Hamiltonian sparsity testing.Source: §1.3 · p. 6

2.1 Notation

• The notation section defines [n] and R+, uses Lebesgue measure on real intervals and uniform measure on {0,1}^n, and specifies Boolean-character and real Fourier-transform conventions.Source: §2.1 · pp. 6–7

2.2 Hamiltonians

• Hamiltonians are bounded Hermitian operators; k-locality is equivalent to having no Pauli coefficients above weight k, and distance is measured by normalized Frobenius norm.The section also introduces time-dependent evolution through the Dyson expansion.Source: §2.2 · pp. 8–9

2.3 Problem and access model

• Experiments prepare a state, interleave forward evolution queries with input-independent unitaries, and measure; locality testing and certification use promised yes-or-far cases.The complexity measure is worst-case total query duration.Source: §2.3 · pp. 9–10

2.3.1 Continuous-time queries

• The continuous-time query model uses an input-dependent query Hamiltonian and an input-independent driver, and can simulate the experimental protocol without increasing total evolution time.Nonnegative query intensity enforces forward-only evolution; inactive branches can be left unqueried in adaptive protocols.Source: §2.3.1 · pp. 10–12

2.4 Useful inequalities

• The preliminaries recall Markov’s, Chebyshev’s, and Young’s convolution inequalities for use in later proofs..Source: §2.4 · p. 12

• The proof adapts the continuous-time adversary method directly to the zero-versus-random-Hamiltonian distinction.The authors introduce the adversary operator and progress function for this problem rather than presenting the general framework.Source: §3 · p. 12
• Hamiltonians drawn from the constructed ensemble are far from local and from zero with high probability.Source: §3 · p. 12
• Any successful algorithm must increase progress by a constant, while the proof bounds its increase per unit evolution time to obtain an Ω(1/ε²) lower bound.Source: §3 · p. 12

• The hard instances are diagonal Hamiltonians whose entries are independently drawn from a distribution ν_ε supported on [−1, 1].Source: §3.1 · p. 13
• The distribution satisfies E[h²] = ε², one of the stated properties used to ensure farness from zero.Source: §3.1 · p. 13
• Choosing entries uniformly from {−ε, ε} makes the ensemble distinguishable with evolution time O(1/ε), so it does not provide the stronger lower bound sought here.Source: §3.1 · pp. 14–15
• Additional bounds involving the bump function and operator M control contributions to the adversary progress argument independently of interval duration.These estimates are used to construct a correction that bounds progress growth by O(ε²) per unit query time.Source: §3.1 · p. 15

3.2.1 Purifying the randomness

• The proof represents each random Hamiltonian entry in an extra input register, making the purified evolution equivalent to drawing one fixed random Hamiltonian for the algorithm.Source: §3.2.1 · p. 16

3.2 The progress function

• The progress function measures separation between the joint evolutions for zero and random Hamiltonians, with a correction added to control its rate of change.Source: §3.2.2 · p. 17

3.2.2 The definition of the progress function

• Combining the required progress for a successful algorithm with the bound on progress growth gives a total evolution-time requirement of Ω(1/ε²).Source: §3.2.2 · p. 17

3.3 A successful algorithm must progress

• A successful distinguisher must have a large progress value at the final time.The section identifies this as a necessary condition for distinguishing the random ensemble from the zero Hamiltonian.Source: §3.3 · p. 17
• If the final states differ in norm by Ω(1), the progress function satisfies P(tf) = Ω(1).This is the formal condition given by Lemma 3.6.Source: §3.3 · p. 17
• The squared final-state distance equals 2(1 − Re⟨ΨZ(tf)|ΨF(tf)⟩), relating state separation to the real overlap.The proof expands the squared norm of the difference between the final states.Source: §3.3 · p. 17

3.4 The progress growth is bounded

• The construction makes G nonnegative and bounded, with G|Ω⟩ = 0, while the auxiliary operators O and R are bounded.D is chosen self-adjoint and at least the identity, so D−1 exists.Source: §3.4 · p. 18

3.4.1 Bounding the change in the correction term

• The correction term g is designed to decrease when overlap is large, up to a contribution proportional to |u(τ)|².For the actual evolution, u(τ) = εq(τ), making that contribution proportional to ε².Source: §3.4.1 · pp. 19–20

3.4.2 Bounding the progress of the algorithm

• The progress function is absolutely continuous and has a bounded derivative, with Cprog := 1 + η².Lemma 3.9 gives the derivative bound for almost every t in [0, tf].Source: §3.4.2 · p. 21

3.5 Putting everything together

• The lower-bound argument compares the required final progress with the rate bound on progress growth.This comparison is the stated step from the two lemmas to the theorem.Source: §3.5 · p. 23
• Theorem 3.10 gives a lower bound on total evolution time T for algorithms whose final states differ by Ω(1).The theorem applies for 0 < ε < 1/2.Source: §3.5 · p. 23
• The proof’s rate bound relies on forward evolution: negative λ would reverse the inequalities and no longer imply the required upper bound.The restriction λ(t) ≥ 0 is used in obtaining the bounds on the progress derivative.Source: §3.5 · p. 23

4.1 Locality testing does not achieve the Heisenberg limit

• Locality testing requires Ω(1/ε²) total evolution time, so this task does not attain Heisenberg-limit scaling.Source: §4.1 · pp. 23, 25

4.2 Hamiltonian certification does not achieve the Heisenberg limit

• Hamiltonian certification requires Ω(1/ε²) total forward evolution; the reduction uses traceless random Hamiltonians so farness is not only an undetectable identity shift.Source: §4.2 · pp. 25–26

4.3 Amplitude estimation requires inverses

• Amplitude estimation to additive error ε requires Ω(1/ε²) total evolution time, shown by turning estimates into a distinguisher for zero versus random Hamiltonians.Source: §4.3 · pp. 26, 28