Abstract
The field of quantum Hamiltonian complexity lies at the intersection of quantum manybody physics and computational complexity theory, with deep implications to both fields. The main object of study is the Local Hamiltonian problem, which is concerned with estimating the groundstate energy of a local Hamiltonian and is complete for the class QMA, a quantum generalization of the class NP. A major challenge in the field is to understand the complexity of the Local Hamiltonian problem in more physically natural parameter regimes. One crucial parameter in understanding the ground space of any Hamiltonian in manybody physics is the spectral gap, which is the difference between the smallest two eigenvalues. Despite its importance in quantum manybody physics, the role played by the spectral gap in the complexity of the Local Hamiltonian problem is less wellunderstood. In this work, we make progress on this question by considering the precise regime, in which one estimates the groundstate energy to within inverse exponential precision. Computing groundstate energies precisely is a task that is important for quantum chemistry and quantum manybody physics.
In the setting of inverseexponential precision (promise gap), there is a surprising result that the complexity of Local Hamiltonian is magnified from QMA to PSPACE, the class of problems solvable in polynomial space (but possibly exponential time). We clarify the reason behind this boost in complexity. Specifically, we show that the full complexity of the high precision case only comes about when the spectral gap is exponentially small. As a consequence of the proof techniques developed to show our results, we uncover important implications for the representability and circuit complexity of ground states of local Hamiltonians, the theory of uniqueness of quantum witnesses, and techniques for the amplification of quantum witnesses in the presence of postselection.
BibTeX  Entry
@InProceedings{deshpande_et_al:LIPIcs.ITCS.2022.54,
author = {Deshpande, Abhinav and Gorshkov, Alexey V. and Fefferman, Bill},
title = {{The Importance of the Spectral Gap in Estimating GroundState Energies}},
booktitle = {13th Innovations in Theoretical Computer Science Conference (ITCS 2022)},
pages = {54:154:6},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959772174},
ISSN = {18688969},
year = {2022},
volume = {215},
editor = {Braverman, Mark},
publisher = {Schloss Dagstuhl  LeibnizZentrum f{\"u}r Informatik},
address = {Dagstuhl, Germany},
URL = {https://drops.dagstuhl.de/opus/volltexte/2022/15650},
URN = {urn:nbn:de:0030drops156501},
doi = {10.4230/LIPIcs.ITCS.2022.54},
annote = {Keywords: Local Hamiltonian problem, PSPACE, PP, QMA}
}
Keywords: 

Local Hamiltonian problem, PSPACE, PP, QMA 
Collection: 

13th Innovations in Theoretical Computer Science Conference (ITCS 2022) 
Issue Date: 

2022 
Date of publication: 

25.01.2022 