Quantum algorithms enable Heisenberg-limited scaling across many tasks in sensing and learning, achieving precision $\varepsilon$ using $O(1/\varepsilon)$ total evolution time. However, in Hamiltonian property testing, the best known algorithms have $O(1/\varepsilon^2)$ total evolution time, unless it is possible to $\textit{reverse}$ the flow of time under the Hamiltonian. In this work, we prove that time reversal is necessary to close this gap. We establish evolution time lower bounds for Hamiltonian certification and locality testing, for a continuous family of error metrics ranging from average- to worst-case. We also prove matching upper bounds for Hamiltonian certification in all cases, both with and without time reversal, showing that the advantage from time reversal persists. Our results follow from a new Fourier-analytic approach to quantum lower bounds in continuous time, which is sensitive to time reversal and applicable beyond Hamiltonian property testing. This gives an alternative proof that inverses are required for amplitude amplification and estimation, improving the lower bounds of Tang and Wright and extending to fractional queries. We also show that, for unstructured search, uncertainty in the phase of the oracle destroys the quantum speedup without inverse queries, even when the oracle is fixed and coherent. Our work rigorously establishes time reversal as a resource governing both the precision of quantum measurement and the robustness of quantum algorithms.
Quantum algorithms enable Heisenberg-limited scaling across many tasks in sensing and learning, achieving precision ε using O(1/ε) total evolution time. However, in Hamiltonian property testing, the best known algorithms have O(1/ε2) total evolution time, unless it is possible to reverse the flow of time under the Hamiltonian. In this work, we prove that time reversal is necessary to close this gap. We establish evolution time lower bounds for Hamiltonian certification and locality testing, for a continuous family of error metrics ranging from average- to worst-case. We also prove matching upper bounds for Hamiltonian certification in all cases, both with and without time reversal, showing that the advantage from time reversal persists. Our results follow from a new Fourier-analytic approach to quantum lower bounds in continuous time, which is sensitive to time reversal and applicable beyond Hamiltonian property testing. This gives an alternative proof that inverses are required for amplitude amplification and estimation, improving the lower bounds of Tang and Wright and extending to fractional queries. We also show that, for unstructured search, uncertainty in the phase of the oracle destroys the quantum speedup without inverse queries, even when the oracle is fixed and coherent. Our work rigorously establishes time reversal as a resource governing both the precision of quantum measurement and the robustness of quantum algorithms.
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 ε-far from every k-local Hamiltonian requires Ω(1/ε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 ε-far from it requires Ω(1/ε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/ε.
As a third result, we show that amplitude estimation to precision ε requires Ω(1/ε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.
We study the problem of certifying local Hamiltonians from real-time access to their dynamics. Given oracle access to e−itH for an unknown k-local Hamiltonian H and a fully specified target Hamiltonian H0, the goal is to decide whether H is exactly equal to H0 or differs from H0 by at least ε in normalized Frobenius norm, while minimizing the total evolution time. We introduce the first intolerant Hamiltonian certification protocol that achieves optimal performance for all constant-locality Hamiltonians. For general n-qubit, k-local, traceless Hamiltonians, our procedure uses O(ck/ε) total evolution time for a universal constant c, and succeeds with high probability. In particular, for O(1)-local Hamiltonians, the total evolution time becomes Θ(1/ε), matching the known Ω(1/ε) lower bounds and achieving the gold-standard Heisenberg-limit scaling. Prior certification methods either relied on implementing inverse evolution of H, required controlled access to e−itH, or achieved near-optimal guarantees only in restricted settings such as the Ising case (k=2). In contrast, our algorithm requires neither inverse evolution nor controlled operations: it uses only forward real-time dynamics and achieves optimal intolerant certification for all constant-locality Hamiltonians.
Locality is a fundamental feature of many physical time evolutions. Assumptions on locality and related structural properties also underlie recently proposed procedures for learning an unknown Hamiltonian from access to the induced time evolution. However, no protocols to rigorously test whether an unknown Hamiltonian is local were known. We investigate Hamiltonian locality testing as a property testing problem, where the task is to determine whether an unknown n -qubit Hamiltonian H is k -local or ε -far from all k -local Hamiltonians, given access to the time evolution along H . First, we emphasize the importance of the chosen distance measure: With respect to the operator norm, a worst-case distance measure, incoherent quantum locality testers require Ω ~ ( 2 n ) many time evolution queries and an expected total evolution time of Ω ~ ( 2 n / ε ) , and even coherent testers need Ω ( 2 n / 2 ) many queries and Ω ( 2 n / 2 / ε ) total evolution time. In contrast, when distances are measured according to the normalized Frobenius norm, corresponding to an average-case distance, we give a sample-, time-, and computationally efficient incoherent Hamiltonian locality testing algorithm based on randomized measurements. In fact, our procedure can be used to simultaneously test a wide class of Hamiltonian properties beyond locality. Finally, we prove that learning a general Hamiltonian remains exponentially hard with this average-case distance, thereby establishing an exponential separation between Hamiltonian testing and learning. Our work initiates the study of property testing for quantum Hamiltonians, demonstrating that a broad class of Hamiltonian properties is efficiently testable even with limited quantum capabilities, and positioning Hamiltonian testing as an independent area of research alongside Hamiltonian learning.
In the quantum state distinguishing problem, an algorithm is given copies of a state ∣ψ⟩ or ∣φ⟩ separated by trace distance ε, and tasked with deciding which is the case. It is a standard result that Θ(ε−2) copies are required, while having access to a unitary state preparation oracle and its inverse improves this to Θ(ε−1) queries. We study the intermediate case with forward-only access, capturing scenarios where the oracle is a physical process that cannot be reversed. Tang and Wright recently showed that distinguishing a known state from an \emph{unknown} close state requires Ω(ε−2) forward queries in high dimension; we strengthen this result by proving the same bound even when both states are known, as in the state distinguishing setting. Moreover, our lower bound uses a direct hybrid argument, avoiding advanced compressed oracle techniques used in the prior work. In contrast, we give a dimension-independent algorithm solving a continuous-time variant of state distinguishing with only O(ε−1) total forward evolution time. The algorithm uses quantum Zeno dynamics to confine evolution to a known two-dimensional subspace. Thus, a quadratic advantage survives without inverse access for a natural continuous-time analogue of state distinguishing.
Characterizing quantum systems by learning their underlying Hamiltonians is a central task in quantum information science. While recent algorithmic advances have achieved near-optimal efficiency in this task, they critically rely on accessing arbitrarily short-time dynamics. This reliance poses severe experimental challenges due to finite control bandwidth and transient pulse errors. In this work, we demonstrate that Heisenberg-limited Hamiltonian learning can be achieved without short-time control. We introduce a framework in which every query to the unknown dynamics has duration at least a prescribed minimum time T, and show that this restriction does not preclude Heisenberg-limited scaling. The key ingredient is a method for emulating the continuous quantum control required by iterative learning algorithms using only such lower-bounded evolution times. This reduces the learning task to sparse pure-state tomography. Notably, for logarithmically sparse Hamiltonians, our algorithm achieves the information-theoretically optimal 1/ε scaling in total evolution time for any arbitrary constant minimum evolution time T. For many-body (polynomially sparse) systems, we uncover a rigorous quantitative tradeoff, showing that the minimum required evolution time can be significantly relaxed from the standard limit at a polynomial cost in total evolution time. Our results affirmatively resolve a prominent open problem in the field and reveal that high-bandwidth, ultra-short pulses are not fundamentally necessary for optimal quantum learning.
The (tolerant) Hamiltonian locality testing problem, introduced in [Bluhm, Caro,Oufkir `24], is to determine whether a Hamiltonian H is ε1-close to being k-local (i.e. can be written as the sum of weight-k Pauli operators) or ε2-far from any k-local Hamiltonian, given access to its time evolution operator and using as little total evolution time as possible, with distance typically defined by the normalized Frobenius norm. We give the tightest known bounds for this problem, proving an O((ε2−ε1)5ε2) evolution time upper bound and an Ω(ε2−ε11) lower bound. Our algorithm does not require reverse time evolution or controlled application of the time evolution operator, although our lower bound applies to algorithms using either tool. Furthermore, we show that if we are allowed reverse time evolution, this lower bound is tight, giving a matching O(ε2−ε11) evolution time algorithm.