---
_id: '67293'
abstract:
- lang: eng
  text: 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.
author:
- first_name: Sevag
  full_name: Gharibian, Sevag
  id: '71541'
  last_name: Gharibian
  orcid: 0000-0002-9992-3379
- first_name: Francois
  full_name: Le Gall, Francois
  last_name: Le Gall
- first_name: Ranitha
  full_name: Mataraarachchi, Ranitha
  last_name: Mataraarachchi
- first_name: Suguru
  full_name: Tamaki, Suguru
  last_name: Tamaki
citation:
  ama: Gharibian S, Le Gall F, Mataraarachchi R, Tamaki S. Near-Optimal Bounds on
    the Density of Low-Energy States of $k$-Local Hamiltonians and Faster Quantum
    Algorithms. Published online 2026.
  apa: Gharibian, S., Le Gall, F., Mataraarachchi, R., &#38; Tamaki, S. (2026). <i>Near-Optimal
    Bounds on the Density of Low-Energy States of $k$-Local Hamiltonians and Faster
    Quantum Algorithms</i>.
  bibtex: '@article{Gharibian_Le Gall_Mataraarachchi_Tamaki_2026, title={Near-Optimal
    Bounds on the Density of Low-Energy States of $k$-Local Hamiltonians and Faster
    Quantum Algorithms}, author={Gharibian, Sevag and Le Gall, Francois and Mataraarachchi,
    Ranitha and Tamaki, Suguru}, year={2026} }'
  chicago: Gharibian, Sevag, Francois Le Gall, Ranitha Mataraarachchi, and Suguru
    Tamaki. “Near-Optimal Bounds on the Density of Low-Energy States of $k$-Local
    Hamiltonians and Faster Quantum Algorithms,” 2026.
  ieee: S. Gharibian, F. Le Gall, R. Mataraarachchi, and S. Tamaki, “Near-Optimal
    Bounds on the Density of Low-Energy States of $k$-Local Hamiltonians and Faster
    Quantum Algorithms.” 2026.
  mla: Gharibian, Sevag, et al. <i>Near-Optimal Bounds on the Density of Low-Energy
    States of $k$-Local Hamiltonians and Faster Quantum Algorithms</i>. 2026.
  short: S. Gharibian, F. Le Gall, R. Mataraarachchi, S. Tamaki, (2026).
date_created: 2026-10-01T07:35:41Z
date_updated: 2026-10-01T08:21:44Z
department:
- _id: '7'
- _id: '623'
language:
- iso: eng
status: public
title: Near-Optimal Bounds on the Density of Low-Energy States of $k$-Local Hamiltonians
  and Faster Quantum Algorithms
type: preprint
user_id: '71541'
year: '2026'
...