Track the frontier, from condensed matter to cosmology.
Search papers, labs, and topics across Lattice.
The authors resolve the optimal quantum query complexity of ground-state preparation within trace-distance error $\varepsilon$, given an energy threshold in the Hamiltonian's spectral gap $\Delta$. They establish two algorithms with matching lower bounds: an expected-complexity approach requiring $O((\alpha/\Delta)(\gamma^{-1} + \log(1/\varepsilon)))$ Hamiltonian queries and $O(1/\gamma)$ state-preparation queries, alongside an optimal worst-case variant. By additively decoupling the inverse initial overlap $\gamma^{-1}$ from target precision $\log(1/\varepsilon)$ in expectation, this work completely closes the complexity landscape for threshold-based ground-state preparation.
Ground-state preparation query complexity is now strictly settled, proving that the overhead of poor initial overlap $\gamma^{-1}$ and target precision $\log(1/\varepsilon)$ can be decoupled additively rather than multiplicatively in expectation.
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.
Tsinghua AI