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.