The complexity of complex quantum systems

我们在日常经验中遇到的物理世界表现出惊人的复杂性和现象的丰富性，即使产生这些现象的相互作用和规则可能很简单。人们早就注意到，计算复杂性的概念和自然物理系统的局部哈密顿模型的基态性质之间存在着深刻的联系：这种联系是哈密顿复杂性领域关注的焦点。重要的是，引用物理学上的丘奇·图灵命题，人们可以将长的平衡时间与识别这种模型的基态的计算难度联系起来。此外，复杂性是我们对物理系统的理论描述中一个不存在的问题。在这里，将物质分类为可有效模拟的相或给定某些资源难以处理的相的问题是一个长期存在的开放问题。基于这些方向的早期步骤，在这个提议中，我们认为计算复杂性和复杂量子系统研究之间的联系比最初预期的要深入得多。该项目提出了一个确定计算复杂性概念与凝聚态物理学中相互作用量子多体系统研究之间密切联系的协调计划，涉及低温物理学，开放系统的动力学方面，基态连接性和能量障碍问题，可分离基态的复杂性，张量网络收缩的复杂性，多体局域化和玻璃态动力学的概念，超越了严格意义上的哈密顿复杂性。更重要的是，该项目的一个关键目标是识别在最坏情况下难以解决的问题的有效可解实例，例如张量网络的收缩或蒙特卡洛的臭名昭著的符号问题，从而有助于对物质的计算易处理阶段进行分类。结合物理系统本质中固有的复杂性以及我们对这种系统的理论描述的观点，我们认为物质的相可以用纯粹的计算术语来捕获。这项研究背后的“大图景”是一个大胆的假设，即对量子多体系统如何与局域相互作用相互作用的理解可以在计算机科学方面获得，从而导致新的定量预测。

The physical world that we encounter in our everyday experience exhibits a remarkable degree of complexity and richness of phenomena, even though the interactions and rules giving rise to these phenomena can be simple. It has long been noted that there is a profound link between notions of computational complexity and ground state properties of local Hamiltonian models of natural physical systems: This link is in the focus of attention of the field of Hamiltonian complexity. Importantly, invoking the physical Church Turing thesis, one can relate long equilibration times with the computational hardness of identifying the ground states of such models. Moreover, complexity is an ominpresent issue in our theoretical descriptions of physical systems. Here, the problem of classifying matter into phases that are efficiently simulable, or intractable given certain resources, is a long-standing open problem. Based on early steps in these directions, in this proposal, we suggest that the link between computational complexity and the study of complex quantum systems runs much deeper than originally anticipated. This project suggests a concerted program of identifying the close links between notions of computational complexity and the study of interacting quantum many-body systems in condensed matter physics, in aspects of low-temperature physics, dynamical aspects of open systems, ground state connectivity and the energy barrier problem, the complexity of separable ground states, the complexity of tensor network contraction, notions of many-body localisation and glassy dynamics, beyond mere Hamiltonian complexity in the strict sense. What is more, a key goal of the project is to identify efficiently solvable instances of problems that are intractable in the worst case, examples being the contraction of tensor networks or the notorious sign problem of Monte Carlo, thus contributing to the classification of a computationally tractable phase of matter. Combining the perspectives from complexity inherent in the nature of physical systems and due to our theoretical description of such systems suggests the claim that the phases of matter can large be captured in purely computational terms. The "big picture" underlying this research is the bold hypothesis that much of the understanding of how quantum many-body systems interacting with local interactions behave can be captured in terms of computer science, leading to new quantitative predictions.