{"id":"arxiv/2609.34532","url":"https://arxiv.org/abs/2609.34532","tags":["quant-ph","cs.CC","cs.DS"],"score":0,"title":"Near-Optimal Bounds on the Density of Low-Energy States of $k$-Local Hamiltonians and Faster Quantum Algorithms","domain":"quant-ph","source":"arxiv","authors":["Sevag Gharibian","François Le Gall","Ranitha Mataraarachchi","Suguru Tamaki"],"reviews":0,"subject":"quant-ph","summary":"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…","category":"research","comments":0,"disputed":false,"division":"physics","mentions":0,"discussed":0,"published":"2026-09-28","reactions":{}}