CAREER: Complexity of quantum many-body systems: learnability, approximations, and entanglement

粒子之间的相互作用产生了在物理世界中看到的物质，并促进了对物质的研究和操纵。然而，在量子领域，量子粒子之间的相互作用可能会带来令人生畏的挑战--它强制执行粒子的复杂集体行为，而这些行为似乎很难使用当前的计算手段进行研究。这个项目旨在通过调查一系列基本问题来确定这种复杂性的本质。首先，交互本身是否足够简单，以至于它们的精确知识可以通过实用的算法获得？这样的算法预计也将使量子技术受益，促进量子设备的学习和测试。第二，即使相互作用的知识是可用的，估计量子粒子的物理性质在计算上有多困难？这个问题将有助于理解近期量子设备在探测量子粒子方面的局限性。第三，在一些关于相互作用的常见假设下，粒子的集体行为可能是简单的而不是复杂的吗？这将允许有效的方法来计算模拟尊重这些假设的系统。该教育计划以计算和物理为中心，包括在哈佛大学举办一系列研讨会，讲者名单多样，在哈佛大学为研究生和本科生开发量子计算课程，以及向波士顿高中的学生教授量子理论，这些高中的学生接受科学、技术、工程和数学教育的机会有限。这个项目将研究局部哈密顿理论--理论计算机科学中约束满足问题的量子类似物--模拟量子多体系统中的相互作用。特别是，它将致力于在三个长期存在的问题上取得进展：能否从吉布斯量子态有效地学习局部哈密顿量？局域哈密顿量(量子概率可查证明猜想)的基能量近似的基本极限是什么？有限纠缠对二维有隙局域哈密顿量(面积定律猜想)的基态成立吗？这些问题从可学习性、可近似性和纠缠这三个已经研究得很好的度量的角度来讨论量子多体系统的复杂性。这是受到理论计算机科学中衡量计算复杂性的三种成功方法的启发-时间复杂性、空间复杂性和随机性。事实上，理论计算机科学的想法预计将对在上述问题上取得进展至关重要。此外，研究将增加量子技术方面的知识：哈密顿学习技术将用于可编程量子设备的测试，量子概率可核查证明猜想的进展将限制各种近期量子算法解决量子多体问题的效率。该奖项反映了NSF的法定使命，并通过使用基金会的智力优势和更广泛的影响审查标准进行评估，被认为值得支持。

Interaction between particles gives rise to the matter seen in the physical world and facilitates the study as well as the manipulation of matter. However in the quantum realm, interaction between quantum particles can lead to daunting challenges - it enforces complex collective behaviour of the particles that appear very hard to study using current computational means. This project aims to pin down the nature of this complexity by investigating a series of fundamental questions. First, are the interactions themselves simple enough that their precise knowledge can be gained by a practical algorithm? Such an algorithm is also expected to benefit quantum technologies, facilitating learning and testing of quantum devices. Second, how computationally difficult is it to estimate physical properties of the quantum particles, even if the knowledge of interactions is available? This question will help understand the limits of near term quantum devices in probing quantum particles. Third, could the collective behaviour of particles be simple rather than complex, under some common assumptions on the interactions? This would allow efficient means to computationally simulate systems that respect the assumptions. The educational plan centers around computation and physics, encompassing a seminar series at Harvard University with a diverse list of speakers, development of a quantum computing curriculum at Harvard University for graduate and undergraduate students, and teaching quantum theory to students from Boston high-schools with limited access to Science, Technology, Engineering and Math education.This project will study local Hamiltonians - the quantum analogues of constraint satisfaction problems in theoretical computer science - that model interactions in quantum many-body systems. In particular, it will aim to make progress on three long-standing questions: Can a local Hamiltonian be learned efficiently from the Gibbs quantum states? What are the fundamental limits on the approximations to the ground energies of a local Hamiltonian (the quantum Probabilistically-Checkable-Proofs conjecture)? Does limited entanglement hold for the ground states of two-dimensional gapped local Hamiltonians (the area law conjecture)? These questions address the complexity of quantum many-body systems from the view of three well-studied measures: learnability, approximability and entanglement. This is inspired by three successful ways to measure complexity of a computation in theoretical computer science - time complexity, space complexity and randomness. In fact, ideas from theoretical computer science are expected to be crucial in making progress on the above questions. Furthermore, research will add to the knowledge in quantum technologies: Hamiltonian learning techniques will find use in the testing of programmable quantum devices and progress on the quantum Probabilistically-Checkable-Proofs conjecture will limit the efficiency of various near-term quantum algorithms for quantum many-body problems.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.