2022-07-20
Complexity of the Guided Local Hamiltonian Problem: Improved Parameters and Extension to Excited States
Publication
Publication
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.
| Additional Metadata | |
|---|---|
| Fermioniq, Amsterdam, the Netherlands | |
| doi.org/10.48550/arXiv.2207.10097 | |
| 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
|
|
