Optimal Lower Bound for Ground-State Energy Estimation with a Guiding State

Abstract

The guided Hamiltonian problem is the following: given access to the unitary $U=e^{iH}$ for some Hamiltonian $H$, and given access to a unitary that prepares a guiding state promised to have overlap at least $\gamma >0$ with the ground space of $H$, estimate the ground-state energy of $H$ within additive error $\delta >0$ and success probability at least $1-\epsilon$, $\epsilon >0$. How many applications of $U$ and its inverse $U^{-1}$ are necessary and sufficient? An upper bound $O(\log (1/\epsilon )\log (1/\gamma )/\gamma \delta )$ was known, and was improved to $O(\log (1/\epsilon )/\gamma \delta )$ very recently [JW26]. A matching lower bound was known whenever one of the three parameters $\delta ,\gamma ,\epsilon$ was held constant [MdW26]. In this paper we prove the joint lower bound $\Omega (\log (1/\epsilon )/\gamma \delta )$ with the tight $\epsilon$-dependence provided the dimension of $H$ is at least $\log (1/\epsilon )/{\gamma }^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 $\delta$ between its first and second eigenvalue; and for ground-state preparation, where $\delta$ denotes the spectral gap and $\epsilon$ 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 $\Omega (\log (1/\epsilon )/\gamma \sqrt{\delta })$ for this case.

14 pages LaTeX