Lower Bounds for Learning Hamiltonians from Time Evolution

• URL: http://arxiv.org/abs/2509.20665v2
• Date: Wed, 01 Oct 2025 22:18:46 GMT
• Title: Lower Bounds for Learning Hamiltonians from Time Evolution
• Authors: Ziyun Chen, Jerry Li,
• Abstract summary: We consider the problem of learning Hamiltonians from time evolution.<n>We show that any learning algorithm with inverse time resolution requires super-polynomial total evolution time.
• Score: 5.118083299467833
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: We consider the problem of learning Hamiltonians from time evolution: given the ability to apply $e^{-iHt}$ for an unknown Hamiltonian on $n$ qubits, the goal is to recover the parameters of $H$. This is a well-studied problem in quantum learning theory, with applications to quantum metrology, sensing, device benchmarking, and many-body physics. For this problem, we demonstrate the first lower bounds which scale with the number of parameters of the unknown Hamiltonian. When the unknown Hamiltonian is arbitrary, we show that learning to error $\epsilon$ requires $2^{(1/2 - o(1))n} / \epsilon$ rounds of interaction with the Hamiltonian. If the Hamiltonian is additionally assumed to be $k$-local, we show that learning to constant error requires $n^{\Omega (k)}$ rounds of interaction with the Hamiltonian, resolving an open question of Tang. These bounds immediately imply that any learning algorithm with inverse polynomial time resolution requires super-polynomial total evolution time. Our lower bounds hold even for very simple planted spike detection problems, where the goal is to detect the presence of a single coefficient which is super-polynomially larger than the other coefficients of the Hamiltonian, as well as for average case instances.

Related papers

• Hamiltonian Decoded Quantum Interferometry [69.7049555871155]
  We introduce Hamiltonian Decoded Quantum Interferometry (HDQI)<n>HDQI utilizes coherent measurements and the symplectic representation of the Pauli group to reduce Gibbs sampling and Hamiltonian Bellians.<n>We show that HDQI efficiently prepares Gibbs states at arbitrary temperatures for a class of physically motivated commuting Hamiltonians.
  arXiv  Detail & Related papers  (2025-10-09T08:06:15Z)
• Accelerating Fermionic System Simulation on Quantum Computers [1.655267861296594]
  A potential approach for demonstrating quantum advantage is using quantum computers to simulate fermionic systems.<n>We introduce a grouping strategy that partitions Hamiltonian terms into $mathcalO(N4)$ groups.<n>We propose a parallel Hamiltonian evolution scheme that reduces the circuit depth of Hamiltonian evolution by a factor of $N$.
  arXiv  Detail & Related papers  (2025-05-13T03:44:07Z)
• New random compiler for Hamiltonians via Markov Chains [0.07499722271664146]
  We develop a new compiler, similar to the first order randomized Trotter, or qDRIFT, but with an arguably simpler framework.<n>We first present the model and derive its governing equations. We then define and analyze the simulation error for a sum of two Hamiltonians, and generalize it to a sum of $Q$ Hamiltonians.
  arXiv  Detail & Related papers  (2024-11-10T14:57:25Z)
• Slow Mixing of Quantum Gibbs Samplers [47.373245682678515]
  We present a quantum generalization of these tools through a generic bottleneck lemma.<n>This lemma focuses on quantum measures of distance, analogous to the classical Hamming distance but rooted in uniquely quantum principles.<n>We show how to lift classical slow mixing results in the presence of a transverse field using Poisson Feynman-Kac techniques.
  arXiv  Detail & Related papers  (2024-11-06T22:51:27Z)
• Predicting Ground State Properties: Constant Sample Complexity and Deep Learning Algorithms [48.869199703062606]
  A fundamental problem in quantum many-body physics is that of finding ground states of local Hamiltonians. We introduce two approaches that achieve a constant sample complexity, independent of system size $n$, for learning ground state properties.
  arXiv  Detail & Related papers  (2024-05-28T18:00:32Z)
• Structure learning of Hamiltonians from real-time evolution [22.397920564324973]
  We present a new, general approach to Hamiltonian learning that not only solves the challenging structure learning variant, but also resolves other open questions in the area.<n>Our algorithm recovers the Hamiltonian to $varepsilon$ error with total evolution time $O(log (n)/varepsilon)$, and has the following appealing properties.<n>As an application, we can also learn Hamiltonians exhibiting power-law decay up to accuracy $varepsilon$ with total evolution time beating the standard limit of $1/varepsilon2$.
  arXiv  Detail & Related papers  (2024-04-30T18:00:00Z)
• Hamiltonian Property Testing [0.8192907805418583]
  Locality is a fundamental feature of many physical time evolutions.<n>No protocols to rigorously test whether an unknown Hamiltonian is local were known.
  arXiv  Detail & Related papers  (2024-03-05T13:44:28Z)
• Some Remarks on the Regularized Hamiltonian for Three Bosons with Contact Interactions [77.34726150561087]
  We discuss some properties of a model Hamiltonian for a system of three bosons interacting via zero-range forces in three dimensions. In particular, starting from a suitable quadratic form $Q$, the self-adjoint and bounded from below Hamiltonian $mathcal H$ can be constructed. We show that the threshold value $gamma_c$ is optimal, in the sense that the quadratic form $Q$ is unbounded from below if $gammagamma_c$.
  arXiv  Detail & Related papers  (2022-07-01T10:01:14Z)
• Average-case Speedup for Product Formulas [69.68937033275746]
  Product formulas, or Trotterization, are the oldest and still remain an appealing method to simulate quantum systems. We prove that the Trotter error exhibits a qualitatively better scaling for the vast majority of input states. Our results open doors to the study of quantum algorithms in the average case.
  arXiv  Detail & Related papers  (2021-11-09T18:49:48Z)
• Hamiltonian simulation with random inputs [74.82351543483588]
  Theory of average-case performance of Hamiltonian simulation with random initial states. Numerical evidence suggests that this theory accurately characterizes the average error for concrete models.
  arXiv  Detail & Related papers  (2021-11-08T19:08:42Z)
• Variational quantum eigensolvers for sparse Hamiltonians [0.0]
  Hybrid quantum-classical variational algorithms such as the variational quantum eigensolver (VQE) are promising applications for noisy, intermediate-scale quantum computers. We extend VQE to general sparse Hamiltonians.
  arXiv  Detail & Related papers  (2020-12-13T22:36:51Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.