论文标题
接近最佳的基态准备
Near-optimal ground state preparation
论文作者
论文摘要
准备给定的哈密顿量的基态并估算其基础能量很重要，但在计算上的艰巨任务。但是，鉴于一些其他信息，这些问题可以在量子计算机上有效解决。我们假设可以有效制备具有非平凡重叠的初始状态，并且地面能量与第一个激发能之间的光谱差距从下方界定。有了这些假设，我们设计了一种算法，该算法在已知地面能的上限时会制备基态，该算法的运行时间对反向误差具有对数依赖性。 When such an upper bound is not known, 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 the current state-of-the-art algorithm proposed in [Ge et al. 2019]。然后可以将这两种算法组合在一起以制备基态，而不知道地面能的上限。我们还证明，我们的算法通过将其应用于非结构化搜索问题和量子近似计数问题来达到复杂性下限。
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, and the spectral gap between the ground energy and the first excited energy is bounded from below. With these assumptions we design an algorithm that prepares the ground state when an upper bound of the ground energy is known, whose runtime has a logarithmic dependence on the inverse error. When such an upper bound is not known, 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 the current state-of-the-art algorithm proposed in [Ge et al. 2019]. These two algorithms can then be combined to prepare a ground state without knowing an upper bound of the ground energy. 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.
