多项式时间结论究竟覆盖什么
这篇论文回答了此前工作留下的一个问题。经典算法此前已经能够在足够高的温度下估计SYK模型的局部热期望，但只能在准多项式时间内完成。这项工作表明，局部可观测量可以在所有恒定温度下于多项式时间内被估计。
这一区分很重要，因为两种结果不是同一类保证。准多项式时间算法的规模约为exp(polylog N)；多项式时间算法的规模为N^k，其中k固定。论文还把相关技术推广到经典系统，解决了一个关于在经典自旋玻璃相变之前计算其热期望的开放问题。
该结论针对的是估计局部可观测量，而不是表示完整的热态。摘要指出，高斯态与热态相距甚远，表示热态需要大型多项式规模的量子电路。算法结果关注的是局部期望，这比完整态制备是更窄的目标。
SYK为何看起来经典上很难
SYK模型定义在具有随机四体相互作用的Majorana费米子上，在凝聚态物理和全息对偶中被大量研究。论文列出了若干暗示经典困难的障碍：符号问题、纠缠、magic，以及其热态巨大的量子电路复杂度。
与经典Ising p-spin模型不同，SYK模型在任何温度下都没有热力学相变。这消除了一个障碍，但没有消除其他障碍。此前针对SYK的严格经典算法基于证明配分函数在复β平面上的无零点区域，论文指出这些技术很可能失效。
此前的高温集团展开在恒定温度下似乎也失效。因此，这一差距不只是优化常数的问题；要到达所有恒定温度，需要一种不同的证明技术。
用通俗语言理解量子腔方法
主要技术步骤是证明经验两点场在鞍点解G*附近的集中性。论文使用腔方法来证明这一点，该方法通过从N+1个格点迭代地约化到N个格点来进行：每个费米子被移除与哈密顿量其余部分的相互作用，转而耦合到一个自由浴。
在经典版本中，加入一个带有新无序的自旋σ_{N+1}，可以把新的配分函数写成腔期望的形式。如果关联函数分解为局部期望的乘积，腔自旋就会感受到一个容易求解的有效哈密顿量。量子版本则把新增Majorana费米子的相互作用浴替换为一个由能量为x_j、耦合为v_j的自由费米子模式组成的二次浴。
论文强调，要让这一方法对SYK严格成立是困难的。直接证明四点关联函数的分解很困难，而此前关于退火自由能的严格工作使用了算子代数的de Finetti定理。这里的构造转而使用谱舍入、测量和细致平衡的恢复，以达到算法所需的足够强的集中性。
从集中性到多项式时间算法
集中性界被表述为定理4：对于由ψ_i和G*构造的有限多个算子的Hermitian线性组合B，e^{βH} B^{2m}的归一化迹被界定为C^m N^{-δm/(4r+4)}。这种随矩阶m增强的N衰减，正是使展开能够达到任意反多项式误差的原因。
腔计算选择浴的能量和耦合，使自能Σ等于β²G³，从构造上匹配SYK鞍点方程。引理17表明，所得二次哈密顿量的两点函数D(Σ)可以表示为自由费米子两点函数。
一旦G和Σ逼近N→∞的解，算法就使用梯形核围绕G*、Σ*展开。论文指出，控制误差需要先有集中性界，而没有量子腔方法这一点很困难。在经典Ising p-spin情形中，p=2需要类似的重新求和，而p≥3不需要，因为其Hessian是平凡的，允许更简单的算法；但两种情形仍然都需要腔方法证明集中性。
经典自旋玻璃结果及其阈值
对于p≥3的经典Ising p-spin模型，该模型具有自旋玻璃相。从无穷温度冷却会在动力学转变1/β_d处陷入亚稳态，而在该转变处，一大类自然算法，例如低阶或稳定算法，也无法从Gibbs测度中采样。
此前的工作表明，准多项式时间算法仍然可以在某些β > β_d处估计局部可观测量的热期望，使用的是Barvinok插值方法。该技术通常在热力学相变之上成功，此时自由能密度在N→∞极限下变得非解析。对于Ising p-spin模型，相变发生在比动力学转变1/β_d更冷的温度1/β*处。
开放问题是，热期望能否一直被高效估计到β*。这篇论文解决了经典自旋玻璃的这一问题，把技术从量子情形直接推广过来。相关阈值是热力学相变β*，而不是动力学转变β_d。
从Gibbs态学习SYK哈密顿量
作为一个应用，论文给出了一种量子算法，可以在任意恒定温度下从Gibbs态学习SYK哈密顿量，具有多项式时间和样本复杂度。这改进了此前的工作，后者获得了从多项式多个高温Gibbs态副本中学习SYK系数的准多项式时间算法，并在所有温度下具有多项式样本复杂度。
该学习算法测量哈密顿量项，并考虑领头阶修正，用物理术语说就是1/N平均场修正，以恢复耦合。用图语言说，它直接使用来自鞍点解的领头阶和1/N修正，然后用腔方法界定高阶余项。
论文指出，由于有了量子腔方法，该算法及其分析相当直接。这是一个由证明技术而非新的测量原语驱动改进的例子。
保证在哪里停止
多项式时间保证适用于在所有恒定温度下估计局部热期望。论文没有声称对随系统规模缩放的温度具有多项式时间，也没有声称可以高效制备完整热态。摘要明确把局部期望与表示热态进行对比，后者需要大型多项式规模的量子电路。
经典自旋玻璃结果被表述为计算直至相变的热期望。论文把向经典系统的推广描述为直接的，但阈值仍然是热力学相变，而不是超越它。
论文还指出，它所改进的严格经典算法基于复β平面上的无零点区域，而这些技术很可能失效。新方法是一套形式化的量子腔方法，论文预期它会在优化、采样、推断和学习中找到进一步应用，但这些是作为预期而非已证明的结果提出的。
腔构造中最值得关注之处
这篇论文中最具决策相关性的比较是动力学转变β_d与热力学相变β*之间的比较。自然算法在β_d处失效，此前的严格算法到达了某些β > β_d。这项工作对经典自旋玻璃到达β*，对SYK到达所有恒定温度。仍然存在的差距是β*与零温之间的差距，而不是β_d与β*之间的差距。
第二个比较是准多项式时间与多项式时间之间的比较。此前的SYK结果是准多项式的；这次是多项式的。对于评估经典模拟是否实用的读者来说，多项式缩放是相关变化，它来自随矩阶增强的集中性界。
论文自身的框架把量子腔方法视为可迁移的贡献。具体的算法成果是SYK热期望算法、SYK哈密顿量学习算法，以及经典自旋玻璃直至β*的结果。关于进一步应用的预期被明确标记为预期，因此读者应把已证明的结果与预测的结果分开看待。
本文引用的文献
Polynomial-time classical algorithms for mean-field models up to the glass transition
经典算法可以在多项式时间内估计SYK模型在所有恒定温度下的局部热期望，并且同样的技术解决了一个关于在经典自旋玻璃相变之前计算其热期望的开放问题。