---
res:
  bibo_abstract:
  - Low-energy estimation and state preparation for general $k$-local Hamiltonians
    are fundamental challenges in quantum complexity theory. Buhrman et al.~ [BGLGST,
    PRL 2025] recently broke the natural Grover bound $O^\ast(2^{n/2})$ for both problems,
    with the improvement depending on the relative accuracy $\varepsilon$ and the
    locality $k$. In this work, we present faster exponential quantum algorithms for
    these problems, where the binary entropy function governs the runtime exponent.
    For sufficiently small $\varepsilon/k$, our algorithms improve the exponent by
    a factor of $\log(k/\varepsilon)$ over [BGLGST, PRL 2025]. Our main technical
    result is an entropy-governed lower bound on the dimension of the Hamiltonian's
    low-energy subspace, obtained by depolarizing its ground state. For fixed $k$,
    this bound is optimal up to constant factors in the exponent. The same framework
    yields tighter bounds for Heisenberg, $XY$, and Ising models on arbitrary interaction
    graphs.@eng
  bibo_authorlist:
  - foaf_Person:
      foaf_givenName: Sevag
      foaf_name: Gharibian, Sevag
      foaf_surname: Gharibian
      foaf_workInfoHomepage: http://www.librecat.org/personId=71541
    orcid: 0000-0002-9992-3379
  - foaf_Person:
      foaf_givenName: Francois
      foaf_name: Le Gall, Francois
      foaf_surname: Le Gall
  - foaf_Person:
      foaf_givenName: Ranitha
      foaf_name: Mataraarachchi, Ranitha
      foaf_surname: Mataraarachchi
  - foaf_Person:
      foaf_givenName: Suguru
      foaf_name: Tamaki, Suguru
      foaf_surname: Tamaki
  dct_date: 2026^xs_gYear
  dct_language: eng
  dct_title: Near-Optimal Bounds on the Density of Low-Energy States of $k$-Local
    Hamiltonians and Faster Quantum Algorithms@
...