Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2609.34532

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

quant-phcs.CCcs.DSSubmitted Sep 28, 2026• Announced Sep 29, 2026• 0 citations
arXivHTMLPDF

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.

Comments
21 pages, 2 tables, 0 figures

Related papers

An Entropy-Governed Speedup for Quantum Algorithms on Local Hamiltonians

Ranitha Mataraarachchi, François Le Gall, Suguru Tamaki

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 with an estimate of this energy. For the class of Hamiltonians with depth-$d$ ground states, our algorithm furthermore achieves exactly the same energy guarantees as Buhrman et al. Our results also provide insight into the distinction between strongly entangled states and those admitting efficient classical descriptions.

quant-pharXiv:2605.18241•May 19, 2026•0 citations

Near-Optimal Ground-State Preparation without Controlled Hamiltonian Evolutions

Dhrumil Patel, Steven T. Flammia, Raul Garcia-Patron

Ground-state preparation, energy estimation, and property estimation are fundamental tasks in quantum simulation. Existing ground-state preparation algorithms achieve near-optimal complexity using block encodings or controlled Hamiltonian evolution, raising a natural question: is controlled Hamiltonian evolution necessary, or can the same scaling be attained in the weaker access model that provides access to only uncontrolled Hamiltonian evolution? We resolve this question by giving two algorithms that access the input Hamiltonian $H$ only through queries to $U_H$ and its inverse $U_H^\dagger$, where $\|H\|\leα_H$ and $τ=Θ(1/α_H)$. Given an input state with ground-state weight at least $η$ and a spectral gap of $H$ of at least $γ$, our first algorithm uses fresh copies of the input state and requires $\widetilde O(α_H/(γη))$ queries to $U_H$ and $U_H^\dagger$, while our second algorithm uses coherent access to the input-state preparation unitary and its inverse to improve this complexity to $\widetilde O(α_H/(γ\sqrtη))$. The latter bound matches the known lower bound up to logarithmic factors, showing that algorithms with additional access to controlled Hamiltonian evolution cannot improve the query complexity for ground-state preparation beyond logarithmic factors. Both algorithms are based on a simple mechanism that we call the spectral descent principle, in which the algorithm starts from the input state $|ψ\rangle$ and progressively descends through the energy spectrum, moving closer to the ground state until the desired fidelity is reached. We also extend this framework to ground-state property and energy estimation and give explicit complexity guarantees for both tasks.

quant-pharXiv:2610.00520•Oct 2, 2026•0 citations

Beating the Natural Grover Bound for Low-Energy Estimation and State Preparation

Harry Buhrman, Sevag Gharibian, Zeph A. Landau +3 more

Estimating ground state energies of many-body Hamiltonians is a central task in many areas of quantum physics. In this Letter, we give quantum algorithms which, given any k-body Hamiltonian H, compute an estimate for the ground state energy and prepare a quantum state achieving said energy, respectively. Specifically, for any ϵ>0, our algorithms return, with high probability, an estimate of the ground state energy of H within additive error ϵM, or a quantum state with the corresponding energy. Here, M is the total strength of all interaction terms, which in general is extensive in the system size. Our approach makes no assumptions about the geometry or spatial locality of interaction terms of the input Hamiltonian and thus handles even long-range or all-to-all interactions, such as in quantum chemistry, where lattice-based techniques break down. In this fully general setting, the run-time of our algorithms scales as 2^{cn/2} for c<1, yielding the first quantum algorithms for low-energy estimation breaking a standard square root Grover speedup for unstructured search. The core of our approach is remarkably simple, and relies on showing that an extensive fraction of the interactions can be neglected with a controlled error. What this ultimately implies is that even arbitrary k-local Hamiltonians have structure in their low energy space, in the form of an exponential-dimensional low energy subspace.

arXiv:2407.03073•Physical Review Letters•May 28, 2025•3 citations

Fine-Grained Complexity for Quantum Problems from Size-Preserving Circuit-to-Hamiltonian Constructions

Nai-Hui Chia, Atsuya Hasegawa, François Le Gall +1 more

The local Hamiltonian (LH) problem is the canonical $\mathsf{QMA}$-complete problem introduced by Kitaev. In this paper, we show its hardness in a very strong sense: we show that the 3-local Hamiltonian problem on $n$ qubits cannot be solved classically in time $O(2^{(1-\varepsilon)n})$ for any $\varepsilon>0$ under the Strong Exponential-Time Hypothesis (SETH), and cannot be solved quantumly in time $O(2^{(1-\varepsilon)n/2})$ for any $\varepsilon>0$ under the Quantum Strong Exponential-Time Hypothesis (QSETH). These lower bounds give evidence that the currently known classical and quantum algorithms for LH cannot be significantly improved. Furthermore, we are able to demonstrate fine-grained complexity lower bounds for approximating the quantum partition function (QPF) with an arbitrary constant relative error. Approximating QPF with relative error is known to be equivalent to approximately counting the dimension of the solution subspace of $\mathsf{QMA}$ problems. We show the SETH and QSETH hardness to estimate QPF with constant relative error. We then provide a quantum algorithm that runs in $O(\sqrt{2^n})$ time for an arbitrary $1/\mathrm{poly}(n)$ relative error, matching our lower bounds and improving the state-of-the-art algorithm by Bravyi, Chowdhury, Gosset, and Wocjan (Nature Physics 2022) in the low-temperature regime. To prove our fine-grained lower bounds, we introduce the first size-preserving circuit-to-Hamiltonian construction that encodes the computation of a $T$-time quantum circuit acting on $N$ qubits into a $(d+1)$-local Hamiltonian acting on $N+O(T^{1/d})$ qubits. This improves the standard construction based on the unary clock, which uses $N+O(T)$ qubits.

quant-pharXiv:2602.14379•Leibniz international proceedings in informatics•Feb 17, 2026•0 citations

Lower Bounds for Learning Hamiltonians from Time Evolution

Ziyun Chen, Jerry Zheng Li, Slote, Joseph

Learning about a Hamiltonian $H$ from its time evolution $e^{-iHt}$ is a fundamental task in quantum science. A flurry of recent work has developed powerful new algorithms with provable guarantees for this task, for a variety of natural settings. Despite this, relatively little is known about lower bounds for learning Hamiltonians. In particular, in the natural setting where we assume $H$ is a $k$-local Hamiltonian on $n$ qubits, all existing algorithms require total evolution time at least $n^{Ω(k)}$ to learn the parameters of $H$, and it remained open whether one could obtain even faster algorithms -- or at the very least, if one could obtain better runtimes for simpler tasks, such as estimating a single designated coefficient of the Hamiltonian. In this work we show the answer is essentially no, by obtaining strong lower bounds for these problems. We find that not only do $k$-local Hamiltonians require $n^{Ω(k)}$ time evolution or interactions to learn, but also that in several senses, learning anything about a Hamiltonian is just as hard as learning everything. In particular, we find the same $n^{Ω(k)}$ lower bound holds for learning a single coefficient of a $k$-local Hamiltonian $H$, even if the rest of $H$ is already known. We also show an $n^{Ω(k)}$ lower bound for the task of effective Hamiltonian learning, where one seeks only to learn a unitary that approximately implements time evolution of $H$. Several related lower bounds, such as for general sparse (but not necessarily local) $H$ are also given. On the technical side, we make a new connection between Hamiltonian learning lower bounds and the analysis of Boolean functions, where we introduce a novel extremal property that may be of independent interest.

arXiv:2509.20665•Sep 25, 2025•0 citations

Improved Product-State Approximation Algorithms for Quantum Local Hamiltonians

Thiago Bergamaschi

The ground state energy and the free energy of Quantum Local Hamiltonians are fundamental quantities in quantum many-body physics, however, it is QMA-Hard to estimate them in general. In this paper, we develop new techniques to find classical, additive error product-state approximations for these quantities on certain families of Quantum $k$-Local Hamiltonians. Namely, those which are either dense, have low threshold rank, or are defined on a sparse graph that excludes a fixed minor, building on the methods and the systems studied by Brandão and Harrow, Gharibian and Kempe, and Bansal, Bravyi and Terhal. We present two main technical contributions. First, we discuss a connection between product-state approximations of local Hamiltonians and combinatorial graph property testing. We develop a series of weak Szemerédi regularity lemmas for $k$-local Hamiltonians, built on those of Frieze and Kannan and others. We use them to develop constant time sampling algorithms, and to characterize the `vertex sample complexity' of the Local Hamiltonian problem, in an analog to a classical result by Alon, de la Vega, Kannan and Karpinski. Second, we build on the information-theoretic product-state approximation techniques by Brandão and Harrow, extending their results to the free energy and to an asymmetric graph setting. We leverage this structure to define families of algorithms for the free energy at low temperatures, and new algorithms for certain sparse graph families.

arXiv:2210.08680•Leibniz international proceedings in informatics•Oct 17, 2022•1 citation
Near-Optimal Bounds on the Density of Low-Energy States of kkk-Local Hamiltonians and Faster Quantum Algorithms
Low-energy estimation and state preparation for general kkk-local Hamiltonians are fundamental challenges in quantum complexity theory. Buhrman et al.~ [BGLGST, PRL 2025] recently broke the natural Grover bound O∗(2n/2)O^\ast(2^{n/2})O∗(2n/2) for both problems, with the improvement depending on the relative accuracy ε\varepsilonε and the locality kkk. In this work, we present faster exponential quantum algorithms for these problems, where the binary entropy function governs the runtime exponent. For sufficiently small ε/k\varepsilon/kε/k, our algorithms improve the exponent by a factor of log⁡(k/ε)\log(k/\varepsilon)log(k/ε) 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 kkk, this bound is optimal up to constant factors in the exponent. The same framework yields tighter bounds for Heisenberg, XYXYXY, and Ising models on arbitrary interaction graphs.
Low-energy estimation and state preparation for general kkk-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(2n/2)O(2^{n/2})O(2n/2), where nnn denotes the number of qubits, for both problems. In this paper, for any sufficiently small parameter d≥0d\ge 0d≥0, we present an even faster quantum algorithm that outputs a quantum state with energy bounded by the minimum energy over all depth-ddd states (i.e., states obtained by applying a depth-ddd circuit to the all-zero state), together with an estimate of this energy. For the class of Hamiltonians with depth-ddd ground states, our algorithm furthermore achieves exactly the same energy guarantees as Buhrman et al. Our results also provide insight into the distinction between strongly entangled states and those admitting efficient classical descriptions.
Ground-state preparation, energy estimation, and property estimation are fundamental tasks in quantum simulation. Existing ground-state preparation algorithms achieve near-optimal complexity using block encodings or controlled Hamiltonian evolution, raising a natural question: is controlled Hamiltonian evolution necessary, or can the same scaling be attained in the weaker access model that provides access to only uncontrolled Hamiltonian evolution? We resolve this question by giving two algorithms that access the input Hamiltonian HHH only through queries to UHU_HUH​ and its inverse UH†U_H^\daggerUH†​, where ∥H∥≤αH\|H\|\leα_H∥H∥≤αH​ and τ=Θ(1/αH)τ=Θ(1/α_H)τ=Θ(1/αH​). Given an input state with ground-state weight at least ηηη and a spectral gap of HHH of at least γγγ, our first algorithm uses fresh copies of the input state and requires O~(αH/(γη))\widetilde O(α_H/(γη))O(αH​/(γη)) queries to UHU_HUH​ and UH†U_H^\daggerUH†​, while our second algorithm uses coherent access to the input-state preparation unitary and its inverse to improve this complexity to O~(αH/(γη))\widetilde O(α_H/(γ\sqrtη))O(αH​/(γη​)). The latter bound matches the known lower bound up to logarithmic factors, showing that algorithms with additional access to controlled Hamiltonian evolution cannot improve the query complexity for ground-state preparation beyond logarithmic factors. Both algorithms are based on a simple mechanism that we call the spectral descent principle, in which the algorithm starts from the input state ∣ψ⟩|ψ\rangle∣ψ⟩ and progressively descends through the energy spectrum, moving closer to the ground state until the desired fidelity is reached. We also extend this framework to ground-state property and energy estimation and give explicit complexity guarantees for both tasks.
Estimating ground state energies of many-body Hamiltonians is a central task in many areas of quantum physics. In this Letter, we give quantum algorithms which, given any k-body Hamiltonian H, compute an estimate for the ground state energy and prepare a quantum state achieving said energy, respectively. Specifically, for any ϵ>0, our algorithms return, with high probability, an estimate of the ground state energy of H within additive error ϵM, or a quantum state with the corresponding energy. Here, M is the total strength of all interaction terms, which in general is extensive in the system size. Our approach makes no assumptions about the geometry or spatial locality of interaction terms of the input Hamiltonian and thus handles even long-range or all-to-all interactions, such as in quantum chemistry, where lattice-based techniques break down. In this fully general setting, the run-time of our algorithms scales as 2^{cn/2} for c<1, yielding the first quantum algorithms for low-energy estimation breaking a standard square root Grover speedup for unstructured search. The core of our approach is remarkably simple, and relies on showing that an extensive fraction of the interactions can be neglected with a controlled error. What this ultimately implies is that even arbitrary k-local Hamiltonians have structure in their low energy space, in the form of an exponential-dimensional low energy subspace.
The local Hamiltonian (LH) problem is the canonical QMA\mathsf{QMA}QMA-complete problem introduced by Kitaev. In this paper, we show its hardness in a very strong sense: we show that the 3-local Hamiltonian problem on nnn qubits cannot be solved classically in time O(2(1−ε)n)O(2^{(1-\varepsilon)n})O(2(1−ε)n) for any ε>0\varepsilon>0ε>0 under the Strong Exponential-Time Hypothesis (SETH), and cannot be solved quantumly in time O(2(1−ε)n/2)O(2^{(1-\varepsilon)n/2})O(2(1−ε)n/2) for any ε>0\varepsilon>0ε>0 under the Quantum Strong Exponential-Time Hypothesis (QSETH). These lower bounds give evidence that the currently known classical and quantum algorithms for LH cannot be significantly improved. Furthermore, we are able to demonstrate fine-grained complexity lower bounds for approximating the quantum partition function (QPF) with an arbitrary constant relative error. Approximating QPF with relative error is known to be equivalent to approximately counting the dimension of the solution subspace of QMA\mathsf{QMA}QMA problems. We show the SETH and QSETH hardness to estimate QPF with constant relative error. We then provide a quantum algorithm that runs in O(2n)O(\sqrt{2^n})O(2n​) time for an arbitrary 1/poly(n)1/\mathrm{poly}(n)1/poly(n) relative error, matching our lower bounds and improving the state-of-the-art algorithm by Bravyi, Chowdhury, Gosset, and Wocjan (Nature Physics 2022) in the low-temperature regime. To prove our fine-grained lower bounds, we introduce the first size-preserving circuit-to-Hamiltonian construction that encodes the computation of a TTT-time quantum circuit acting on NNN qubits into a (d+1)(d+1)(d+1)-local Hamiltonian acting on N+O(T1/d)N+O(T^{1/d})N+O(T1/d) qubits. This improves the standard construction based on the unary clock, which uses N+O(T)N+O(T)N+O(T) qubits.
Learning about a Hamiltonian HHH from its time evolution e−iHte^{-iHt}e−iHt is a fundamental task in quantum science. A flurry of recent work has developed powerful new algorithms with provable guarantees for this task, for a variety of natural settings. Despite this, relatively little is known about lower bounds for learning Hamiltonians. In particular, in the natural setting where we assume HHH is a kkk-local Hamiltonian on nnn qubits, all existing algorithms require total evolution time at least nΩ(k)n^{Ω(k)}nΩ(k) to learn the parameters of HHH, and it remained open whether one could obtain even faster algorithms -- or at the very least, if one could obtain better runtimes for simpler tasks, such as estimating a single designated coefficient of the Hamiltonian. In this work we show the answer is essentially no, by obtaining strong lower bounds for these problems. We find that not only do kkk-local Hamiltonians require nΩ(k)n^{Ω(k)}nΩ(k) time evolution or interactions to learn, but also that in several senses, learning anything about a Hamiltonian is just as hard as learning everything. In particular, we find the same nΩ(k)n^{Ω(k)}nΩ(k) lower bound holds for learning a single coefficient of a kkk-local Hamiltonian HHH, even if the rest of HHH is already known. We also show an nΩ(k)n^{Ω(k)}nΩ(k) lower bound for the task of effective Hamiltonian learning, where one seeks only to learn a unitary that approximately implements time evolution of HHH. Several related lower bounds, such as for general sparse (but not necessarily local) HHH are also given. On the technical side, we make a new connection between Hamiltonian learning lower bounds and the analysis of Boolean functions, where we introduce a novel extremal property that may be of independent interest.
The ground state energy and the free energy of Quantum Local Hamiltonians are fundamental quantities in quantum many-body physics, however, it is QMA-Hard to estimate them in general. In this paper, we develop new techniques to find classical, additive error product-state approximations for these quantities on certain families of Quantum kkk-Local Hamiltonians. Namely, those which are either dense, have low threshold rank, or are defined on a sparse graph that excludes a fixed minor, building on the methods and the systems studied by Brandão and Harrow, Gharibian and Kempe, and Bansal, Bravyi and Terhal. We present two main technical contributions. First, we discuss a connection between product-state approximations of local Hamiltonians and combinatorial graph property testing. We develop a series of weak Szemerédi regularity lemmas for kkk-local Hamiltonians, built on those of Frieze and Kannan and others. We use them to develop constant time sampling algorithms, and to characterize the `vertex sample complexity' of the Local Hamiltonian problem, in an analog to a classical result by Alon, de la Vega, Kannan and Karpinski. Second, we build on the information-theoretic product-state approximation techniques by Brandão and Harrow, extending their results to the free energy and to an asymmetric graph setting. We leverage this structure to define families of algorithms for the free energy at low temperatures, and new algorithms for certain sparse graph families.