Optimal Lower Bound for Ground-State Energy Estimation with a Guiding State
Abstract
Suppose we can apply the unitary U=ei H 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.
Related
- Optimal Ground-State Preparation with a Guiding State
- Ground state energy estimation and preparation by the truncated power method
- Compiling the 2D Fermi-Hubbard ground-state energy estimation algorithm for active volume quantum architectures
- Low-Depth Initial-State Preparation for Ground-State Energy Estimation of Two-Dimensional Strongly Correlated Systems
- Long-term yields of short-rate models as Feynman-Kac ground states: a variational quantum eigensolver with single-setting energy estimation on two NISQ platforms
BibTeX
@misc{somma2026optimal,
title = {{Optimal Lower Bound for Ground-State Energy Estimation with a Guiding State}},
author = {Rolando D. Somma and Ronald de Wolf},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2608.24493},
eprint = {2608.24493},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2608.24493},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - Optimal Lower Bound for Ground-State Energy Estimation with a Guiding State
AU - Rolando D. Somma
AU - Ronald de Wolf
PY - 2026
DA - 2026/09/30
PB - arXiv
DO - 10.48550/arxiv.2608.24493
UR - https://arxiv.org/abs/2608.24493
AB - Suppose we can apply the unitary U=e^i H 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.
ER -