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}$.
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 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}.
We study the computational complexity of estimating the normalized trace 2−nTr[f(A)] for a log-local Hamiltonian A acting on n qubits. This problem arises naturally in the DQC1 model, yet its complexity is only understood for a limited class of functions f(x).
We show that if f(x) is a continuous function with approximate degree Ω(poly(n)), then estimating 2−nTr[f(A)] up to constant additive error is DQC1-complete, under a technical condition on the polynomial approximation error of f(x). This condition holds for a broad class of functions, including exponentials, trigonometric functions, logarithms, and inverse-type functions. We further prove that when A is sparse, the classical query complexity of this problem is exponential in the approximate degree. Together, these results identify the approximate degree as the key parameter governing the complexity of normalized trace estimation: it characterizes both the quantum complexity (via efficient DQC1 algorithms) and the classical hardness, yielding an exponential quantum-classical separation. Our proof develops a unified framework that cleanly combines circuit-to-Hamiltonian constructions, periodic Jacobi operators, and tools from polynomial approximation theory, including the Chebyshev equioscillation theorem.
The problem of estimating the spectral gap of a local Hamiltonian is known to be contained in the class PQMA[log]: polynomial time with access to a logarithmic number of QMA queries. The problem was shown to be hard for 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]-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].
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.
The local Hamiltonian problem is famously complete for the class QMA, the quantum analogue of NP. The complexity of its semi-classical version, in which the terms of the Hamiltonian are required to commute (the CLH problem), has attracted considerable attention recently due to its intriguing nature, as well as in relation to growing interest in the qPCP conjecture. We show here that if the underlying bipartite interaction graph of the CLH instance is a good locally-expanding graph, namely, the expansion of any constant-size set is e-close to optimal, then approximating its ground energy to within additive factor O(e) lies in NP. The proof holds for k- local Hamiltonians for any constant k and any constant dimensionality of particles d. We also show that the approximation problem of CLH on such good local expanders is NP-hard. This implies that too good local expansion of the interaction graph constitutes an obstacle against quantum hardness of the approximation problem, though it retains its classical hardness. The result highlights new difficulties in trying to mimic classical proofs (in particular Dinur's PCP proof) in an attempt to prove the quantum PCP conjecture. A related result was discovered recently independently by Brandao and Harrow, for 2-local general Hamiltonians, bounding the quantum hardness of the approximation problem on good expanders, though no NP-hardness is known in that case.
Near-Optimal Bounds on the Density of Low-Energy States of k-Local Hamiltonians and Faster Quantum Algorithms
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∗(2n/2) for both problems, with the improvement depending on the relative accuracy ε 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 ε/k, our algorithms improve the exponent by a factor of 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 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.