Optimal ways to prepare quantum ground states with fewer queries
Optimal Query Complexity for Ground-State Preparation
Computational ComplexityData Structures and Algorithms
Summary
Preparing the lowest energy state, or ground state, of a quantum system is important for quantum computing and simulations. This paper finds the best possible number of times you need to use certain quantum operations (queries) to successfully prepare this ground state within a desired accuracy. The authors provide two methods: one that is efficient on average and one that guarantees performance in the worst case. They also prove that no algorithm can use fewer queries than the one they present, making their methods optimal for this task.
What this means in practice
- •For quantum algorithm developers: Design algorithms that prepare quantum ground states using the fewest possible quantum operations for simulations or computations.
- •For quantum hardware engineers: Optimize quantum device control sequences to prepare ground states efficiently with provably minimal resource use.
A theory result. No direct application yet.
Authors
Boyang Chen, Minbo Gao, Xinzhao Wang, Shuo Zhou
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.