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.

量子计算机是一项新兴技术，可利用量子力学的基本属性，使他们能够在整个科学，工程和行业的许多应用中都超越非Quantum计算机。 尽管这种现实世界的应用程序刚刚开始实现，但量子计算机的大规模开发和部署必须克服两个主要挑战。 首先是容错的实际问题：量子计算机本质上容易出错，因此科学家和工程师必须设计策略，尽管这些错误，但仍可以使他们执行量子算法。 第二是量子优势的理论问题，该问题旨在准确识别哪些类型的问题值得用量子计算机而不是使用非量子计算机来攻击。 该项目将通过调查两个与量子代数和拓扑密切相关的数学子场中某些算法问题的严格计算复杂性来直接进步。 该项目还将通过重大的教育和外展活动来更广泛地解决这些挑战，包括在普渡大学创建新的招聘管道进行量子科学培训的量子培训，这些管道将促进社会在新兴的量子劳动力中的公平代表性。教学企业自然会在研究量子的量子系统时自然而然地进行量子机械系统，因为IT为量子机械制度提供了分析，因为它是分析的属性。例如由量子计算机内部的噪声和错误引起的。 解决可容忍问题问题的一种特别令人信服的方法是“拓扑量子计算”，旨在通过编码量子机械系统内的所有可能的量子电路来构建易于断层的量子计算机，该量子机械系统的行为受到3维拓扑量子量子场理论（3-D-D TQFT）的控制。 众所周知，对于一些3-D TQFTS，可以实现这一目标，而对于其他3-D TQFT，尽管仍然缺乏干净的二分法定理。 考虑到这一点，该项目的第一个主要目标是根据其在拓扑量子计算范式中支持完全可编程的量子计算的能力，将3-D TQFTS的完整分类。 这将需要为结理论中的某些相关问题开发新的复杂性理论结果。 尽管该项目的第一个目标试图了解哪些TQFTS对于量子计算有用，但该项目的第二个目标是相反，要了解量子计算机在多大程度上可能对研究TQFT有用。 为此，研究者将分析通过通用量子计算机上的Oracle访问提供的有关TQFT的各种决策问题的计算复杂性。 该方法将涉及开发用于骨骼化模块化张量类别的新计算代数技术，这些技术是一种有限的组合 - 代数数据类型的实例，这对于3-D TQFTS的研究至关重要。 预计这一调查线将导致量子优势的新示例，并且该项目的两个部分与关于物质拓扑秩序阶段的凝结物理学中的问题密切相关。 特别是，该项目的结果可能对拓扑顺序的实验表征具有实际意义。该奖项反映了NSF的法定任务，并被认为是值得通过基金会的知识分子优点和更广泛的影响评估标准通过评估来支持的。