pith. sign in

arxiv: 2509.20665 · v4 · submitted 2025-09-25 · 🪐 quant-ph

Lower Bounds for Learning Hamiltonians from Time Evolution

Ziyun Chen , Jerry Li , Joseph Slote This is my paper

Pith reviewed 2026-05-18 14:55 UTC · model grok-4.3

classification 🪐 quant-ph
keywords Hamiltonian learninglower boundstime evolutionk-local Hamiltoniansquantum informationBoolean functionseffective Hamiltonian
0
0 comments X

The pith

Learning even one coefficient of a k-local Hamiltonian requires n to the Omega of k evolution time.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper proves that algorithms for learning k-local Hamiltonians from time evolution need at least n to the power of Omega of k total evolution time or interactions in the worst case. This lower bound remains unchanged even when the task is reduced to estimating a single designated coefficient while assuming the rest of the Hamiltonian is already known. The same hardness applies to the related problem of learning an approximate effective Hamiltonian that reproduces the time evolution. The results hold in the standard model where the only access to the system is through the unitary e to the minus i H t. The proof proceeds by linking the learning task to an extremal property of Boolean functions.

Core claim

We show that k-local Hamiltonians on n qubits require n to the Omega of k total evolution time to learn their parameters from e to the minus i H t, and that this bound persists even for estimating a single coefficient when the remaining terms are known. We extend this to effective Hamiltonian learning and sparse Hamiltonians, using a reduction to extremal properties of Boolean functions.

What carries the argument

A novel extremal property of Boolean functions that lower-bounds the complexity of distinguishing Hamiltonian evolutions.

If this is right

  • Any algorithm for full parameter estimation of k-local Hamiltonians requires Omega of n to the k evolution time in the worst case.
  • The hardness of learning one coefficient matches the hardness of learning all coefficients.
  • The n to the Omega of k lower bound also applies when the goal is only to produce a unitary that approximately matches the time evolution of H.
  • Related lower bounds hold for general sparse but non-local Hamiltonians.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The result suggests that locality imposes a fundamental sample-complexity barrier that cannot be bypassed by focusing on partial information.
  • It may be worth checking whether the same extremal Boolean-function property yields lower bounds for other quantum system-identification tasks such as learning Lindblad operators.
  • Relaxing the model to allow additional measurements or oracles might change the picture, but the current proof technique does not address those relaxations.

Load-bearing premise

The only access to the Hamiltonian is through its time-evolution operator.

What would settle it

An algorithm that learns a single coefficient of a k-local Hamiltonian using o of n to the k total evolution time would contradict the bound.

read the original abstract

Learning about a Hamiltonian $H$ from its time evolution $e^{-iHt}$ is a fundamental task in quantum science. A flurry of recent work has developed powerful new algorithms with provable guarantees for this task, for a variety of natural settings. Despite this, relatively little is known about lower bounds for learning Hamiltonians. In particular, in the natural setting where we assume $H$ is a $k$-local Hamiltonian on $n$ qubits, all existing algorithms require total evolution time at least $n^{\Omega (k)}$ to learn the parameters of $H$, and it remained open whether one could obtain even faster algorithms -- or at the very least, if one could obtain better runtimes for simpler tasks, such as estimating a single designated coefficient of the Hamiltonian. In this work we show the answer is essentially no, by obtaining strong lower bounds for these problems. We find that not only do $k$-local Hamiltonians require $n^{\Omega(k)}$ time evolution or interactions to learn, but also that in several senses, learning anything about a Hamiltonian is just as hard as learning everything. In particular, we find the same $n^{\Omega(k)}$ lower bound holds for learning a single coefficient of a $k$-local Hamiltonian $H$, even if the rest of $H$ is already known. We also show an $n^{\Omega(k)}$ lower bound for the task of effective Hamiltonian learning, where one seeks only to learn a unitary that approximately implements time evolution of $H$. Several related lower bounds, such as for general sparse (but not necessarily local) $H$ are also given. On the technical side, we make a new connection between Hamiltonian learning lower bounds and the analysis of Boolean functions, where we introduce a novel extremal property that may be of independent interest.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 2 minor

Summary. The manuscript claims that learning the parameters of a k-local Hamiltonian on n qubits from its time-evolution operator requires total evolution time n^Ω(k), and that this lower bound continues to hold for the simpler task of learning a single designated coefficient even when all other coefficients are already known. It further establishes an n^Ω(k) lower bound for effective Hamiltonian learning (recovering only an approximating unitary) and for learning general sparse Hamiltonians. The proofs proceed via a reduction from these tasks to a novel extremal property of Boolean functions.

Significance. If the central claims hold, the results are significant because they close the gap with existing upper bounds, establishing near-optimality of current algorithms for k-local Hamiltonian learning. The demonstration that partial learning is information-theoretically as hard as full learning is a strong conceptual contribution. The new extremal property of Boolean functions is explicitly flagged as potentially of independent interest and is a clear strength of the work.

major comments (1)
  1. [Proof of single-coefficient lower bound / extremal property reduction] The load-bearing step for the single-coefficient lower bound (abstract and the corresponding theorem) is the claim that the extremal property and reduction continue to apply when a nontrivial background Hamiltonian is known. The manuscript must explicitly verify that the reduction does not rely on the background being identically zero and that no compensating evolutions are possible that would invalidate the n^Ω(k) bound; otherwise the reduction does not automatically carry over to the stated setting.
minor comments (2)
  1. [Introduction / problem statement] Notation for total evolution time versus number of interactions should be clarified in the problem formulation section to avoid ambiguity between continuous-time and discrete-query models.
  2. [Theorem statements] The abstract states the results for both time-evolution access and equivalent interactions; the precise model used in each theorem should be stated explicitly in the theorem statements.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for their careful reading, positive assessment of the significance of our results, and constructive feedback. We address the single major comment below and will incorporate the requested clarification to strengthen the presentation of the single-coefficient lower bound.

read point-by-point responses

  1. Referee: [Proof of single-coefficient lower bound / extremal property reduction] The load-bearing step for the single-coefficient lower bound (abstract and the corresponding theorem) is the claim that the extremal property and reduction continue to apply when a nontrivial background Hamiltonian is known. The manuscript must explicitly verify that the reduction does not rely on the background being identically zero and that no compensating evolutions are possible that would invalidate the n^Ω(k) bound; otherwise the reduction does not automatically carry over to the stated setting.

    Authors: We agree that the reduction from the extremal Boolean function property to the single-coefficient learning task requires explicit verification when a known nontrivial background Hamiltonian H_0 is present, rather than assuming it is zero. In the revised manuscript we will add a new subsection (in the proof of the relevant theorem) that directly addresses this. We will show that the distinguishing problem remains hard because the contribution of the unknown coefficient cannot be canceled or compensated by the known evolution generated by H_0; any such compensation would require additional evolution time that still scales as n^Ω(k) in the worst case. The argument proceeds by reducing to the same extremal function property after conjugating by the known unitary evolution of H_0, which preserves the relevant Fourier-analytic quantities and does not weaken the lower bound. This explicit check confirms that the n^Ω(k) bound carries over unchanged to the partial-learning setting. revision: yes

Circularity Check

0 steps flagged

No circularity: lower bounds via independent reduction to new extremal Boolean property

full rationale

The derivation chain relies on a reduction from Hamiltonian learning (including the single-coefficient case with known background) to a novel extremal property of Boolean functions that the paper introduces and analyzes on its own terms. This property is not defined in terms of the target learning task, nor is any parameter fitted to the output quantity and then relabeled as a prediction. The abstract and technical overview explicitly frame the connection as new and potentially of independent interest, with no load-bearing self-citation to prior author work that would close the loop. The lower bounds are therefore self-contained against external benchmarks and do not reduce to their inputs by construction.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The central claims rest on the standard quantum-mechanical model of Hamiltonian evolution and on the new extremal property introduced for Boolean functions; no free parameters or invented physical entities are described.

axioms (2)
  • domain assumption Access to the system is provided solely through the unitary time-evolution operator e^{-i H t} for chosen times t.
    This is the natural setting assumed throughout the abstract for both prior algorithms and the new lower bounds.
  • domain assumption H is exactly k-local on n qubits.
    The lower bounds are stated for this class of Hamiltonians.

pith-pipeline@v0.9.0 · 5861 in / 1425 out tokens · 50720 ms · 2026-05-18T14:55:26.459137+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

55 extracted references · 55 canonical work pages

  1. [1]

    Anshu, S

    A. Anshu, S. Arunachalam, T. Kuwahara, and M. Soleimanifar. Efficient learning of commuting hamiltonians on lattices.Electronic notes, 25, 2021

    work page 2021

  2. [2]

    Anshu, S

    A. Anshu, S. Arunachalam, T. Kuwahara, and M. Soleimanifar. Sample-efficient learning of interacting quantum systems.Nature Physics, 17(8):931–935, 2021

    work page 2021

  3. [3]

    Arunachalam, A

    S. Arunachalam, A. Dutt, and F. Escudero Guti´ errez. Testing and learning structured quantum hamiltonians. InProceedings of the 57th Annual ACM Symposium on Theory of Computing, pages 1263–1270, 2025

    work page 2025

  4. [4]

    Bairey, I

    E. Bairey, I. Arad, and N. H. Lindner. Learning a local hamiltonian from local measurements. Physical review letters, 122(2):020504, 2019

    work page 2019

  5. [5]

    Bakshi, A

    A. Bakshi, A. Liu, A. Moitra, and E. Tang. Learning quantum hamiltonians at any temper- ature in polynomial time. InProceedings of the 56th Annual ACM Symposium on Theory of Computing, pages 1470–1477, 2024

    work page 2024

  6. [6]

    Bakshi, A

    A. Bakshi, A. Liu, A. Moitra, and E. Tang. Structure learning of hamiltonians from real- time evolution. In2024 IEEE 65th Annual Symposium on Foundations of Computer Science (FOCS), pages 1037–1050. IEEE, 2024

    work page 2024

  7. [7]

    Bluhm, M

    A. Bluhm, M. C. Caro, and A. Oufkir. Hamiltonian property testing.arXiv preprint arXiv:2403.02968, 2024

    work page arXiv 2024

  8. [8]

    J. J. Bollinger, W. M. Itano, D. J. Wineland, and D. J. Heinzen. Optimal frequency measure- ments with maximally correlated states.Physical Review A, 54(6):R4649, 1996

    work page 1996

  9. [9]

    Boulant, T

    N. Boulant, T. F. Havel, M. A. Pravia, and D. G. Cory. Robust method for estimating the lindblad operators of a dissipative quantum process from measurements of the density operator at multiple time points.Physical Review A, 67(4):042322, 2003. 16

    work page 2003

  10. [10]

    M. C. Caro. Learning quantum processes and hamiltonians via the pauli transfer matrix.ACM Transactions on Quantum Computing, 5(2):1–53, 2024

    work page 2024

  11. [11]

    C. M. Caves. Quantum-mechanical noise in an interferometer.Physical Review D, 23(8):1693, 1981

    work page 1981

  12. [12]

    Chen and W

    S. Chen and W. Gong. Efficient pauli channel estimation with logarithmic quantum memory. PRX Quantum, 6(2):020323, 2025

    work page 2025

  13. [13]

    S. Chen, J. Cotler, H.-Y. Huang, J. Li, and E. Tang. Open questions session, recent advances in quantum learning (focs 2024 workshop). Workshop presentation, Oct. 2024. URLhttps: //jerryzli.github.io/focs24-workshop.html. FOCS 2024, Chicago. Includes list of open problems in quantum learning

    work page 2024

  14. [14]

    S. Chen, C. Oh, S. Zhou, H.-Y. Huang, and L. Jiang. Tight bounds on pauli channel learning without entanglement.Physical Review Letters, 132(18):180805, 2024

    work page 2024

  15. [15]

    M. P. da Silva, O. Landon-Cardinal, and D. Poulin. Practical characterization of quantum devices without tomography.Physical Review Letters, 107(21):210404, 2011

    work page 2011

  16. [16]

    De Burgh and S

    M. De Burgh and S. D. Bartlett. Quantum methods for clock synchronization: Beating the standard quantum limit without entanglement.Physical Review A—Atomic, Molecular, and Optical Physics, 72(4):042301, 2005

    work page 2005

  17. [17]

    Dutkiewicz, T

    A. Dutkiewicz, T. E. O’Brien, and T. Schuster. The advantage of quantum control in many- body hamiltonian learning.Quantum, 8:1537, 2024

    work page 2024

  18. [18]

    Fawzi, O

    H. Fawzi, O. Fawzi, and S. O. Scalet. Certified algorithms for equilibrium states of local quantum hamiltonians.Nature Communications, 15(1):7394, 2024

    work page 2024

  19. [19]

    Flynn, A

    B. Flynn, A. A. Gentile, N. Wiebe, R. Santagati, and A. Laing. Quantum model learning agent: characterisation of quantum systems through machine learning.New Journal of Physics, 24 (5):053034, 2022

    work page 2022

  20. [20]

    D. S. Fran¸ ca, T. M¨ obus, C. Rouz´ e, and A. H. Werner. Learning and certification of local time-dependent quantum dynamics and noise.arXiv preprint arXiv:2510.08500, 2025

    work page arXiv 2025

  21. [21]

    L. P. Garc´ ıa-Pintos, K. Bharti, J. Bringewatt, H. Dehghani, A. Ehrenberg, N. Yunger Halpern, and A. V. Gorshkov. Estimation of hamiltonian parameters from thermal states.Physical Review Letters, 133(4):040802, 2024

    work page 2024

  22. [22]

    A. A. Gentile, B. Flynn, S. Knauer, N. Wiebe, S. Paesani, C. E. Granade, J. G. Rarity, R. Santagati, and A. Laing. Learning models of quantum systems from experiments.Nature Physics, 17(7):837–843, 2021

    work page 2021

  23. [23]

    Giovannetti, S

    V. Giovannetti, S. Lloyd, and L. Maccone. Quantum-enhanced measurements: beating the standard quantum limit.Science, 306(5700):1330–1336, 2004

    work page 2004

  24. [24]

    J. Haah, R. Kothari, and E. Tang. Optimal learning of quantum hamiltonians from high- temperature gibbs states. In2022 IEEE 63rd Annual Symposium on Foundations of Computer Science (FOCS), pages 135–146. IEEE, 2022. 17

    work page 2022

  25. [25]

    J. Haah, R. Kothari, R. O’Donnell, and E. Tang. Query-optimal estimation of unitary channels in diamond distance. In2023 IEEE 64th Annual Symposium on Foundations of Computer Science (FOCS), pages 363–390. IEEE, 2023

    work page 2023

  26. [26]

    J. Haah, R. Kothari, and E. Tang. Learning quantum hamiltonians from high-temperature gibbs states and real-time evolutions.Nature Phys., 20(arXiv: 2108.04842):1027–1031, 2024

    work page arXiv 2024

  27. [27]

    M. J. Holland and K. Burnett. Interferometric detection of optical phase shifts at the heisenberg limit.Physical review letters, 71(9):1355, 1993

    work page 1993

  28. [28]

    H.-Y. Hu, M. Ma, W. Gong, Q. Ye, Y. Tong, S. T. Flammia, and S. F. Yelin. Ansatz-free hamiltonian learning with heisenberg-limited scaling.arXiv preprint arXiv:2502.11900, 2025

    work page arXiv 2025

  29. [29]

    Huang, Y

    H.-Y. Huang, Y. Tong, D. Fang, and Y. Su. Learning many-body hamiltonians with heisenberg- limited scaling.Physical Review Letters, 130(20):200403, 2023

    work page 2023

  30. [30]

    Innocenti, L

    L. Innocenti, L. Banchi, A. Ferraro, S. Bose, and M. Paternostro. Supervised learning of time-independent hamiltonians for gate design.New Journal of Physics, 22(6):065001, 2020

    work page 2020

  31. [31]

    H. Lee, P. Kok, and J. P. Dowling. A quantum rosetta stone for interferometry.Journal of Modern Optics, 49(14-15):2325–2338, 2002

    work page 2002

  32. [32]

    Leibfried, M

    D. Leibfried, M. D. Barrett, T. Schaetz, J. Britton, J. Chiaverini, W. M. Itano, J. D. Jost, C. Langer, and D. J. Wineland. Toward heisenberg-limited spectroscopy with multiparticle entangled states.Science, 304(5676):1476–1478, 2004

    work page 2004

  33. [33]

    H. Li, Y. Tong, T. Gefen, H. Ni, and L. Ying. Heisenberg-limited hamiltonian learning for interacting bosons.npj Quantum Information, 10(1):83, 2024

    work page 2024

  34. [34]

    M. Ma, S. T. Flammia, J. Preskill, and Y. Tong. Learningk-body hamiltonians via compressed sensing.arXiv preprint arXiv:2410.18928, 2024

    work page arXiv 2024

  35. [35]

    McKenzie, D

    K. McKenzie, D. A. Shaddock, D. E. McClelland, B. C. Buchler, and P. K. Lam. Exper- imental demonstration of a squeezing-enhanced power-recycled michelson interferometer for gravitational wave detection.Physical review letters, 88(23):231102, 2002

    work page 2002

  36. [36]

    Mirani and P

    A. Mirani and P. Hayden. Learning interacting fermionic hamiltonians at the heisenberg limit. Physical Review A, 110(6):062421, 2024

    work page 2024

  37. [37]

    Narayanan

    S. Narayanan. Improved algorithms for learning quantum hamiltonians, via flat polynomials. arXiv preprint arXiv:2407.04540, 2024

    work page arXiv 2024

  38. [38]

    H. Ni, H. Li, and L. Ying. Quantum hamiltonian learning for the fermi-hubbard model.Acta Applicandae Mathematicae, 191(1):2, 2024

    work page 2024

  39. [39]

    Odake, H

    T. Odake, H. Kristj´ ansson, A. Soeda, and M. Murao. Higher-order quantum transformations of hamiltonian dynamics.Physical Review Research, 6(1):L012063, 2024

    work page 2024

  40. [40]

    O’Donnell.Analysis of boolean functions

    R. O’Donnell.Analysis of boolean functions. Cambridge University Press, 2014

    work page 2014

  41. [41]

    N. F. Ramsey. A molecular beam resonance method with separated oscillating fields.Physical Review, 78(6):695, 1950. 18

    work page 1950

  42. [42]

    Shabani, M

    A. Shabani, M. Mohseni, S. Lloyd, R. L. Kosut, and H. Rabitz. Estimation of many-body quantum hamiltonians via compressive sensing.Physical Review A—Atomic, Molecular, and Optical Physics, 84(1):012107, 2011

    work page 2011

  43. [43]

    Sheldon, E

    S. Sheldon, E. Magesan, J. M. Chow, and J. M. Gambetta. Procedure for systematically tuning up cross-talk in the cross-resonance gate.Physical Review A, 93(6):060302, 2016

    work page 2016

  44. [44]

    M. D. Shulman, S. P. Harvey, J. M. Nichol, S. D. Bartlett, A. C. Doherty, V. Umansky, and A. Yacoby. Suppressing qubit dephasing using real-time hamiltonian estimation.Nature communications, 5(1):5156, 2014

    work page 2014

  45. [45]

    S. D. Sinha and Y. Tong. Improved hamiltonian learning and sparsity testing through bell sampling.arXiv preprint arXiv:2509.07937, 2025

    work page arXiv 2025

  46. [46]

    Sundaresan, I

    N. Sundaresan, I. Lauer, E. Pritchett, E. Magesan, P. Jurcevic, and J. M. Gambetta. Reducing unitary and spectator errors in cross resonance with optimized rotary echoes.PRX Quantum, 1(2):020318, 2020

    work page 2020

  47. [47]

    Valencia, G

    A. Valencia, G. Scarcelli, and Y. Shih. Distant clock synchronization using entangled photon pairs.Applied Physics Letters, 85(13):2655–2657, 2004

    work page 2004

  48. [48]

    Verdon, J

    G. Verdon, J. Marks, S. Nanda, S. Leichenauer, and J. Hidary. Quantum hamiltonian-based models and the variational quantum thermalizer algorithm.Bulletin of the American Physical Society, 65, 2020

    work page 2020

  49. [49]

    J. Wang, S. Paesani, R. Santagati, S. Knauer, A. A. Gentile, N. Wiebe, M. Petruzzella, J. L. O’brien, J. G. Rarity, A. Laing, et al. Experimental quantum hamiltonian learning.Nature Physics, 13(6):551–555, 2017

    work page 2017

  50. [50]

    Wiebe, C

    N. Wiebe, C. Granade, C. Ferrie, and D. Cory. Quantum hamiltonian learning using imperfect quantum resources.Physical Review A, 89(4):042314, 2014

    work page 2014

  51. [51]

    Wiebe, C

    N. Wiebe, C. Granade, C. Ferrie, and D. G. Cory. Hamiltonian learning and certification using quantum resources.Physical review letters, 112(19):190501, 2014

    work page 2014

  52. [52]

    R. M. Wilcox. Exponential operators and parameter differentiation in quantum physics.Jour- nal of Mathematical Physics, 8(4):962–982, 1967

    work page 1967

  53. [53]

    D. J. Wineland, J. J. Bollinger, W. M. Itano, F. Moore, and D. J. Heinzen. Spin squeezing and reduced quantum noise in spectroscopy.Physical Review A, 46(11):R6797, 1992

    work page 1992

  54. [54]

    A. Zhao. Learning the structure of any hamiltonian from minimal assumptions. InProceedings of the 57th Annual ACM Symposium on Theory of Computing, pages 1201–1211, 2025

    work page 2025

  55. [55]

    Zubida, E

    A. Zubida, E. Yitzhaki, N. H. Lindner, and E. Bairey. Optimal short-time measurements for hamiltonian learning.arXiv preprint arXiv:2108.08824, 2021. 19

    work page arXiv 2021