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

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

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.