热力学极限下的哈密顿复杂性

《Journal of the ACM》：Hamiltonian Complexity in the Thermodynamic Limit

量子计算复杂性研究：针对平移不变哈密顿量在热力学极限下基态能量估计的复杂度问题，通过构建环形时钟结构模型，结合谱图论方法证明了该问题属于FEXP^QMA-EXP且困难于FEXP^NEXP，揭示其双重指数复杂度特性。

　　

摘要

尽管在过去十年中，量子哈密顿量复杂性研究取得了巨大进展，但对于热力学极限下的量子物理计算复杂性仍知之甚少。事实上，正确定义这个问题本身并不容易。我们研究了在热力学极限下，如何以给定的精度估算一个固定且平移不变的（TI）哈密顿量的基态能量；这个精度（由参数n表示，即近似所需的比特数）是问题的唯一输入。理解这个问题的复杂性，有助于我们了解物理学家在热力学极限下测量或计算物理量近似值时所面临的难度。我们证明了该问题属于FEXP^{QMA-EXP ? L}复杂度类，并且对于FEXP^NEXP复杂度类来说是难以解决的。这意味着该问题的难度与输入大小的关联是“双重”指数级的。

作为我们研究的一部分，我们探讨了计算平移不变的一维有限链的基态能量的问题。在有限链中，每个粒子对都作用着一个固定的哈密顿量项。在这种情况下，链的长度是问题的唯一输入，任务是计算基态能量的近似值。与标准形式的局部哈密顿量问题不同，这里没有设定任何阈值。我们证明该问题属于FP^QMA-EXP复杂度类，并且对于FP^NEXP复杂度类来说也是困难的。我们的技术采用了一种循环时钟结构，通过循环的长度来校准基态能量。这需要比以往的QMA-复杂性证明方法更精确的基态能量表达式，甚至需要对无限情况使用谱图理论技术来推导出精确的解析界限。据我们所知，这是首次利用“电路到哈密顿量”的构造方法来证明某个函数类的复杂性。