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

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 γ>0 with the ground space of H, estimate the ground-state energy of H within additive error δ> 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/γ)/γδ) was known, and was improved to O\(log(1/varepsilon\)/γδ) very recently [JW26]. A matching lower bound was known whenever one of the three parameters δ,γ,varepsilon was held constant [MdW26]. In this paper we prove the joint lower bound Ω\(log(1/varepsilon\)/γδ) with the tight varepsilon-dependence provided the dimension of H is at least log\(1/varepsilon\)/γ². 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 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 Ω\(log(1/varepsilon\)/γsqrtδ) for this case.