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.
AI Summary
The paper asks when guided ground-state energy estimation and preparation admit efficient classical algorithms even at inverse-polynomial precision. It analyzes the truncated power method (TPM): repeatedly apply $A=\alpha I-H$, retain the $k$ largest-magnitude amplitudes, and normalize. Inputs are a classical Pauli decomposition $H=\sum_{j=1}^M h_jP_j$, with $\alpha=\sum_j|h_j|$, and an explicitly sparse guiding vector with ground-state overlap squared at least $\delta$.
For a unique normalized ground state $\psi$, TPM estimates its energy within additive error $\varepsilon$ in $\widetilde O(\|\psi\|_1^2M\alpha^3/(\delta\varepsilon^3)+MS)$ time, where $S$ is the guiding vector’s support size. This guarantee requires no spectral-gap bound. Given gap lower bound $\Delta$, it outputs an explicit vector with fidelity at least $1-\eta$ in $\widetilde O(\|\psi\|_1^2M\alpha^3\Delta^{-3}\max\{1/\delta,1/\eta\}+MS)$ time. Thus polynomially bounded $\|\psi\|_1^2$ gives polynomial-time algorithms when the remaining parameters scale appropriately, extending earlier support-size-dependent guarantees.
The proofs bound overlap loss under truncation using the ground state’s $\ell_1$ norm. Energy estimation combines cosine growth with Rayleigh-quotient monotonicity; preparation tracks tangent contraction toward a small fixed point. Degenerate-ground-space guarantees use a worst-case ground-space $\ell_1$ parameter. A separate tomography result gives a tight, up to logarithms, $\widetilde\Theta(\|\psi\|_1^2/\eta^{3/2})$ worst-case controlled-query bound.
The stated limitations are basis dependence and potentially exponential $\ell_1$ norm even for unentangled states. Precision and gap dependence remain polynomially worse than quantum benchmarks; possible improvements using Chebyshev filtering or frustration-free structure are left open.
No sign of AI-generated textAI use disclosedStrong assumptions
GPT-5.6 Sol (and above) proved our conjectures, which became the basis of our main theorems
Central claim may not hold: The abstract omits that the efficient classical guarantee assumes an explicitly supplied, polynomially supported guiding state, rather than an arbitrary efficiently quantum-preparable guide.
The preparation bounds establish polynomial comparability only with an accuracy qualification or a changed output requirement, because TPM has polynomial inverse-infidelity dependence while quantum-state preparation has logarithmic dependence.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
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.
The paper asks when guided ground-state energy estimation and preparation admit efficient classical algorithms even at inverse-polynomial precision. It analyzes the truncated power method (TPM): repeatedly apply A=αI−H, retain the k largest-magnitude amplitudes, and normalize. Inputs are a classical Pauli decomposition H=∑j=1MhjPj, with α=∑j∣hj∣, and an explicitly sparse guiding vector with ground-state overlap squared at least δ.
For a unique normalized ground state ψ, TPM estimates its energy within additive error ε in O(∥ψ∥12Mα3/(δε3)+MS) time, where S is the guiding vector’s support size. This guarantee requires no spectral-gap bound. Given gap lower bound Δ, it outputs an explicit vector with fidelity at least 1−η in O(∥ψ∥12Mα3Δ−3max{1/δ,1/η}+MS) time. Thus polynomially bounded ∥ψ∥12 gives polynomial-time algorithms when the remaining parameters scale appropriately, extending earlier support-size-dependent guarantees.
The proofs bound overlap loss under truncation using the ground state’s ℓ1 norm. Energy estimation combines cosine growth with Rayleigh-quotient monotonicity; preparation tracks tangent contraction toward a small fixed point. Degenerate-ground-space guarantees use a worst-case ground-space ℓ1 parameter. A separate tomography result gives a tight, up to logarithms, Θ(∥ψ∥12/η3/2) worst-case controlled-query bound.
The stated limitations are basis dependence and potentially exponential ℓ1 norm even for unentangled states. Precision and gap dependence remain polynomially worse than quantum benchmarks; possible improvements using Chebyshev filtering or frustration-free structure are left open.
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.
The local Hamiltonian (LH) problem, the quantum analog of the classical constraint satisfaction problem, is a cornerstone of quantum computation and complexity theory. It is known to be QMA-complete, indicating that it is challenging even for quantum computers. Interestingly, the guided local Hamiltonian (GLH) problem -- an LH problem with a guiding state that has a non-trivial overlap with the ground state -- can be efficiently solved on a quantum computer and is proved to be BQP-complete. This makes the GLH problem a valuable framework for exploring the fundamental separation between classical and quantum computation. Remarkably, the quantum algorithm for solving the GLH problem can be `dequantized' (i.e., made classically simulatable) under certain conditions, such as when only constant accuracy is required and when the Hamiltonian satisfies an unrealistic constant operator norm constraint. In this work, we relieve these restrictions by introducing a dequantized classical algorithm for a randomized quantum imaginary-time evolution quantum algorithm. We demonstrate that it achieves either limited or arbitrary constant accuracy, depending on whether the guiding state's overlap is general or exceeds a certain threshold. Crucially, our approach eliminates the constant operator norm constraint on the Hamiltonian, opening its applicability to realistic problems. Our results advance the classical solution of the GLH problem in practical settings and provide new insights into the boundary between classical and quantum computational power.
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 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.