preprint
Beating Grover search for low-energy estimation and state preparation
Harry
Buhrman
author
Sevag
Gharibian
author 715410000-0002-9992-3379
Zeph
Landau
author
François Le
Gall
author
Norbert
Schuch
author
Suguru
Tamaki
author
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.
2024
eng
arXiv:2407.03073
2407.03073
H. Buhrman, S. Gharibian, Z. Landau, F. L. Gall, N. Schuch, and S. Tamaki, “Beating Grover search for low-energy estimation and state preparation,” <i>arXiv:2407.03073</i>. 2024.
Buhrman, Harry, et al. “Beating Grover Search for Low-Energy Estimation and State Preparation.” <i>ArXiv:2407.03073</i>, 2024.
@article{Buhrman_Gharibian_Landau_Gall_Schuch_Tamaki_2024, title={Beating Grover search for low-energy estimation and state preparation}, journal={arXiv:2407.03073}, author={Buhrman, Harry and Gharibian, Sevag and Landau, Zeph and Gall, François Le and Schuch, Norbert and Tamaki, Suguru}, year={2024} }
Buhrman, H., Gharibian, S., Landau, Z., Gall, F. L., Schuch, N., & Tamaki, S. (2024). Beating Grover search for low-energy estimation and state preparation. In <i>arXiv:2407.03073</i>.
H. Buhrman, S. Gharibian, Z. Landau, F.L. Gall, N. Schuch, S. Tamaki, ArXiv:2407.03073 (2024).
Buhrman, Harry, Sevag Gharibian, Zeph Landau, François Le Gall, Norbert Schuch, and Suguru Tamaki. “Beating Grover Search for Low-Energy Estimation and State Preparation.” <i>ArXiv:2407.03073</i>, 2024.
Buhrman H, Gharibian S, Landau Z, Gall FL, Schuch N, Tamaki S. Beating Grover search for low-energy estimation and state preparation. <i>arXiv:240703073</i>. Published online 2024.
550372024-07-04T09:02:42Z2024-07-04T09:03:23Z