Quantum Glassiness from Efficient Learning

Eric R. Anschuetz

doi:10.1007/s00220-025-05536-7

2026-01-14

PRE

Eric R. Anschuetz *

DOI：10.1007/s00220-025-05536-7

原文链接

原文求助

摘要

En 中文

我们展示了量子学习理论与算法难度之间的关系。我们利用用于能量估计的高效局部学习算法（如经典影子算法）的存在性，证明对于满足特定拓扑性质的混乱量子系统，在平均情况下无法用Lipschitz量子算法找到近基态。我们的结果的一个推论是，许多标准量子算法在寻找这些系统的近基态时会失败，包括从任意初始状态的时-时间T Lindbladian动力学、时-时间T量子退火、精度为T位的相位估计以及深度-T变分量子算法，只要T小于某个与系统大小对数成比例的普适常数。为此，我们引入了量子系统重叠间隙性质（OGP）的一个推广，称为量子重叠间隙性质（QOGP）。该性质由高效局部学习算法输出的低能量子态表示的特定拓扑结构定义。我们证明，对于其输出在输入扰动下稳定的量子算法，准备满足QOGP的系统低能态是不可行的。然后我们证明，QOGP对于量子p-自旋模型的稀疏化变体成立，给出了已知的首个量子算法在寻找非Stoquastic、非交换量子系统基态时的算法近似难度结果。我们关于使用Lindbladian演化优化该模型的量子算法的下界结果（在常数因子范围内）与优化经典p-自旋模型的经典Langevin动力学的已知最佳时间下界相匹配。因此我们推测，使用量子算法寻找这些量子自旋模型典型实例的基态，在实践中与经典算法优化经典p-自旋模型一样不可行。相反，我们证明Sachdev-Ye-Kitaev模型不满足QOGP，这与该模型在低温下快速混合的先前证据一致。

Keyword:

quantum learning theory

algorithmic hardness

quantum overlap gap property

ground state estimation

quantum spin models