Abstract
Recently it was shown that the so-called guided local Hamiltonian problem -- estimating the smallest eigenvalue of a k-local Hamiltonian when provided with a description of a quantum state ('guiding state') that is guaranteed to have substantial overlap with the true groundstate -- is BQP-complete for k ≥ 6 when the required precision is inverse polynomial in the system size n, and remains hard even when the overlap of the guiding state with the groundstate is close to a constant (1/2 - Ω(1/poly(n))). We improve upon this result in three ways: by showing that it remains BQP-complete when i) the Hamiltonian is 2-local, ii) the overlap between the guiding state and target eigenstate is as large as 1 - Ω(1/poly(n)), and iii) when one is interested in estimating energies of excited states, rather than just the groundstate. Interestingly, iii) is only made possible by first showing that ii) holds.