Certifying and learning local quantum Hamiltonians
Andreas Bluhm, Matthias C. Caro, Francisco Escudero Gutiérrez, Junseo Lee, Aadil Oufkir, Cambyse Rouzé, Myeongjin Shin
Abstract
In this work, we study the problems of certifying and learning quantum -local Hamiltonians, for a constant . 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 evolution time. This is optimal, as it matches the Heisenberg-scaling lower bound of . 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).
AI Impact Assessments
(3 models)Scientific Impact Assessment
Core Contribution
This paper addresses three interrelated problems concerning k-local quantum Hamiltonians (constant k): (1) optimal certification of Hamiltonians via time-evolution access, (2) sample-efficient learning of Gibbs states, and (3) sample- and time-efficient certification of Gibbs states.
The headline result is an O(1/ε) total evolution time algorithm for certifying whether an unknown k-local Hamiltonian H equals a known target H₀ or is ε-far in normalized Frobenius norm. This achieves the Heisenberg scaling limit, matching the Ω(1/ε) lower bound, making it the first provably optimal algorithm for any Hamiltonian property testing task. The key technical innovation is applying the Bonami Hypercontractivity Lemma to show that the eigenvalue spectrum of local Hamiltonians is sufficiently spread, enabling discrimination via Bell sampling at longer evolution times than prior approaches could handle.
For Gibbs states, the paper circumvents a known exponential-in-β lower bound on Hamiltonian learning by directly targeting the state learning problem, achieving Õ(poly(n)β²/ε⁴) sample complexity. The certification algorithm for Gibbs states resolves an open question posed by Anshu (2022).
Methodological Rigor
The technical approach is clean and well-executed. The proof architecture for Hamiltonian certification is elegant:
1. Bell sampling on the time evolution of ΔH = H - H₀ yields a probability I(t) depending on eigenvalue differences.
2. The Bonami Lemma bounds the 4-norm of k-local operators by their 2-norm (∥ΔH∥₄⁴ ≤ 9^k ∥ΔH∥₂⁴), ensuring spectral spread.
3. The Paley-Zygmund inequality then lower bounds the proportion of ε-separated eigenvalue pairs Λ(ΔH, ε) ≥ 1/(3·9^k).
4. A random time selection in [0, 2/ε] ensures I(t) is bounded away from 1 with constant probability.
The lower bound I(t) ≥ 1 - t²∥ΔH∥²_F (Lemma 12) completes the two-sided analysis needed for tolerant certification. The Trotterization step (Theorem 5) is handled carefully, and the algorithm requires no quantum memory or ancilla qubits, enhancing practical relevance.
For Gibbs state results, the covering net argument via Pinsker's inequality and classical shadows is standard but applied effectively. The key insight—Eq. (3)—that trace distance between Gibbs states is controlled by Pauli coefficient differences scaled by βn^k, combined with the Yatracos-type minimum distance estimator, yields the sample-efficient learning algorithm.
One concern: the Gibbs state learning algorithm (Result 2) is not time-efficient, with the covering net having size (n^k β/ε)^{O(n^k)}, which is exponential in n for any fixed k ≥ 1. The authors acknowledge this limitation transparently and pose time-efficient Gibbs state learning as an open problem.
Potential Impact
Quantum device verification. The optimal Hamiltonian certification protocol has direct implications for verifying quantum hardware. As quantum devices scale to thousands of qubits, efficient certification becomes critical. The O(1/ε) evolution time, independence from operator norm bounds, robustness to SPAM errors, and memoryless operation make this protocol practically deployable.
Bridging Fourier analysis and quantum information. The use of hypercontractivity (Bonami Lemma) for quantum Hamiltonian problems is novel and potentially influential. This connection could inspire further applications of Boolean/quantum Fourier analysis tools to quantum learning and testing problems.
Gibbs state learning paradigm. By decoupling Gibbs state learning from Hamiltonian learning, the paper opens a new algorithmic direction. The exponential-in-β barrier for Hamiltonian learning from Gibbs states was widely considered fundamental; showing it can be circumvented for state learning (though not for Hamiltonian recovery) is conceptually important.
Resolving open problems. Answering Anshu's question about efficient Gibbs state certification and providing the first optimal Hamiltonian property testing result positions this work as a benchmark in the field.
Timeliness & Relevance
The paper is highly timely. Hamiltonian learning and testing have seen explosive growth (the reference list itself documents this). The gap between learning and testing complexity has been recognized but underexplored, and this paper provides sharp separations. The concurrent work by Sinha-Tong [ST25] on Bell sampling bounds provides context: their O(1/ε²) result for general Hamiltonians is quadratically worse than the O(1/ε) achieved here under the locality promise, cleanly delineating the power of structural assumptions.
Strengths
Limitations
Overall Assessment
This is a strong theoretical contribution that achieves optimal complexity for a fundamental quantum certification task, introduces a novel analytical technique (hypercontractivity for Hamiltonian testing), and resolves an open question about Gibbs state certification. The results are clean, the proofs are rigorous, and the practical considerations are well-addressed. The main limitations—exponential constants in k, computational inefficiency for Gibbs learning—are acknowledged and leave clear directions for future work.
Generated Apr 1, 2026
Comparison History (71)
Paper 2 likely has higher impact: it delivers optimal (Heisenberg-scaling) certification of local Hamiltonians with a novel analytical ingredient (hypercontractivity), plus sample- and time-efficient algorithms for learning and certifying Gibbs states, addressing a posed open question. These results are broadly applicable across quantum information, Hamiltonian learning, verification, and near-term quantum characterization, with strong methodological rigor and generality. Paper 1 is an impressive large-scale experimental quantum simulation, but its impact is narrower (specific model/hardware) and more contingent on near-term device capabilities and error models.
Paper 2 demonstrates a landmark experimental achievement in quantum simulation at scale (120 qubits, 90 Trotter steps) on actual hardware, directly observing spin-charge separation in the Fermi-Hubbard model and achieving quantitative agreement with classical methods while being 3000x faster in certain regimes. This represents a concrete step toward quantum advantage in scientifically relevant problems, with immediate implications for condensed matter physics and quantum computing. While Paper 1 makes important theoretical contributions to Hamiltonian certification and learning with optimal scaling, Paper 2's experimental demonstration of competitive quantum simulation of a canonical many-body model has broader immediate impact across quantum computing, condensed matter, and materials science communities.
Paper 1 presents fundamental theoretical breakthroughs in quantum learning theory, including the first optimal algorithm for testing a Hamiltonian property with Heisenberg-limited scaling. By also solving an open question regarding the sample-efficient certification of Gibbs states, it provides rigorous bounds that will broadly influence future theoretical and algorithmic research in quantum information. While Paper 2 offers a valuable practical tool for characterizing current hardware, Paper 1's foundational advances in complexity and learning limits possess a deeper, more enduring scientific impact.
Paper 2 presents a practical, data-driven framework validated on real superconducting quantum processors, addressing the immediate and critical need for accurate noise and dynamics modeling in NISQ devices. Its direct applicability to experimental calibration and model selection gives it a broader and more immediate real-world impact compared to the theoretical advancements in sample complexity and algorithmic bounds presented in Paper 1.
Paper 2 presents optimal algorithms for fundamental problems in quantum information science—certifying and learning local Hamiltonians and Gibbs states—achieving Heisenberg-scaling optimality and resolving open questions. Its theoretical contributions have broad impact across quantum computing, complexity theory, and quantum learning theory. Paper 1 demonstrates a notable experimental milestone (2% optical squeezing via levitated oscillators at quantum ground state), but the squeezing level is modest and the result, while technically impressive, represents an incremental advance in optomechanics rather than a paradigm shift. Paper 2's foundational algorithmic results will likely influence multiple research directions more broadly.
Paper 1 has higher potential impact due to substantial theoretical novelty (first optimal Hamiltonian property testing matching Heisenberg lower bounds, plus new hypercontractivity-based analysis) and broad applicability to quantum characterization, verification, and learning—core bottlenecks for quantum simulation/quantum computing. Its Gibbs-state learning/certification results address known open questions and improve parameter scaling (avoiding exponential dependence on inverse temperature), making the methods widely relevant across quantum information, many-body physics, and algorithms. Paper 2 is a strong experimental advance, but the demonstrated squeezing is modest (2% below vacuum) and likely narrower in cross-field impact.
Paper 2 addresses fundamental theoretical problems in quantum information with provably optimal algorithms and resolves an open question. Its contributions—optimal Hamiltonian certification achieving the Heisenberg limit, sample-efficient Gibbs state learning avoiding exponential scaling, and efficient Gibbs state certification—have broad impact across quantum computing theory, quantum learning theory, and statistical mechanics. The novel use of Bonami Hypercontractivity connects disparate mathematical fields. Paper 1, while practically valuable for fluxonium processor design, is more narrowly focused on a specific engineering methodology for one qubit platform.
Paper 1 provides fundamental theoretical breakthroughs in quantum learning theory, achieving optimal Heisenberg-scaling bounds for Hamiltonian certification and solving an open question regarding Gibbs states. These rigorous foundational results will broadly impact quantum algorithms and many-body physics. While Paper 2 offers a valuable first-of-its-kind hardware implementation for computational electromagnetics, Paper 1's theoretical innovations and optimal complexity bounds represent a more foundational scientific advancement with broader implications across quantum information science.
Paper 2 addresses multiple fundamental problems (certification and learning of Hamiltonians and Gibbs states) with optimal or near-optimal algorithms, achieving Heisenberg-scaling bounds and resolving an open question. It combines techniques from Fourier analysis with quantum information in novel ways, has broader applicability across quantum computing, quantum simulation, and quantum thermodynamics, and provides practically important results for Gibbs state learning that overcome exponential scaling barriers. Paper 1, while providing valuable complementary results on stabilizer learning, addresses a narrower problem with more incremental contributions.
Paper 1 offers higher potential impact due to strong novelty and breadth: it gives (apparently first) optimal-time certification for local Hamiltonian properties matching a fundamental lower bound, introduces new analytical tools (hypercontractivity) to quantum property testing, and provides sample-efficient learning/certification of Gibbs states, addressing an explicit open question. These results are broadly relevant to quantum information, Hamiltonian learning, verification, and near-term quantum simulation/benchmarking. Paper 2 is timely and experimentally relevant for bosonic squeezing, but its scope is narrower and primarily yields bounds/criteria rather than broadly enabling new algorithmic capabilities.