Near optimal bounds speed up quantum low energy state estimates
Near-Optimal Bounds on the Density of Low-Energy States of $k$-Local Hamiltonians and Faster Quantum Algorithms
Computational ComplexityData Structures and Algorithms
Summary
Estimating low-energy states in complex quantum systems is a key task for advancing quantum computing. The authors improve on recent work by creating faster algorithms that better estimate these states for certain quantum systems described by k-local Hamiltonians. Their approach uses a mathematical relationship involving entropy, which measures uncertainty, to set tight limits on how many low-energy states exist. This leads to more efficient quantum algorithms for important models like the Heisenberg and Ising, potentially aiding simulations in physics and chemistry.
What this means in practice
- •For quantum computing engineers: Develop faster quantum routines to prepare and estimate properties of low-energy states in complex quantum systems.
- •For condensed matter physicists: Use improved bounds on low-energy state density to better model and simulate physical systems like Heisenberg and Ising spin networks.
A theory result. No direct application yet.
Authors
Sevag Gharibian, François Le Gall, Ranitha Mataraarachchi, Suguru Tamaki
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.