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 维拓扑量子场控制理论（3-d TQFT）。 众所周知，对于某些 3-d TQFT 来说，可以实现这一点，而对于其他 3-d TQFT 来说则不然，尽管仍然缺乏干净的二分定理。 考虑到这一点，该项目的第一个主要目标是根据 3-d TQFT 在拓扑量子计算范式中支持完全可编程量子计算的能力，对 3-d TQFT 进行完整分类。 这将需要为结理论中的某些相关问题开发新的复杂性理论结果。 该项目的第一个目标是了解哪些 TQFT 对量子计算有用，而该项目的第二个目标是了解量子计算机在多大程度上可用于研究 TQFT。 为此，研究人员将分析有关通过通用量子计算机上的预言机访问提供的 TQFT 的各种决策问题的计算复杂性。 这些方法将涉及针对骨架化模张量类别开发新的计算代数技术，这些模张量类别是一种有限组合代数数据类型的实例，是 3-d TQFT 研究的核心。 这一研究方向预计将带来量子优势的新例子，并且该项目的两个部分都与凝聚态物理中有关物质拓扑有序相的问题密切相关。 特别是，该项目的结果可能对拓扑顺序的实验表征产生实际影响。该奖项反映了 NSF 的法定使命，并通过使用基金会的智力价值和更广泛的影响审查标准进行评估，被认为值得支持。