{"id":"arxiv/2605.18241","url":"https://arxiv.org/abs/2605.18241","tags":["quant-ph","cs.CC","cs.DS"],"score":0,"title":"An Entropy-Governed Speedup for Quantum Algorithms on Local Hamiltonians","domain":"quant-ph","source":"arxiv","authors":["Ranitha Mataraarachchi","François Le Gall","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. For constant relative accuracy, Buhrman et al. (PRL 2025) recently broke the natural Grover bound $O(2^{n/2})$, where $n$ denotes the number of qubits, for both problems. In this paper, for any sufficiently small parameter $d\\ge 0$, we present an even faster quantum algorithm that outputs a quantum state with energy bounded by the minimum energy over all depth-$d$ states (i.e., states obtained by applying a depth-$d$ circuit to the all-zero state), together…","category":"research","comments":0,"disputed":false,"division":"physics","mentions":0,"discussed":0,"published":"2026-05-18","reactions":{}}