Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:2609.38091

Optimal Ground-State Preparation with a Guiding State

Stacey Jeffery, Rolando D. Somma, Freek Witteveen, Ronald de Wolf

quant-phSubmitted Sep 29, 2026• Announced Sep 30, 2026• 1 citation• Revised Oct 5, 2026 (v2)
v1 · Sep 29, 2026v2 · Oct 5, 2026
arXivHTMLPDF

Abstract

Suppose a Hamiltonian $H$ has a unique ground state $|ψ_0\rangle$ with an eigenvalue $E_0$, and we have an estimate $\tilde{E}_0$ such that $|\tilde{E}_0-E_0|\leqδ$, and there is a gap of at least $3δ$ between $E_0$ and all other eigenvalues. Suppose we have a unitary $A$ available that can produce a "guiding state'" $A|0\rangle$ that has overlap at least $γ$ with $|ψ_0\rangle$. We show how to obtain an $η$-approximation of $|ψ_0\rangle$ with probability at least $1-\varepsilon$ using $O(\log(1/\varepsilon)/γδ+ \log(1/η)/δ)$ applications of $U=e^{iH}$ its inverse, and $O(\log(1/\varepsilon)/γ)$ applications of $A$ and its inverse. We give two different algorithms, one based on interleaving amplitude amplification and error-reduction in the style of [HMdW03], and one using the composition of transducers. This paper is the state-preparation follow-up to our two recent ground-state-energy estimation papers [JW26,SdW26]. Combined with the optimal energy-estimation of [JW26], our results show the claimed upper bound for ground-state preparation. The bound is optimal up to a constant factor in terms of the number of applications of $U$ and $U^\dagger$ if $\varepsilon=η$, as follows from [SdW26]. In one of our approaches to ground state preparation, we construct transducers for amplitude amplification and LCU that might be of independent interest.

AI Summary

The paper studies preparation of a unique ground state given controlled access to $U=e^{iH}$ and a guiding-state unitary $A$ whose output has ground-state overlap at least $\gamma$. The spectrum is normalized to $[0,\pi]$, the spectral gap is at least $\Delta$, and initially the ground energy is known within $\Delta/3$. It gives algorithms producing a state within trace-norm distance $\eta$ of the ground state, with success probability at least $1-\varepsilon$, using $O(\log(1/\varepsilon)/(\gamma\Delta)+\log(1/\eta)/\Delta)$ calls to $U$ and its inverse, and $O(\log(1/\varepsilon)/\gamma)$ calls to $A$ and its inverse. This removes a multiplicative $\log(1/\gamma)$ overhead from previous bounds. A lower bound from prior work establishes optimality of the evolution-query count when $\varepsilon=\eta$. Combining with prior energy estimation removes the supplied-estimate assumption without changing that count. Two constructions establish the bound: recursive robust amplitude amplification interleaved with increasingly accurate phase-estimation verification, and composition of transducers for spectral filtering and amplitude amplification. The latter includes an LCU construction costed by the first moment of its Fourier coefficients and an amplitude-amplification transducer with reduced space overhead. Staged verification separates the dependence on output accuracy from repeated preparation costs. The guarantees concern oracle-query complexity, not end-to-end Hamiltonian-simulation cost. The transducer construction has logarithmic ancilla overhead and polylogarithmic gate overhead; its loose constant bounds may offset the logarithmic improvement in practice. Independent concurrent work obtains similar query-optimal preparation results.

No sign of AI-generated textAI use disclosed
We also used LLMs for generating some figures and proofs, and extensively for proofreading.

Central claim may not hold: Without the body's spectrum restriction or an equivalent no-aliasing promise, the abstract's ground-state preparation claim is false because distinct Hamiltonians with orthogonal ground states can provide identical evolution and guiding-state oracles. The abstract leaves controlled-oracle access unspecified, although the main theorem explicitly assumes controlled calls, an additional capability not generally supplied by arbitrary black-box unitaries and their inverses.

Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.

Comments
v2: improved the presentation

Related papers

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

Rolando D. Somma, Ronald de Wolf

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.

quant-pharXiv:2608.24493•Aug 26, 2026•3 citations

Optimal Query Complexity for Ground-State Preparation

Boyang Chen, Minbo Gao, Xinzhao Wang +1 more

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.

quant-pharXiv:2609.35668•Sep 29, 2026•1 citation

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

Stacey Jeffery, Freek Witteveen

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.

quant-pharXiv:2608.24494•Aug 26, 2026•8 citations

Near-Optimal Ground-State Preparation without Controlled Hamiltonian Evolutions

Dhrumil Patel, Steven T. Flammia, Raul Garcia-Patron

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.

quant-pharXiv:2610.00520•Oct 2, 2026•0 citations

Near-optimal ground state preparation

Lin Lin, Yu Tong

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.

arXiv:2002.12508•Quantum•Dec 14, 2020•247 citations

Ground state energy estimation and preparation by the truncated power method

Savero Lukianto Chandra, Daochen Wang, Carolyn Zhang

The Guided Local Hamiltonian Problem (GLHP) is the problem of ground state energy estimation and preparation given a guiding state having good overlap with the true ground state. The problem is known to be BQP-complete for small error but is classically tractable for larger error. In this work, we identify an orthogonal regime in which the problem is classically tractable, namely when the true ground state $ψ$ has polynomially bounded $\ell_1$-norm. In particular, we show that the Truncated Power Method (TPM), a classical algorithm introduced by Kirby et al. in the quantum context, has a runtime that is polynomially comparable to quantum algorithms for GLHP in all relevant parameters, except for an extra factor of $\|ψ\|_1^2$. In other words, if $\|ψ\|_1^2$ is polynomially bounded, then TPM dequantizes quantum algorithms for GLHP.

quant-pharXiv:2610.05627•Oct 6, 2026•0 citations
Suppose a Hamiltonian HHH has a unique ground state ∣ψ0⟩|ψ_0\rangle∣ψ0​⟩ with an eigenvalue E0E_0E0​, and we have an estimate E~0\tilde{E}_0E~0​ such that ∣E~0−E0∣≤δ|\tilde{E}_0-E_0|\leqδ∣E~0​−E0​∣≤δ, and there is a gap of at least 3δ3δ3δ between E0E_0E0​ and all other eigenvalues. Suppose we have a unitary AAA available that can produce a "guiding state'" A∣0⟩A|0\rangleA∣0⟩ that has overlap at least γγγ with ∣ψ0⟩|ψ_0\rangle∣ψ0​⟩. We show how to obtain an ηηη-approximation of ∣ψ0⟩|ψ_0\rangle∣ψ0​⟩ with probability at least 1−ε1-\varepsilon1−ε using O(log⁡(1/ε)/γδ+log⁡(1/η)/δ)O(\log(1/\varepsilon)/γδ+ \log(1/η)/δ)O(log(1/ε)/γδ+log(1/η)/δ) applications of U=eiHU=e^{iH}U=eiH its inverse, and O(log⁡(1/ε)/γ)O(\log(1/\varepsilon)/γ)O(log(1/ε)/γ) applications of AAA and its inverse. We give two different algorithms, one based on interleaving amplitude amplification and error-reduction in the style of [HMdW03], and one using the composition of transducers. This paper is the state-preparation follow-up to our two recent ground-state-energy estimation papers [JW26,SdW26]. Combined with the optimal energy-estimation of [JW26], our results show the claimed upper bound for ground-state preparation. The bound is optimal up to a constant factor in terms of the number of applications of UUU and U†U^\daggerU† if ε=η\varepsilon=ηε=η, as follows from [SdW26].
In one of our approaches to ground state preparation, we construct transducers for amplitude amplification and LCU that might be of independent interest.
The paper studies preparation of a unique ground state given controlled access to U=eiHU=e^{iH}U=eiH and a guiding-state unitary AAA whose output has ground-state overlap at least γ\gammaγ. The spectrum is normalized to [0,π][0,\pi][0,π], the spectral gap is at least Δ\DeltaΔ, and initially the ground energy is known within Δ/3\Delta/3Δ/3.
It gives algorithms producing a state within trace-norm distance η\etaη of the ground state, with success probability at least 1−ε1-\varepsilon1−ε, using O(log⁡(1/ε)/(γΔ)+log⁡(1/η)/Δ)O(\log(1/\varepsilon)/(\gamma\Delta)+\log(1/\eta)/\Delta)O(log(1/ε)/(γΔ)+log(1/η)/Δ) calls to UUU and its inverse, and O(log⁡(1/ε)/γ)O(\log(1/\varepsilon)/\gamma)O(log(1/ε)/γ) calls to AAA and its inverse. This removes a multiplicative log⁡(1/γ)\log(1/\gamma)log(1/γ) overhead from previous bounds. A lower bound from prior work establishes optimality of the evolution-query count when ε=η\varepsilon=\etaε=η. Combining with prior energy estimation removes the supplied-estimate assumption without changing that count.
Two constructions establish the bound: recursive robust amplitude amplification interleaved with increasingly accurate phase-estimation verification, and composition of transducers for spectral filtering and amplitude amplification. The latter includes an LCU construction costed by the first moment of its Fourier coefficients and an amplitude-amplification transducer with reduced space overhead. Staged verification separates the dependence on output accuracy from repeated preparation costs.
The guarantees concern oracle-query complexity, not end-to-end Hamiltonian-simulation cost. The transducer construction has logarithmic ancilla overhead and polylogarithmic gate overhead; its loose constant bounds may offset the logarithmic improvement in practice. Independent concurrent work obtains similar query-optimal preparation results.
Suppose we can apply the unitary U=eiHU=e^{i H}U=eiH for some Hamiltonian HHH, and are given access to a unitary that prepares a guiding state promised to have overlap at least γ>0γ>0γ>0 with the ground space of HHH. Our goal is to estimate the ground-state energy of HHH within additive error δ>0δ> 0δ>0 and success probability at least 1−ε1-\varepsilon1−ε, ε>0\varepsilon>0ε>0. How many applications of UUU and its inverse U−1U^{-1}U−1 are necessary and sufficient? This quantity corresponds to the total Hamiltonian-simulation time needed. An upper bound O(log⁡(1/ε)log⁡(1/γ)/γδ)O(\log(1/\varepsilon)\log(1/γ)/γδ)O(log(1/ε)log(1/γ)/γδ) was known, and was improved to O(log⁡(1/ε)/γδ)O(\log(1/\varepsilon)/γδ)O(log(1/ε)/γδ) 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/ε)/γδ)Ω(\log(1/\varepsilon)/γδ)Ω(log(1/ε)/γδ) with the tight ε\varepsilonε-dependence provided the dimension of HHH is at least log⁡(1/ε)/γ2\log(1/\varepsilon)/γ^2log(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 HHH 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 UUU are allowed, as in continuous-time Hamiltonian simulation. Lastly, improved upper bounds are known when HHH is nonnegative and presented as a sum of squares; and our results imply the lower bound Ω(log⁡(1/ε)/γδ)Ω(\log(1/\varepsilon)/γ\sqrtδ)Ω(log(1/ε)/γδ​) for this case.
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 UHU_HUH​ be an ααα-block-encoding of a Hamiltonian with unique ground state ∣ψ0⟩|ψ_0\rangle∣ψ0​⟩, and suppose ∣⟨ψ0∣UI∣0⟩∣≥γ|\langleψ_0|U_I|0\rangle|\geγ∣⟨ψ0​∣UI​∣0⟩∣≥γ for a state-preparation oracle UIU_IUI​. The threshold lies at least Δ/2Δ/2Δ/2 above the ground-state energy and at least Δ/2Δ/2Δ/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/ε)))O((α/Δ)(γ^{-1}+\log(1/\varepsilon)))O((α/Δ)(γ−1+log(1/ε))) calls to UHU_HUH​ in expectation; the other uses O((α/(γΔ))log⁡(1/ε))O((α/(γΔ))\log(1/\varepsilon))O((α/(γΔ))log(1/ε)) calls to UHU_HUH​ 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 UIU_IUI​ are O(1/γ)O(1/γ)O(1/γ) in expectation and O(γ−1log⁡(1/ε))O(γ^{-1}\log(1/\varepsilon))O(γ−1log(1/ε)) in the worst case. On (N+1)(N+1)(N+1)-dimensional systems, these UIU_IUI​ bounds are also optimal when the expected or worst-case count of UHU_HUH​ calls, respectively, is o((α/Δ)N)o((α/Δ)\sqrt N)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.
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 UUU. We give a quantum algorithm that estimates the largest eigenphase of a unitary UUU in this guided setting using a factor of log⁡1γ\log\frac{1}γlogγ1​ fewer queries to UUU 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.
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 HHH only through queries to UHU_HUH​ and its inverse UH†U_H^\daggerUH†​, where ∥H∥≤αH\|H\|\leα_H∥H∥≤αH​ and τ=Θ(1/αH)τ=Θ(1/α_H)τ=Θ(1/αH​). Given an input state with ground-state weight at least ηηη and a spectral gap of HHH of at least γγγ, our first algorithm uses fresh copies of the input state and requires O~(αH/(γη))\widetilde O(α_H/(γη))O(αH​/(γη)) queries to UHU_HUH​ and UH†U_H^\daggerUH†​, while our second algorithm uses coherent access to the input-state preparation unitary and its inverse to improve this complexity to O~(αH/(γη))\widetilde O(α_H/(γ\sqrtη))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 ∣ψ⟩|ψ\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.
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.
The Guided Local Hamiltonian Problem (GLHP) is the problem of ground state energy estimation and preparation given a guiding state having good overlap with the true ground state. The problem is known to be BQP-complete for small error but is classically tractable for larger error. In this work, we identify an orthogonal regime in which the problem is classically tractable, namely when the true ground state ψψψ has polynomially bounded ℓ1\ell_1ℓ1​-norm. In particular, we show that the Truncated Power Method (TPM), a classical algorithm introduced by Kirby et al. in the quantum context, has a runtime that is polynomially comparable to quantum algorithms for GLHP in all relevant parameters, except for an extra factor of ∥ψ∥12\|ψ\|_1^2∥ψ∥12​. In other words, if ∥ψ∥12\|ψ\|_1^2∥ψ∥12​ is polynomially bounded, then TPM dequantizes quantum algorithms for GLHP.