CS Paper Radar

Optimal Quantum Algorithm for Ground-State Energy Estimation with a Guiding State

Stacey Jeffery, Freek Witteveen

cs.CC quant-phcs.DS ·submitted 2026-08-25 12:43 UTC · v1
theoryhighly cited

Abstract

In the problem of ground-state energy estimation, one aims to estimate the smallest eigenvalue of a Hamiltonian, often given a guiding state, with some promised overlap $γ$ with the ground space. The main approach to this problem is to simulate its evolution, and estimate the smallest (or equivalently, largest) eigenphase of the resulting unitary $U$. We give a quantum algorithm that estimates the largest eigenphase of a unitary $U$ in this guided setting using a factor of $\log\frac{1}γ$ fewer queries to $U$ than the previous best approach. The result matches an existing lower bound, and answers an open question from Mande and de Wolf. The algorithm is based on transducers, which often allow composition of quantum algorithms without overhead from error reduction.

Comment
25 pages

Closest papers

Nearest neighbours by meaning across the whole index.

Near-Optimal Bounds on the Density of Low-Energy States of $k$-Local Hamiltonians and Faster Quantum Algorithms

cs.CC quant-phcs.DS ·2026-09-28 ·Sevag Gharibian, François Le Gall, Ranitha Mataraarachchi, Suguru Tamaki
theoryhot direction similarity 0.70
Abstract · 21 pages, 2 tables, 0 figures

Low-energy estimation and state preparation for general $k$-local Hamiltonians are fundamental challenges in quantum complexity theory. Buhrman et al.~ [BGLGST, PRL 2025] recently broke the natural Grover bound $O^\ast(2^{n/2})$ for both problems, with the improvement depending on the relative accuracy $\varepsilon$ and the locality $k$. In this work, we present faster exponential quantum algorithms for these problems, where the binary entropy function governs the runtime exponent. For sufficiently small $\varepsilon/k$, our algorithms improve the exponent by a factor of $\log(k/\varepsilon)$ over [BGLGST, PRL 2025]. Our main technical result is an entropy-governed lower bound on the dimension of the Hamiltonian's low-energy subspace, obtained by depolarizing its ground state. For fixed $k$, this bound is optimal up to constant factors in the exponent. The same framework yields tighter bounds for Heisenberg, $XY$, and Ising models on arbitrary interaction graphs.

0.29

Optimal Query Complexity for Ground-State Preparation

cs.CC quant-phcs.DS ·2026-09-28 ·Boyang Chen, Minbo Gao, Xinzhao Wang, Shuo Zhou
theoryhighly cited similarity 0.70
Abstract · 48 pages

We determine the optimal query complexity of ground-state preparation to trace-distance error $\varepsilon$ when an energy threshold in the spectral gap is known. Let $U_H$ be an $α$-block-encoding of a Hamiltonian with unique ground state $|ψ_0\rangle$, and suppose $|\langleψ_0|U_I|0\rangle|\geγ$ for a state-preparation oracle $U_I$. The threshold lies at least $Δ/2$ above the ground-state energy and at least $Δ/2$ below every excited-state energy. We give two algorithms that prepare a state within trace distance $\varepsilon$ of the ground state. One uses $O((α/Δ)(γ^{-1}+\log(1/\varepsilon)))$ calls to $U_H$ in expectation; the other uses $O((α/(γΔ))\log(1/\varepsilon))$ calls to $U_H$ in the worst case. We prove a lower bound matching the expected query count; the corresponding worst-case lower bound follows from Somma and de Wolf [SdW26]. The respective bounds on calls to $U_I$ are $O(1/γ)$ in expectation and $O(γ^{-1}\log(1/\varepsilon))$ in the worst case. On $(N+1)$-dimensional systems, these $U_I$ bounds are also optimal when the expected or worst-case count of $U_H$ calls, respectively, is $o((α/Δ)\sqrt N)$. Both algorithms use a constant-accuracy spectral filter to construct a purifier, which we then sequentially compose during amplitude amplification to prepare a state with constant overlap with the ground state. The expected-query algorithm repeats the preparation followed by one high-accuracy spectral filter until success. The worst-case algorithm uses filters of increasing accuracy and limits the total number of queries.

0.49

Optimal Joint Bounds for Sparse Ground-State Energy Estimation and Ground-State Preparation

cs.CC quant-phcs.DS ·2026-11-17 ·Dhrumil Patel
theory similarity 0.69
Abstract · 77 pages

Ground-state energy estimation (GSEE) and ground-state preparation (GSP) are fundamental problems in quantum computing. Given a Hamiltonian $H$ with $\|H\|\le1$ and a guiding state $|ψ\rangle$ with overlap at least $γ>0$ with the ground space of $H$, the goal in GSEE is to estimate the ground-state energy of $H$ to additive error $δ$ with failure probability at most $\varepsilon$, while in GSP it is to prepare a state with ground-space weight at least $1-\varepsilon$, given a gap lower bound $Δ$. Their costs are measured by quantum query complexity, i.e., the number of oracle calls needed to access $H$. Recent work proved optimal bounds $Θ(\log(1/\varepsilon)/(γδ))$ for GSEE and $Θ(\log(1/\varepsilon)/(γΔ))$ for GSP in the time-evolution and block-encoding models. However, these models do not directly account for the sparsity of $H$, measured by the maximum number $s$ of nonzero entries in any row or column. In the sparse-access model, oracles instead return the locations and values of these entries. This introduces the additional parameter $s$, and it remained open how query complexity depends jointly on $s$, $γ$, $δ$ or $Δ$, and $\varepsilon$. We resolve this by proving sparse-query lower bounds $Ω(\sqrt{s}\log(1/\varepsilon)/(γδ))$ for GSEE and $Ω(\sqrt{s}\log(1/\varepsilon)/(γΔ))$ for GSP, even for stoquastic Hamiltonians. We also show that these constructions recover the earlier time-evolution and block-encoding lower-bound scalings. We then give matching upper-bound algorithms in the reversible in-place sparse-location model. Thus, we obtain $Θ(\sqrt{s}\log(1/\varepsilon)/(γδ))$ for GSEE and $Θ(\sqrt{s}\log(1/\varepsilon)/(γΔ))$ for GSP, showing that $\sqrt{s}$ is necessary and sufficient and completing the joint dependence on all problem parameters.

0.21

Optimal von Neumann Entropy Estimation

cs.IT quant-ph ·2026-08-11 ·Ziyun Chen, Minbo Gao, Qisheng Wang
theoryhighly cited similarity 0.68
Abstract · 22 pages, 1 table, 1 algorithm. Improved the sample complexity to optimal

We show that the von Neumann entropy of an unknown $d$-dimensional quantum state $ρ$ can be estimated to within additive error $\varepsilon$ using \[ Θ\!\left(\frac{d^2}{\varepsilon\log^2(d)(1+\varepsilon\log^2(d))} + \frac{\log^2(d)}{\varepsilon^2}\right) \] samples of $ρ$, matching the lower bound due to Wang (2026). Our estimator is based on a high-degree approximation polynomial and the main technical challenge is bounding its variance despite the large polynomial degree. We overcome this using a quantum Hoeffding decomposition, which preserves cancellations between different polynomial terms and reduces the analysis to derivative bounds for the approximation polynomial.

0.49

Local Relaxation Hierarchies for Quantum Ground State Energies: Convergence Guarantees and Message Passing Algorithms

cs.DC quant-ph ·2026-09-30 ·Sheng-Ku Lin, Ricardo Rivera Cardoso, Roberto Bondesan
benchmarkcode/datahot direction similarity 0.67
Abstract · 39 pages, 4 figures

Convex relaxation hierarchies provide lower bounds to the ground state energy of quantum many-body systems that can be computed in polynomial time on a classical computer, at any fixed hierarchy level. However, scaling these methods to large systems and accurate approximations remains challenging due to the computational cost of traditional solvers and the scarcity of efficiency guarantees. In this work, we develop local relaxation hierarchies and efficient, highly parallelisable message passing algorithms for estimating the relaxed ground state energies. We show that the first level of the hierarchy---based on local consistency of pairwise reduced density matrices---is exact for commuting Hamiltonians on trees. We further establish that another hierarchy, based on consistent intervals, converges exponentially fast in the interval size to the ground state energy for weak perturbations of separable Hamiltonians on a chain, thereby providing an efficient classical algorithm for these systems. Then, we introduce two variants of message passing algorithms that run in $\mathcal{O}(n/ε^2)$ and $\mathcal{O}(n/ε)$ time for any fixed level of the local hierarchy on bounded-degree graphs, where $ε$ is the precision for the relaxed ground state energy per site. This assumes that the optimal messages have $\mathcal{O}(1)$ norm---a condition we observe in practical settings in our experiments. These algorithms are based on the subgradient method and the Nesterov-type accelerated gradient descent method applied to an entropy-smoothed objective. Finally, we benchmark the message passing algorithms across different quantum Hamiltonians, lattice geometries, and relaxation levels, validating the theoretical predictions and their potential to surpass standard convex optimisation solvers for this problem. We release the resulting library at github.com/rick1924/gse-message-passing.

0.44

Improved classical optimization of fermionic Hamiltonians beyond Gaussian states

cs.DS quant-ph ·2026-10-09 ·Ojas Parekh
theory similarity 0.67
Abstract

We give a polynomial-time randomized classical algorithm that approximates the largest eigenvalue $λ_{\max}$ of a traceless quartic fermionic Hamiltonian $H$ on $n$ modes. The algorithm achieves energy at least $λ_{\max}/O(\sqrt n)$ and outputs either a fermionic Gaussian state or a polynomially sparse state in the Fock basis. This is achieved through a new upper bound on $λ_{\max}$ in terms of the maximum energy of a Gaussian state and $\sqrt{2^{-n}\operatorname{Tr}(H^2)}$.

0.22

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

cs.CC quant-phcs.DS ·2026-08-25 ·Rolando D. Somma, Ronald de Wolf
theoryhighly cited similarity 0.66
Abstract · v2: some small changes and a few extra references in the introduction

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-\varepsilon$, $\varepsilon>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/\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.

0.60

A provable quantum advantage for approximate optimization via decoded quantum interferometry

cs.CC quant-phcs.DS ·2026-10-01 ·Maximilian J. Kramer, Elies Gil-Fuster, Benjamin D. M. Jones, Jens Eisert, Franz J. Schreiber
similarity 0.65
Abstract · 59 pages, 3 figures

Decoded quantum interferometry (DQI) is a novel paradigm for tackling approximate optimization problems on quantum computers. This framework comes with strong performance guarantees and exploits a well-established duality between optimization and coding theory. A central question, however, is whether DQI can actually provably outperform all polynomial-time classical algorithms. In this work, we establish such an advantage in an oracle setting: we consider an optimization task called folded optimal polynomial intersection (folded OPI), where the acceptance sets are chosen randomly and accessed through membership oracles. We establish a strict gap between the approximation ratio achievable by any polynomial-time classical algorithm and the approximation ratio achieved by the DQI algorithm. Our proof builds on Jordan et al.'s DQI framework for approximate optimization and extends the classical lower-bound method underlying Yamakawa and Zhandry's exact-search oracle separation to approximation. Building on recent developments by Sun and Wootters, Horinaga and Yamakawa, and Jo, we further show that a modified version of the DQI algorithm achieves a strictly higher score guarantee on typical sampled folded OPI instances. As a concrete example, for code rate $0.3$, DQI achieves expected scores of approximately $0.85$. In contrast, exceeding the classical threshold of $0.65$ by any fixed amount with constant probability on sampled instances requires super-polynomially many classical membership queries.

0.47