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（包含不可判定问题的类，例如停机问题）。调查员将从事三个主要方向的工作。第一个将简化和推广的MIP* = RE结果的技术到一个通用的工具套件，用于构建和分析量子协议的multiprover设置。希望这项研究将导致新的量子推广的重要思想，从经典的交互式证明，如直接产品测试和组合证明的PCP定理。也有连接到问题的算子代数和群论，如存在的非超线性群体。第二个主要方向是使用量子密码技术来设计新的协议，使经典客户端能够在单设备设置中委托量子计算。以前解决这个问题的方法都是针对特定的、强密码学假设的。研究人员的目标是建立工具，使多个协议转换在一个黑盒子的方式，单设备协议，在更通用的密码学假设。第三个主要方向是研究哈密顿复杂性：多体量子系统低能态计算性质的复杂性。在数学上，哈密顿复杂度和MIP* 证明系统都可以被看作是组合优化问题（如MAX-CUT）对非交换矩阵值变量的不同推广。这里的一个主要目标是在量子PCP猜想方面取得进展，这是该领域的主要开放问题，借鉴MIP*=RE或其他地方的想法。该奖项反映了NSF的法定使命，并通过使用基金会的智力价值和更广泛的影响审查标准进行评估，被认为值得支持。