Complexity of the Guided Local Hamiltonian Problem: Improved Parameters and Extension to Excited States

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\ge 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 $(\frac{1}{2}-\mathrm{\Omega }\left(\frac{1}{(n)}\right))$. 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-\mathrm{\Omega }\left(\frac{1}{(n)}\right)$, 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.