Near-Optimal Ground State Preparation*

Preparing the ground state of a given Hamiltonian and estimating its ground energy are important but computationally hard tasks. However, given some additional information, these problems can be solved efficiently on a quantum computer. We assume that an initial state with non-trivial overlap with the ground state can be efficiently prepared. With this assumption we propose a hybrid quantum-classical algorithm to estimate the ground energy, where the dependence of the number of queries to the initial state on the desired precision is exponentially improved compared to current state-of-the-art algorithms. When further assuming the existence of a spectral gap, we design an algorithm that prepares the ground state, whose runtime has a logarithmic dependence on the inverse error. We also prove that our algorithms reach the complexity lower bounds by applying it to the unstructured search problem and the quantum approximate counting problem.