Beating the Natural Grover Bound for Low-Energy Estimation and State Preparation

Estimating ground state energies of many-body Hamiltonians is a central task in many areas of quantum physics. In this Letter, we give quantum algorithms which, given any k-body Hamiltonian H, compute an estimate for the ground state energy and prepare a quantum state achieving said energy, respectively. Specifically, for any ϵ>0, our algorithms return, with high probability, an estimate of the ground state energy of H within additive error ϵM, or a quantum state with the corresponding energy. Here, M is the total strength of all interaction terms, which in general is extensive in the system size. Our approach makes no assumptions about the geometry or spatial locality of interaction terms of the input Hamiltonian and thus handles even long-range or all-to-all interactions, such as in quantum chemistry, where lattice-based techniques break down. In this fully general setting, the run-time of our algorithms scales as 2^{cn/2} for c<1, yielding the first quantum algorithms for low-energy estimation breaking a standard square root Grover speedup for unstructured search. The core of our approach is remarkably simple, and relies on showing that an extensive fraction of the interactions can be neglected with a controlled error. What this ultimately implies is that even arbitrary k-local Hamiltonians have structure in their low energy space, in the form of an exponential-dimensional low energy subspace.