Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2505.06478 · Leibniz international proceedings in informatics

Hamiltonian Locality Testing via Trotterized Postselection

John Kallaugher, Daniel Liang

Published Jan 1, 2025• 11 citations
arXivHTMLPDF

Abstract

The (tolerant) Hamiltonian locality testing problem, introduced in [Bluhm, Caro,Oufkir `24], is to determine whether a Hamiltonian $H$ is $\varepsilon_1$-close to being $k$-local (i.e. can be written as the sum of weight-$k$ Pauli operators) or $\varepsilon_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 $\text{O}\left(\sqrt{\frac{\varepsilon_2}{(\varepsilon_2-\varepsilon_1)^5}}\right)$ evolution time upper bound and an $Ω\left(\frac{1}{\varepsilon_2-\varepsilon_1}\right)$ 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 $\text{O}\left(\frac{1}{\varepsilon_2-\varepsilon_1}\right)$ evolution time algorithm.

DOI
10.4230/lipics.tqc.2025.10

Related papers

Hamiltonian locality testing and certification do not achieve the Heisenberg limit

Francisco Escudero Gutiérrez, Junseo Lee, Sebastian Zur

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 $Ω(1/\varepsilon^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 $\varepsilon$-far from it requires $Ω(1/\varepsilon^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/\varepsilon$. As a third result, we show that amplitude estimation to precision $\varepsilon$ requires $Ω(1/\varepsilon^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.

quant-pharXiv:2610.03205•Oct 5, 2026•0 citations

Testing and Learning Structured Quantum Hamiltonians

Srinivasan Arunachalam, Arkopal Dutt, Francisco Escudero Gutiérrez

We consider the problems of testing and learning an n -qubit Hamiltonian \(H=\sum _x \lambda _x \sigma _x\) expressed in its Pauli basis, from queries to its evolution operator \(U=e^{-iHt}\) . To this end, we prove the following results. Testing : We give a tolerant testing protocol to decide if a Hamiltonian is \(\varepsilon _1\) -close to k -local or \(\varepsilon _2\) -far from k -local in the \(\ell _2\) norm of the coefficients, with \(O(1/(\varepsilon _2-\varepsilon _1)^{4})\) queries, thereby solving two open questions posed in a recent work by Bluhm, Caro and Oufkir (Bluhm, A., Caro, M.C., Oufkir, A.). We give a protocol for testing whether a Hamiltonian is \(\varepsilon _1\) -close to being s -sparse or \(\varepsilon _2\) -far from being s -sparse in the \(\ell _2\) norm of the coefficients, with \(O(s^{6}/(\varepsilon _2^2-\varepsilon _1^2)^{6})\) queries. Learning : We give a protocol to \(\varepsilon \) -learn unstructured Hamiltonian in the \(\ell _\infty \) norm of the coefficients with \(O(1/\varepsilon ^4)\) queries. Combining this with the non-commutative Bohnenblust-Hille inequality, we obtain an algorithm for learning k -local Hamiltonians in \(\ell _2\) norm of the coefficients that only uses \(O(\exp (k^2+k\log (1/\varepsilon )))\) queries. For Hamiltonians that are s -sparse in the Pauli basis, we can learn them in the \(\ell _2\) norm with \(O(s^2/\varepsilon ^4)\) queries. Learning without quantum memory : The learning results stated above have no dependence on the system size n , but require n -qubit quantum memory. We give subroutines that allow us to reproduce all the above learning results without quantum memory; squaring the query complexity and paying a \((\log n)\) -factor in the local case and an n -factor in the sparse case. Testing without quantum memory : We give a new subroutine called Pauli hashing , which allows one to tolerantly test s -sparse Hamiltonians in the \(\ell _2\) norm using \(\tilde{O}(s^{14}/(\varepsilon _2^2-\varepsilon _1^2)^{18})\) query complexity. A key ingredient is showing that s -sparse Pauli channels can be tested in a tolerant fashion as being \(\varepsilon _1\) -close to being s -sparse or \(\varepsilon _2\) -far under the diamond norm, using \(\tilde{O}(s^2/(\varepsilon _2-\varepsilon _1)^6)\) queries via Pauli hashing. In order to prove these results, we prove new structural theorems for local Hamiltonians, sparse Pauli channels and sparse Hamiltonians. We complement our learning algorithms with lower bounds that are polynomially weaker. Furthermore, our algorithms use short time evolutions and do not assume prior knowledge of the terms on which the Pauli spectrum is supported on, i.e., we do not require prior knowledge of the support of the Hamiltonian.

Communications in Mathematical Physics•Dec 8, 2025•2 citations

Optimal certification of constant-local Hamiltonians

Junseo Lee, Myeongjin Shin

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 $H_0$, the goal is to decide whether $H$ is exactly equal to $H_0$ or differs from $H_0$ by at least $\varepsilon$ 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(c^k/\varepsilon)$ 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/\varepsilon)$, matching the known $Ω(1/\varepsilon)$ 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.

quant-pharXiv:2512.09778•Dec 11, 2025•7 citations

Certifying and learning local quantum Hamiltonians

Andreas Bluhm, Matthias C. Caro, Francisco Escudero Gutiérrez +4 more

In this work, we study the problems of certifying and learning quantum $k$-local Hamiltonians, for a constant $k$. Our main contributions are as follows: - Certification of Hamiltonians. We show that certifying a local Hamiltonian in normalized Frobenius norm via access to its time-evolution operator can be achieved with only $O(1/\varepsilon)$ evolution time. This is optimal, as it matches the Heisenberg-scaling lower bound of $Ω(1/\varepsilon)$. To our knowledge, this is the first optimal algorithm for testing a Hamiltonian property. A key ingredient in our analysis is the Bonami Hypercontractivity Lemma from Fourier analysis. - Learning Gibbs states. We design an algorithm for learning Gibbs states of local Hamiltonians in trace norm that is sample-efficient in all relevant parameters. In contrast, previous approaches learned the underlying Hamiltonian (which implies learning the Gibbs state), and thus inevitably suffered from exponential sample complexity scaling in the inverse temperature. - Certification of Gibbs states. We give an algorithm for certifying Gibbs states of local Hamiltonians in trace norm that is both sample and time-efficient in all relevant parameters, thereby solving a question posed by Anshu (Harvard Data Science Review, 2022).

quant-pharXiv:2603.29809•Apr 1, 2026•8 citations

The power of time reversal in Hamiltonian property testing

Richard R. Allen, Matthias C. Caro, Yanlin Chen +2 more

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.

quant-pharXiv:2610.04996•Oct 6, 2026•0 citations

Hamiltonian Property Testing

Andreas Blühm, Matthias C. Caro, Aadil Oufkir

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.

arXiv:2403.02968•Quantum•Jan 21, 2026•34 citations
The (tolerant) Hamiltonian locality testing problem, introduced in [Bluhm, Caro,Oufkir `24], is to determine whether a Hamiltonian HHH is ε1\varepsilon_1ε1​-close to being kkk-local (i.e. can be written as the sum of weight-kkk Pauli operators) or ε2\varepsilon_2ε2​-far from any kkk-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(ε2−ε1)5)\text{O}\left(\sqrt{\frac{\varepsilon_2}{(\varepsilon_2-\varepsilon_1)^5}}\right)O((ε2​−ε1​)5ε2​​​) evolution time upper bound and an Ω(1ε2−ε1)Ω\left(\frac{1}{\varepsilon_2-\varepsilon_1}\right)Ω(ε2​−ε1​1​) 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(1ε2−ε1)\text{O}\left(\frac{1}{\varepsilon_2-\varepsilon_1}\right)O(ε2​−ε1​1​) evolution time algorithm.
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 kkk-local or ε\varepsilonε-far from every kkk-local Hamiltonian requires Ω(1/ε2)Ω(1/\varepsilon^2)Ω(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 ε\varepsilonε-far from it requires Ω(1/ε2)Ω(1/\varepsilon^2)Ω(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/ε1/\varepsilon1/ε. As a third result, we show that amplitude estimation to precision ε\varepsilonε requires Ω(1/ε2)Ω(1/\varepsilon^2)Ω(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 consider the problems of testing and learning an n -qubit Hamiltonian H=∑xλxσxH=\sum _x \lambda _x \sigma _xH=∑x​λx​σx​ expressed in its Pauli basis, from queries to its evolution operator U=e−iHtU=e^{-iHt}U=e−iHt . To this end, we prove the following results. Testing : We give a tolerant testing protocol to decide if a Hamiltonian is ε1\varepsilon _1ε1​ -close to k -local or ε2\varepsilon _2ε2​ -far from k -local in the ℓ2\ell _2ℓ2​ norm of the coefficients, with O(1/(ε2−ε1)4)O(1/(\varepsilon _2-\varepsilon _1)^{4})O(1/(ε2​−ε1​)4) queries, thereby solving two open questions posed in a recent work by Bluhm, Caro and Oufkir (Bluhm, A., Caro, M.C., Oufkir, A.). We give a protocol for testing whether a Hamiltonian is ε1\varepsilon _1ε1​ -close to being s -sparse or ε2\varepsilon _2ε2​ -far from being s -sparse in the ℓ2\ell _2ℓ2​ norm of the coefficients, with O(s6/(ε22−ε12)6)O(s^{6}/(\varepsilon _2^2-\varepsilon _1^2)^{6})O(s6/(ε22​−ε12​)6) queries. Learning : We give a protocol to ε\varepsilon ε -learn unstructured Hamiltonian in the ℓ∞\ell _\infty ℓ∞​ norm of the coefficients with O(1/ε4)O(1/\varepsilon ^4)O(1/ε4) queries. Combining this with the non-commutative Bohnenblust-Hille inequality, we obtain an algorithm for learning k -local Hamiltonians in ℓ2\ell _2ℓ2​ norm of the coefficients that only uses O(exp⁡(k2+klog⁡(1/ε)))O(\exp (k^2+k\log (1/\varepsilon )))O(exp(k2+klog(1/ε))) queries. For Hamiltonians that are s -sparse in the Pauli basis, we can learn them in the ℓ2\ell _2ℓ2​ norm with O(s2/ε4)O(s^2/\varepsilon ^4)O(s2/ε4) queries. Learning without quantum memory : The learning results stated above have no dependence on the system size n , but require n -qubit quantum memory. We give subroutines that allow us to reproduce all the above learning results without quantum memory; squaring the query complexity and paying a (log⁡n)(\log n)(logn) -factor in the local case and an n -factor in the sparse case. Testing without quantum memory : We give a new subroutine called Pauli hashing , which allows one to tolerantly test s -sparse Hamiltonians in the ℓ2\ell _2ℓ2​ norm using O~(s14/(ε22−ε12)18)\tilde{O}(s^{14}/(\varepsilon _2^2-\varepsilon _1^2)^{18})O~(s14/(ε22​−ε12​)18) query complexity. A key ingredient is showing that s -sparse Pauli channels can be tested in a tolerant fashion as being ε1\varepsilon _1ε1​ -close to being s -sparse or ε2\varepsilon _2ε2​ -far under the diamond norm, using O~(s2/(ε2−ε1)6)\tilde{O}(s^2/(\varepsilon _2-\varepsilon _1)^6)O~(s2/(ε2​−ε1​)6) queries via Pauli hashing. In order to prove these results, we prove new structural theorems for local Hamiltonians, sparse Pauli channels and sparse Hamiltonians. We complement our learning algorithms with lower bounds that are polynomially weaker. Furthermore, our algorithms use short time evolutions and do not assume prior knowledge of the terms on which the Pauli spectrum is supported on, i.e., we do not require prior knowledge of the support of the Hamiltonian.
We study the problem of certifying local Hamiltonians from real-time access to their dynamics. Given oracle access to e−itHe^{-itH}e−itH for an unknown kkk-local Hamiltonian HHH and a fully specified target Hamiltonian H0H_0H0​, the goal is to decide whether HHH is exactly equal to H0H_0H0​ or differs from H0H_0H0​ by at least ε\varepsilonε 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 nnn-qubit, kkk-local, traceless Hamiltonians, our procedure uses O(ck/ε)O(c^k/\varepsilon)O(ck/ε) total evolution time for a universal constant ccc, and succeeds with high probability. In particular, for O(1)O(1)O(1)-local Hamiltonians, the total evolution time becomes Θ(1/ε)Θ(1/\varepsilon)Θ(1/ε), matching the known Ω(1/ε)Ω(1/\varepsilon)Ω(1/ε) lower bounds and achieving the gold-standard Heisenberg-limit scaling. Prior certification methods either relied on implementing inverse evolution of HHH, required controlled access to e−itHe^{-itH}e−itH, or achieved near-optimal guarantees only in restricted settings such as the Ising case (k=2k=2k=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.
In this work, we study the problems of certifying and learning quantum kkk-local Hamiltonians, for a constant kkk. Our main contributions are as follows: - Certification of Hamiltonians. We show that certifying a local Hamiltonian in normalized Frobenius norm via access to its time-evolution operator can be achieved with only O(1/ε)O(1/\varepsilon)O(1/ε) evolution time. This is optimal, as it matches the Heisenberg-scaling lower bound of Ω(1/ε)Ω(1/\varepsilon)Ω(1/ε). To our knowledge, this is the first optimal algorithm for testing a Hamiltonian property. A key ingredient in our analysis is the Bonami Hypercontractivity Lemma from Fourier analysis. - Learning Gibbs states. We design an algorithm for learning Gibbs states of local Hamiltonians in trace norm that is sample-efficient in all relevant parameters. In contrast, previous approaches learned the underlying Hamiltonian (which implies learning the Gibbs state), and thus inevitably suffered from exponential sample complexity scaling in the inverse temperature. - Certification of Gibbs states. We give an algorithm for certifying Gibbs states of local Hamiltonians in trace norm that is both sample and time-efficient in all relevant parameters, thereby solving a question posed by Anshu (Harvard Data Science Review, 2022).
Quantum algorithms enable Heisenberg-limited scaling across many tasks in sensing and learning, achieving precision ε\varepsilonε using O(1/ε)O(1/\varepsilon)O(1/ε) total evolution time. However, in Hamiltonian property testing, the best known algorithms have O(1/ε2)O(1/\varepsilon^2)O(1/ε2) total evolution time, unless it is possible to reverse\textit{reverse}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.
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.