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

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

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.