Career: The Complexity pf Quantum Tasks

该项目的目标是通过理论计算机科学的透镜研究物理学（特别是量子力学）研究中自然出现的计算问题。举个例子，给定一个量子力学系统的描述，人们能有效地计算系统的能量吗？自从量子计算出现以来，诸如此类的问题变得越来越重要，量子计算是计算机科学领域，它使用量子力学的奇怪特性来设计可能比我们今天拥有的计算机更快的计算机。对这些问题的研究揭示了理论计算机科学和物理学之间深刻而意想不到的联系，本研究项目的目标是进一步探索和加强这些联系。作为该项目的一部分，研究员将指导研究生，编写和传播新的教育材料，包括课程笔记和教科书，并设计关于这些主题的新的研究生课程。第一组目标旨在确定计算非局部博弈的各种属性的难度，这些非局部博弈是对量子力学基础很重要的简单合作博弈。第二组目标旨在了解人们可以在多大程度上计算由局部哈密顿描述的物理系统的各种属性，例如它们的基态能量;具体来说，这里的兴趣是了解经典优化技术（如半定规划）在这些任务中的表现。第三组目标是确定计算最一般的量子任务的难度，例如实现通用的酉运算，以及这些任务是否可以证明比任何经典计算都要困难。最后，最后一组目标是通过测量量子态的相同副本来了解量子态的性质，以及是否可以改进该领域的最先进算法。该奖项反映了NSF的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

The goal of this project is to study computational problems which arise naturally in the study of physics (and quantum mechanics, in particular) through the lens of theoretical computer science. As an example, given a description of a quantum mechanical system, can one efficiently compute the energy of the system? Problems such as this one have become increasingly important since the advent of quantum computing, the area of computer science which uses the strange properties of quantum mechanics to design computers which are potentially faster than the computers we have today. The study of these problems has revealed deep and unexpected connections between theoretical computer science and physics, and the goal of this research project is to further explore and strengthen these connections. As a part of this project, the investigator will mentor graduate students, write and disseminate new educational materials including course notes and a textbook, and design new graduate-level coursework on these topics.This project has four sets of broad goals. The first set of goals seeks to determine the difficulty of computing various properties of nonlocal games, which are simple cooperative games important to the foundations of quantum mechanics. The second set of goals seeks to understand to what extent one can compute various properties of physical systems described by local Hamiltonians, such as their ground state energies; specifically, the interest here is in understanding how well classical optimization techniques such as semidefinite programming perform at these tasks. The third set of goals is to determine the difficulty of computing the most general of quantum tasks, such as implementing a generic unitary operation, and whether these tasks can be shown to be harder than any classical computation. Finally, the last set of goals pertains to understanding how well one can learn properties of quantum states by measuring identical copies of the states, and whether one can improve on state-of-the-art algorithms in this area.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.