Complexity of the Guided Local Hamiltonian Problem: Improved Parameters and Extension to Excited States
share
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.
READ FULL TEXT