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.35668

Optimal Query Complexity for Ground-State Preparation

Boyang Chen, Minbo Gao, Xinzhao Wang, Shuo Zhou

quant-phcs.CCcs.DSSubmitted Sep 28, 2026• Announced Sep 29, 2026• 0 citations
v1 · Sep 28, 2026v2 · Oct 1, 2026
arXivHTMLPDF

Abstract

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.

Comments
47 pages

Related papers

Optimal Ground-State Preparation with a Guiding State

Stacey Jeffery, Rolando D. Somma, Freek Witteveen +1 more

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.

quant-pharXiv:2609.38091•Sep 30, 2026•0 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

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•0 citations

Simultaneously Query-Optimal Quantum Linear-System Algorithm

Minbo Gao, Zhengfeng Ji, Chenghua Liu

Quantum linear-system algorithms access the coefficient matrix through a block-encoding oracle $U_A$ and the right-hand side through a state-preparation oracle $U_b$. The optimal query complexities of these two oracles are known separately: $O(κ\log(1/\varepsilon))$ queries to $U_A$ and $O(κ/s)$ queries to $U_b$, where $s=α\|A^{-1}b\|$. 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 $\varepsilon$ using simultaneously $ O\left(κ\log\frac1\varepsilon\right)$ queries to $U_A$ and $O\left(κ/{s}\right)$ queries to $U_b$. 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/\varepsilon))$ matrix queries and $Ω(κ/s)$ state-preparation queries. Thus the two oracle complexities can be optimized simultaneously, and the resulting bounds are jointly optimal.

quant-pharXiv:2609.33686•Sep 29, 2026•0 citations

On estimating operator norm distance, with optimal trace distance estimation when one state is pure

Yupan Liu, Qisheng Wang, Zhan Yu

We investigate the computational complexity of estimating the operator norm distance ${\rm T}_{\infty}(ρ_0,ρ_1)$, defined via the operator norm $\|A\|_{\infty} = σ_{\max}(A)$, given ${\rm 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 ${\rm poly}(n)$ time. Since the operator norm distance ${\rm T}_{\infty}(|ψ\rangle\!\langleψ|,ρ)$ is exactly half of the trace distance ${\rm T}(|ψ\rangle\!\langleψ|,ρ)$, 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 ${\rm rank}(ρ)$, which can be $\exp(n)$ in general. 2. For general quantum states, we also provide a quantum estimator using $\widetilde{O}(1/ε^{3/2})$ queries to the state-preparation circuits, which shows that the corresponding promise problem is ${\sf BQP}$-complete and improves the ${\sf 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 $|ψ\rangle$ has overlap at least $1/2$ with the top unit eigenvector of $|ψ\rangle\!\langleψ|-ρ$, reflecting a structural feature specific to the operator norm distance.

quant-pharXiv:2607.03905•Leibniz international proceedings in informatics•Jul 7, 2026•0 citations

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•0 citations
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.
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.
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.
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.
Quantum linear-system algorithms access the coefficient matrix through a block-encoding oracle UAU_AUA​ and the right-hand side through a state-preparation oracle UbU_bUb​. The optimal query complexities of these two oracles are known separately: O(κlog⁡(1/ε))O(κ\log(1/\varepsilon))O(κlog(1/ε)) queries to UAU_AUA​ and O(κ/s)O(κ/s)O(κ/s) queries to UbU_bUb​, where s=α∥A−1b∥s=α\|A^{-1}b\|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 sss, we give a quantum linear-system algorithm that prepares the normalized solution to error ε\varepsilonε using simultaneously $ O\left(κ\log\frac1\varepsilon\right)$ queries to UAU_AUA​ and O(κ/s)O\left(κ/{s}\right)O(κ/s) queries to UbU_bUb​. 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/ε))Ω(κ\log(1/\varepsilon))Ω(κlog(1/ε)) matrix queries and Ω(κ/s)Ω(κ/s)Ω(κ/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){\rm T}_{\infty}(ρ_0,ρ_1)T∞​(ρ0​,ρ1​), defined via the operator norm ∥A∥∞=σmax⁡(A)\|A\|_{\infty} = σ_{\max}(A)∥A∥∞​=σmax​(A), given poly(n){\rm poly}(n)poly(n)-size state-preparation circuits of nnn-qubit quantum states ρ0ρ_0ρ0​ and ρ1ρ_1ρ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/ε)Θ(1/ε)Θ(1/ε) queries to the state-preparation circuits. Consequently, for constant additive error, say ε=1/5ε=1/5ε=1/5, our estimator runs in poly(n){\rm poly}(n)poly(n) time. Since the operator norm distance T∞(∣ψ⟩ ⁣⟨ψ∣,ρ){\rm T}_{\infty}(|ψ\rangle\!\langleψ|,ρ)T∞​(∣ψ⟩⟨ψ∣,ρ) is exactly half of the trace distance T(∣ψ⟩ ⁣⟨ψ∣,ρ){\rm T}(|ψ\rangle\!\langleψ|,ρ)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(ρ){\rm rank}(ρ)rank(ρ), which can be exp⁡(n)\exp(n)exp(n) in general. 2. For general quantum states, we also provide a quantum estimator using O~(1/ε3/2)\widetilde{O}(1/ε^{3/2})O(1/ε3/2) queries to the state-preparation circuits, which shows that the corresponding promise problem is BQP{\sf BQP}BQP-complete and improves the QMA{\sf QMA}QMA upper bound sketched by Liu and Wang (ESA 2025). Together with an Ω(1/ε)Ω(1/ε)Ω(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 ∣ψ⟩|ψ\rangle∣ψ⟩ has overlap at least 1/21/21/2 with the top unit eigenvector of ∣ψ⟩ ⁣⟨ψ∣−ρ|ψ\rangle\!\langleψ|-ρ∣ψ⟩⟨ψ∣−ρ, reflecting a structural feature specific to the operator norm distance.
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.