arXiv:2404.06282

Simple algorithms to test and learn local Hamiltonians

Francisco Escudero Gutiérrez

Published Apr 9, 2024• 0 citations

Abstract

We consider the problems of testing and learning an $n$-qubit $k$-local Hamiltonian from queries to its evolution operator with respect the 2-norm of the Pauli spectrum, or equivalently, the normalized Frobenius norm. For testing whether a Hamiltonian is $ε_1$-close to $k$-local or $ε_2$-far from $k$-local, we show that $O(1/(ε_2-ε_1)^{8})$ queries suffice. This solves two questions posed in a recent work by Bluhm, Caro and Oufkir. For learning up to error $ε$, we show that $\exp(O(k^2+k\log(1/ε)))$ queries suffice. Our proofs are simple, concise and based on Pauli-analytic techniques.

DOI: 10.48550/arxiv.2404.06282

Related papers

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 PhysicsDec 8, 20250 citations

Certifying and learning local quantum Hamiltonians

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

quant-pharXiv:2603.29809Apr 1, 20260 citations

Testing and learning structured quantum Hamiltonians

Srinivasan Arunachalam, Arkopal Dutt, Francisco Escudero Gutiérrez

arXiv:2411.00082Oct 31, 20240 citations

Hamiltonian locality testing and certification do not achieve the Heisenberg limit

Francisco Escudero Gutiérrez, Junseo Lee, Sebastian Zur

quant-pharXiv:2610.03205Oct 5, 20260 citations

Testing and Learning Structured Quantum Hamiltonians

Srinivasan Arunachalam, Arkopal Dutt, Francisco Escudero Gutiérrez

ACM Symposium on Theory of Computing (STOC)Jun 15, 20253 citations

Optimal certification of constant-local Hamiltonians

Junseo Lee, Myeongjin Shin

quant-pharXiv:2512.09778Dec 11, 20250 citations

arXiv:2404.06282

Simple algorithms to test and learn local Hamiltonians

Francisco Escudero Gutiérrez

Published Apr 9, 2024• 0 citations

arXiv HTML PDF

Abstract

We consider the problems of testing and learning an

n

-qubit

k

-local Hamiltonian from queries to its evolution operator with respect the 2-norm of the Pauli spectrum, or equivalently, the normalized Frobenius norm. For testing whether a Hamiltonian is

ε_1

-close to

k

-local or

ε_2

-far from

k

-local, we show that

O(1/(ε_2-ε_1)^{8})

queries suffice. This solves two questions posed in a recent work by Bluhm, Caro and Oufkir. For learning up to error

ε

, we show that

\exp(O(k^2+k\log(1/ε)))

queries suffice. Our proofs are simple, concise and based on Pauli-analytic techniques.

DOI: 10.48550/arxiv.2404.06282

Related papers

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.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 PhysicsDec 8, 20250 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).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.29809Apr 1, 20260 citations

Testing and learning structured quantum Hamiltonians

Srinivasan Arunachalam, Arkopal Dutt, Francisco Escudero Gutiérrez

We consider the problems of testing and learning an unknown $n$ -qubit Hamiltonian $H$ from queries to its evolution operator $e^{-iHt}$ under the normalized Frobenius norm. We prove: 1. Local Hamiltonians: We give a tolerant testing protocol to decide if $H$ is $ε_1$ -close to $k$ -local or $ε_2$ -far from $k$ -local, with $O(1/(ε_2-ε_1)^{4})$ queries, solving open questions posed in a recent work by Bluhm et al. For learning a $k$ -local $H$ up to error $ε$ , we give a protocol with query complexity $\exp(O(k^2+k\log(1/ε)))$ independent of $n$ , by leveraging the non-commutative Bohnenblust-Hille inequality. 2. Sparse Hamiltonians: We give a protocol to test if $H$ is $ε_1$ -close to being $s$ -sparse (in the Pauli basis) or $ε_2$ -far from being $s$ -sparse, with $O(s^{6}/(ε_2^2-ε_1^2)^{6})$ queries. For learning up to error $ε$ , we show that $O(s^{4}/ε^{8})$ queries suffice. 3. Learning without memory: The learning results stated above have no dependence on $n$ , but require $n$ -qubit quantum memory. We give subroutines that allow us to learn without memory; increasing the query complexity by a $(\log n)$ -factor in the local case and an $n$ -factor in the sparse case. 4. Testing without memory: We give a new subroutine called Pauli hashing, which allows one to tolerantly test $s$ -sparse Hamiltonians with $O(s^{14}/(ε_2^2-ε_1^2)^{18})$ queries. A key ingredient is showing that $s$ -sparse Pauli channels can be tolerantly tested under the diamond norm with $O(s^2/(ε_2-ε_1)^6)$ queries. Along the way, we prove new structural theorems for local and sparse Hamiltonians. We complement our learning results with polynomially weaker lower bounds. Furthermore, our algorithms use short time evolutions and do not assume prior knowledge of the terms in the support of the Pauli spectrum.We consider the problems of testing and learning an unknown $n$-qubit Hamiltonian $H$ from queries to its evolution operator $e^{-iHt}$ under the normalized Frobenius norm. We prove: 1. Local Hamiltonians: We give a tolerant testing protocol to decide if $H$ is $ε_1$-close to $k$-local or $ε_2$-far from $k$-local, with $O(1/(ε_2-ε_1)^{4})$ queries, solving open questions posed in a recent work by Bluhm et al. For learning a $k$-local $H$ up to error $ε$, we give a protocol with query complexity $\exp(O(k^2+k\log(1/ε)))$ independent of $n$, by leveraging the non-commutative Bohnenblust-Hille inequality. 2. Sparse Hamiltonians: We give a protocol to test if $H$ is $ε_1$-close to being $s$-sparse (in the Pauli basis) or $ε_2$-far from being $s$-sparse, with $O(s^{6}/(ε_2^2-ε_1^2)^{6})$ queries. For learning up to error $ε$, we show that $O(s^{4}/ε^{8})$ queries suffice. 3. Learning without memory: The learning results stated above have no dependence on $n$, but require $n$-qubit quantum memory. We give subroutines that allow us to learn without memory; increasing the query complexity by a $(\log n)$-factor in the local case and an $n$-factor in the sparse case. 4. Testing without memory: We give a new subroutine called Pauli hashing, which allows one to tolerantly test $s$-sparse Hamiltonians with $O(s^{14}/(ε_2^2-ε_1^2)^{18})$ queries. A key ingredient is showing that $s$-sparse Pauli channels can be tolerantly tested under the diamond norm with $O(s^2/(ε_2-ε_1)^6)$ queries. Along the way, we prove new structural theorems for local and sparse Hamiltonians. We complement our learning results with polynomially weaker lower bounds. Furthermore, our algorithms use short time evolutions and do not assume prior knowledge of the terms in the support of the Pauli spectrum.

arXiv:2411.00082Oct 31, 20240 citations

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.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.03205Oct 5, 20260 citations

Testing and Learning Structured Quantum Hamiltonians

Srinivasan Arunachalam, Arkopal Dutt, Francisco Escudero Gutiérrez

We consider the problems of testing and learning an unknown n -qubit quantum Hamiltonian H =∑ x λ x σ x expressed in its Pauli basis, from queries to its evolution operator e − iHt under the normalized Frobenius norm. To this end, we prove the following results (with and without quantum memory) for Hamiltonians whose Pauli spectrum involves only k -local terms or has sparsity at most s : (1) Local Hamiltonians : We give a tolerant testing protocol to decide if a Hamiltonian is ε 1 -close to k -local or ε 2 -far from k -local, with O (1/(ε 2 −ε 1 ) 4 ) queries, thereby solving two open questions posed in a recent work by Bluhm, Caro and Oufkir [BCO’24]. For learning a k -local Hamiltonian up to error ε, we give a protocol with query complexity and total time evolution exp( O ( k 2 + k log(1/ε))). Our algorithm leverages the non-commutative Bohnenblust-Hille inequality in order to get a complexity independent of n . (2) Sparse Hamiltonians : We give a protocol for testing whether a Hamiltonian is ε 1 -close to being s -sparse or ε 2 -far from being s -sparse, with O ( s 6 /(ε 2 2 −ε 1 2 ) 6 ) queries. For learning up to error ε, we show that O ( s 4 /ε 8 ) queries suffices. (3) 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; increasing the query complexity by a (log n )-factor in the local case and an n -factor in the sparse case. (4) Testing without quantum memory : We give a new subroutine called Pauli hashing , which allows one to tolerantly test s -sparse Hamiltonians using Õ( s 14 /(ε 2 2 −ε 1 2 ) 18 ) query complexity. A key ingredient is showing that s -sparse Pauli channels can be tested in a tolerant fashion as being ε 1 -close to being s -sparse or ε 2 -far under the diamond norm, using Õ( s 2 /(ε 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 about the support of the Hamiltonian terms.We consider the problems of testing and learning an unknown n -qubit quantum Hamiltonian H =∑ x λ x σ x expressed in its Pauli basis, from queries to its evolution operator e − iHt under the normalized Frobenius norm. To this end, we prove the following results (with and without quantum memory) for Hamiltonians whose Pauli spectrum involves only k -local terms or has sparsity at most s : (1) Local Hamiltonians : We give a tolerant testing protocol to decide if a Hamiltonian is ε 1 -close to k -local or ε 2 -far from k -local, with O (1/(ε 2 −ε 1 ) 4 ) queries, thereby solving two open questions posed in a recent work by Bluhm, Caro and Oufkir [BCO’24]. For learning a k -local Hamiltonian up to error ε, we give a protocol with query complexity and total time evolution exp( O ( k 2 + k log(1/ε))). Our algorithm leverages the non-commutative Bohnenblust-Hille inequality in order to get a complexity independent of n . (2) Sparse Hamiltonians : We give a protocol for testing whether a Hamiltonian is ε 1 -close to being s -sparse or ε 2 -far from being s -sparse, with O ( s 6 /(ε 2 2 −ε 1 2 ) 6 ) queries. For learning up to error ε, we show that O ( s 4 /ε 8 ) queries suffices. (3) 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; increasing the query complexity by a (log n )-factor in the local case and an n -factor in the sparse case. (4) Testing without quantum memory : We give a new subroutine called Pauli hashing , which allows one to tolerantly test s -sparse Hamiltonians using Õ( s 14 /(ε 2 2 −ε 1 2 ) 18 ) query complexity. A key ingredient is showing that s -sparse Pauli channels can be tested in a tolerant fashion as being ε 1 -close to being s -sparse or ε 2 -far under the diamond norm, using Õ( s 2 /(ε 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 about the support of the Hamiltonian terms.

ACM Symposium on Theory of Computing (STOC)Jun 15, 20253 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.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.09778Dec 11, 20250 citations

We consider the problems of testing and learning an

n

-qubit

k

-local Hamiltonian from queries to its evolution operator with respect the 2-norm of the Pauli spectrum, or equivalently, the normalized Frobenius norm. For testing whether a Hamiltonian is

ε_1

-close to

k

-local or

ε_2

-far from

k

-local, we show that

O(1/(ε_2-ε_1)^{8})

queries suffice. This solves two questions posed in a recent work by Bluhm, Caro and Oufkir. For learning up to error

ε

, we show that

\exp(O(k^2+k\log(1/ε)))

queries suffice. Our proofs are simple, concise and based on Pauli-analytic techniques.

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.

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).

We consider the problems of testing and learning an unknown

n

-qubit Hamiltonian

H

from queries to its evolution operator

e^{-iHt}

under the normalized Frobenius norm. We prove: 1. Local Hamiltonians: We give a tolerant testing protocol to decide if

H

ε_1

-close to

k

-local or

ε_2

-far from

k

-local, with

O(1/(ε_2-ε_1)^{4})

queries, solving open questions posed in a recent work by Bluhm et al. For learning a

k

-local

H

up to error

ε

, we give a protocol with query complexity

\exp(O(k^2+k\log(1/ε)))

independent of

n

, by leveraging the non-commutative Bohnenblust-Hille inequality. 2. Sparse Hamiltonians: We give a protocol to test if

H

ε_1

-close to being

s

-sparse (in the Pauli basis) or

ε_2

-far from being

s

-sparse, with

O(s^{6}/(ε_2^2-ε_1^2)^{6})

queries. For learning up to error

ε

, we show that

O(s^{4}/ε^{8})

queries suffice. 3. Learning without memory: The learning results stated above have no dependence on

n

, but require

n

-qubit quantum memory. We give subroutines that allow us to learn without memory; increasing the query complexity by a

(\log n)

-factor in the local case and an

n

-factor in the sparse case. 4. Testing without memory: We give a new subroutine called Pauli hashing, which allows one to tolerantly test

s

-sparse Hamiltonians with

O(s^{14}/(ε_2^2-ε_1^2)^{18})

queries. A key ingredient is showing that

s

-sparse Pauli channels can be tolerantly tested under the diamond norm with

O(s^2/(ε_2-ε_1)^6)

queries. Along the way, we prove new structural theorems for local and sparse Hamiltonians. We complement our learning results with polynomially weaker lower bounds. Furthermore, our algorithms use short time evolutions and do not assume prior knowledge of the terms in the support of the Pauli spectrum.

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.

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.