FET: SMALL: Quantum algorithms and complexity for quantum algebra and topology

FET：小：量子算法以及量子代数和拓扑的复杂性

• 批准号: 2330130
• 负责人: Eric Samperton
• 金额: $ 59.09万
• 依托单位: Purdue University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2024
• 资助国家: 美国
• 起止时间: 2024-01-01 至 2026-12-31
• 项目状态: 未结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=2330130&HistoricalAwards=false
• 关键词: FET; SMALL; Quantum; algorithms; complexity

Quantum computers are an emerging technology that exploit the fundamental properties of quantum mechanics in ways that will allow them to outperform non-quantum computers in numerous applications throughout science, engineering and industry. While such real-world applications are just now starting to be realized, the large-scale development and deployment of quantum computers must yet overcome two major challenges. First is the practical issue of fault tolerance: quantum computers are inherently prone to making errors, and so scientists and engineers must design strategies that allow them to perform quantum algorithms despite these errors. Second is the theoretical issue of quantum advantage, which seeks to identify exactly which types of problems are worth attacking with quantum computers instead of with non-quantum computers. This project will make direct progress on both of these challenges by investigating the rigorous computational complexity of certain algorithmic problems in two closely-related mathematical subfields called quantum algebra and topology. The project will also contribute to the resolution of these challenges more broadly through significant educational and outreach activities, including the creation of new recruiting pipelines for quantum science training at Purdue that will promote an equitable representation of society within the burgeoning quantum workforce.Topology naturally arises when studying quantum mechanical systems like quantum computers because it provides a rigorous mathematical language for analyzing the properties of systems that are invariant under deformations, such as those induced by the noise and errors inside of a quantum computer. An especially compelling approach to addressing the fault tolerance problem is "topological quantum computation," which aims to build a fault-tolerant quantum computer by encoding all possible quantum circuits inside a quantum mechanical system whose behavior is governed by a 3-dimensional topological quantum field theory (3-d TQFT). It is known that for some 3-d TQFTs it is possible to achieve this, and for others it is not, although a clean dichotomy theorem is still lacking. With this in mind, the first major goal of this project is to work towards a complete classification of 3-d TQFTs according to their ability to support fully-programmable quantum computation within the topological quantum computation paradigm. This will require developing new complexity-theoretic results for certain associated problems in knot theory. Whereas this first goal of the project seeks to understand which TQFTs are useful for quantum computation, the second goal of the project is to understand, conversely, to what extent quantum computers might be useful for studying TQFTs. To this end, the investigator will analyze the computational complexity of various decision problems concerning TQFTs that are provided via oracle access on a universal quantum computer. The methods will involve the development of new computational algebra techniques for skeletalized modular tensor categories, which are instances of a kind of finite combinatorial-algebraic data type that are central to the study of 3-d TQFTs. This line of investigation is expected to lead to new examples of quantum advantage, and both parts of the project are closely related to questions in condensed matter physics concerning topologically ordered phases of matter. In particular, the results of this project could have practical implications for the experimental characterization of topological order.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.

量子计算机是一种新兴技术，它利用量子力学的基本特性，使它们在整个科学，工程和工业的许多应用中优于非量子计算机。 虽然这种现实世界的应用才刚刚开始实现，但量子计算机的大规模开发和部署还必须克服两个主要挑战。 首先是容错的实际问题：量子计算机天生就容易出错，因此科学家和工程师必须设计策略，使它们能够在存在这些错误的情况下执行量子算法。 第二个是量子优势的理论问题，它试图准确地确定哪些类型的问题值得用量子计算机而不是非量子计算机来解决。 该项目将通过研究两个密切相关的数学子领域（称为量子代数和拓扑学）中某些算法问题的严格计算复杂性，在这两个挑战上取得直接进展。 该项目还将通过重要的教育和外联活动，促进更广泛地解决这些挑战，包括为普渡大学的量子科学培训创建新的招聘渠道，这将促进社会在蓬勃发展的量子劳动力中的公平代表。拓扑学在研究量子计算机等量子力学系统时自然会出现，因为它提供了一种严格的数学语言来分析在变形下不变的系统属性，例如量子计算机内部的噪声和错误引起的变形。 解决容错问题的一个特别引人注目的方法是“拓扑量子计算”，其目的是通过对量子力学系统中所有可能的量子电路进行编码来构建容错量子计算机，该系统的行为由三维拓扑量子场论（3-d TQFT）控制。 据了解，对于一些3-D TQFT，它是可能实现这一点，而对于其他人，它不是，虽然一个干净的二分法定理仍然缺乏。 考虑到这一点，该项目的第一个主要目标是根据它们在拓扑量子计算范式中支持完全可编程量子计算的能力，对3-d TQFT进行完整的分类。 这就需要为纽结理论中的某些相关问题发展新的复杂性理论结果。 虽然该项目的第一个目标是了解哪些TQFT对量子计算有用，但该项目的第二个目标是了解量子计算机在多大程度上对研究TQFT有用。 为此，研究人员将分析有关TQFT的各种决策问题的计算复杂性，这些问题是通过通用量子计算机上的Oracle访问提供的。 该方法将涉及新的计算代数技术的开发，用于实现模块化的模张量类别，这是一种有限的组合代数数据类型的实例，是3-D TQFT研究的核心。 这一研究方向有望带来量子优势的新例子，该项目的两个部分都与凝聚态物理学中有关物质拓扑有序相的问题密切相关。 特别是，这个项目的结果可能有实际意义的拓扑order.This奖项的实验表征反映了NSF的法定使命，并已被认为是值得通过使用基金会的智力价值和更广泛的影响审查标准进行评估的支持。