CAREER:Exploring the power of quantum protocols for interactive proofs

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, a field called complexity theory. A fundamental phenomenon in complexity theory is that intractable problems can have efficiently verifiable solutions, especially when the verification process (or "proof") is allowed to be interactive. Interactive proof protocols already play a central role in the theory of classical computing today, and have applications ranging from algorithms and optimization to cryptography. This project seeks to explore the power of interactive proofs in the presence of quantum computers, building on a line of recent work showing that quantum interactive proof protocols can exploit entanglement to be much more efficient than their classical counterparts. Areas of investigation of the project include methods to test untrusted quantum computers, studying the complexity of optimization problems arising in quantum physics and chemistry; as well as connections to the mathematics of quantum entanglement and operator algebras. The project will also support the training of graduate students and integration of ideas from the research into new courses at the undergraduate and graduate level aimed at computer scientists, physicists, and engineers. Technically, the starting point of the project is the recent complexity-theoretical result that the class MIP* of multiprover interactive proofs is equal to the class RE of recursively enumerable languages (a class including undecidable problems such as the halting problem). The investigator will undertake three major directions of work. The first will simplify and generalize the techniques of the MIP* = RE result into a general suite of tools for constructing and analyzing quantum protocols in the multiprover setting. It is hoped that this research will lead to new quantum generalizations of important ideas from classical interactive proofs, such as direct product testing and the combinatorial proof of the PCP theorem. There are also connections to questions in operator algebras and group theory, such as the existence of non-hyperlinear groups. The second major direction is to use techniques from quantum cryptography to design new protocols to enable a classical client to delegate quantum computations in the single-device setting. Previous approaches to this problem are highly tailored to a specific, strong cryptographic assumption. The investigator’s goal is to build tools that enable multiprover protocols to be converted in a black-box way to single-device protocols, under more generic cryptographic assumptions. The third major direction is to investigate Hamiltonian complexity: the complexity of computing properties of low-energy states of a many-body quantum system. Mathematically, both Hamiltonian complexity and MIP* proof systems can be viewed as different generalizations of combinatorial optimization problems, such as MAX-CUT, to noncommuting matrix-valued variables. A major goal here is to make progress towards the quantum PCP conjecture, the major open problem in this area, drawing on ideas from MIP*=RE or elsewhere. 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.