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

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

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.