AF: Medium: Quantum Hamiltonian Complexity: Through the Computational Lens

量子计算告诉我们，一般来说，量子系统是指数级强大的。这是一把双刃剑：在使量子计算机成为可能的同时，它也是分析和理解物理系统的巨大障碍。事实上，这不仅仅是一个抽象的问题；随着凝聚态物理学在研究和创造高度纠缠态方面的重大推动，这些系统的计算复杂性已经成为一个主要问题，这是量子哈密顿复杂性新兴领域的主要焦点。这里列出了这一领域的三个基本问题：能“典型”的状态吗？自然发生的吗?量子系统应该被简洁地描述（即，粒子数量是多项式而不是指数）？一般量子系统的指数复杂性在高温下是否持续存在？科学方法是否足够强大，可以应用于一般的量子系统？每个问题都可以被表述为一个精确的计算问题——第一个问题是关于复杂度类NP问题的自然推广，第二个问题是关于著名的PCP定理，第三个问题是关于交互证明系统的。在过去的几年里，对这些问题的一些显著的积极答案的概要已经出现，并且有一些必要的基本技术来解决这些问题。本项目旨在探究这一问题。这个项目在最深层次上是跨学科的。它带来了一个计算的镜头，承担在凝聚态物理和科学哲学的一些最基本的问题。相反，它在重要的新方向上扩展了计算复杂性理论的核心概念，同时借鉴了物理学的深刻见解，在基本问题上取得了进展。

Quantum computation has taught us that, in general, quantum systems are exponentially powerful. This is a double-edged sword: while making quantum computers possible, it is also an enormous obstacle to analyzing and understanding physical systems. Indeed, this is not just an abstract concern; with the major push in condensed matter physics towards studying and creating highly entangled states of matter, the computational complexity of these systems has moved to the fore as a major issue, and this is the main focus of the emerging area of Quantum Hamiltonian Complexity. Here is a list of three basic questions in this area:1. Can "typical" states of ?naturally occurring? quantum systems be described succinctly (i.e. polynomial rather than exponential in the number of particles)?2. Does the exponential complexity of general quantum systems persist at high temperature?3. Is the scientific method sufficiently powerful to be applicable to general quantum systems?Each of these can be formulated as a precise computational question -- the first is a natural generalization of a question about the complexity class NP, the second about the celebrated PCP theorem and the third about interactive proof systems. Over the last few years the outline of remarkable positive answers to some of these questions has emerged, and there are in place some of the basic techniques necessary to tackle these questions. This project aims to pursue this line of inquiry.This project is interdisciplinary at the deepest level. It brings a computational lens to bear on some of the most basic issues in condensed matter physics and in the philosophy of science. Conversely, it extends the core concepts of computational complexity theory in important new directions, at the same time drawing on deep insights from physics to make progress on fundamental questions.