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

• URL: http://arxiv.org/abs/2608.24493v1
• Date: Tue, 25 Aug 2026 12:43:54 GMT
• Title: Optimal Lower Bound for Ground-State Energy Estimation with a Guiding State
• Abstract summary: We prove the joint lower bound $(log(1/varepsilon)/)$ with the tight $varepsilon$-dependence.<n>We show that this same lower bound 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.
• Score: 0.5947766849585866
• License: http://creativecommons.org/licenses/by/4.0/
• 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 $γ>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)/γ^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 $\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.

Related papers

• Sparse Quantum State Preparation with Sublinear T-Count [5.929956715430168]
  We show that any $n$-qubit $s$-sparse state can be prepared up to error $$ using $widetildeO(mins, n3/4sqrts+sqrtslog (1/)+log (1/)$ $T$ gates.<n>For every $0le$ and $2le sle 2n/2$, sparse-state preparation requires $(mins,sqrtns)$ $T
  arXiv  Detail & Related papers  (2026-08-01T03:33:19Z)
• Near-Optimal Dimension Lower Bounds for Single-Vector Embeddings of Maximum Inner Product Similarity [75.14269295861845]
  For singleton queries, Chamfer becomes maximum inner product similarity (MAX-IP)<n>For every fixed $in(0,1)$, there are constants $A_,c_>0$.<n>Unit-sphere MAX-IP matrix is an exact two-valued affine image of the DNF pattern matrix with gap of at least $8$.
  arXiv  Detail & Related papers  (2026-07-22T17:27:20Z)
• Hardness of High-Dimensional Linear Classification [58.29089693778071]
  We establish new exponential in dimension lower bounds for the Maximum Halfspace Discrepancy problem.<n>Both are fundamental problems in computational geometry and machine learning in their exact and approximate forms.
  arXiv  Detail & Related papers  (2026-03-19T15:53:41Z)
• Inverse-free quantum state estimation with Heisenberg scaling [4.191671741497842]
  We present an inverse-free pure quantum state estimation protocol that achieves Heisenberg scaling.<n>Our result implies a query upper bound $O(mind3/2/varepsilon,1/varepsilon2)$ for inverse-free amplitude estimation.
  arXiv  Detail & Related papers  (2025-10-29T17:48:46Z)
• Approximating the operator norm of local Hamiltonians via few quantum states [53.16156504455106]
  Consider a Hermitian operator $A$ acting on a complex Hilbert space of $2n$.<n>We show that when $A$ has small degree in the Pauli expansion, or in other words, $A$ is a local $n$-qubit Hamiltonian.<n>We show that whenever $A$ is $d$-local, textiti.e., $deg(A)le d$, we have the following discretization-type inequality.
  arXiv  Detail & Related papers  (2025-09-15T14:26:11Z)
• Near-Optimal Convergence of Accelerated Gradient Methods under Generalized and $(L_0, L_1)$-Smoothness [57.93371273485736]
  We study first-order methods for convex optimization problems with functions $f$ satisfying the recently proposed $ell$-smoothness condition $||nabla2f(x)|| le ellleft(||nabla f(x)||right),$ which generalizes the $L$-smoothness and $(L_0,L_1)$-smoothness.
  arXiv  Detail & Related papers  (2025-08-09T08:28:06Z)
• Coresets for Multiple $\ell_p$ Regression [47.790126028106734]
  We construct coresets of size $tilde O(varepsilon-2d)$ for $p2$ and $tilde O(varepsilon-pdp/2)$ for $p>2$. For $1p2$, every matrix has a subset of $tilde O(varepsilon-1k)$ rows which spans a $(varepsilon-1k)$-approximately optimal $k$-dimensional subspace for $ell_p$ subspace approximation
  arXiv  Detail & Related papers  (2024-06-04T15:50:42Z)
• Area laws and tensor networks for maximally mixed ground states [4.527719466355631]
  We show an area law in the mutual information for the maximally-mixed state $Omega$ in the ground space of general Hamiltonians.<n>Similarities are derived for the mutual information of 2D frustration-free and locally-gapped local Hamiltonians.
  arXiv  Detail & Related papers  (2023-10-29T14:36:30Z)
• $\boldsymbol{\alpha_{>}(\epsilon) = \alpha_{<}(\epsilon)}$ For The Margolus-Levitin Quantum Speed Limit Bound [0.0]
  I show that $alpha_>(epsilon)$ is indeed equal to $alpha_(epsilon)$. I also point out a numerical stability issue in computing $alpha_>(epsilon)$.
  arXiv  Detail & Related papers  (2023-05-17T10:07:31Z)
• Sparse Dimensionality Reduction Revisited [13.170012290527017]
  The sparse Johnson-Lindenstrauss transform is one of the central techniques in dimensionality reduction. We revisit sparse embeddings and identify a loophole in the lower bound. We also improve the sparsity of the best oblivious subspace embeddings for optimal embedding dimensionality.
  arXiv  Detail & Related papers  (2023-02-13T08:01:25Z)
• Low-Rank Approximation with $1/\epsilon^{1/3}$ Matrix-Vector Products [58.05771390012827]
  We study iterative methods based on Krylov subspaces for low-rank approximation under any Schatten-$p$ norm. Our main result is an algorithm that uses only $tildeO(k/sqrtepsilon)$ matrix-vector products.
  arXiv  Detail & Related papers  (2022-02-10T16:10:41Z)
• Learning low-degree functions from a logarithmic number of random queries [77.34726150561087]
  We prove that for any integer $ninmathbbN$, $din1,ldots,n$ and any $varepsilon,deltain(0,1)$, a bounded function $f:-1,1nto[-1,1]$ of degree at most $d$ can be learned.
  arXiv  Detail & Related papers  (2021-09-21T13:19:04Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.