The Guided Local Hamiltonian Problem (GLHP) is the problem of ground state energy estimation and preparation given a guiding state having good overlap with the true ground state. The problem is known to be BQP-complete for small error but is classically tractable for larger error. In this work, we identify an orthogonal regime in which the problem is classically tractable, namely when the true ground state $ψ$ has polynomially bounded $\ell_1$-norm. In particular, we show that the Truncated Power Method (TPM), a classical algorithm introduced by Kirby et al. in the quantum context, has a runtime that is polynomially comparable to quantum algorithms for GLHP in all relevant parameters, except for an extra factor of $\|ψ\|_1^2$. In other words, if $\|ψ\|_1^2$ is polynomially bounded, then TPM dequantizes quantum algorithms for GLHP.
The Guided Local Hamiltonian Problem (GLHP) is the problem of ground state energy estimation and preparation given a guiding state having good overlap with the true ground state. The problem is known to be BQP-complete for small error but is classically tractable for larger error. In this work, we identify an orthogonal regime in which the problem is classically tractable, namely when the true ground state ψ has polynomially bounded ℓ1-norm. In particular, we show that the Truncated Power Method (TPM), a classical algorithm introduced by Kirby et al. in the quantum context, has a runtime that is polynomially comparable to quantum algorithms for GLHP in all relevant parameters, except for an extra factor of ∥ψ∥12. In other words, if ∥ψ∥12 is polynomially bounded, then TPM dequantizes quantum algorithms for GLHP.
Estimating the ground state energy of a local Hamiltonian is a central problem in quantum chemistry. In order to further investigate its complexity and the potential of quantum algorithms for quantum chemistry, Gharibian and Le Gall (STOC 2022) recently introduced the guided local Hamiltonian problem (GLH), which is a variant of the local Hamiltonian problem where an approximation of a ground state (which is called a guiding state) is given as an additional input. Gharibian and Le Gall showed quantum advantage (more precisely, BQP-completeness) for GLH with 6-local Hamiltonians when the guiding state has fidelity (inverse-polynomially) close to 1/2 with a ground state. In this paper, we optimally improve both the locality and the fidelity parameter: we show that the BQP-completeness persists even with 2-local Hamiltonians, and even when the guiding state has fidelity (inverse-polynomially) close to 1 with a ground state. Moreover, we show that the BQP-completeness also holds for 2-local physically motivated Hamiltonians on a 2D square lattice or a 2D triangular lattice. Beyond the hardness of estimating the ground state energy, we also show BQP-hardness persists when considering estimating energies of excited states of these Hamiltonians instead. Those make further steps towards establishing practical quantum advantage in quantum chemistry.
Estimating the ground state energy of a local Hamiltonian is a central problem in quantum chemistry. In order to further investigate its complexity and the potential of quantum algorithms for quantum chemistry, Gharibian and Le Gall (STOC 2022) recently introduced the guided local Hamiltonian problem (GLH), which is a variant of the local Hamiltonian problem where an approximation of a ground state (which is called a guiding state) is given as an additional input. Gharibian and Le Gall showed quantum advantage (more precisely, BQP-completeness) for GLH with 6-local Hamiltonians when the guiding state has fidelity (inverse-polynomially) close to 1/2 with a ground state. In this paper, we optimally improve both the locality and the fidelity parameter: we show that the BQP-completeness persists even with 2-local Hamiltonians, and even when the guiding state has fidelity (inverse-polynomially) close to 1 with a ground state. Moreover, we show that the BQP-completeness also holds for 2-local physically motivated Hamiltonians on a 2D square lattice or a 2D triangular lattice. Beyond the hardness of estimating the ground state energy, we also show BQP-hardness persists when considering estimating energies of excited states of these Hamiltonians instead. Those make further steps towards establishing practical quantum advantage in quantum chemistry.
We study the computational complexity of the Guided Local Hamiltonian problem: given a local Hamiltonian H together with a classical description of a guiding state that has non-negligible overlap with the ground state of H, estimate the ground-state energy within inverse-polynomial precision. This setting captures real-world scenarios in quantum chemistry and many-body physics, where trial states derived from classical heuristics can be used to guide quantum algorithms. We identify families of physically-motivated guiding states for which the computational hardness of ground-state energy estimation persists in the guided setting. Extending prior results for semi-classical subset states, we prove BQP-hardness for classes including fixed-weight states, matrix product states, Gaussian states, and Fendley states. Our hardness results are obtained via refined Feynman-Kitaev circuit-to-Hamiltonian constructions that explicitly expose the structural role of the guiding state in the reduction. Complementing these results, we give a constructive proof of BQP containment when the guiding state admits a polynomial-size classical description, establishing BQP-completeness for the canonical formulation of the problem. Our results show that quantum advantage persists for the newly introduced state classes, and classical methods also remain viable when said guiding states admit appropriate descriptions. Together, our results identify a Goldilocks zone of guiding states that are efficiently preparable, succinctly described, and sample-query accessible, within which quantum advantage for ground-state estimation can be meaningfully assessed. We additionally formalise the Guided Fermi-Hubbard Hamiltonian problem and prove BQP-completeness on 2D square and triangular lattices, both with and without magnetic fields, when provided with an appropriate fermionic guiding state.
Suppose we can apply the unitary U=eiH for some Hamiltonian H, and are given access to a unitary that prepares a guiding state promised to have overlap at least γ>0 with the ground space of H. Our goal is to estimate the ground-state energy of H within additive error δ>0 and success probability at least 1−ε, ε>0. How many applications of U and its inverse U−1 are necessary and sufficient? This quantity corresponds to the total Hamiltonian-simulation time needed. An upper bound O(log(1/ε)log(1/γ)/γδ) was known, and was improved to O(log(1/ε)/γδ) very recently [JW26]. A matching lower bound was known whenever one of the three parameters δ,γ,ε was held constant [MdW26]. In this paper we prove the joint lower bound Ω(log(1/ε)/γδ) with the tight ε-dependence provided the dimension of H is at least log(1/ε)/γ2. Furthermore, we show that this same lower bound (with slightly larger dimension) holds for both the special case in which the ground state is guaranteed to be unique and H has a gap of δ between its first and second eigenvalue; and for ground-state preparation, where δ denotes the spectral gap and ε now is the approximation error. The lower bounds also apply when the Hamiltonian can be accessed via its block-encoding, and when fractional powers of U are allowed, as in continuous-time Hamiltonian simulation. Lastly, improved upper bounds are known when H is nonnegative and presented as a sum of squares; and our results imply the lower bound Ω(log(1/ε)/γδ) for this case.
In the problem of ground-state energy estimation, one aims to estimate the smallest eigenvalue of a Hamiltonian, often given a guiding state, with some promised overlap γ with the ground space. The main approach to this problem is to simulate its evolution, and estimate the smallest (or equivalently, largest) eigenphase of the resulting unitary U. We give a quantum algorithm that estimates the largest eigenphase of a unitary U in this guided setting using a factor of logγ1 fewer queries to U than the previous best approach. The result matches an existing lower bound, and answers an open question from Mande and de Wolf. The algorithm is based on transducers, which often allow composition of quantum algorithms without overhead from error reduction.
We construct classical algorithms computing an approximation of the ground state energy of an arbitrary k-local Hamiltonian acting on n qubits. We first consider the setting where a good ``guiding state'' is available, which is the main setting where quantum algorithms are expected to achieve an exponential speedup over classical methods. We show that a constant approximation (i.e., an approximation with constant relative accuracy) of the ground state energy can be computed classically in poly(1/χ,n) time and poly(n) space, where χ denotes the overlap between the guiding state and the ground state (as in prior works in dequantization, we assume sample-and-query access to the guiding state). This gives a significant improvement over the recent classical algorithm by Gharibian and Le Gall (SICOMP 2023), and matches (up a to polynomial overhead) both the time and space complexities of quantum algorithms for constant approximation of the ground state energy. We also obtain classical algorithms for higher-precision approximation. For the setting where no guided state is given (i.e., the standard version of the local Hamiltonian problem), we obtain a classical algorithm computing a constant approximation of the ground state energy in 2O(n) time and poly(n) space. To our knowledge, before this work it was unknown how to classically achieve these bounds simultaneously, even for constant approximation. We also discuss complexity-theoretic aspects of our results.