CAREER:Exploring the power of quantum protocols for interactive proofs

职业：探索量子协议用于交互式证明的力量

• 批准号: 2339948
• 负责人: Anand Natarajan
• 金额: $ 60万
• 依托单位: Massachusetts Institute of Technology
• 依托单位国家: 美国
• 项目类别: Continuing Grant
• 财政年份: 2024
• 资助国家: 美国
• 起止时间: 2024-02-01 至 2029-01-31
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2339948&HistoricalAwards=false
• 关键词: CAREER; Exploring; power; quantum; protocols

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.

该项目的目的是研究通过理论计算机科学的镜头（一个称为复杂性理论的领域）来研究物理学研究（尤其是量子力学）中自然的计算问题。复杂性理论中的基本现象是，棘手的问题可以有效地可验证解决方案，尤其是当允许验证过程（或“证明”）互动时。交互式证明协议已经在当今的古典计算理论中起着核心作用，并且具有从算法和优化到加密术的应用。该项目旨在在量子计算机的存在下探索交互式证明的力量，这是基于最近的一系列工作，表明量子交互式证明可以探索纠缠比其经典同行更有效。该项目的投资领域包括测试不信任量子计算机的方法，研究量子物理和化学中出现的优化问题的复杂性；以及与量子纠缠和操作员代数的数学连接。该项目还将支持对研究生的培训，并将研究的思想整合到针对计算机科学家，物理学家和工程师的本科和研究生层面的新课程。调查人员将承担三个主要工作方向。第一个将简化并概括MIP* = RE的技术中，以在多个设置中构造和分析量子协议的一般工具套件。希望这项研究能够从经典互动证明（例如直接产品测试和PCP定理的组合证明）中实现重要思想的新量子概括。在操作员代数和群体理论中，也存在联系，例如非杂交群体的存在。第二个主要方向是使用量子密码学的技术设计新协议，以使经典客户端在单个设备设置中委派量子计算。以前解决此问题的方法是针对特定的，强大的加密假设量身定制的。研究者的目标是构建工具，以使多框的方式在更通用的加密假设下以黑盒方式转换为单个设备协议。第三个主要方向是研究哈密顿的复杂性：许多人体量子系统低能状态的计算特性的复杂性。从数学上讲，哈密顿的复杂性和MIP*证明系统都可以看作是组合优化问题（例如最大切割）的不同概括，即最大值的矩阵值变量。这里的主要目的是朝着量子PCP猜想迈进，这是该领域的主要开放问题，借鉴了MIP*=或其他地方的想法。该奖项反映了NSF的法定任务，并被认为是通过基金会的智力优点和更广泛的影响来通过评估来获得的支持。