论文标题
光谱差距在估计基础能量中的重要性
Importance of the spectral gap in estimating ground-state energies
论文作者
论文摘要
量子哈密顿复杂性的领域在于量子多体物理学和计算复杂性理论的交集，对这两个领域都有深刻的影响。研究的主要目的是Localhamiltonian问题，它涉及估计当地哈密顿量的基础能量，并且对于QMA类是完整的，QMA是NP类的量子概括。该领域的一个主要挑战是了解Localhamiltonian问题在更自然的参数方面的复杂性。在理解多体物理学中任何哈密顿量的地面空间的一个关键参数是光谱间隙，这是最小的两个特征值之间的差异。尽管它在量子多体物理学中的重要性，但频谱差距在Localhamiltonian的复杂性中所扮演的角色却不太受到良好的理解。在这项工作中，我们通过考虑确切的制度来在这个问题上取得进展，在该制度中，人们将基础能量估算为在反指数级的精度内。精确计算地面能量是一项对于量子化学和量子多体物理学很重要的任务。 在逆指数精度的情况下，令人惊讶的结果是，Localhamiltonian的复杂性从QMA放大到Pspace，这是多项式空间中可解决的问题类别。我们澄清了这种复杂性的原因。具体而言，我们表明，只有在频谱差距成倍小时，高精度案例的全部复杂性才会出现。由于开发了证明我们的结果的证明技术的结果，我们发现了对当地汉密尔顿人的基础状态，量子见证人的唯一性理论的代表性和回路复杂性的重要含义，以及在选择后的情况下放大量子证人的技术。
The field of quantum Hamiltonian complexity lies at the intersection of quantum many-body physics and computational complexity theory, with deep implications to both fields. The main object of study is the LocalHamiltonian problem, which is concerned with estimating the ground-state 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 LocalHamiltonian problem in more physically natural parameter regimes. One crucial parameter in understanding the ground space of any Hamiltonian in many-body physics is the spectral gap, which is the difference between the smallest two eigenvalues. Despite its importance in quantum many-body physics, the role played by the spectral gap in the complexity of the LocalHamiltonian is less well-understood. In this work, we make progress on this question by considering the precise regime, in which one estimates the ground-state energy to within inverse exponential precision. Computing ground-state energies precisely is a task that is important for quantum chemistry and quantum many-body physics. In the setting of inverse-exponential precision, there is a surprising result that the complexity of LocalHamiltonian is magnified from QMA to PSPACE, the class of problems solvable in polynomial space. 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.
