Optimal Query Complexity for Ground-State Preparation
Abstract
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.
Related
- The power of oracle access: Optimal sample and query complexity of the abelian state hidden subgroup problem
- Optimal Ground-State Preparation with a Guiding State
- Near-Optimal Ground-State Preparation without Controlled Hamiltonian Evolutions
- Near-Optimal Separations of Certificate Complexity from Randomized and Quantum Query Complexity
- Optimal query complexity for fractional quantum evolution
BibTeX
@misc{chen2026optimal,
title = {{Optimal Query Complexity for Ground-State Preparation}},
author = {Boyang Chen and Minbo Gao and Xinzhao Wang and Shuo Zhou},
howpublished = {arXiv},
year = {2026},
month = oct,
doi = {10.48550/arxiv.2609.35668},
eprint = {2609.35668},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.35668},
}
RIS
TY - UNPB
TI - Optimal Query Complexity for Ground-State Preparation
AU - Boyang Chen
AU - Minbo Gao
AU - Xinzhao Wang
AU - Shuo Zhou
PY - 2026
DA - 2026/10/01
PB - arXiv
DO - 10.48550/arxiv.2609.35668
UR - https://arxiv.org/abs/2609.35668
AB - 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 U_H be an α-block-encoding of a Hamiltonian with unique ground state |ψ_0⟩, and suppose |⟨ψ_0|U_I|0⟩|≥γ 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 ε of the ground state. One uses O((α/Δ)(γ^−1+log(1/ε))) calls to U_H in expectation; the other uses O((α/(γΔ))log(1/ε)) 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(γ^−1log(1/ε)) 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((α/Δ)√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.
ER -