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≥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 (12−Ω(1poly(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−Ω(1poly(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.
|Fermioniq, Amsterdam, the Netherlands|
|Startimpuls Nationale Quantumtechnologie (KAT-1)|
|Organisation||Algorithms and Complexity|
Cade, C.W, Folkertsma, M.J, & Weggemans, J.R. (2022). Complexity of the Guided Local Hamiltonian Problem: Improved Parameters and Extension to Excited States. doi:10.48550/arXiv.2207.10097