Career: The Complexity pf Quantum Tasks

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.