Optimizing strongly interacting fermionic Hamiltonians
Optimizing strongly interacting fermionic Hamiltonians
复制标题
DOI：
10.1145/3519935.3519960
复制
发表时间：
2021-10
期刊：
影响因子：
--
通讯作者：
M. Hastings;R. O'Donnell
中科院分区：
文献类型：
--
作者：
M. Hastings;R. O'Donnell
许多物理学和量子化学中的基本问题是在某些反对易变量中优化低次多项式。作为一个量子力学问题，在许多情况下，我们不知道最优的有效经典见证，甚至不知道最优的近似。一个突出的例外是，当最优状态被描述为所谓的“高斯态”时，也被称为自由费米子态。在这项工作中，我们感兴趣的是当不存在好的高斯态时，这个优化问题的复杂性。我们的主要实验平台是随机次Q多项式的Sachdev-Ye-Kitaev(SYK)模型，这是当前凝聚态物理和弦理论中非常感兴趣的模型，从计算复杂性的角度来看，它具有显著的性质。在其他结果中，我们给出了Q=4SYK模型中最大本征值上界的一个有效的经典认证算法，以及这个最大本征值下界的一个有效的量子认证算法；这两个算法都以高概率实现了恒因子近似。
The fundamental problem in much of physics and quantum chemistry is to optimize a low-degree polynomial in certain anticommuting variables. Being a quantum mechanical problem, in many cases we do not know an efficient classical witness to the optimum, or even to an approximation of the optimum. One prominent exception is when the optimum is described by a so-called “Gaussian state”, also called a free fermion state. In this work we are interested in the complexity of this optimization problem when no good Gaussian state exists. Our primary testbed is the Sachdev–Ye–Kitaev (SYK) model of random degree-q polynomials, a model of great current interest in condensed matter physics and string theory, and one which has remarkable properties from a computational complexity standpoint. Among other results, we give an efficient classical certification algorithm for upper-bounding the largest eigenvalue in the q=4 SYK model, and an efficient quantum certification algorithm for lower-bounding this largest eigenvalue; both algorithms achieve constant-factor approximations with high probability.