@inproceedings{32407,
  abstract     = {{Estimating the ground state energy of a local Hamiltonian is a central
problem in quantum chemistry. In order to further investigate its complexity
and the potential of quantum algorithms for quantum chemistry, Gharibian and Le
Gall (STOC 2022) recently introduced the guided local Hamiltonian problem
(GLH), which is a variant of the local Hamiltonian problem where an
approximation of a ground state is given as an additional input. Gharibian and
Le Gall showed quantum advantage (more precisely, BQP-completeness) for GLH
with $6$-local Hamiltonians when the guiding vector has overlap
(inverse-polynomially) close to 1/2 with a ground state. In this paper, we
optimally improve both the locality and the overlap parameters: we show that
this quantum advantage (BQP-completeness) persists even with 2-local
Hamiltonians, and even when the guiding vector has overlap
(inverse-polynomially) close to 1 with a ground state. Moreover, we show that
the quantum advantage also holds for 2-local physically motivated Hamiltonians
on a 2D square lattice. This makes a further step towards establishing
practical quantum advantage in quantum chemistry.}},
  author       = {{Gharibian, Sevag and Hayakawa, Ryu and Gall, François Le and Morimae, Tomoyuki}},
  booktitle    = {{Proceedings of the 50th EATCS International Colloquium on Automata, Languages and Programming (ICALP)}},
  number       = {{32}},
  pages        = {{1--19}},
  title        = {{{Improved Hardness Results for the Guided Local Hamiltonian Problem}}},
  doi          = {{10.4230/LIPIcs.ICALP.2023.32}},
  volume       = {{261}},
  year         = {{2023}},
}