AF: Small: Ground State Complexity in Quantum Many-Body Systems

量子信息论的中心目标之一是从计算复杂性的角度来理解量子系统。几十年来，物理学家一直在使用计算机来理解量子系统的各个方面，但这些方法通常是启发式的，只在有限类别的系统上取得成功。通过计算和信息论的复杂性来理解量子系统，已经导致了物理学中新的强大的计算方法，并更深入地了解了一旦我们走出特定的类，这些方法会失败的原因。同时，硬度结果往往对量子计算有重要的影响。如果计算一个系统的性质和计算一个任意量子电路的输出一样困难，那么这个系统就会成为量子计算机的候选者。这个建议特别关注基态的复杂性，基态是系统的最低能量状态。计算量子系统的基态能量有多难？系统的哪些特性会导致计算基态的算法被证明是有效的？基态的结构是什么？在什么情况下，基州会有一个简洁的表述？PI将在一维系统的背景下探索这些问题，并将开始研究对其知之甚少的二维系统。

One of the central goals of quantum information theory is to understand quantum systems from the standpoint of computational complexity. Physicists have been using computers for decades to understand various aspects of quantum systems, but these methods are typically heuristic and achieve success on only limited classes of systems. Understanding quantum systems through the lens of computational and information-theoretic complexity has already lead to new powerful computational methods in physics and deeper insight into what causes these methods to fail once we step outside specific classes. Meanwhile hardness results often have important implications for quantum computation. If computing a property of a system is shown to be as difficult as computing the output of an arbitrary quantum circuit, that system becomes a candidate for a quantum computer.This proposal focuses specifically on the complexity of ground states, the lowest energy state of a system. How hard is it to compute the ground energy of a quantum system? What are the properties of a system that give rise to provably efficient algorithms to compute the ground state? What is the structure of the ground state? Under what circumstances does the ground state have a succinct representation? The PI will pursue these questions in the context of one-dimensional systems and will begin work on two-dimensional systems about which much less is known.