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:2009.04993

Short proof of a spectral Chernoff bound for local Hamiltonians

Nilin Abrahamsen

Published Sep 10, 2020• 0 citations
arXivHTMLPDF

Abstract

We give a simple proof of a Chernoff bound for the spectrum of a $k$-local Hamiltonian based on Weyl's inequalities. The complexity of estimating the spectrum's $ε(n)$-th quantile up to constant relative error thus exhibits the following dichotomy: For $ε(n)=d^{-n}$ the problem is NP-hard and maybe even QMA-hard, yet there exists constant $a>1$ such that the problem is trivial for $ε(n)=a^{-n}$. We note that a related Chernoff bound due to Kuwahara and Saito (Ann. Phys. '20) for a generalized problem is also sufficient to establish such a dichotomy, its proof relying on a careful analysis of the \emph{cluster expansion}.

DOI
10.48550/arxiv.2009.04993

Related papers

Simple and deterministic spectral concentration bound for local Hamiltonians

Nilin Abrahamsen

We give a simple proof of a Chernoff bound for the spectrum of a $k$-local Hamiltonian based on Weyl's inequalities. The complexity of estimating the spectrum's $\epsilon(n)$-th quantile up to constant relative error thus exhibits the following dichotomy: For $\epsilon(n)=d^{-n}$ the problem is NP-hard and maybe even QMA-hard, yet there exists constant $a>1$ such that the problem is trivial for $\epsilon(n)=a^{-n}$.

Quantum Information and Computation•Dec 1, 2023•0 citations

A Note on the Complexity of the Spectral Gap Problem

Justin Yirka

The problem of estimating the spectral gap of a local Hamiltonian is known to be contained in the class $P^{QMA[log]}$: polynomial time with access to a logarithmic number of QMA queries. The problem was shown to be hard for $P^{UQMA[log]}$, a weaker class, under Turing reductions by Gharibian and Yirka [arXiv:1606.05626]. I give a brief proof that the Spectral Gap problem is QMA-hard under a many-one (Karp) reduction. Consequently, the problem is $P^{QMA[log]}$-complete under truth-table reductions. It remains open to characterize the complexity of the Spectral Gap problem under many-one reductions. I conjecture that the problem belongs to a strict subclass of $P^{QMA[log]}$.

arXiv:2503.02747•Mar 4, 2025•0 citations

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 +1 more

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.

quant-pharXiv:2609.34532•Sep 29, 2026•0 citations

Spectral gap and the exponential localization in general one-particle systems

Tomotaka Kuwahara

We investigate the relationship between the spectral gap delta E_0 and the localization length xi in general one-particle systems. A relationship for many-body systems between the spectral gap and the exponential clustering has been derived from the Lieb-Robinson bound, which reduces to the inequality xi le const. times delta E_0^{-1} for one-particle systems. This inequality, however, turned out not to be optimal qualitatively. As a refined upper bound, we here prove the inequality xi le const. times delta E_0^{-1/2} in general one-particle systems. Our proof is not based on the Lieb-Robinson bound, but on our complementary inequality related to the uncertainty principle [T. Kuwahara, J. Phys. A: Math. Theor. 46 (2013)]. We give a specific form of the upper bound and test its tightness in the tight-binding Hamiltonian with a diagonal impurity, where the localization length behaves as xi ~ delta E_0^{-1/2}. We ensure that our upper bound is quantitatively tight in the case of nearest-neighbor hopping.

arXiv:1404.7026•Apr 28, 2014•0 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

The complexity of estimating local physical quantities.

Sevag Gharibian, Justin Yirka

An important task in quantum physics is the estimation of local quantities for ground states of local Hamiltonians. Recently, [Ambainis, CCC 2014] defined the complexity class P^QMA[log], and motivated its study by showing that the physical task of estimating the expectation value of a local observable against the ground state of a local Hamiltonian is P^QMA[log]-complete. In this paper, we continue the study of P^QMA[log], obtaining the following results: (1) The P^QMA[log]-completeness result of [Ambainis, CCC 2014] above requires O(log(n))-local Hamiltonians and O(log(n))-local observables. Whether this could be improved to the more physically appealing O(1)-local setting was left as an open question. We resolve this question positively by showing that simulating even a single qubit measurement on ground states of 5-local Hamiltonians is P^QMA[log]-complete. (2) We formalize the complexity theoretic study of estimating two-point correlation functions against ground states, and show that this task is P^QMA[log]-complete. (3) P^QMA[log] is thought of as slightly harder than QMA. We give a formal justification of this intuition by exploiting the technique of hierarchical voting of [Beigel, Hemachandra, and Wechsung, SCT 1989] to show P^QMA[log] is in PP. This improves the known containment that QMA is in PP [Kitaev, Watrous, STOC 2000]. (4) A central theme of this work is the subtlety involved in the study of oracle classes in which the oracle solves a promise problem. In this vein, we identify a flaw in [Ambainis, CCC 2014] regarding a P^UQMA[log]-hardness proof for estimating spectral gaps of local Hamiltonians. By introducing a query validation technique, we build on [Ambainis, CCC 2014] to obtain P^UQMA[log]-hardness for estimating spectral gaps under polynomial-time Turing reductions.

•Jun 17, 2016•0 citations
We give a simple proof of a Chernoff bound for the spectrum of a kkk-local Hamiltonian based on Weyl's inequalities. The complexity of estimating the spectrum's ε(n)ε(n)ε(n)-th quantile up to constant relative error thus exhibits the following dichotomy: For ε(n)=d−nε(n)=d^{-n}ε(n)=d−n the problem is NP-hard and maybe even QMA-hard, yet there exists constant a>1a>1a>1 such that the problem is trivial for ε(n)=a−nε(n)=a^{-n}ε(n)=a−n. We note that a related Chernoff bound due to Kuwahara and Saito (Ann. Phys. '20) for a generalized problem is also sufficient to establish such a dichotomy, its proof relying on a careful analysis of the \emph{cluster expansion}.
We give a simple proof of a Chernoff bound for the spectrum of a kkk-local Hamiltonian based on Weyl's inequalities. The complexity of estimating the spectrum's ϵ(n)\epsilon(n)ϵ(n)-th quantile up to constant relative error thus exhibits the following dichotomy: For ϵ(n)=d−n\epsilon(n)=d^{-n}ϵ(n)=d−n the problem is NP-hard and maybe even QMA-hard, yet there exists constant a>1a>1a>1 such that the problem is trivial for ϵ(n)=a−n\epsilon(n)=a^{-n}ϵ(n)=a−n.
The problem of estimating the spectral gap of a local Hamiltonian is known to be contained in the class PQMA[log]P^{QMA[log]}PQMA[log]: polynomial time with access to a logarithmic number of QMA queries. The problem was shown to be hard for PUQMA[log]P^{UQMA[log]}PUQMA[log], a weaker class, under Turing reductions by Gharibian and Yirka [arXiv:1606.05626]. I give a brief proof that the Spectral Gap problem is QMA-hard under a many-one (Karp) reduction. Consequently, the problem is PQMA[log]P^{QMA[log]}PQMA[log]-complete under truth-table reductions. It remains open to characterize the complexity of the Spectral Gap problem under many-one reductions. I conjecture that the problem belongs to a strict subclass of PQMA[log]P^{QMA[log]}PQMA[log].
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.
We investigate the relationship between the spectral gap delta E_0 and the localization length xi in general one-particle systems. A relationship for many-body systems between the spectral gap and the exponential clustering has been derived from the Lieb-Robinson bound, which reduces to the inequality xi le const. times delta E_0^{-1} for one-particle systems. This inequality, however, turned out not to be optimal qualitatively. As a refined upper bound, we here prove the inequality xi le const. times delta E_0^{-1/2} in general one-particle systems. Our proof is not based on the Lieb-Robinson bound, but on our complementary inequality related to the uncertainty principle [T. Kuwahara, J. Phys. A: Math. Theor. 46 (2013)]. We give a specific form of the upper bound and test its tightness in the tight-binding Hamiltonian with a diagonal impurity, where the localization length behaves as xi ~ delta E_0^{-1/2}. We ensure that our upper bound is quantitatively tight in the case of nearest-neighbor hopping.
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.
An important task in quantum physics is the estimation of local quantities for ground states of local Hamiltonians. Recently, [Ambainis, CCC 2014] defined the complexity class P^QMA[log], and motivated its study by showing that the physical task of estimating the expectation value of a local observable against the ground state of a local Hamiltonian is P^QMA[log]-complete. In this paper, we continue the study of P^QMA[log], obtaining the following results: (1) The P^QMA[log]-completeness result of [Ambainis, CCC 2014] above requires O(log(n))-local Hamiltonians and O(log(n))-local observables. Whether this could be improved to the more physically appealing O(1)-local setting was left as an open question. We resolve this question positively by showing that simulating even a single qubit measurement on ground states of 5-local Hamiltonians is P^QMA[log]-complete. (2) We formalize the complexity theoretic study of estimating two-point correlation functions against ground states, and show that this task is P^QMA[log]-complete. (3) P^QMA[log] is thought of as slightly harder than QMA. We give a formal justification of this intuition by exploiting the technique of hierarchical voting of [Beigel, Hemachandra, and Wechsung, SCT 1989] to show P^QMA[log] is in PP. This improves the known containment that QMA is in PP [Kitaev, Watrous, STOC 2000]. (4) A central theme of this work is the subtlety involved in the study of oracle classes in which the oracle solves a promise problem. In this vein, we identify a flaw in [Ambainis, CCC 2014] regarding a P^UQMA[log]-hardness proof for estimating spectral gaps of local Hamiltonians. By introducing a query validation technique, we build on [Ambainis, CCC 2014] to obtain P^UQMA[log]-hardness for estimating spectral gaps under polynomial-time Turing reductions.