Co-authored by Harry Buhrman, Sevag Gharibian, Zeph Landau, François Le Gall, Norbert Schuch, and Suguru Tamaki, the work titled "Beating the Natural Grover Bound for Low-Energy Estimation and State Preparation" has just been published in Physical Review Letters [Physical Review Letters 135, 030601 (2025)].
For more information on this paper, take a look at the abstract below and at the open-access article (DOI: 10.1103/29qw-bssx).
Abstract
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 2cn/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.
This work has received support through the ERC grant SEQUAM as well as the Austrian Science Fund FWF (grant DOIs 10.55776/COE1, 10.55776/P36305 and 10.55776/F71), and the European Union (NextGenerationEU).
