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^{i H}$ 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-\varepsilon $, $\varepsilon>0$. How many applications of $U$ and its inverse $U^{-1}$ are necessary and sufficient? An upper bound $O(\log(1/\varepsilon)\log(1/\gamma)/\gamma\delta)$ was known, and was improved to $O(\log(1/\varepsilon)/\gamma\delta)$ very recently [JW26]. A matching lower bound was known whenever one of the three parameters $\delta,\gamma,\varepsilon$ was held constant [MdW26]. In this paper we prove the joint lower bound $\Omega(\log(1/\varepsilon)/\gamma\delta)$ with the tight $\varepsilon$-dependence provided the dimension of $H$ is at least $\log(1/\varepsilon)/\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 $\varepsilon$ 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/\varepsilon)/\gamma\sqrt{\delta})$ for this case.

Quantum Physics (quant-ph); Computational Complexity (cs.CC); Data Structures and Algorithms (cs.DS)

arXiv:2608.24493 [quant-ph]

(or arXiv:2608.24493v1 [quant-ph] for this version)

https://doi.org/10.48550/arXiv.2608.24493 Focus to learn more arXiv-issued DOI via DataCite (pending registration)

arXivLabs is a framework that allows collaborators to develop and share new arXiv features directly on our website.

Both individuals and organizations that work with arXivLabs have embraced and accepted our values of openness, community, excellence, and user data privacy. arXiv is committed to these values and only works with partners that adhere to them.

Have an idea for a project that will add value for arXiv's community? Learn more about arXivLabs.