Near-Optimal Bounds on the Density of Low-Energy States of $k$-Local Hamiltonians and Faster Quantum Algorithms

AI summary

Overview

Research area: Quantum Hamiltonian complexity and quantum algorithms — specifically, ground-energy estimation and low-energy state preparation for (k)-local Hamiltonians.

Technical level: Advanced. The paper is a theoretical quantum-complexity result; it assumes familiarity with QMA, Schatten norms, Rényi entropy, and amplitude amplification, though the central ideas can be explained without the full formalism.

Scope: The paper proves a near-optimal, entropy-governed lower bound on the dimension of the low-energy subspace of any (k)-local Hamiltonian and uses it to construct quantum algorithms for ground-energy estimation and low-energy state preparation that are faster than the previous best known algorithms.

What This Paper Is About

Given an (n)-qubit (k)-local Hamiltonian (H=\sum_{\alpha=1}^{m} h_\alpha) with total interaction strength (M=\sum_\alpha \lVert h_\alpha\rVert), two fundamental tasks are estimating the ground-state energy (\lambda_0(H)) and preparing a state (\rho) with (\operatorname{Tr}(H\rho)\le \lambda_0+\varepsilon M). The natural Grover-type runtime for both is (O^*(2^{n/2})), and Buhrman et al. (PRL 2025) recently beat it with a runtime depending on (\varepsilon) and (k). This paper replaces that improvement with one governed by the binary entropy function, giving faster algorithms and a density-of-states bound that is optimal up to constant factors in the exponent for fixed (k).

Key Contributions

1. A near-optimal density-of-states lower bound. The paper shows that the number of eigenvalues of (H) at most (\lambda_0+\mu M) satisfies (N_H(\lambda_0+\mu M)=\Omega^!\left(2^{\frac{3}{5}n h_2(\mu/(6k))}\right)) (Corollary 3.9), where (h_2) is the binary entropy in bits and (\Omega^) suppresses inverse-polynomial factors in (n). Proposition 3.11 exhibits a classical diagonal Hamiltonian with scaling (2^{\Theta(n h_2(\mu/(6k)))}), so the binary-entropy dependence cannot be improved in general for fixed (k), although the numerical constants may be sharpenable.

2. Faster quantum algorithms. Theorem 1.2 gives a quantum algorithm that, with high probability, prepares (\rho) with (\operatorname{Tr}[H\rho]\le \lambda_0+\varepsilon M) and outputs (\widehat{E}\in[\lambda_0,\lambda_0+\varepsilon M]) in time (O^!\left(2^{\frac{n}{2}\left(1-\frac{3}{5}h_2\left(\frac{\varepsilon}{6k}\right)\right)}\right)), improving on the (O^!\left(2^{\frac{n}{2}\left(1-\frac{\varepsilon}{2k+\varepsilon}\right)}\right)) runtime of Buhrman et al.

3. A depolarization-based proof technique. The core technical tool is a Rényi-parameterized bound (Theorem 3.8) obtained by applying a qubit depolarizing channel independently to each qubit of a ground-state density operator, then controlling the resulting energy increase and Schatten (p)-th moment.

4. Tighter bounds for structured interaction models. The same framework yields sharper bounds for the Heisenberg, (XY), and Ising models on arbitrary interaction graphs, summarized in Table 2 of the paper.

Main Findings

• Entropy governs the low-energy spectrum. The central bound is (N_H(\lambda_0+\mu M)=\Omega^*!\left(2^{\frac{3}{5}n h_2(\mu/(6k))}\right)) for (0<\mu\le 1) with (\mu=\Omega(1/\operatorname{poly}(n))). The exponent is driven by the binary entropy function rather than by a simple linear function of (\mu/k).

• Rényi-parameterized core theorem (Theorem 3.8). For (\mu>0), (b\in(0,1/2)) with (3kb<\mu), and every (p>1): (N_H(\lambda_0+\mu M)\ge \left(1-\frac{3kb}{\mu}\right)^{p/(p-1)}\exp!\left

Authors’ 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.