⚛️ quantum physics

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

This paper establishes a tight joint lower bound of $\Omega(\log(1/\varepsilon)/\gamma\delta)$ on the query complexity for estimating the ground-state energy of a Hamiltonian given a guiding state with overlap $\gamma$ , matching recent upper bounds and extending to scenarios involving unique ground states, ground-state preparation, block-encodings, and nonnegative Hamiltonians.

Original authors: Rolando D. Somma, Ronald de Wolf

Published 2026-08-26

📖 7 min read🧠 Deep dive

CC BY 4.0

Original authors: Rolando D. Somma, Ronald de Wolf

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

In the world of quantum chemistry, scientists often need to solve a specific, difficult puzzle: finding the lowest possible energy level of a complex system, known as the ground-state energy. This value is crucial because it dictates how molecules behave, how they bond, and how they react. To find this number, researchers use a quantum computer to simulate the system, but the simulation is not a simple calculation; it is a process of listening to the system's natural rhythm. The system is described by a mathematical object called a Hamiltonian, which acts like a map of all possible energy states. By applying a specific operation that mimics the passage of time, the computer can reveal the system's energy levels as distinct frequencies.

The challenge lies in the fact that while the computer can easily listen to these frequencies, it does not know which one is the lowest. To find the answer, the computer needs a starting point, a hint about where the lowest energy might be hiding. This hint is called a guiding state. Imagine trying to find the deepest point in a vast, dark ocean. If you have no idea where to look, you might swim in circles forever. But if you have a sonar ping that tells you the deepest point is somewhere within a certain radius, you can focus your search. In the quantum world, this "sonar ping" is a guiding state that is guaranteed to have some overlap with the true lowest energy state. The better the overlap, the easier the search should be. For years, scientists have known how to use this hint to find the energy, but they have been unsure about the absolute limit of how efficient this search can be. They knew there was a ceiling on how fast the answer could be found, but they did not know if that ceiling was the true wall or just a temporary barrier.

A team of researchers has now proven what that true wall looks like. They demonstrated that the number of times a quantum computer must interact with the system to find the ground-state energy is strictly determined by three factors: how precise the answer needs to be, how strong the initial hint is, and how often the computer is allowed to make a mistake. Their work shows that there is a fundamental limit to how much faster the search can go, no matter how clever the algorithm becomes. They proved that if you want the answer to be very precise, or if your initial hint is very weak, the computer must perform a specific, minimum number of interactions. This limit is not just a suggestion or a trend; it is a mathematical certainty that holds true across a wide range of scenarios.

The researchers focused on a problem where the computer is given a guiding state that is promised to share at least a certain amount of similarity with the true ground state. They asked a simple but profound question: what is the minimum number of steps required to guarantee the correct answer within a specific margin of error? They found that the answer depends on a delicate balance. If the desired precision is high, the number of steps increases. If the guiding state is a poor match for the true ground state, the number of steps increases significantly. Even the tolerance for error plays a role; if the computer is allowed to be wrong more often, it can find the answer faster, but if it must be almost always correct, the cost rises. The team showed that the relationship between these factors is linear and unavoidable. They proved that you cannot bypass this cost by using a smarter trick or a different type of computer, provided the computer follows the standard rules of quantum mechanics.

To reach this conclusion, the team constructed a series of difficult test cases designed to trick the most advanced algorithms. They created scenarios where the ground state was hidden in a vast space of possibilities, and the guiding state was only a faint whisper of the truth. In one version of their test, the ground state was not unique, meaning there were many different states that shared the lowest energy. In another, they forced the ground state to be unique, with a clear gap separating it from the next lowest energy level. In both cases, they showed that any algorithm trying to find the energy would fail if it tried to do so with fewer steps than their calculated limit. They used a method that treats the computer's output as a mathematical curve, showing that this curve cannot rise or fall fast enough to distinguish the correct answer from the wrong ones without a sufficient number of interactions.

The findings are particularly significant because they match the best possible performance that other researchers have recently achieved. This means the limit is not just a theoretical barrier; it is a practical reality that has already been reached by the most efficient known methods. The work confirms that the current state-of-the-art algorithms are essentially perfect; there is no hidden shortcut waiting to be discovered that would allow for a dramatic reduction in the number of steps. The researchers also showed that this limit applies even when the system is accessed in different ways, such as through a block-encoding method, which is a common technique for handling complex quantum systems. Furthermore, they proved that the same limit applies whether the goal is to find the energy value or to actually prepare the ground state itself, a task that is often even harder.

One surprising aspect of their proof is that the hardest cases they constructed involved guiding states that were effectively useless, despite technically meeting the requirement of having some overlap with the ground state. In these difficult scenarios, the guiding state pointed to a region that contained the ground state but also contained a vast amount of irrelevant information. This suggests that the standard requirement for a guiding state—simply having a certain amount of overlap—might not be the best way to frame the problem. The researchers noted that for the problem to be truly solvable in an efficient manner, the guiding state might need to provide more genuine, useful information about the ground state, rather than just a vague statistical connection. This observation opens a new line of inquiry for future research, suggesting that the way we define a "good" starting point for quantum simulations might need to be rethought.

The paper also touches on a specific technique called spectral amplification, which is used to speed up these calculations by treating the system as a sum of squares. This method allows the computer to amplify the signal of the ground state, effectively making the gap between the lowest energy and the next one appear larger. The researchers showed that even with this powerful tool, the fundamental limit they discovered still holds, though the relationship between the parameters changes slightly. This confirms that while spectral amplification is a near-optimal strategy, it cannot break the underlying laws of quantum query complexity. The work serves as a definitive boundary marker for the field, telling scientists exactly how far they can push their current tools and where the hard limits of nature begin.

In the end, this research provides a clear map of the terrain for quantum ground-state energy estimation. It tells us that while we can make the search faster by improving our guiding states or accepting a bit more error, there is a hard floor beneath which we cannot go. The number of steps required is not a matter of engineering ingenuity but a fundamental property of the information available. For those building quantum computers to solve chemical problems, this result is both a constraint and a relief. It is a constraint because it sets a firm limit on efficiency, but it is a relief because it confirms that the best algorithms we have are already doing everything that is physically possible. The journey to find the lowest energy of a molecule is now understood to have a fixed cost, and that cost has been precisely calculated.

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

Problem Definition
The paper addresses the "guided Hamiltonian problem," a fundamental task in quantum chemistry and quantum computing. The objective is to estimate the ground-state energy (the smallest eigenvalue $\lambda_{\min}$ ) of a Hamiltonian $H$ , given:

Access to the unitary $U = e^{iH}$ (and its inverse $U^{-1}$ ), where eigenvalues of $H$ are normalized to $[0, 2\pi - 2\delta)$ .
Access to a unitary $A$ that prepares a "guiding state" $A|0\rangle$ with a guaranteed overlap of at least $\gamma > 0$ with the ground space of $H$ .

The goal is to estimate $\lambda_{\min}$ within an additive error $\delta$ with a success probability of at least $1-\epsilon$ . The primary metric of interest is the query complexity: the number of applications of $U$ and $U^{-1}$ required. While upper bounds were known, the optimal dependence on all three parameters ( $\delta$ , $\gamma$ , and $\epsilon$ ) simultaneously remained an open question.

Methodology
The authors employ the polynomial method to establish lower bounds on the query complexity. The core approach involves:

Reduction to Decision Problems: The estimation problem is reduced to distinguishing between specific instances of Hamiltonians (e.g., distinguishing a zero eigenvalue from a non-zero eigenvalue within a specific range).
Fractional Queries: The authors analyze algorithms making "fractional queries" to the underlying bit string encoded in the Hamiltonian's phases. They utilize a variant of the polynomial method (Lemma 3.2 and Lemma 4.2) to show that the acceptance probability of a quantum algorithm making $T$ queries can be approximated by a low-degree real polynomial.
Approximation Theory: The lower bound is derived by analyzing the degree of polynomials required to approximate specific functions (related to the Hamming weight of input strings or the overlap parameter $a$ $a$ ). The authors leverage:
- Coppersmith-Rivlin inequalities to bound polynomial growth on intervals.
- Chebyshev polynomials and their extremal properties to establish that polynomials cannot grow too rapidly without increasing their degree.
- Symmetrization techniques to convert multivariate polynomials (dependent on input bits) into univariate polynomials (dependent on Hamming weight or overlap parameters).

Key Contributions and Results

Joint Lower Bound: The paper proves a tight lower bound of $\Omega(\log(1/\epsilon)/\gamma\delta)$ applications of $U$ and $U^{-1}$ . This result matches the recently improved upper bound by Jeffery and Witteveen [JW26], establishing optimality in all three parameters ( $\delta, \gamma, \epsilon$ ) simultaneously.
- Condition: This bound holds provided the dimension of the Hilbert space is at least $\Omega(\log(1/\epsilon)/\gamma^2)$ .
Unique Ground State Case: The authors extend the result to the more physically relevant scenario where the ground state is unique and separated from the first excited state by a spectral gap of at least $\delta$ .
- Result: The same lower bound $\Omega(\log(1/\epsilon)/\gamma\delta)$ holds, though it requires a larger dimension of $O(\log(1/\epsilon)^2/\gamma^2)$ .
- Implication: This resolves an open question from [MdW26] regarding the hardness of the unique ground state case.
Ground-State Preparation: The paper demonstrates that the same lower bound applies to the task of preparing a ground state (approximating the eigenvector) within trace distance $\epsilon$ , assuming a spectral gap $\delta$ and overlap $\gamma$ . This is shown via a reduction from the energy estimation problem.
Extensions to Other Models:
- Block-Encoding: The lower bounds extend to the block-encoding model, where $H$ is accessed via a unitary $V$ such that $\langle 0|V|0\rangle = H$ .
- Spectral Amplification (SOSSA): The authors analyze the case where $H$ is presented as a sum of squares ( $H=G^\dagger G$ ) and accessed via a "square root" operator $G$ . They derive a lower bound of $\Omega(\log(1/\epsilon)/\gamma\sqrt{\delta})$ for queries to $G$ . This implies that the quadratic improvement in error dependence offered by Sum-of-Squares Spectral Amplification (SOSSA) is near-optimal when treating $G$ as a black box.

Significance and Claims
The paper claims to provide the optimal query complexity for guided ground-state energy estimation. By proving that the dependence on the error probability $\epsilon$ is logarithmic ( $\log(1/\epsilon)$ ) rather than linear, and that this dependence is necessary even when the overlap $\gamma$ and precision $\delta$ are small, the work settles the complexity landscape for this problem.

The authors note that their "hard families" of instances involve guiding states that are effectively independent of the specific ground state (having overlap spread uniformly or concentrated in a trivial state), suggesting that the standard requirement of "large overlap" might not be the most informative constraint for the problem's difficulty. However, within the standard query model defined, the derived bounds are tight.

The paper explicitly states that these results do not apply to the sparse-matrix access model (where $H$ is $d$ -sparse), leaving the inclusion of the sparsity parameter $d$ in the lower bound as an open problem.

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

More like this