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.
AI Summary
The paper studies ground-state preparation given an $\alpha$-block-encoding $U_H$, an initial-state oracle $U_I$ with ground-state overlap at least $\gamma$, and a known threshold separated from the ground and excited energies by at least $\Delta/2$. The target is trace-distance error $\varepsilon$ for a unique ground state.
It gives an almost-surely terminating algorithm using $O((\alpha/\Delta)(\gamma^{-1}+\log(1/\varepsilon)))$ Hamiltonian queries and $O(\gamma^{-1})$ initial-state queries in expectation, with matching lower bounds on Hamiltonian queries. A second algorithm has worst-case bounds $O((\alpha/(\gamma\Delta))\log(1/\varepsilon))$ and $O(\gamma^{-1}\log(1/\varepsilon))$, respectively. The Hamiltonian bound matches an existing lower bound. Compared with the filtering-and-amplification baseline, the expected bound separates overlap amplification from precision dependence and removes a $\log(1/\gamma)$ overhead.
The construction uses a constant-accuracy QSVT filter, a purifier, and transducer composition to implement amplitude amplification to constant ground-state weight without separately tightening every approximate reflection. A final high-accuracy filter supplies the requested precision; restarting until acceptance gives the expected bound. Increasing-accuracy filters and a query cutoff establish the worst-case guarantee. Lower bounds use hybrid arguments, trigonometric-polynomial inequalities, and an existing worst-case hardness construction.
The results assume the threshold and overlap lower bound are supplied; they do not address arbitrary unguided preparation. Optimality of the initial-state query counts requires Hamiltonian queries to be $o((\alpha/\Delta)\sqrt N)$ in dimension $N+1$, since sufficiently many Hamiltonian queries can replace $U_I$. The stated optimality theorems cover $\gamma\le1/\sqrt2$, $\varepsilon\le1/10$, and $\Delta\le\alpha/8$.
Little sign of AI-generated textAI use disclosed
Large language models were used to develop the detailed constructions and proofs.
Error found: The abstract omits the overlap restriction needed for its matching lower bounds: when γ ≥ √(1−ε²), the supplied initial state already meets the trace-distance target with zero Hamiltonian queries.
Written by gpt-6.1-sol from the paper's full text. Automated: it can be wrong.
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.
The paper studies ground-state preparation given an α-block-encoding UH, an initial-state oracle UI with ground-state overlap at least γ, and a known threshold separated from the ground and excited energies by at least Δ/2. The target is trace-distance error ε for a unique ground state.
It gives an almost-surely terminating algorithm using O((α/Δ)(γ−1+log(1/ε))) Hamiltonian queries and O(γ−1) initial-state queries in expectation, with matching lower bounds on Hamiltonian queries. A second algorithm has worst-case bounds O((α/(γΔ))log(1/ε)) and O(γ−1log(1/ε)), respectively. The Hamiltonian bound matches an existing lower bound. Compared with the filtering-and-amplification baseline, the expected bound separates overlap amplification from precision dependence and removes a log(1/γ) overhead.
The construction uses a constant-accuracy QSVT filter, a purifier, and transducer composition to implement amplitude amplification to constant ground-state weight without separately tightening every approximate reflection. A final high-accuracy filter supplies the requested precision; restarting until acceptance gives the expected bound. Increasing-accuracy filters and a query cutoff establish the worst-case guarantee. Lower bounds use hybrid arguments, trigonometric-polynomial inequalities, and an existing worst-case hardness construction.
The results assume the threshold and overlap lower bound are supplied; they do not address arbitrary unguided preparation. Optimality of the initial-state query counts requires Hamiltonian queries to be o((α/Δ)N) in dimension N+1, since sufficiently many Hamiltonian queries can replace UI. The stated optimality theorems cover γ≤1/2, ε≤1/10, and Δ≤α/8.
Suppose a Hamiltonian H has a unique ground state ∣ψ0⟩ with an eigenvalue E0, and we have an estimate E~0 such that ∣E~0−E0∣≤δ, and there is a gap of at least 3δ between E0 and all other eigenvalues. Suppose we have a unitary A available that can produce a "guiding state'" A∣0⟩ that has overlap at least γ with ∣ψ0⟩. We show how to obtain an η-approximation of ∣ψ0⟩ with probability at least 1−ε using O(log(1/ε)/γδ+log(1/η)/δ) applications of U=eiH its inverse, and O(log(1/ε)/γ) 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† if ε=η, 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.
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.
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.
Quantum linear-system algorithms access the coefficient matrix through a block-encoding oracle UA and the right-hand side through a state-preparation oracle Ub. The optimal query complexities of these two oracles are known separately: O(κlog(1/ε)) queries to UA and O(κ/s) queries to Ub, where s=α∥A−1b∥. Whether a single algorithm can achieve both bounds simultaneously has remained open.
We resolve this question affirmatively. Given a constant-factor estimate of s, we give a quantum linear-system algorithm that prepares the normalized solution to error ε using simultaneously $ O\left(κ\log\frac1\varepsilon\right)$ queries to UA and O(κ/s) queries to Ub. The algorithm separates state preparation from precision refinement, so only the matrix-query count depends on the target accuracy.
We also prove a matching same-instance worst-case lower bound: for every quantum linear-system algorithm and every solution-norm scale, there exists a single Hermitian instance on which that algorithm requires both Ω(κlog(1/ε)) matrix queries and Ω(κ/s) state-preparation queries. Thus the two oracle complexities can be optimized simultaneously, and the resulting bounds are jointly optimal.
We investigate the computational complexity of estimating the operator norm distance T∞(ρ0,ρ1), defined via the operator norm ∥A∥∞=σmax(A), given poly(n)-size state-preparation circuits of n-qubit quantum states ρ0 and ρ1. We provide efficient quantum estimators for the operator norm distance whose complexity is independent of the rank (and thus the dimension) of the states:
1. When one state is pure, we establish an optimal quantum estimator using Θ(1/ε) queries to the state-preparation circuits. Consequently, for constant additive error, say ε=1/5, our estimator runs in poly(n) time. Since the operator norm distance T∞(∣ψ⟩⟨ψ∣,ρ) is exactly half of the trace distance T(∣ψ⟩⟨ψ∣,ρ), our result also gives rank-independent query complexity for estimating both quantities, whereas the approaches due to van Apeldoorn, Cornelissen, Gily{é}n, and Nannicini (SODA 2023) and Wang and Zhang (TIT 2024) have query complexity scaling at least linearly with rank(ρ), which can be exp(n) in general.
2. For general quantum states, we also provide a quantum estimator using O(1/ε3/2) queries to the state-preparation circuits, which shows that the corresponding promise problem is BQP-complete and improves the QMA upper bound sketched by Liu and Wang (ESA 2025). Together with an Ω(1/ε) quantum query complexity lower bound, this leaves only square-root room for improvement.
The key intuition behind our estimators is that, when one state is pure, the pure state ∣ψ⟩ has overlap at least 1/2 with the top unit eigenvector of ∣ψ⟩⟨ψ∣−ρ, reflecting a structural feature specific to the operator norm distance.
Quantum simulation is expected to be a main application of quantum computers with realistic utility in quantum chemistry, materials science and beyond. However, preparing excited or general eigenstates is a central challenge, particularly when the desired eigenvalue is not known in advance, or when the overlap with the initial state is insufficient. We introduce the Dominant Eigenstate Filtering via Eigenprobability Amplification and Thresholding (DEFEAT) algorithm that identifies and filters the eigenstate with the largest overlap with the supplied initial state. Our key observation is that we do not need prior knowledge of the target eigenvalue, as we construct efficient twirling superoperators that map initial states to eigenprobability density operators ρ, diagonal in the Hamiltonian eigenbasis and encoding its spectral weights, alongside its block-encoding implementation. Our crucial innovation is the quadratic amplification of probabilities via the factorisation ρ=ρsqrt†ρsqrt, analogous to the recently introduced sum-of-squares spectral amplification (SOSSA), which we use here to amplify the separation between dominant and subdominant components. Thresholding then yields the dominant-eigenstate projector. Compared with conventional phase estimation, DEFEAT improves the dependence on the overlap with the initial state while requiring substantially fewer ancillary qubits. We prove that the query complexity of the filtering step is optimal up to logarithmic factors and establish a complementary lower bound for eigenstate preparation under purified query access to ρ. We validate in numerical simulations that the convergence rate of DEFEAT matches our theoretical results. Our results provide a general eigenvalue-agnostic primitive for dominant eigenstate filtering and preparation, and for estimating properties of dominant eigenstates.