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:2509.10239

Certifying and learning quantum Ising Hamiltonians

Andreas Blühm, Caro, Matthias C., Francisco Escudero Gutiérrez, Aadil Oufkir, Cambyse Rouzé

Published Sep 12, 2025• 9 citations
arXivHTMLPDF

Abstract

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

DOI
10.48550/arxiv.2509.10239

Related papers

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

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

Optimal learning of quantum Hamiltonians from high-temperature Gibbs states

Jeongwan Haah, Robin Kothari, Ewin Tang

We study the problem of learning a Hamiltonian H to precision $\varepsilon$, supposing we are given copies of its Gibbs state $\rho =\exp(-\beta H)/\mathrm{Tr}(\exp(-\beta H))$ at a known inverse temperature $\beta$. Anshu, Arunachalam, Kuwahara, and Soleimanifar [AAKS21] recently studied the sample complexity (number of copies of $\rho$ needed) of this problem for geometrically local N-qubit Hamiltonians. In the high-temperature (low $\beta$) regime, their algorithm has sample complexity poly (N, 1/$\beta$, 1/$\varepsilon$) and can be implemented with polynomial, but suboptimal, time complexity. In this paper, we study the same question for a more general class of Hamiltonians. We show how to learn the coefficients of a Hamiltonian to error $\varepsilon$ with sample complexity $S=O(\log N/(\beta\varepsilon)^{2}$) and time complexity linear in the sample size, O(SN). Furthermore, we prove a matching lower bound showing that our algorithm’s sample complexity is optimal, and hence our time complexity is also optimal. In the appendix, we show that virtually the same algorithm can be used to learn H from a real-time evolution unitary $e^{-i t H}$ in a small t regime with similar sample and time complexity.

Annual Symposium on Foundations of Computer Science•Oct 1, 2022•49 citations

Learning Quantum Hamiltonians at Any Temperature in Polynomial Time

Ainesh Bakshi, Allen Liu, Ankur Moitra +1 more

Abstract. We study the problem of learning a local quantum Hamiltonian [Formula: see text] given copies of its Gibbs state [Formula: see text] at a known inverse temperature [Formula: see text]. Anshu et al. [2020 IEEE 61st Annual Symposium on Foundations of Computer Science, pp. 685–691] gave an algorithm to learn a Hamiltonian on [Formula: see text] qubits to precision [Formula: see text] with only polynomially many copies of the Gibbs state, but which takes exponential time. Obtaining a computationally efficient algorithm has been a major open problem [ Alhambra, PRX Quantum, 4 (2023), 040201 ; Anshu and Arunachalam, Nature Rev. Phys., 6 (2023), pp. 59–69 ], with prior work only resolving this in the limited cases of high temperature [ Haah, Kothari, and Tang, Markov field on finite graphs and lattices, 1971 ] or commuting terms [ Anshu et al., Efficient learning of commuting Hamiltonians on lattices, 2021 ]. We fully resolve this problem, giving a polynomial time algorithm for learning [Formula: see text] to precision [Formula: see text] from polynomially many copies of the Gibbs state at any constant [Formula: see text]. Our main technical contribution is a new flat polynomial approximation to the exponential function, and a translation between multivariate scalar polynomials and nested commutators. This enables us to formulate Hamiltonian learning as a polynomial system. We then show that solving a low-degree sum-of-squares relaxation of this polynomial system suffices to accurately learn the Hamiltonian.

arXiv:2310.02243•SIAM Journal on Computing•Oct 6, 2026•33 citations

Hamiltonian Learning and Certification via Eigenphase Engineering

Myeongjin Shin, Yu Tong

We study Hamiltonian learning for $k$-local Hamiltonians at large step size, using only forward time evolution at integer multiples of a fixed time interval. For this task, our new technique, which we call eigenphase engineering, achieves Heisenberg-limited learning with a step size that is optimal up to logarithmic factors. For an unknown $s$-sparse Hamiltonian with fixed locality $k$ and $\|H\|_{\mathrm{op}}\leqΛ$, our algorithm recovers its Pauli coefficients to $\ell_2$ error $\varepsilon$ in total evolution time $\widetilde{O}(s/\varepsilon)$, matching the best known scaling while allowing a near-maximal step size $\widetildeΘ(1/Λ)$. As an independent contribution, we strengthen the evolution-time lower bound to $Ω_k(s^{1-1/(2k)}/\varepsilon)$, placing our algorithm within a factor $\widetilde{O}(s^{1/(2k)})$ of being optimal. Eigenphase engineering departs from approaches based on dynamical approximation or iteratively canceling the unknown Hamiltonian. It encodes energy expectation differences in the perturbative response of eigenphases of the actual controlled evolution, then extracts them through phase estimation and high-order extrapolation. This avoids the need for polynomially shorter evolution steps as the target precision improves. A version using only single-qubit operations retains the same step size with a $\sqrt n$ overhead in $\ell_2$ learning time for $n$ qubits. The method also enables tolerant Hamiltonian certification and estimation of a specified Pauli coefficient, the latter without locality or sparsity assumptions. These results establish eigenphase engineering as a versatile approach to extracting Hamiltonian information with infrequent control.

quant-pharXiv:2609.26596•Sep 23, 2026•3 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
In this work, we study the problems of certifying and learning quantum Ising Hamiltonians. Our main contributions are as follows: Certification of Ising Hamiltonians. We show that certifying an Ising Hamiltonian in normalized Frobenius norm via access to its time-evolution operator requires only O~(1/ε)\widetilde O(1/\varepsilon)O(1/ε) time evolution. This matches the Heisenberg-scaling lower bound of Ω(1/ε)Ω(1/\varepsilon)Ω(1/ε) up to logarithmic factors. To our knowledge, this is the first nearly-optimal algorithm for testing a Hamiltonian property. A key ingredient in our analysis is the Bonami Lemma from Fourier analysis. Learning Ising Gibbs states. We design an algorithm for learning Ising Gibbs states in trace norm that is sample-efficient in all parameters. In contrast, previous approaches learned the underlying Hamiltonian (which implies learning the Gibbs state) but suffered from exponential sample complexity in the inverse temperature. Certification of Ising Gibbs states. We give an algorithm for certifying Ising Gibbs states in trace norm that is both sample and time-efficient, thereby solving a question posed by Anshu (Harvard Data Science Review, 2022). Finally, we extend our results on learning and certification of Gibbs states to general kkk-local Hamiltonians for any constant kkk.
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).
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.
We study the problem of learning a Hamiltonian H to precision ε\varepsilonε, supposing we are given copies of its Gibbs state ρ=exp⁡(−βH)/Tr(exp⁡(−βH))\rho =\exp(-\beta H)/\mathrm{Tr}(\exp(-\beta H))ρ=exp(−βH)/Tr(exp(−βH)) at a known inverse temperature β\betaβ. Anshu, Arunachalam, Kuwahara, and Soleimanifar [AAKS21] recently studied the sample complexity (number of copies of ρ\rhoρ needed) of this problem for geometrically local N-qubit Hamiltonians. In the high-temperature (low β\betaβ) regime, their algorithm has sample complexity poly (N, 1/β\betaβ, 1/ε\varepsilonε) and can be implemented with polynomial, but suboptimal, time complexity. In this paper, we study the same question for a more general class of Hamiltonians. We show how to learn the coefficients of a Hamiltonian to error ε\varepsilonε with sample complexity S=O(log⁡N/(βε)2S=O(\log N/(\beta\varepsilon)^{2}S=O(logN/(βε)2) and time complexity linear in the sample size, O(SN). Furthermore, we prove a matching lower bound showing that our algorithm’s sample complexity is optimal, and hence our time complexity is also optimal. In the appendix, we show that virtually the same algorithm can be used to learn H from a real-time evolution unitary e−itHe^{-i t H}e−itH in a small t regime with similar sample and time complexity.
Abstract. We study the problem of learning a local quantum Hamiltonian [Formula: see text] given copies of its Gibbs state [Formula: see text] at a known inverse temperature [Formula: see text]. Anshu et al. [2020 IEEE 61st Annual Symposium on Foundations of Computer Science, pp. 685–691] gave an algorithm to learn a Hamiltonian on [Formula: see text] qubits to precision [Formula: see text] with only polynomially many copies of the Gibbs state, but which takes exponential time. Obtaining a computationally efficient algorithm has been a major open problem [ Alhambra, PRX Quantum, 4 (2023), 040201 ; Anshu and Arunachalam, Nature Rev. Phys., 6 (2023), pp. 59–69 ], with prior work only resolving this in the limited cases of high temperature [ Haah, Kothari, and Tang, Markov field on finite graphs and lattices, 1971 ] or commuting terms [ Anshu et al., Efficient learning of commuting Hamiltonians on lattices, 2021 ]. We fully resolve this problem, giving a polynomial time algorithm for learning [Formula: see text] to precision [Formula: see text] from polynomially many copies of the Gibbs state at any constant [Formula: see text]. Our main technical contribution is a new flat polynomial approximation to the exponential function, and a translation between multivariate scalar polynomials and nested commutators. This enables us to formulate Hamiltonian learning as a polynomial system. We then show that solving a low-degree sum-of-squares relaxation of this polynomial system suffices to accurately learn the Hamiltonian.
We study Hamiltonian learning for kkk-local Hamiltonians at large step size, using only forward time evolution at integer multiples of a fixed time interval. For this task, our new technique, which we call eigenphase engineering, achieves Heisenberg-limited learning with a step size that is optimal up to logarithmic factors. For an unknown sss-sparse Hamiltonian with fixed locality kkk and ∥H∥op≤Λ\|H\|_{\mathrm{op}}\leqΛ∥H∥op​≤Λ, our algorithm recovers its Pauli coefficients to ℓ2\ell_2ℓ2​ error ε\varepsilonε in total evolution time O~(s/ε)\widetilde{O}(s/\varepsilon)O(s/ε), matching the best known scaling while allowing a near-maximal step size Θ~(1/Λ)\widetildeΘ(1/Λ)Θ(1/Λ). As an independent contribution, we strengthen the evolution-time lower bound to Ωk(s1−1/(2k)/ε)Ω_k(s^{1-1/(2k)}/\varepsilon)Ωk​(s1−1/(2k)/ε), placing our algorithm within a factor O~(s1/(2k))\widetilde{O}(s^{1/(2k)})O(s1/(2k)) of being optimal. Eigenphase engineering departs from approaches based on dynamical approximation or iteratively canceling the unknown Hamiltonian. It encodes energy expectation differences in the perturbative response of eigenphases of the actual controlled evolution, then extracts them through phase estimation and high-order extrapolation. This avoids the need for polynomially shorter evolution steps as the target precision improves. A version using only single-qubit operations retains the same step size with a n\sqrt nn​ overhead in ℓ2\ell_2ℓ2​ learning time for nnn qubits. The method also enables tolerant Hamiltonian certification and estimation of a specified Pauli coefficient, the latter without locality or sparsity assumptions. These results establish eigenphase engineering as a versatile approach to extracting Hamiltonian information with infrequent control.
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.