Ground-state preparation, energy estimation, and property estimation are fundamental tasks in quantum simulation. Existing ground-state preparation algorithms achieve near-optimal complexity using block encodings or controlled Hamiltonian evolution, raising a natural question: is controlled Hamiltonian evolution necessary, or can the same scaling be attained in the weaker access model that provides access to only uncontrolled Hamiltonian evolution? We resolve this question by giving two algorithms that access the input Hamiltonian $H$ only through queries to $U_H$ and its inverse $U_H^\dagger$, where $\|H\|\leα_H$ and $τ=Θ(1/α_H)$. Given an input state with ground-state weight at least $η$ and a spectral gap of $H$ of at least $γ$, our first algorithm uses fresh copies of the input state and requires $\widetilde O(α_H/(γη))$ queries to $U_H$ and $U_H^\dagger$, while our second algorithm uses coherent access to the input-state preparation unitary and its inverse to improve this complexity to $\widetilde O(α_H/(γ\sqrtη))$. The latter bound matches the known lower bound up to logarithmic factors, showing that algorithms with additional access to controlled Hamiltonian evolution cannot improve the query complexity for ground-state preparation beyond logarithmic factors. Both algorithms are based on a simple mechanism that we call the spectral descent principle, in which the algorithm starts from the input state $|ψ\rangle$ and progressively descends through the energy spectrum, moving closer to the ground state until the desired fidelity is reached. We also extend this framework to ground-state property and energy estimation and give explicit complexity guarantees for both tasks.
AI Summary
The paper asks whether ground-state preparation can attain near-optimal query complexity without controlled Hamiltonian evolution or block encodings. It assumes a unique ground state, $\|H\|\le\alpha_H$, a known gap lower bound $\gamma$, and an input state with ground-state weight at least $\eta$. Hamiltonian access consists of $U_H=e^{-iH\tau}$ and its inverse, with $\tau=\Theta(1/\alpha_H)$.
Two algorithms prepare an output with ground-state fidelity at least $1-\xi$. Spectral Descent uses fresh input copies and $O(\alpha_H(\gamma\eta)^{-1}\log^2(1/(\eta\xi)))$ Hamiltonian queries. Coherent Spectral Descent uses the input-preparation unitary and its inverse, reducing this to $O(\alpha_H(\gamma\sqrt\eta)^{-1}\log^2(1/(\eta\xi)))$, matching the known lower bound up to logarithmic factors even when controlled evolution is available.
Both algorithms compare an anchor register with a candidate input copy and replace the anchor upon a lower-energy witness. A two-register “SWAP echo” combines uncontrolled forward/backward evolution with controlled-SWAP gates to encode energy differences on a signal qubit. Laurent quantum signal processing implements a soft comparator; a spectral-weight potential establishes convergence. Fixed-point amplitude amplification supplies the coherent algorithm’s quadratic overlap improvement.
Extensions give property estimation and gap-free preparation within an energy interval above the ground energy. Property estimation has $\varepsilon^{-2}$ sampling dependence, improved to $\widetilde O(\varepsilon^{-1})$ with reversible preparation and coherent observable access; optimal joint parameter dependence remains open. Absolute energy estimation requires additional measurement access because uncontrolled evolution cannot reveal additive energy offsets. The access model still requires inverse evolution, two system registers, and controlled-SWAP operations.
Little sign of AI-generated text
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
Comments
The authors acknowledge the use of ChatGPT 5.6 and 6 for help with writing and reviewing the manuscript, including identifying technical errors and inconsistencies in earlier versions
Ground-state preparation, energy estimation, and property estimation are fundamental tasks in quantum simulation. Existing ground-state preparation algorithms achieve near-optimal complexity using block encodings or controlled Hamiltonian evolution, raising a natural question: is controlled Hamiltonian evolution necessary, or can the same scaling be attained in the weaker access model that provides access to only uncontrolled Hamiltonian evolution? We resolve this question by giving two algorithms that access the input Hamiltonian H only through queries to UH and its inverse UH†, where ∥H∥≤αH and τ=Θ(1/αH). Given an input state with ground-state weight at least η and a spectral gap of H of at least γ, our first algorithm uses fresh copies of the input state and requires O(αH/(γη)) queries to UH and UH†, while our second algorithm uses coherent access to the input-state preparation unitary and its inverse to improve this complexity to O(αH/(γη)). The latter bound matches the known lower bound up to logarithmic factors, showing that algorithms with additional access to controlled Hamiltonian evolution cannot improve the query complexity for ground-state preparation beyond logarithmic factors. Both algorithms are based on a simple mechanism that we call the spectral descent principle, in which the algorithm starts from the input state ∣ψ⟩ and progressively descends through the energy spectrum, moving closer to the ground state until the desired fidelity is reached. We also extend this framework to ground-state property and energy estimation and give explicit complexity guarantees for both tasks.
The paper asks whether ground-state preparation can attain near-optimal query complexity without controlled Hamiltonian evolution or block encodings. It assumes a unique ground state, ∥H∥≤αH, a known gap lower bound γ, and an input state with ground-state weight at least η. Hamiltonian access consists of UH=e−iHτ and its inverse, with τ=Θ(1/αH).
Two algorithms prepare an output with ground-state fidelity at least 1−ξ. Spectral Descent uses fresh input copies and O(αH(γη)−1log2(1/(ηξ))) Hamiltonian queries. Coherent Spectral Descent uses the input-preparation unitary and its inverse, reducing this to O(αH(γη)−1log2(1/(ηξ))), matching the known lower bound up to logarithmic factors even when controlled evolution is available.
Both algorithms compare an anchor register with a candidate input copy and replace the anchor upon a lower-energy witness. A two-register “SWAP echo” combines uncontrolled forward/backward evolution with controlled-SWAP gates to encode energy differences on a signal qubit. Laurent quantum signal processing implements a soft comparator; a spectral-weight potential establishes convergence. Fixed-point amplitude amplification supplies the coherent algorithm’s quadratic overlap improvement.
Extensions give property estimation and gap-free preparation within an energy interval above the ground energy. Property estimation has ε−2 sampling dependence, improved to O(ε−1) with reversible preparation and coherent observable access; optimal joint parameter dependence remains open. Absolute energy estimation requires additional measurement access because uncontrolled evolution cannot reveal additive energy offsets. The access model still requires inverse evolution, two system registers, and controlled-SWAP operations.
We determine the optimal query complexity of ground-state preparation to trace-distance error ε when an energy threshold in the spectral gap is known. Let UH be an α-block-encoding of a Hamiltonian with unique ground state ∣ψ0⟩, and suppose ∣⟨ψ0∣UI∣0⟩∣≥γ for a state-preparation oracle UI. 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 ε of the ground state. One uses O((α/Δ)(γ−1+log(1/ε))) calls to UH in expectation; the other uses O((α/(γΔ))log(1/ε)) calls to UH 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 UI are O(1/γ) in expectation and O(γ−1log(1/ε)) in the worst case. On (N+1)-dimensional systems, these UI bounds are also optimal when the expected or worst-case count of UH calls, respectively, is o((α/Δ)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.
Preparing the ground state of a given Hamiltonian and estimating its ground energy are important but computationally hard tasks. However, given some additional information, these problems can be solved efficiently on a quantum computer. We assume that an initial state with non-trivial overlap with the ground state can be efficiently prepared, and the spectral gap between the ground energy and the first excited energy is bounded from below. With these assumptions we design an algorithm that prepares the ground state when an upper bound of the ground energy is known, whose runtime has a logarithmic dependence on the inverse error. When such an upper bound is not known, we propose a hybrid quantum-classical algorithm to estimate the ground energy, where the dependence of the number of queries to the initial state on the desired precision is exponentially improved compared to the current state-of-the-art algorithm proposed in [Ge et al. 2019]. These two algorithms can then be combined to prepare a ground state without knowing an upper bound of the ground energy. We also prove that our algorithms reach the complexity lower bounds by applying it to the unstructured search problem and the quantum approximate counting problem.
Suppose we can apply the unitary U=eiH 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.
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γ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.
Near-Optimal Bounds on the Density of Low-Energy States of k-Local Hamiltonians and Faster Quantum Algorithms
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∗(2n/2) for both problems, with the improvement depending on the relative accuracy ε 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 ε/k, our algorithms improve the exponent by a factor of log(k/ε) 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.
Under suitable assumptions, the algorithms in [Lin, Tong, Quantum 2020] can estimate the ground state energy and prepare the ground state of a quantum Hamiltonian with near-optimal query complexities. However, this is based on a block encoding input model of the Hamiltonian, whose implementation is known to require a large resource overhead. We develop a tool called quantum eigenvalue transformation of unitary matrices with real polynomials (QET-U), which uses a controlled Hamiltonian evolution as the input model, a single ancilla qubit and no multi-qubit control operations, and is thus suitable for early fault-tolerant quantum devices. This leads to a simple quantum algorithm that outperforms all previous algorithms with a comparable circuit structure for estimating the ground state energy. For a class of quantum spin Hamiltonians, we propose a new method that exploits certain anti-commutation relations and further removes the need of implementing the controlled Hamiltonian evolution. Coupled with Trotter based approximation of the Hamiltonian evolution, the resulting algorithm can be very suitable for early fault-tolerant quantum devices. We demonstrate the performance of the algorithm using IBM Qiskit for the transverse field Ising model. If we are further allowed to use multi-qubit Toffoli gates, we can then implement amplitude amplification and a new binary amplitude estimation algorithm, which increases the circuit depth but decreases the total query complexity. The resulting algorithm saturates the near-optimal complexity for ground state preparation and energy estimating using a constant number of ancilla qubits (no more than 3).