PaperlayerView exact revision on arXiv

Source-linked AI summary

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

Sevag Gharibian, François Le Gall, Ranitha Mataraarachchi, Suguru Tamaki

arXiv:2609.34532v1quant-phcs.CCcs.DS

TL;DR

Low-energy estimation and state preparation for k-local Hamiltonians are important tasks, while prior results motivate improved runtimes for estimating the true ground energy. The paper combines properties of a depolarized ground state to bound the low-energy subspace, yielding entropy-governed algorithms whose bound is nearly optimal for fixed k.

  • Problem

    Low-energy estimation and state preparation are important tasks, and prior work on entropy-governed runtimes for depth-bounded states left the true ground-energy case open.

    Source: §1.1 · pp. 1–2

  • Method

    The proof combines a low-energy bound and a Schatten p-moment bound for a depolarized ground state to lower-bound the number of low-energy eigenstates.

    Source: §1.4 · p. 5

  • Results

    The binary-entropy dependence of the low-energy-subspace bound is optimal up to constant factors in the exponent for fixed k, and the algorithms improve on [11].

    Source: §5 · p. 18

  • Takeaways & Limitations

    The framework also gives tighter bounds for Heisenberg, XY, and Ising models on arbitrary interaction graphs.

    Source: §5 · p. 18

    The runtime remains exponential, the prepared low-energy state is not guaranteed to have high ground-state fidelity, and accuracy is relative to M, which may grow with n for dense interaction graphs.

    Source: §5 · p. 18

Abstract

from arXiv · show

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.

1 Introduction

The introduction frames ground-energy estimation and low-energy state preparation as central tasks for k-local Hamiltonians, then presents entropy-governed algorithms and a low-energy-subspace bound for arbitrary such Hamiltonians. The bound is nearly optimal for fixed k, and the resulting algorithms improve on prior runtimes.

1.1 Background and Motivation

  • The paper targets ground-energy estimation and preparation of states with energy close to the ground energy, tasks connected to low-temperature equilibrium properties and applications in quantum chemistry, condensed-matter physics, and quantum information.Unlike approaches relying on restricted interaction graphs or variational ansätze, the stated guarantee applies without geometric restrictions or a guiding state; the runtime remains exponential and the prepared state need not have high ground-state fidelity.Source: §1.1 · p. 1, §1.5 · p. 5

1.2 Previous Results

  • The prior O*(2^{n/2}) approach uses phase estimation and amplitude amplification, while [11] first obtained faster algorithms for both tasks through a lower bound on low-energy eigenstate counts.Work in [13] gave entropy-governed runtimes for depth-bounded minimum energy, leaving the true ground-state energy case open.Source: §1.2 · pp. 2–3

1.3 Our Contributions

  • The algorithms give an entropy-governed speedup for low-energy estimation and state preparation for any k-local Hamiltonian, directly improving on [11].For constant k and ε, their exponent is below n/2; for small ε/k, they achieve a logarithmic-factor speedup in k/ε over [11].Source: §1.3 · p. 3
  • For fixed k, the low-energy-subspace bound has binary-entropy scaling that is optimal up to constant factors in the exponent, as shown by a classical diagonal Hamiltonian.The introduction also states that the entropy dependence cannot be improved in general, even if numerical constants may be sharpened.Source: §1.3 · p. 3

1.4 Proof Overview

  • Depolarizing an arbitrary ground state replaces direct counting of perturbed states with an entropy analysis of a mixture, while k-locality controls its energy increase and its Schatten p-th moment is bounded using binary Rényi entropy.Combining these properties with a low-energy projector overlap and Hölder’s inequality yields a lower bound on the number of low-energy eigenstates.Source: §1.4 · pp. 4–5
  • The proof’s depolarization-based density bound feeds into the algorithmic framework of [13] to obtain the stated estimation and state-preparation algorithms.The introduction also situates the work against variational methods, which it says do not provide worst-case convergence guarantees for arbitrary local Hamiltonians.Source: §1.4 · p. 5, §1.5 · p. 5

2 Preliminaries

The preliminaries establish notation for the Hamiltonian, its energy spectrum, and low-energy subspaces, alongside the entropy and norm tools used in the analysis.

Hamiltonian notation

  • An n-qubit k-local Hamiltonian is written as a sum of local terms, with total interaction strength M equal to the sum of their spectral norms.A ground-state density operator is supported on the ground space.Source: §2 · p. 6

Spectral notation

  • The cumulative density of states N_H(E) counts eigenvalues at most E with multiplicity, and the corresponding projector spans their eigenvectors.Source: §2 · p. 6

Norms

  • Schatten p-norms and Hölder’s inequality provide the norm relation used to bound overlaps involving operators.Source: §2 · p. 6

Entropy

  • For p > 1, the Rényi p-entropy of a density operator is defined from the logarithm of its p-th moment; the binary Rényi entropy H_p(b) is given for the binary parameter b.Source: §2 · p. 6

Quantum channels and Pauli operators

  • The qubit depolarizing map is described through Pauli operators, and the map R_i retains Pauli strings acting as identity on qubit i.The norm difference between an interaction term and its R_i image measures the part acting nontrivially on that qubit.Source: §2 · pp. 6–7

Asymptotic notation

  • O*(·) and Ω*(·) suppress polynomial factors in n in upper and lower bounds, respectively.Source: §2 · p. 7

3 An Entropy-Governed Low-Energy Spectrum

The section depolarizes a ground state, bounds the resulting state's energy and Schatten p-moment, and combines those bounds to lower-bound the dimension of the low-energy subspace. It then derives binary-entropy and interaction-dependent forms of the bound.

3.1 The Qubit Depolarizing Channel

  • The qubit depolarizing channel maps every pure input to a state with eigenvalues 1 − b and b, supporting a bound on the n-qubit output's p-th moment.The p-th moment bound also gives a lower bound on binary Rényi p-entropy.Source: §3.1 · p. 8

3.2 Energy Bound for the Depolarized Ground State

  • For 0 ≤ b ≤ 2/3, the depolarized ground state's energy increase is at most ybM, where y depends on the interaction types in H.The bound never exceeds the generic bound in Lemma 3.5; the proof uses the probability that depolarization leaves each local term's support unchanged.Source: §3.2 · pp. 9–10

3.3 Lower Bounds on the Density of Low-Energy States

  • Theorem 3.8 combines energy and Schatten p-moment bounds for the depolarized ground state to lower-bound the low-energy subspace dimension, when 3kb < µ.The resulting bound is parameterized by the depolarized state's Rényi entropy.Source: §3.3 · p. 11
  • Corollary 3.9 gives a binary-entropy lower bound of Ω*(2^(3/5 n h2(µ/6k))) when 0 < µ ≤ 1 and µ = Ω(1/poly(n)).The corollary is a simpler, coarser consequence of the Rényi-parameterized bound; its constants may be improved, while the binary-entropy dependence is optimal up to constant factors in the exponent for fixed k.Source: §3.3 · pp. 12–13
  • For fixed k, a family of classical diagonal k-local Hamiltonians shows that the binary-entropy exponent is optimal up to constant factors.The corollary's constants may still be sharpened.Source: §3.3 · pp. 13–14
  • Corollary 3.12 gives interaction-dependent refinements using y(H), including a bound under yb < µ and a simplified bound when y ≥ 2.Its proof substitutes the interaction-dependent energy bound for the generic one.Source: §3.3 · p. 14

4 Algorithmic Implications

The section combines the low-energy density bound with the algorithmic framework of [13] to prepare low-energy states and estimate energies. It then derives runtime bounds for restricted interaction models on arbitrary interaction graphs.

4 Algorithmic Implications

  • The result combines the density-of-states bound in Corollary 3.9 with the quantum algorithm of [13, Section 3], based on the low-energy state-preparation procedure of [24, Section 6].Source: §4 · p. 15

4.1 Runtime Bounds for Restricted Interaction Types

  • For y(H) ≥ 2, Corollary 4.2 gives the algorithmic guarantee under ε = Ω(1/poly(n)); the model-specific bounds require M > 0.The interaction graphs may be arbitrary, with no structural assumption on their nonzero couplings.Source: §4.1 · p. 16
  • For classical Ising, depolarization is not optimal: directly counting low-energy states by perturbing an optimal assignment gives a stronger bound.The Hamiltonian is diagonal in the computational basis, so a ground state can be chosen as a basis state; this direct-counting approach was used for max-k-sat [12].Source: §4.1 · p. 17
  • For the restricted interaction models, Table 2 compares entropy arguments, and a larger argument yields a smaller runtime exponent.The section evaluates y(H) for Heisenberg, XY, transverse-field Ising, and classical Ising interactions; its local-term norm and R_i calculations supply the model-specific bounds.Source: §4.1 · pp. 16–17, Table 2 · p. 17

5 Conclusion

The conclusion establishes an entropy-governed lower bound on the low-energy subspace and uses it to obtain faster quantum algorithms. It also states the bounds’ scope and limitations, while leaving matching conditional lower bounds open.

5 Conclusion

  • The low-energy subspace has dimension at least an entropy-governed bound, and for fixed k that scaling is optimal up to constant factors in the exponent.A classical diagonal Hamiltonian witnesses the near-optimality.Source: §5 · p. 18
  • The resulting algorithms prepare low-energy states and estimate energy with entropy-governed running time, improving directly on the runtimes in [11].The parameter y(H) further tightens bounds for the Heisenberg, XY, and Ising models in Table 2.Source: §5 · p. 18
  • The worst-case guarantee covers arbitrary k-local Hamiltonians without geometric locality, a variational ansatz, or ground-state structural assumptions.The output state need not have high ground-state fidelity, the runtime remains exponential, and for dense graphs M may grow with n.Source: §5 · p. 18
  • The runtime remains exponential and is consistent with the proposed quantum GAP-ETH; establishing matching conditional lower bounds remains open.The discussion frames the result as an update to the quantitative benchmark in Theorem 1 of [11].Source: §5 · p. 18
  • The authors conclude that low-energy preparation and estimation for general k-local Hamiltonians are more accessible than previous results suggested.Source: §5 · p. 18

Disclosure of AI Tools

The authors report using AI tools for research assistance and manuscript presentation, and state that they take full accountability for the content.

Disclosure of AI Tools

  • ChatGPT and Gemini were used to explore proof strategies, identify literature, and propose the complete proof of Theorem 1.2 based on that literature.Source: Disclosure of AI Tools · p. 18
  • ChatGPT-6 Astra helped draft and improve the manuscript’s presentation, while the authors take full accountability for its content.Source: Disclosure of AI Tools · p. 18

A Properties of the Qubit Depolarizing Channel

The channel is shown to be completely positive and trace preserving by expressing it as a convex combination of unitary channels.

A Properties of the Qubit Depolarizing Channel

Loading 2609.34532v1…