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

Purdue University, West Lafayette IN

Investigators

Abstract

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.