CAREER:Exploring the power of quantum protocols for interactive proofs

该项目的目标是通过理论计算机科学（一个称为复杂性理论的领域）的视角，研究物理（特别是量子力学）研究中自然出现的计算问题。复杂性理论中的一个基本现象是，棘手的问题可以有有效的可验证的解决方案，特别是当验证过程（或“证明”）被允许是交互式的时候。交互式证明协议已经在今天的经典计算理论中发挥了核心作用，并且应用范围从算法和优化到密码学。该项目旨在探索在量子计算机存在的情况下交互证明的力量，建立在最近一系列工作的基础上，这些工作表明量子交互证明协议可以利用纠缠比传统的同行更有效。该项目的研究领域包括测试不可信量子计算机的方法，研究量子物理和化学中出现的优化问题的复杂性；以及与量子纠缠和算子代数的数学联系。该项目还将支持研究生的培训，并将研究成果整合到面向计算机科学家、物理学家和工程师的本科和研究生新课程中。从技术上讲，该项目的出发点是最近的复杂性理论结果，即多证明者交互证明的类MIP*等于递归可枚举语言的类RE（包括不可判定问题，如停机问题）。研究者将承担三个主要的工作方向。第一部分将简化和推广MIP* = RE结果的技术，使其成为一套通用的工具，用于在多证明者设置中构建和分析量子协议。希望这一研究将导致经典交互证明中重要思想的新的量子推广，如直接乘积检验和PCP定理的组合证明。它还与算子代数和群论中的问题有联系，例如非超线性群的存在性。第二个主要方向是使用量子密码学的技术来设计新的协议，使经典客户端能够在单设备设置中委托量子计算。以前解决这个问题的方法是高度针对特定的、强加密假设定制的。研究人员的目标是构建工具，使多证明者协议能够在更通用的加密假设下以黑盒方式转换为单设备协议。第三个主要方向是研究哈密顿复杂性：多体量子系统低能态计算特性的复杂性。在数学上，哈密顿复杂度和MIP*证明系统都可以看作是组合优化问题的不同推广，例如MAX-CUT，到非交换矩阵值变量。这里的一个主要目标是利用MIP*=RE或其他地方的思想，在量子PCP猜想方面取得进展，这是该领域的主要开放问题。该奖项反映了美国国家科学基金会的法定使命，并通过使用基金会的知识价值和更广泛的影响审查标准进行评估，被认为值得支持。

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.