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.