preprint Sevag Gharibian author 715410000-0002-9992-3379 Francois Le Gall author Ranitha Mataraarachchi author Suguru Tamaki author 7 department 623 department 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. 2026 eng 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. @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} } 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. 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. S. Gharibian, F. Le Gall, R. Mataraarachchi, S. Tamaki, (2026). 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>. 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. 672932026-10-01T07:35:41Z2026-10-01T08:21:44Z