@unpublished{55037,
abstract = {{Estimating ground state energies of many-body Hamiltonians is a central task
in many areas of quantum physics. In this work, 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 $\varepsilon>0$, our algorithms return, with high
probability, an estimate of the ground state energy of $H$ within additive
error $\varepsilon 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 runtime of our algorithms scales as $2^{cn/2}$ for $c<1$, yielding
the first quantum algorithms for low-energy estimation breaking the natural
bound based on Grover search. The core of our approach is remarkably simple,
and relies on showing that any $k$-body Hamiltonian has a low-energy subspace
of exponential dimension.}},
author = {{Buhrman, Harry and Gharibian, Sevag and Landau, Zeph and Gall, François Le and Schuch, Norbert and Tamaki, Suguru}},
booktitle = {{arXiv:2407.03073}},
title = {{{Beating Grover search for low-energy estimation and state preparation}}},
year = {{2024}},
}