AF: Small: Approximation algorithms for quantum mechanical problems

计算机科学中的一个基本问题是约束满足问题 MAX-SAT，它问：给定 n 位上的一组布尔约束，通过对所有位进行赋值可以同时满足的最大约束数量是多少？尽管 MAX-SAT 有许多应用，但遗憾的是人们认为它不可能有效地求解。幸运的是，此类问题通常可以通过所谓的近似算法来近似解决。 在量子环境中，存在 MAX-SAT 的物理驱动推广，称为 LH，它涉及极低温度下量子系统的重要属性的计算。不幸的是，与 MAX-SAT 一样，LH 也被认为是棘手的。因此，这个项目提出了一个问题：我们可以通过近似算法的框架计算 k-LH 的近似解吗？这个问题的解决将使我们深入了解我们近似计算自然界中量子系统特性的能力。获得的成果将通过各种途径传播，包括会议、高中研讨会和旨在让公众了解研究前沿的工程公开讲座系列。在较高层面上，该项目旨在为各种类别的局部哈密顿问题（LH）设计多项式时间逼近算法，从物理驱动的特殊情况到更一般的设置。所使用的技术主要受到近似算法和量子信息论领域的想法的启发。除其他结果外，该项目的一个关键目标是深入了解经典有效可表示的量子态如何能够近似解决涉及局部哈密顿量的地面空间的真正量子问题。

A fundamental problem in computer science is the constraint satisfaction problem MAX-SAT, which asks: Given a set of Boolean constraints on n bits, what is the maximum number of constraints which can be simultaneously satisfied by an assignment to all the bits? Despite its many applications, MAX-SAT is unfortunately believed to be impossible to solve efficiently. Fortunately, such problems can often be solved approximately via so-called approximation algorithms.In the quantum setting, a physically motivated generalization of MAX-SAT exists, known as LH, which concerns the computation of important properties of quantum systems at very low temperatures. Unfortunately, like MAX-SAT, LH is also believed intractable. This project hence asks the question: Can we compute approximate solutions to k-LH via the framework of approximation algorithms? The resolution of this question will yield deep insight into our ability to approximately compute properties of quantum systems in nature. The results obtained will be disseminated through a variety of avenues, including conferences, high school workshops, and engineering public lecture series aimed at exposing the general public to the frontiers of research. At a high level, this project aims to design polynomial-time approximation algorithms for a variety of classes of the local Hamiltonian problem (LH), from physically motivated special cases to more general settings. The techniques used are inspired primarily by ideas from the fields of approximation algorithms and quantum information theory. Among other results, a key aim of the project is to obtain insight into how well classically efficiently representable quantum states can approximate solutions to genuinely quantum problems involving ground spaces of local Hamiltonians.